Sage Journals: Discover world-class research

Abstract

In assembly optimisation, assembly sequence planning and assembly line balancing have been extensively studied because both activities are directly linked with assembly efficiency that influences the final assembly costs. Both activities are categorised as NP-hard and usually performed separately. Assembly sequence planning and assembly line balancing optimisation presents a good opportunity to be integrated, considering the benefits such as larger search space that leads to better solution quality, reduces error rate in planning and speeds up time-to-market for a product. In order to optimise an integrated assembly sequence planning and assembly line balancing, this work proposes a multi-objective discrete particle swarm optimisation algorithm that used discrete procedures to update its position and velocity in finding Pareto optimal solution. A computational experiment with 51 test problems at different difficulty levels was used to test the multi-objective discrete particle swarm optimisation performance compared with the existing algorithms. A statistical test of the algorithm performance indicates that the proposed multi-objective discrete particle swarm optimisation algorithm presents significant improvement in terms of the quality of the solution set towards the Pareto optimal set.

Keywords

Integrated assembly sequence planning and assembly line balancing particle swarm optimisation multi-objective optimisation discrete particle swarm optimisation

Introduction

In the recent years, various multi-objective optimisation techniques have been proposed to solve assembly optimisation problems.^1–3 This trend shows the attention given by researchers to assembly optimisation activities because of their complexity and relevance of the actual industrial problems. The research in assembly optimisation can be classified according to product development and production stage.⁴ Although there are many activities classified in the assembly optimisation, assembly sequence planning (ASP) and assembly line balancing (ALB) are the most prominent because they are directly linked with assembly efficiency.

ASP refers to a task for which planners, usually based on their particular heuristics in assembling all the components of a product, arrange a specific collision-free assembly sequence according to the product design description.^5,6 Figure 1 shows a common assembly representation using a precedence graph. From this graph, numerous feasible assembly sequences can be generated such as {1 6 7 2 4 3 5}, {1 7 3 6 5 4 2} or {1 6 2 7 4 3 5}. Based on this example, ASP is about determining the most optimum sequence to assemble a product from all feasible assembly sequences.

Figure 1.

Assembly representation using precedence graph.

Once the optimum assembly sequence has been determined from ASP activity, the assembly jobs will be assigned to workstations, so that every workstation will have equal or almost equal workload. The assembly job assignment activity refers to ALB that is defined as the decision problem of optimally partitioning assembly work among stations with respect to some objectives and constraints.^7,8 For example, let the optimum assembly sequence from ASP be {1 6 2 7 4 3 5} and this assembly jobs will be assigned to three workstations. There are many possible assembly job assignment combinations such as {(1 6), (2 7 4), (3 5)} or {(1 6 2), (7 4), (3 5)} or {(1 6 2 7), (4 3), (5)}. In this process, ALB will determine the best assembly job combination which comes out with equal or almost equal workload between workstations.

Figure 2 shows the main assembly optimisation activities in every product development and production stage. Based on this figure, ASP and ALB activities are performed individually because they take place in different stages of the product development process. ASP is located in the production planning while ALB is in the manufacturing process stage.⁴ However, the current global market drives a demand for shorter product life-cycles and also for products to be more competitive in terms of time-to-market, quality and also manufacturing cost. One approach to stay competitive is by integrating manufacturing activities across the different stages.⁹ From the aspect of assembly optimisation, the ASP and ALB optimisation activities present a good integration opportunity with various potential benefits to the manufacturer.

Figure 2.

Main assembly optimisation activities in product development and production stages.

The main benefit of using an integrated ASP and ALB is that the quality of assembly plans could be improved as the search space of the integrated problem would become larger than when optimising each problem sequentially. Besides, the integrated ASP and ALB could reduce the rate of errors in both planning and costing during the manufacturing stages.⁵ At the same time, the integrated optimisation also speeds up the aspect of time-to-market for a product.

In ASP and ALB optimisation, several objectives have been used to determine the optimal solution for the problem. When an optimisation problem involves more than one objective, this problem is known as multi-objective optimisation.¹⁰ Traditionally, the simplest way to optimise multi-objective problem is to bundle all the objectives into a single fitness using some kind of weighted assignment. However, this approach requires high prior knowledge on the importance of one objective over another. Therefore, instead of focusing on one single optimum point, the researchers might be interested in all the best options available, which are known as Pareto optimal solutions.¹¹ Furthermore, by having a set of optimum solutions, the decision-makers in the industry are offered more flexibility in selecting the solution that is deemed suitable with a variety of preferences.

Although various optimisation algorithms have been developed and used to optimise different multi-objective problems, to the best of the authors’ knowledge, only techniques based on genetic algorithm (GA) and ant colony optimisation (ACO) have been proposed to optimise integrated ASP and ALB.^1,12,13 Chen et al.¹⁴ proposed a hybrid GA to optimise integrated ASP and ALB, where GA is combined with heuristic search. The objectives were to minimise cycle time, maximise workload smoothness, minimise tool changes, minimise the number of tools and minimise the total penalty of assembly relations. Although this article does not clearly state the integration of ASP and ALB, this relationship was acknowledged following the optimisation objectives.

Tseng and Tang studied combining ASP together with ALB based on the assembly ‘connectors’ (i.e. the connector basis) using GA. In their work, optimisation was conducted in three stages. First, each part was assigned to a specific connector type. Then, the algorithm generated the assembly planning based on the connectors. Finally, the algorithm assigned the connectors to stations and selected proper types of stations. Meanwhile, in the second and third stages, GA was applied to generate connector-based assembly in a sequential order, as well as to determine the suitable station types for the sequential order. However, when using this approach, whenever the number of connectors is increased, a few of the parameters that govern GA performance need to be reset.⁵

Another work by Tseng et al.¹⁵ on integrated ASP and ALB was done in 2008. This work adopted the hybrid evolutionary multi-objective algorithm (HEMOA) that was based on GA. On the basis of multi-objective optimisation, the Pareto optimal approach was adopted in this study. However, the weighted sum approach was employed to obtain a better solution, instead of measuring the solution crowding that has been frequently used in recent multi-objective algorithm.

Another integrated ASP and ALB optimisation work was also formulated based on the assembly connectors.¹⁶ In this work, the guided-modified weighted Pareto-based multi-objective genetic algorithm (G-WPMOGA) had been proposed to optimise the integrated ASP and ALB problem with two, three and four objectives. The proposed algorithm displayed better performance in the problem with two and four objectives, but not in the problem with three objectives.

In the recent optimisation work of integrated ASP and ALB, the GA-based algorithms performed well in optimising the problem with low and medium difficulties. However, the performance of GA-based algorithms did not last when optimising high difficulty problem, especially the problem with a large number of tasks.¹⁷ On the other hand, the researcher also concluded that the different GA-based variants should be used in order to optimise the problem with a different number of criteria.¹⁶

Besides GA-based algorithm, the researcher implemented ant colony algorithm to optimise the integrated ASP and ALB problems.^12,13 In Yang et al.,¹² they proposed an optimisation model to implement ACO for integrated ASP and ALB without numerical experiment. Meanwhile, in Lu and Yang,¹³ the authors optimised several objectives such as line efficiency, smoothness index, assembly time and number of workstations. However, the problem was treated as single objective, by combining all the objectives. In order to overcome the limitation, a new algorithm to optimise integrated ASP and ALB problems is needed.

In many different works that compare algorithm performance, particle swarm optimisation (PSO) has shown strong performance compared with competing algorithms. This algorithm is popular due to its simplicity and ability to quickly converge to a reasonably good solution.¹⁸ PSO is a population-based stochastic optimisation technique that was developed by Kennedy and Eberhart in 1995. In PSO, the potential solutions, called particles, ‘fly’ through the problem space by following the current optimum particles.¹⁹ In micro-ASP, PSO was found to provide less computational time compared with other considered algorithms.²⁰ PSO was shown to outperform GA and simulated annealing in scheduling problems in the majority of applications by considering computation efficiency, optimality and robustness.²¹ In another research, PSO was found to perform better than GA, memetic algorithm, shuffled frog leaping and ant algorithm in solving continuous and discrete optimisation problems.²² PSO algorithm also performs better compared with commercial software for robotic ALB problem.²³

Even though several researches on ASP and ALB implemented PSO, they were independent works.^24–27 At this point, no existing works are using PSO algorithms to optimise the integrated ASP and ALB problems. In this article, the multi-objective discrete particle swarm optimisation (MODPSO) to optimise integrated ASP and ALB is proposed. In comparison with Nearchou,²⁸ Coello Coello and Lechuga²⁹ and Tseng et al.³⁰ who used continuous encoding in PSO, the proposed algorithm implemented discrete encoding to match with discrete combinatorial optimisation problem. On the other hand, different from DPSO as found in Rameshkumar et al.,³¹ Jianping et al.,³² Lv and Lu³³ and Wang and Liu,³⁴ the proposed algorithm implemented non-dominated sorting concept to deal with multi-objective. The proposed MODPSO algorithm also integrates the crowding distance (CD) concept from elitist non-dominated sorting genetic algorithm II (NSGA-II)³⁵ to determine the leaders (Pbest and Gbest).

This work was motivated by the benefits of integrating ASP and ALB and also the expected performance gained through using PSO in optimising multi-objective problems to overcome limitation of GA-based algorithms. Section ‘ASP and ALB problem representation’ explains the problem representation for integrated ASP and ALB. Section ‘Proposed MODPSO’ details the proposed MODPSO algorithm, followed by experimental strategy and set-up in section ‘Experimental design’. Section ‘Experimental results’ presents the results and section ‘Discussion of results’ discusses the result of experiments that deploy various algorithms to optimise multi-objective ASP and ALB problems. Finally, section ‘Conclusion’ concludes the finding from the proposed MODPSO algorithm.

ASP and ALB problem representation

In order to incorporate ASP and ALB optimisations into a single integrated optimisation, a clear prerequisite is the availability of an integrated ASP and ALB representation. For this purpose, an integrated assembly task-based representation scheme is used to represent both ASP and ALB problems.³⁶ In this scheme, the assembly plan is represented by a precedence graph (Figure 3) and the assembly data are presented in a data matrix (Table 1). Each node in the precedence graph represents an assembly task, while the connecting arc represents assembly precedence.

Figure 3.

Example of precedence graph.

Table 1.

Data matrix.

Task	Direction	Tool	Time
1	+x	T1	4
2	−x	T2	12
3	+x	T1	7
4	−x	T3	4
5	+x	T1	12
6	+x	T1	5
7	−x	T2	12

However, the precedence graph used to represent the assembly plan needs to be coded into a numerical format for computational application. For this purpose, the precedence matrix is used to characterise assembly precedence graph. Precedence matrix is an n × n matrix that consists of 0 and 1 values. The precedence matrix in Table 2 represents the assembly precedence graph in Figure 3. In this matrix, value 0 shows no precedence relation between task i and task j, while value 1 shows that task i must be performed prior to task j.

Table 2.

Precedence matrix.

i	j
i	1	2	3	4	5	6	7
1	0	1	1	1	0	0	0
2	0	0	0	0	1	0	0
3	0	0	0	0	0	1	0
4	0	0	0	0	0	0	1
5	0	0	0	0	0	0	1
6	0	0	0	0	0	0	1
7	0	0	0	0	0	0	0

Objective function

Various objective functions have been designed and used to optimise ASP and ALB problems. A prior literature survey has collated objective functions that have been used by researchers in both problems.¹ This survey also found that the most frequently used ASP optimisation objectives are to minimise assembly direction change and the number of tool change. In ALB works, even though there were various objectives such as maximising worker efficiency and equipment,³⁷ the dominant optimisation objectives are to minimise cycle time, number of workstation and workload variance.

The number of assembly direction change (n_dc) is counted when the next assembly task requires a different assembly direction compared with the present assembly task. In equations (1) and (2), s refers to the position of a task in a feasible assembly sequence

n_{dc} = \sum_{s = 1}^{n - 1} d_{s}; d_{s} = {\begin{matrix} 1 if direction s \neq direction s + 1 \\ 0 if direction s = direction s + 1 \end{matrix}

(1)

The number of assembly tool change (n_tc) is also counted when the next assembly task requires a different assembly tool compared with the present assembly task

n_{t c} = \sum_{s = 1}^{n - 1} t_{s}; t_{s} = {\begin{matrix} 1 if tool s \neq tool s + 1 \\ 0 if tool s = tool s + 1 \end{matrix}

(2)

Cycle time (ct) is the time interval at which product units must be finished in order to meet demand.³⁸ In this case, ct for particular assembly sequence is the highest processing time among all workstations. Processing time (pt) refers to the total assembly time in a particular workstation. Once the total processing time for the current workstation is larger than the maximum allowable cycle time (ct_max), the present assembly task will be assigned to the next workstation. Normally, ct_max is determined from the number of demand or required output in the assignment period.

The number of workstation (nws) can be determined after all the assembly tasks were assigned to workstations. Once completed, the number of generated workstation is used as the fourth objective. The number of workstation depends on the cycle time where larger cycle time leads to a smaller number of workstation and vice versa.

Workload variation (v) calculates the average of idle time in workstations. In this case, a smaller workload variation shows that the assembly line has an almost equal load between workstations

v = \frac{\sum_{i = 1}^{n w s} (c t - p t_{i})}{n w s}

(3)

Proposed MODPSO

Various versions of PSO algorithm have been proposed to optimise multi-objective problems for independent ASP and ALB.^{28,30,33,39,40} One of the PSO versions for optimising multi-objective problems is known as DPSO that was first proposed by Rameshkumar et al.³¹ for scheduling problem and later adopted to optimise ASP problem.⁴⁰ However, in these works, the multi-objective problem was handled by bundling all objectives into a single objective that leads to only one solution. This approach required high-quality prior knowledge and experience on the importance of an objective compared with others. Another PSO version called multi-objective particle swarm optimisation (MOPSO) was proposed by Coello Coello and Lechuga²⁹ with the objective to extend the application of PSO for multi-objective problem. This algorithm uses the original PSO operators for generating new particle position and velocity, but uses the non-dominated approach to find the set of optimum solutions.

In order to treat the problem as real multi-objective optimisation, this work proposed to apply the Pareto-based approach in the proposed algorithm. In PSO, the potential solution is represented by a particle, which brings three important vectors particle position (X_i), particle velocity (V_i) and particle best solutions (Pbest). Figure 4 shows the working flow of MODPSO algorithm.

Figure 4.

Flow chart of the MODPSO.

Initialisation

The number of particle (npar) and the maximum number of iteration (iter_max) were set in this step. Then the initial population known as swarm was produced by generating the npar set of initial position (X) and velocity (V) that consists of permutation of integer from 1 to n in random orders. Next, the swarm was decoded to generate feasible sequences according to the precedence constraint using topological sort procedure. Topological sort is an approach to establish feasible sequence by selecting only one available assembly task in each iteration. The topological sort procedure is presented as follows:⁴¹

Procedure: Topological Sort

Begin

n; number of tasks

st = 0; number of selected task

While st ≤ n

○ Establish available set

○ st = st + 1

○ Select one task from available set and place in stth position of feasible sequence

○ Remove all outgoing arcs from selected task

○ Eliminate selected task from precedence graph

End While

End Procedure

In the procedure above, the available set consists of tasks without incoming arc. Then, one of the tasks in the available set was selected using a predetermined selection rule. There are a few selection rules regularly used such as random selection, weight-based selection and ordered-based selection. Next, all the outgoing arcs from selected task were removed and the selected task was eliminated from the graph to avoid selecting similar task. In this work, the selection rule for topological sort was set to follow the ordered-based selection. It means that the first available task found in the particle order will be selected to be placed in the feasible sequence.

Evaluation

In this step, the decoded feasible sequence was evaluated using the predefined objective functions. The objective functions were calculated using procedures and formulas in equations (1)–(3). Next, the non-dominated sorting was applied to establish the Pareto set solution. This approach is adopted from Deb¹⁰ in 2002. The Pareto set was updated in every iteration by evaluating each particle with solution in the Pareto set.

Update Pbest and Gbest

Pbest is the best personal particle solution while Gbest is the best solution for all particles. To evaluate and determine the Pbest and Gbest, a mechanism to select the best solution within all particles is needed. For this purpose, CD that provides the estimation of solutions density surrounding that solution was used. For Pbest, the CD was calculated within the solution in the swarm, whereas the CD for Gbest was calculated within the Pareto set. The following algorithm was used to calculate the CD of each point in the set R.¹⁰

CD calculation procedure:

Step 1: call the number of the solution in R as l = |R|. For each i in the set, assign d_i = 0.

Step 2: for each objective function m = 1, 2,…, M, sort the set in a descending order of r_m.

Step 3: for m = 1, 2,…, M, assign maximum (max_m) and minimum (min_m) values for each objective m.

Step 4: calculate $d_{i}^{m}$ for each objective m for solution i

d_{i}^{m} = (\frac{I_{u p^{i}}^{m} - I_{l o w^{i}}^{m}}{m a x_{m} - m i n_{m}})

(4)

Step 5: calculate summation of $d_{i}^{m}$

C D_{i} = \sum_{m = 1}^{M} d_{i}^{m}

(5)

In equation (4), $I_{u p^{i}}^{m}$ is the nearest upper mth objective value for solution i. Meanwhile, $I_{lo w^{i}}^{m}$ represents the nearest lower mth objective value for solution i. In this case, if the objective value is located at the first or last place in the r_m, the max_m and min_m values are used to replace the nearest value, respectively.

For Pbest, if the current particle has larger CD compared to the existing Pbest, the Pbest is replaced with the current position; otherwise, the existing Pbest is reused. Meanwhile, Gbest was selected as the highest CD among all Pareto solutions. In the proposed MODPSO, Gbest does not represent the most optimum solution as in traditional PSO, but it will be the leader to update the swarm position and velocity for the next iteration.

Update position and velocity

The final step in MODPSO is to update swarm position and velocity. The purpose of this step is to establish new swarm set that follows the current Pbest and Gbest. In the original PSO, the position and velocity are updated using the following formulas

X_{i}^{t + 1} = X_{i}^{t} + V_{i}^{t + 1}

(6)

V_{i}^{t + 1} = c_{1} V_{i}^{t} + c_{2} ({P b e s t}_{i}^{t} - X_{i}^{t}) + c_{3} (G b e s t_{t} - X_{i}^{t})

(7)

All the operations in equations (6) and (7) can be easily performed for the continuous problem. However, for the discrete problem, the following discrete position and velocity update procedure were proposed to replace the original operations.^31,33

Subtraction operator (position−position)

This operation was found in equation (7), $({P b e s t}_{i}^{t} - X_{i}^{t})$ and $(G b e s t_{t} - X_{i}^{t})$ and produced the velocity. Let X₁^t = [x_1,1, x_1,2, x_1,3, x_1,4, x_1,5, x_1,6, x_1,7], X₂^t = [x_2,1, x_2,2, x_2,3, x_2,4, x_2,5, x_2,6, x_2,7] and V₁^t = X₁^t − X₂^t. In this case, if x₁ and x₂ in the jth position are equal, then v₁ = 0. Otherwise, v₁ = x₁.

Addition operator (position+velocity)

For the addition of position and velocity in equation (6), if the jth element of velocity (v_j) is equal to 0, the jth position value (x_j^t) is inserted into the jth element of the new position (x_j^t⁺¹). In the meantime, if v_j is nonzero and does not appear in the new position, then x_j^t⁺¹ = v_j. Otherwise, x_j^t⁺¹ is equal to 0.

Multiplication operator (coefficient+velocity)

This operation was performed to make an adjustment on the influence of Pbest and Gbest on the new velocity. This operation can be represented as V₂ = c × V₁, where coefficient c ∈ [0, 1] is used to control the effect of V₁ that inherit in V₂. For this purpose, a random number, rand ∈ [0, 1] is generated. If rand < c, v₂ = v₁, or else, v₂ = 0. In this work, coefficients c₁, c₂ and c₃ were set at 0.7.

Addition operator (velocity+velocity)

This operation was performed to sum up the velocities in equation (7). For new velocity, V = V₁ + V₂, the jth element of V can be derived as follows

v_{j} = {\begin{matrix} v_{1, j} if v_{1, j} \neq 0, v_{2, j} = 0 \\ v_{1, j} if v_{1, j} \neq 0, v_{2, j} \neq 0, r < cp \\ v_{2, j}, otherwise \end{matrix}

(8)

In equation (8), r is a random number between 0 and 1, while cp ∈ [0, 1] is inheriting constant that influences either v₁ or v₂ into new velocity.

Table 3 presents the comparison of the proposed MODPSO with NSGA-II, DPSO and MOPSO algorithms in terms of major algorithm stages. In general, the MODPSO algorithm applied similar strategies with NSGA-II for initialisation, evaluation and selection stages, but different in regeneration stage. The MODPSO regeneration strategy used discrete position and velocity update procedure that was adopted from DPSO algorithm. Meanwhile, indifferent with MOPSO, the proposed MODPSO used different selection and regeneration strategies to handle multi-objective problem.

Table 3.

Comparison of the NSGA-II, DPSO, MOPSO and the proposed MODPSO.

Algorithm stage	NSGA-II	DPSO	MOPSO	MODPSO
Initialisation	Random initial population	Random initial particles	Random initial particles	Random initial particles
Evaluation	Individual fitness evaluation	Weighted based evaluation	Individual fitness evaluation	Individual fitness evaluation
Selection	Best crowding distance of non-dominated solution	Best weighted fitness	Random selection from less density hypercube of non-dominated solution	Best crowding distance of non-dominated solution
Regeneration	Crossover and mutation operators	Discrete PSO procedure to update position and velocity	Standard PSO operators to update position and velocity	Discrete PSO procedure to update position and velocity

NSGA-II: non-dominated sorting genetic algorithm II; DPSO: discrete particle swarm optimisation; MOPSO: multi-objective particle swarm optimisation; MODPSO: multi-objective discrete particle swarm optimisation.

Experimental design

In order to test the proposed MODPSO, the experimental design was set up. The main purpose of this experiment was to test the performance of the proposed MODPSO compared with other algorithms using a set of wide range of problem difficulties. In previous work, a tuneable test problem generator for ASP and ALB has been developed.¹⁷ The results indicate that the ASP and ALB problem difficulties can be increased using larger number of tasks (n), lower order strength (OS), lower time variability ratio (TV) and higher frequency ratio (FR).

For experimental purpose, each of input variables was divided into five levels from low to high difficulty as in Table 4. Then a reference variable setting (datum) was selected as a baseline, while the rest of the problem variable setting was generated by changing only one variable value at a time. In total, there were 17 test problems (including reference setting) generated from one reference variable setting. In order to confirm algorithm performance, three different reference variable settings were used (Levels 1, 3 and 5). Therefore, the complete number of test problem that involved in this experiment was 51 problems as shown in Table 5, and the problem setting in bold (Problems 1, 18 and 35) represented the reference variable setting for Levels 1, 3 and 5, respectively.

Table 4.

Level of tuneable input setting.

Level	n	OS	TV	FR
1	15	0.6	8	0.2
2	20	0.5	6	0.3
3	40	0.4	4	0.4
4	60	0.3	3	0.6
5	80	0.2	2	0.8

OS: order strength; TV: time variability ratio; FR: frequency ratio.

Table 5.

Experimental design for integrated ASP and ALB.

Test problem variable for reference setting at Level 1					Test problem variable for reference setting at Level 3					Test problem variable for reference setting at Level 5
Problem	n	OS	TV	FR	Problem	n	OS	TV	FR	Problem	n	OS	TV	FR
1	15	0.6	8	0.2	18	40	0.4	4	0.4	35	80	0.2	2	0.8
2	20	0.6	8	0.2	19	15	0.4	4	0.4	36	15	0.2	2	0.8
3	40	0.6	8	0.2	20	20	0.4	4	0.4	37	20	0.2	2	0.8
4	60	0.6	8	0.2	21	60	0.4	4	0.4	38	40	0.2	2	0.8
5	80	0.6	8	0.2	22	80	0.4	4	0.4	39	60	0.2	2	0.8
6	15	0.5	8	0.2	23	40	0.6	4	0.4	40	80	0.6	2	0.8
7	15	0.4	8	0.2	24	40	0.5	4	0.4	41	80	0.5	2	0.8
8	15	0.3	8	0.2	25	40	0.3	4	0.4	42	80	0.4	2	0.8
9	15	0.2	8	0.2	26	40	0.2	4	0.4	43	80	0.3	2	0.8
10	15	0.6	6	0.2	27	40	0.4	8	0.4	44	80	0.2	8	0.8
11	15	0.6	4	0.2	28	40	0.4	6	0.4	45	80	0.2	6	0.8
12	15	0.6	3	0.2	29	40	0.4	3	0.4	46	80	0.2	4	0.8
13	15	0.6	2	0.2	30	40	0.4	2	0.4	47	80	0.2	3	0.8
14	15	0.6	8	0.3	31	40	0.4	4	0.2	48	80	0.2	2	0.2
15	15	0.6	8	0.4	32	40	0.4	4	0.3	49	80	0.2	2	0.3
16	15	0.6	8	0.6	33	40	0.4	4	0.6	50	80	0.2	2	0.4
17	15	0.6	8	0.8	34	40	0.4	4	0.8	51	80	0.2	2	0.6

OS: order strength; TV: time variability ratio; FR: frequency ratio.

The MODPSO for integrated ASP and ALB problem was coded using MATLAB software. For the performance comparison purpose, six other algorithms used to optimise integrated ASP and ALB are as follows:

ACO: this algorithm has been used for simple ALB problem in Bautista and Pereira.⁴² On the other hand, the ACO algorithm has also been used in integrated ASP and ALB.¹³ This algorithm was selected based on its popularity.

Hybrid genetic algorithm (HGA): HGA has been proposed by Chen et al.¹⁴ and selected based on citation popularity for integrated ASP and ALB optimisation.

MOGA: this algorithm used in Choi et al.⁴³ to optimise ASP problem was chosen because GA is one of the most frequently used algorithms for solving and optimising ASP problems.¹ In common with this work, it used task-based representation for ASP problem.

NSGA-II: NSGA-II was introduced by Deb et al.³⁵ in 2002. This algorithm was selected because of its popularity in multi-objective optimisation.

MOPSO: the MOPSO acronym was introduced by Coello Coello and Lechuga²⁹ to extend the PSO application for Pareto-based multi-objective optimisation instead of weighted-based approach in earlier version.

DPSO: DPSO was proposed by Rameshkumar et al.³¹ for discrete problem. Instead of using normal mathematical operation to update position and velocity in PSO, this algorithm introduced special procedure to incorporate the discrete problem.

The originality of all the above algorithms was retained, as proposed by the researchers. For example, the HGA and the MOGA that were previously encoded using permutation chromosome had been directly applied to the integrated ASP and ALB. Meanwhile, the ACO algorithm functioned by constructing the assembly sequence according to the pheromone level. Hence, different assembly sequences were generated by controlling the amount of pheromone level. Therefore, no modification was required to suit the algorithm to be integrated with ASP and ALB. Besides, the DPSO was also directly implemented because it was purposely proposed to address combinatorial problem.

On the other hand, the NSGA-II and the MOPSO were originally proposed to combat the continuous optimisation problem. In order to fit both algorithms to be integrated with ASP and ALB, the continuous value of chromosome/particle position had been defined as weight to determine the sequence of assembly task. For instance, the particle positioned at X₁ = [0.35, 7.27, 2.41, 6.38, 2.12] was decoded into X₁’ = [2 4 3 5 1], giving priority to the larger position value. With this approach, the originality of NSGA-II and MOPSO had been successfully preserved since the original chromosome/particle was directly evaluated.

In this work, the population or swarm size was set at 20 with 500 iterations. For each problem, 30 simulation runs with different random seeds were performed and the output from each run was gathered and filtered to get the non-dominated solution.

Performance indicators

To evaluate the performance of each algorithm when dealing with different complexity problems, the following performance indicators adopted from Deb¹⁰ and Yoosefelahi et al.⁴⁴ were used:

Number of non-dominated solution in Pareto optimal, $\tilde{η}$ : the number of non-dominated solution generated by each algorithm in Pareto solution. Higher $\tilde{η}$ shows better algorithm performance.

Error ratio (ER): the number of solution which is not member of the Pareto optimal set divided by the number of solution generated by algorithm q. Smaller ER shows better algorithm performance.

Generational distance (GD): GD finds an average distance of solution with the nearest Pareto optimal solution. Smaller GD provides better algorithm performance

G D_{q} = \frac{\sum_{i = 1}^{s_{q}} d_{i}}{s_{q}}

(9)

s_q is the number of solution generated by algorithm q

d_{i} = {m i n}_{k = 1}^{P} \sqrt{\sum_{m = 1}^{M} {(f_{m}^{(i)} - f_{m}^{* (k)})}^{2}}

(10)

where $f_{m}^{(i)}$ is the mth objective function value of solution i and $f_{m}^{* (k)}$ is the mth objective function value of kth member of Pareto optimal.

4. Spacing: this indicator measures the relative distance between each solution

S p a c i n g = \sqrt{\frac{1}{N} \sum_{i = 1}^{s_{q}} {(d_{i} - \bar{d})}^{2}}

(11)

where $d_{i}$ is the distance between solution i and the nearest solution, while $\bar{d}$ is the average of all $d_{i}$ . The smaller spacing index shows better solution and has better space between each solution.

5. Maximum spread, Spread_max: the spread of solution found by each algorithm. Larger maximum spread is better

S p r e a d_{m a x} = \sqrt{\sum_{i = 1}^{M} {(\min f_{i} - \max f_{i})}^{2}}

(12)

Experimental results

Figure 5 shows the number of the non-dominated solution in Pareto optimal ( $\tilde{η}$ ) for all test problems using different algorithms. This figure shows that the proposed MODPSO performed better than other algorithms in all test problems. In the majority of test problems, there was a significant gap between MODPSO and other algorithms in terms of $\tilde{η}$ found. According to the output pattern, larger problem size will come out with broader gaps between MODPSO and other algorithms.

Figure 5.

Number of non-dominated set throughout test problems.

The ER for all algorithms is presented in Figure 6. From 51 test problems, MODPSO algorithms performed better in 82% of the problems. While the remaining 18% of problems was led by NSGA-II, where most of these problems involved larger task numbers (60 and 80 tasks). However, the mean of ER using MODPSO for all test problems remained the smallest (0.34) compared with NSGA-II (0.57) and other algorithms (between 0.81 and 0.93).

Figure 6.

Error ratio throughout test problems.

Meanwhile, Figure 7 presents the GD for algorithms throughout the test problems. For this indicator, MODPSO also performed better in 82% of the problems in almost similar problems as in ER. This is because the GD was measured between the solutions with the nearest Pareto solution. When the number of the non-Pareto solution increased (higher ER), the average of distance to Pareto solution would also increase. However, it still depends on how far the distance of non-Pareto with the Pareto solution. For example in Problem 22, although the ER using MODPSO was better than other algorithms, the GD using this algorithm was in the third position after MOGA and ACO. It shows that the distance of non-Pareto solution in MODPSO was relatively larger than MOGA and ACO, since these algorithms also produced good $\tilde{η}$ for a particular problem.

Figure 7.

Generational distance throughout test problems.

Figure 8 shows the performance of Spacing indicator that leads to different algorithms. For this indicator, MOPSO algorithm performed better in 37% of test problems. Then it was followed with MODPSO (22%), HGA (18%), DPSO (15%), MOGA (6%) and ACO (2%).

Figure 8.

Solution Spacing throughout test problems.

For maximum spread (Spread_max) in Figure 9, all algorithms show almost similar graph pattern with small gaps between one another. For this indicator, MODPSO algorithm performed better in 71% of test problems. In this case, MODPSO achieved better performance in the problem with the larger number of tasks, as it performed better in all test problems with 60 and 80 tasks.

Figure 9.

Maximum spread throughout test problems.

Figure 10 shows the average CPU time to complete 500 iterations for different algorithms. Based on the results, NSGA-II consistently required the highest computational time compared with other algorithms. This is related to NSGA-II feature which combined the parent and offspring chromosomes in the evaluation stage. In other words, the number of evaluated chromosomes in NSGA-II was doubled compared with other algorithms. On the other hand, MOPSO algorithm was the fastest due to the basic updating procedures implemented in this algorithm. The proposed MODPSO meanwhile was the second highest computational time behind the NSGA-II. Besides implementing the discrete updating procedure, the proposed algorithm also required additional time to adopt the non-dominated sorting concept and calculate CD for the leaders.

Figure 10.

Average CPU time.

Discussion of results

Table 6 presents the mean of performance indicators obtained using different reference variable settings. The number in bracket presents the algorithm ranking based on the mean of each indicator. According to this table, the MODPSO algorithm consistently performed better in $\tilde{η}$ , ER, GD and Spread_max for all the reference settings. Meanwhile, for Spacing indicator, HGA and MOPSO algorithms showed better performance than MODPSO. Based on this table, the proposed MODPSO algorithm came out with better performance in all indicators except in Spacing indicator.

Table 6.

Mean of performance indicators by the different reference settings.

Reference setting	Indicator	Algorithms
Reference setting	Indicator	MOGA	ACO	HGA	NSGA-II	MOPSO	DPSO	MODPSO
Level 1	$\tilde{η}$	14.0000	5.5882	15.4118	15.7059	4.8235	5.3529	57.2353
		(4)	(5)	(3)	(2)	(7)	(6)	(1)
	ER	0.7530	0.8906	0.6901	0.5386	0.9034	0.9504	0.2174
		(4)	(5)	(3)	(2)	(6)	(7)	(1)
	GD	1.3890	1.9020	1.2328	0.9307	1.9463	2.1462	0.4029
		(4)	(5)	(3)	(2)	(6)	(7)	(1)
	Spacing	1.5743	1.6869	1.2509	2.2123	1.2932	1.3366	1.2690
		(5)	(6)	(1)	(7)	(3)	(4)	(2)
	Spread_max	43.2394	43.0415	43.2337	42.2759	43.7500	43.8658	44.1101
		(4)	(6)	(5)	(7)	(3)	(2)	(1)
Level 3	$\tilde{η}$	25.7059	25.5882	14.4706	27.1176	6.2941	11.6471	164.6471
		(3)	(4)	(5)	(2)	(7)	(6)	(1)
	ER	0.8419	0.8210	0.9222	0.6531	0.9647	0.9544	0.3533
		(4)	(3)	(5)	(2)	(7)	(6)	(1)
	GD	1.9089	1.8061	2.3055	1.4281	2.7429	2.5469	0.7438
		(4)	(3)	(5)	(2)	(7)	(6)	(1)
	Spacing	1.5697	1.5558	1.3120	2.0204	1.2011	1.3345	1.3033
		(6)	(5)	(3)	(7)	(1)	(4)	(2)
	Spread_max	52.9868	52.4293	52.9695	51.8761	52.8396	52.9752	54.5288
		(2)	(6)	(4)	(7)	(5)	(3)	(1)
Level 5	$\tilde{η}$	27.9412	36.7059	18.9412	36.7647	9.5882	23.1765	152.7059
		(4)	(3)	(6)	(2)	(7)	(5)	(1)
	ER	0.8076	0.7638	0.8756	0.5318	0.9247	0.8939	0.4460
		(4)	(3)	(5)	(2)	(7)	(6)	(1)
	GD	2.1575	1.8858	2.4961	1.3660	2.9583	2.4755	1.0768
		(4)	(3)	(6)	(2)	(7)	(5)	(1)
	Spacing	1.8601	1.8992	1.5246	2.5535	1.4429	1.5062	1.5530
		(5)	(6)	(3)	(7)	(1)	(2)	(4)
	Spread_max	64.8871	63.9614	64.8369	64.4443	64.8487	65.2652	67.2345
		(3)	(7)	(5)	(6)	(4)	(2)	(1)

MOGA: multi-objective genetic algorithm; ACO: ant colony optimisation; HGA: hybrid genetic algorithm; NSGA-II: non-dominated sorting genetic algorithm II; MOPSO: multi-objective particle swarm optimisation; DPSO: discrete particle swarm optimisation; MODPSO: multi-objective discrete particle swarm optimisation; ER: error ratio; GD: generational distance.

Number in bracket shows algorithm ranking based on mean indicator value.

In Spacing indicator, all non-dominated solutions found by the particular algorithm were taken into account, regardless of Pareto or non-Pareto solutions. This indicator showed the uniformity of the space between one solution and the nearest other. Thus, the algorithm that generated more non-dominated solutions has greater chances to produce better (smaller) Spacing. However, the solution distribution is more important in achieving better Spacing. This is because the solutions that are only distributed to particular side(s) of solution space will have better Spacing compared with solutions that are distributed uniformly over the entire solution space, even though the number of non-dominated solution is much smaller. As an example in Problem 3, the numbers of non-dominated solution found using MODPSO and MOGA were 152 and 84, respectively, but MOGA came out with better Spacing compared with MODPSO. Figure 11 shows the scatter-plot matrix for Problem 3 using both algorithms. From these figures, the MODPSO solution was distributed in larger solution space compared with MOGA.

Figure 11.

Scatter plot matrix for Problem 3 using MOGA and MODPSO algorithms.

Based on the means of the performance indicator, the algorithms with the basis of GA showed good performance behind the proposed MODPSO. The NSGA-II consistently showed impressive performance in three indicators behind MODPSO, although it did not perform well in Spacing and Spread_max indicators. Meanwhile, the MOGA algorithm showed medium performance in most of the indicators for all reference settings. By the calculated mean, this algorithm was located between the third and fourth ranks. However, HGA showed inconsistent performance from one reference setting level to another. For the reference setting at Level 1, HGA shows quite good performance at the third ranking. But when the reference setting was changed to Levels 3 and 5, the HGA mean ranking dropped to the fourth and fifth positions, respectively.

On the other hand, the ACO algorithm showed improvement from one reference setting the level to another for $\tilde{η}$ , ER and GD. On average, the ACO was placed in the fifth rank among all algorithms. The remaining two algorithms, DPSO and MOPSO, were placed in the sixth and seventh ranks according to the indicator means. Both algorithms did not perform well in $\tilde{η}$ , ER and GD but showed quite impressive performance in Spacing and Spread_max indicators.

The performance of DPSO showed that the algorithm designed with weighted objective functional approach was unsuitable for finding a non-dominated solution, although it used an efficient regeneration procedure as in MODPSO. Meanwhile, the MOPSO’s performance showed that the original PSO operator to update position and velocity was not good enough for the discrete problem. On the other hand, the NSGA-II that performed efficiently in three indicators showed that the selection strategy based on CD of non-dominated solution worked effectively, since the MODPSO that adopted similar strategy also did well. Based on the performance of NSGA-II and DPSO algorithms, the proposed MODPSO algorithm has inherited good features from NSGA-II and DPSO because the MODPSO algorithm mainly adopted strategies from these algorithms.

The results in Table 6 also indicate that the proposed MODPSO consistently performed better than GA-based algorithms (i.e. MOGA, HGA and NSGA-II) for all the indicators except Spacing in all reference settings. It shows that the MODPSO was able to optimise integrated ASP and ALB problem from various difficulty levels efficiently compared with GA-based algorithms.

Statistical tests

To test the significance of the results, statistical tests were performed. In this case, analysis of variance (ANOVA) test was carried out to test whether there was any significant difference between the results obtained by an algorithm compared with other algorithms. The null hypothesis stated that there was no significant difference among all algorithm means. When the null hypothesis was accepted, it means that there was no significant improvement achieved by any algorithms. The summary of ANOVA test is presented in Table 7.

Table 7.

Summary of ANOVA test.

	$\tilde{η}$	ER	GD	Spacing	Spread_max
SSB	512147.60	14.30	121.93	35.03	183.90
SSW	301524.1	8.1442	137.805	74.207	72260.1
MSB	85358	2.38395	20.3224	5.83856	30.648
MSW	861.5	0.02327	0.3937	0.21202	206.457
f*	3.68	3.68	3.68	3.68	3.68
f	99.08	102.45	51.62	27.54	0.15

ER: error ratio; GD: generational distance; SSB: sum of square between groups; SSW: sum of square within groups; MSB: mean squares between groups; MSW: mean squares within groups; f*: critical f-value; f: calculated f-value.

In order to accept the null hypothesis, the calculated f-value must be smaller than the critical f-value (f*). The f* obtained from f-distribution table at 0.05 confidence interval was 3.86.⁴⁵ Based on Table 7, only the f-value for Spread_max fulfilled the requirement to accept the null hypothesis. Meanwhile, the f-values for $\tilde{η}$ , ER, GD and Spacing indicators showed larger values compared with f*. It means that four of the five performance indicators rejected the null hypothesis which brought the meaning that there were significant differences between algorithms. In this case, it shows that there were significant improvements achieved at least by one algorithm compared to others. Meanwhile, the acceptance of null hypothesis by Spread_max indicator shows that all algorithms were able to explore the extreme minimum and maximum values in the search space.

However, the ANOVA test did not tell us the exact algorithms that have significant mean differences. Therefore, a posteriori test known as the Tukey’s honestly significant different (HSD) test was performed to identify whether there was any significant improvement achieved by the proposed MODPSO compared to other algorithms. The Tukey’s HSD test was only conducted for the performance indicators that rejected the null hypothesis ( $\tilde{η}$ , ER, GD and Spacing) since only these groups showed the significant difference between algorithms. The summary of the Tukey’s HSD test is presented in Table 8.

Table 8.

Summary of Tukey’s HSD test.

Indicator (HSD*)		Absolute mean difference between MODPSO and algorithm
		$\tilde{η}$ (11.102099)	ER (0.089074)	GD (0.366382)	Spacing (0.268868)
Algorithm	MOGA	102.313725	0.461927	1.077286	0.292912
	ACO	102.235294	0.486218	1.123465	0.338841
	HGA	108.588235	0.490418	1.270296	0.012637
	NSGA-II	98.3333333	0.235592	0.500439	0.886947
	MOPSO	117.960784	0.592025	1.807975	0.062702
	DPSO	111.470588	0.593996	1.648349	0.017292

HSD: honestly significant different; MODPSO: multi-objective discrete particle swarm optimisation; ER: error ratio; GD: generational distance; MOGA: multi-objective genetic algorithm; ACO: ant colony optimisation; HGA: hybrid genetic algorithm; NSGA-II: non-dominated sorting genetic algorithm II; MOPSO: multi-objective particle swarm optimisation; DPSO: discrete particle swarm optimisation.

Table 8 presents the absolute mean difference between MODPSO and other algorithms. The number in bracket shows the critical HSD value (HSD*) that was calculated based on the Tukey’s table.⁴⁵ When the absolute mean difference between MODPSO and the particular algorithm is larger than HSD*, it means that the significant improvement has been identified between these two algorithms. Based on Table 8, the significant improvement was achieved by the proposed MODPSO compared with all other algorithms for $\tilde{η}$ , ER and GD indicators. In the meantime, the significant Spacing improvements were observed between MODPSO and MOGA, ACO and NSGA-II, but not with HGA, MOPSO and DPSO. This result was consistent with earlier finding in Figure 8 and Table 6 that prioritised the HGA, MOPSO and DPSO algorithms together with MODPSO for Spacing indicator.

The Tukey’s HSD test result explained that the proposed MODPSO performed well to converge to Pareto optimal solutions since the indicators that directly linked with it ( $\tilde{η}$ , ER and GD) showed significant improvement compared with other algorithms. On the other hand, the MODPSO only showed significant improvement in some cases in terms of uniformity of the found solution. Meanwhile, no significant improvement was found for the solution spreading, although small difference as presented in Figure 9 was notified.

The proposed MODPSO algorithm showed better performance because of the fine-tuning feature towards the end of iterations. This feature is important in ASP and ALB, where small changes may lead to sudden improvement in the results. The discrete updating procedure in MODPSO was designed to enable fine tuning towards the end of iterations. In PSO, all particles moved towards personal and global best solutions. According to the discrete updating procedure (subtraction operator (X_i − X_j)) in MODPSO, zero velocity was given when similar elements in X_i and X_j were found (this is the case when all particles move towards the best solution at the end of iterations). When the majority of velocity elements were 0, only small changes occurred in assembly sequence as presented by addition operator (X_i + V_i). This feature allowed fine tuning of the assembly sequences in MODPSO.

Conclusion

In this work, a MODPSO algorithm was proposed to optimise an integrated ASP and ALB problems. Indifferent with the existing algorithms, MODPSO that used Pareto-based approach to deal with multi-objective problem adopted discrete procedure instead of standard mathematical operators to update its position and velocity. A set of 51 test problems with different ranges of difficulties were used to test the performance of MODPSO compared with other algorithms.

The results show that the MODPSO performed better in all test problems in finding a non-dominated solution ( $\tilde{η}$ ), 82% in ER, 82% in GD, 22% in Spacing and 71% in Spread_max. Meanwhile, the result in Table 6 presents that the MODPSO performed better in four of the five performance indicators in all difficulty levels. This result shows the proposed MODPSO successfully overcame the underperformance of GA-based algorithms for the test problem with a larger number of tasks.

A statistical test was conducted to identify any significant improvement achieved by the proposed MODPSO. The statistical test concluded that the MODPSO showed significant improvement compared with other algorithms to converge to Pareto optimal solutions. In terms of solution uniformity, the significant improvement achieved by MODPSO was only applied to certain comparison algorithms. Furthermore, no significant improvement was achieved for the solution spreading using the MODPSO. Therefore, it can be concluded that the proposed MODPSO has shown good performance in terms of solution quality towards Pareto optimal solutions.

Instead of specific application to optimise integrated ASP and ALB problem, the proposed MODPSO can also be used to optimise other types of discrete problems represented using precedence graph. This includes the travelling salesman problem and vehicle routing problem with precedence constraint. However, the proposed MODPSO has limited performance in terms of solution uniformity as attained by Spacing indicator. Besides that, the CPU time for MODPSO is also among the highest within the comparison algorithms.

In future, an extensive effort to improve the solution uniformity and spreading is proposed to improve the quality of the overall solution. This might be achieved by hybridising the MODPSO with different algorithms with better solution spread. Besides, the MODPSO algorithm could be tested with higher complexity assembly problems, such as mixed model, as well as two-sided and parallel lines, in order to better understand the behaviour of the algorithm at varied complexity levels. Furthermore, the application of the algorithm to the industrial problem is also suggested.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The author(s) received financial support from Universiti Malaysia Pahang and Ministry of Higher Education, Malaysia for the research and publication of this article.

References

Rashid

MFF

Hutabarat

Tiwari

. A review on assembly sequence planning and assembly line balancing optimisation using soft computing approaches. Int J Adv Manuf Tech 2011; 59(1–4): 335–349.

Hamta

Shirazi

Ghomi

. A bi-level programming model for supply chain network optimization with assembly line balancing and push-pull strategy. Proc IMechE, Part B: J Eng Manuf 2016; 230(6): 1127–1143.

Zhang

Zeng

et al . The modified firefly algorithm considering fireflies’ visual range and its application in assembly sequences planning. Int J Adv Manuf Tech 2015; 82(5–8): 1381–1403.

Marian

. Optimisation of assembly sequences using genetic algorithm. PhD Thesis, University of South Australia, Adelaide, SA, Australia, 2003.

Tseng

H-E

Tang

C-E

. A sequential consideration for assembly sequence planning and assembly line balancing using the connector concept. Int J Prod Res 2006; 44(1): 97–116.

Ghandi

Masehian

. A breakout local search (BLS) method for solving the assembly sequence planning problem. Eng Appl Artif Intel 2015; 39: 245–266.

Becker

Scholl

. A survey on problems and methods in generalized assembly line balancing. Eur J Oper Res 2006; 168(3): 694–715.

Sungur

Yavuz

. Assembly line balancing with hierarchical worker assignment. J Manuf Syst 2015; 37: 290–298.

Haddadzade

Razfar

Zarandi

MHF

. Multipart setup planning through integration of process planning and scheduling. Proc IMechE, Part B: J Eng Manuf 2016; 230(6): 1097–1113.

10.

Deb

. Multi-objective optimization using evolutionary algorithms. Chichester: John Wiley & Sons, 2002.

11.

Luke

. Essentials of metaheuristics. 1st ed. Palm Springs, CA: Lulu, 2010.

12.

Yang

Zhao

. An ant colony algorithm for integrating assembly sequence planning and assembly line balancing. Appl Mech Mater 2013; 397–400: 2570–2573.

13.

Yang

. Integrated assembly sequence planning and assembly line balancing with ant colony optimization approach. Int J Adv Manuf Tech 2016; 83(1): 243–256.

14.

Chen

. A hybrid genetic algorithm approach on multi-objective of assembly planning problem. Eng Appl Artif Intel 2002; 15: 447–457.

15.

Tseng

H-E

Chen

M-H

Chang

C-C

et al . Hybrid evolutionary multi-objective algorithms for integrating assembly sequence planning and assembly line balancing. Int J Prod Res 2008; 46(21): 5951–5977.

16.

Wang

Che

Chiang

. A hybrid genetic algorithm for multi-objective product plan selection problem with ASP and ALB. Expert Syst Appl 2012; 39(5): 5440–5450.

17.

Ab Rashid

MFF

Hutabarat

Tiwari

. Development of a tunable test problem generator for assembly sequence planning and assembly line balancing. Proc IMechE, Part B: J Eng Manuf 2012; 226(11): 1900–1913.

18.

Xinchao

. A perturbed particle swarm algorithm for numerical optimization. Appl Soft Comput 2010; 10(1): 119–124.

19.

Kennedy

Eberhart

. Particle swarm optimization. In: Proceedings of IEEE international conference on neural networks, Perth, Australia, 27 November-1 December 1995, pp.1942–1948. New York: IEEE.

20.

Shuang

Chen

. Microrobot based micro-assembly sequence planning with hybrid ant colony algorithm. Int J Adv Manuf Tech 2007; 38(11–12): 1227–1235.

21.

Gao

Sun

Wang

et al . An efficient approach for type II robotic assembly line balancing problems. Comput Ind Eng 2009; 56(3): 1065–1080.

22.

Elbeltagi

Hegazy

Grierson

. Comparison among five evolutionary-based optimization algorithms. Adv Eng Inform 2005; 19(1): 43–53.

23.

Mukund Nilakantan

Ponnambalam

. Robotic U-shaped assembly line balancing using particle swarm optimization. Eng Optimiz 2015; 48(2): 231–252.

24.

Liu

Wen

. Application of multi-objective culture particle swarm optimization in complex product assembly line balancing. Adv Mater Res 2013; 694–697: 3526–3530.

25.

et al . A hybrid assembly sequence planning approach based on discrete particle swarm optimization and evolutionary direction operation. Int J Adv Manuf Tech 2013; 68(1–4): 617–630.

26.

Hamta

Fatemi Ghomi

SMT

Jolai

et al . A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect. Int J Prod Econ 2013; 141(1): 99–111.

27.

Xing

Wang

. Assembly sequence planning based on a hybrid particle swarm optimisation and genetic algorithm. Int J Prod Res 2012; 50: 7303–7312.

28.

Nearchou

. Maximizing production rate and workload smoothing in assembly lines using particle swarm optimization. Int J Prod Econ 2011; 129(2): 242–250.

29.

Coello Coello

Lechuga

. MOPSO: a proposal for multiple objective particle swarm optimization. In: Proceedings of the 2002 congress on evolutionary computation, Honolulu, HI, 12–17 May 2002, pp.1051–1056. Washington, DC: IEEE Computer Society.

30.

Tseng

Y-J

Chen

J-Y

Huang

F-Y

. A particle swarm optimisation algorithm for multi-plant assembly sequence planning with integrated assembly sequence planning and plant assignment. Int J Prod Res 2010; 48(10): 2765–2791.

31.

Rameshkumar

Suresh

Mohanasundaram

. Discrete particle swarm optimization (DPSO) algorithm for permutation flowshop scheduling to minimize makespan. Adv Nat Computation 2005; 3612: 572–581.

32.

Jianping

Chun

Jun

. A discrete particle swarm optimization algorithm for assembly line balancing problem of type 1. In: Proceedings of the 2011 third international conference on measuring technology and mechatronics automation, Shanghai, China., 6–7 January 2011, pp. 44–47. Washington DC: IEEE Computer Society.

33.

. An assembly sequence planning approach with a discrete particle swarm optimization algorithm. Int J Adv Manuf Tech 2010; 50(5–8): 761–770.

34.

Wang

Liu

. Chaotic particle swarm optimization for assembly sequence planning. Robot Cim: Int Manuf 2010; 26(2): 212–222.

35.

Deb

Member

Pratap

et al . A fast and elitist multiobjective genetic algorithm. IEEE Trans Evol Comput 2002; 6(2): 182–197.

36.

Rashid

MFF

Tiwari

Hutabarat

. An integrated representation scheme for assembly sequence planning and assembly line balancing. In: Proceedings of the 9th international conference on manufacturing research, Glasgow, 6–8 September 2011, pp.125–131. Glasgow Caledonian University.

37.

Jiang

. A memetic algorithm approach for batch-model assembly line balancing problem of sub-block in shipbuilding. Proc IMechE, Part B: J Eng Manuf 2014; 228(10): 1290–1304.

38.

Whitney

. Mechanical assemblies: their design, manufacture, and role in product development (vol. 1). Oxford: Oxford University Press, 2004.

39.

Zhang

. An particle swarm optimization approach for assembly sequence planning. Appl Mech Mater 2009; 16–19: 1228–1232.

40.

Zha

. A hybrid DPSO-SA approach to assembly sequence planning. In: 2010 IEEE international conference on mechatronics and automation, Xi’an, China, 4–7 August 2010, pp.1998–2003. New York: IEEE.

41.

Moon

Kim

Choi

et al . An efficient genetic algorithm for the traveling salesman problem with precedence constraints. Eur J Oper Res 2002; 140(3): 606–617.

42.

Bautista

Pereira

. Ant algorithms for a time and space constrained assembly line balancing problem. Eur J Oper Res 2007; 177(3): 2016–2032.

43.

Choi

Y-K

Lee

Bin Cho

. An approach to multi-criteria assembly sequence planning using genetic algorithms. Int J Adv Manuf Tech 2008; 42(1–2): 180–188.

44.

Yoosefelahi

Aminnayeri

Mosadegh

et al . Type II robotic assembly line balancing problem: an evolution strategies algorithm for a multi-objective model. J Manuf Syst 2012; 31(2): 139–151.

45.

Coolidge

. Statistics: a gentle introduction. London: SAGE, 2000.

i	j
i	1	2	3	4	5	6	7
1	0	1	1	1	0	0	0
2	0	0	0	0	1	0	0
3	0	0	0	0	0	1	0
4	0	0	0	0	0	0	1
5	0	0	0	0	0	0	1
6	0	0	0	0	0	0	1
7	0	0	0	0	0	0	0

i	j
i	1	2	3	4	5	6	7
1	0	1	1	1	0	0	0
2	0	0	0	0	1	0	0
3	0	0	0	0	0	1	0
4	0	0	0	0	0	0	1
5	0	0	0	0	0	0	1
6	0	0	0	0	0	0	1
7	0	0	0	0	0	0	0

Multi-objective discrete particle swarm optimisation algorithm for integrated assembly sequence planning and assembly line balancing

Abstract

Keywords

Introduction

ASP and ALB problem representation

Objective function

Proposed MODPSO

Initialisation

Evaluation

Update Pbest and Gbest

Update position and velocity

Subtraction operator (position−position)

Addition operator (position+velocity)

Multiplication operator (coefficient+velocity)

Addition operator (velocity+velocity)

Experimental design

Performance indicators

Experimental results

Discussion of results

Statistical tests

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

i	j
i	1	2	3	4	5	6	7
1	0	1	1	1	0	0	0
2	0	0	0	0	1	0	0
3	0	0	0	0	0	1	0
4	0	0	0	0	0	0	1
5	0	0	0	0	0	0	1
6	0	0	0	0	0	0	1
7	0	0	0	0	0	0	0