Sequencing problem for a hull mixed-model assembly line considering manufacturing complexity

Abstract

To ensure effective hull assembly line production, it is vital to consider the problems on delivery date of order and sequencing complexity within mixed-model production environments. In this paper two criteria are considered for stratified optimization according to their importance: to minimize the satisfaction ratio of delivery date, and to minimize the complexity degree of the system arising from its state frequent changes. Finding an optimal solution for this complicated problem in reasonable computational time is cumbersome. Therefore, this paper presents an improved particle swarm optimization (IPSO) algorithm to solve the multi-objective sequencing problems. Instead of modeling the positions of particles in a continuous value manner in traditional PSO, IPSO uses an encoding and decoding scheme of task-oriented assignment for representing the discrete input sequences of products. Furthermore, dynamic mutation operator and chaos strategy are introduced to help the particles escape from local optima and the strategy for population decomposition is proposed to further improve the efficiency of the optimization. Numerical simulation suggests that the proposed IPSO scheduler can provide obvious improvement on solution quality and running time. Finally, a case study of the optimization of a panel block assembly line was given to illustrate the effectiveness of the method.

Keywords

Improved particle swarm optimization multi-objective satisfaction degree of delivery date manufacturing complexity hull mixed model assembly line sequencing

1 Introduction

In most cases, a ship is built to order and customized to the specific requirements of the purchaser. Hence, shipbuilding is a non-repeatable project and can’t employ the mass production method. Initially, ships were all produced from scratch in a dry dock. It is obvious that traditional shipbuilding is the one-of-a-kind production mode and is difficult to gain the high production effectiveness.

In recent years, with the application of automated equipment and advanced process technology, a modern shipyard can apply the group technology, product-oriented work breakdown structure and process lanes to achieve continuous and uniform process flows. In this way, a lot of different workshops/assembly lines are used to construct large blocks of the ship, which are then transported to the dry dock and erected. According to the geometrical characteristics of block, blocks of a ship can be divided into panel blocks and curve blocks. The assembly of panel blocks can be performed on an assembly line because of their similarity of process and huge production quantities. Each of these panel blocks in a ship are produced at the panel block assembly line (PBAL) and then are to be delivered at the dry dock at a given time. Therefore, it is very important to ensure the high production effectiveness and efficient use of the resources on the PBAL.

As a classic mixed model assembly line (MMAL), a crucial problem in PBAL is scheduling which involves determining the detailed sequencing and timing of all assembly tasks at each station to maximize the performance of the line. Scheduling problems within MMAL have been studied for decades, most of which adopt two main steps to solve them. One is that the scheduling objectives must be exactly selected and determined according to characteristics and demands of the assembly line. Secondly, it is known that a scheduling problem in MMAL falls into the NP-hard class of combinatorial optimization problems. Hence, a good solving algorithm is the key for these kind of problems [1 , 22]. Extensive models and procedures are developed and excellent reviews of these works are given by Boysen et al. [11].

Salehi et al. [10] considered three sequencing objectives in mixed-model synchronous assembly lines, i.e., minimizing total idle cost, total production rate variation cost, and total setup cost. These objectives are weighted by their relative importance weights and a mathematical formulation is presented, which is capable of solving the small-sized ones of these problems. A heuristic algorithm based on simulated annealing approach is developed to solve the mathematical model. Chutima et al. [17] presented a Pareto biogeography-based optimization approach to mixed-model sequencing problems on a two-sided assembly line where a learning effect is also taken into consideration. Three objectives which typically conflict with each other are optimized simultaneously comprising minimizing the variance of production rate, minimizing the total utility work and minimizing the total sequence-dependent setup time. Mannavizadeh et al. [13] considered a multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a Make-to-Order environment. To minimize the tardiness cost of the orders for customers with high priority, they presented six objective functions. Particle swarm optimization and simulated annealing (SA) algorithms are used to check the feasibility of the model. Tian et al. [23] proposed a discrete PSO algorithm called DPSO to solve the two stage assembly scheduling problem with respect to bicriteria of makespan and mean completion time where setup times are treated as separate from processing times. Ozturk et al. [3] proposed mixed integer programming and constraint programming models which consider both balancing and model sequencing within the same formulation along with the optimal schedule of tasks at a station. Furthermore, they also compare the proposed exact models with decomposition schemes developed for solving different instances of varying sizes. Mansouri et al. [18] presented a multi-objective genetic algorithm approach to a Just-In-Time (JIT) sequencing problem where variation of production rates and number of setups are to be optimized simultaneously. In this paper, the performance of the proposed algorithm was compared against a total enumeration scheme in small problems and also against three other search heuristics in small, medium and large problems. Al-Anzi et al. [4] presented the two-stage assembly flow shop scheduling problem with respect to maximum lateness criterion where setup times are treated as separate from processing times. They formulated the problem and obtained a dominance relation. Moreover, they proposed a self-adaptive differential evolution heuristic.

Although the PBAL has the characteristics of general MMAL, it still owns particularity unlike any other assembly line. For example, shipbuilding is a Make-to-Order and one-of-a-kind production mode, the demand of delivery date is stricter than other MMALs. In addition, shipbuilding corporations often operate in a dynamic environment driven by frequent changes in the hybrid production. The resulting complexity and uncertainty heavily limit the effectiveness of conventional production control and scheduling approaches. Therefore, how to measure the complexity and use the complexity to effectively control the PBAL is a very important issue. In this paper, we mainly consider two kinds of complexity which are arisen from changes of setup times and overload and idleness. In the PBAL, welding equipment must be used during hull assembly process. During the mixed-model production, the setup-time of welding equipment must be changed frequently according to its different operating object. Meanwhile, owing to heavy and large hull blocks heavily occupy work space, there is no buffer between the workstations. The PBAL has the characteristics of a zero buffer assembly line and is easier to frequently cause overload and idleness of the station because of the uneven assembly time.

As far as our best knowledge, few attempts have been made to schedule block assembly considering the above scheduling objectives within mixed-model assembly production environments. In this research, two indices which typically conflict with each other are optimized comprising minimizing the satisfaction ratio of deliverydate and minimizing the sequencing complexity on mixed-model assembly based on the stratified optimization idea. It is obvious that it is a multi-objective optimization problem and is easy to fall into a NP-hard class.

Although there are many alternative meta-heuristic methods for solving the mixed-model assembly line sequencing problem, there is still no clear guidance available regarding the optimal choice for a particular problem. In these algorithms, PSO has been advocated to be especially suitable for multi-objective optimization due to its fast convergence and good quality of solutions. Therefore, we designed an improved PSO algorithm which is called IPSO to solve the PBAL sequencing problem with bi-criteria. In IPSO, an encoding and decoding scheme of task-oriented assignment is designed for representing the scheduling sequences of products. In order to refrain from the shortcoming of premature convergence, the dynamic mutation operator is designed, which is used to control adaptive mutation of the particle. Furthermore, the chaos idea is introduced to further enhance the local search ability of the particle. Meanwhile, the population decomposition tactics is used in the early iterations of the particle to help particles to escape from local minimum. The IPSO can be not only used to solve a multi-objective optimization problem according to the stratified scheduling tactic, but also be used as a single-objective method after filtering it’s stratified optimal mechanism.

The rest of this paper is organized as follows: In Section 2, we present the problem’s assumptions, objective functions and stratified scheduling idea considering index importance. A novel PSO-based algorithm is provided in Section 3. In Section 4, we present an experimental design in which the results achieved by the proposed algorithm and the performances of the proposed algorithm are also experimented and analyzed by through comparing method. Conclusions are given in Section 5.

2 Representation models of hull assembly line

2.1 Problem’s assumptions

The PBAL considered in this paper consist of 11 workstations and is shown in Fig. 1. A workstation is a physical location which consists of operators, welding machines, and process equipment. Products are moved between the workstations via the conveyor roller. Some general assumptions of the considered problems are as follows [2 , 9]:

Parallel stations and work-in-process buffer are not allowed.

The travel times of workers between stations are ignored.

A PBAL with limited intermediate storage spaces between the workstations, a product cannot leave its current workstation unless the next workstation becomes available and is ready to accept a new product.

Each workstation is closed and the operator can only be responsible for assembly tasks within the length range of workstation. With the help of additional workers outside PBAL, unfinished assembly tasks can be completed.

Without loss of generality, we can assume that there are J stations in the PBAL and the length of the ith station is L_i (i = 1, ⋯ , J). Each block to be produced is rolled through the PBAL at a constant rate V_c, thereby getting assembled. At each station, a predefined set of tasks is performed on each component within a specified fixed time called as the cycle time C. It is assumed that there are M kinds of block type which need to be assembled in the PBAL and D_i is the demand number of the ith block. The demand numbers of these blocks are mainly determined by the dock cycle index in the node plans. To conveniently described the control on the PBAL, the minimum production set (MPS) which is widely accepted in the mixed-model assembly system is used in this paper. As a result, the production quantity of the ith block in a MPS can be defined as $d_{i} = \frac{D_{i}}{h}$ (1)

Where i = 1, …, M and h is the greatest common divisor of {D₁, D₂, …, D_M}. According to the definition, the total project tasks should be completed through h times of repeating the MPS.

2.2 Objective functions

With the mentioned basic assumptions, the mathematical model will be presented using the notations defined in Table 1.

2.2.1 Satisfaction ratio of delivery date

As we all known, a shipbuilding enterprise should organize the production according to the order. It is no doubt that it will lead to additional early loss if the order is completed ahead of schedule. On the contrary, it will cause a delay loss if the production is delayed. Therefore, the satisfaction ratio of delivery date is the most important production index which should comprehensively consider the influence on the earliness loss and lateness loss according to the Just-In-Time production theory. The proposed index of this paper can be described by the below equations. $\begin{matrix} f (x) = min {\sum_{n = 1}^{N} W_{n} (S_{e} \times C_{en} \times E_{n} + \\ S_{d} \times C_{dn} \times D_{n})} \end{matrix}$ (2)

Subject to:

(S_e = 0, S_d = 1) or (S_e = 1, S_d = 0)

When (S_e = 0, S_d = 1), it expresses that the order has been finished behind schedule and when (S_e = 1, S_d = 0), it expresses that the order has been finished ahead of schedule.

2.2.2 Sequencing complexity in a PBAL

As product variety increases, the assembly process in mixed-model assembly systems can become quite complex, which in turn influences the system performance. As a result, the manufacturing system complexity can be defined by the uncertainty level of its system. At present, the majority of complexity definitions in manufacturing system are based on Shannon entropy [5 , 20]. From an information theoretic perspective, entropy is defined as the amount of information required to describe the state of the manufacturing system and its equation is described as: $E (X) = - \sum_{i = 1}^{n} p_{i} {log}_{2} p_{i}$ (3)

Where E (X) is the information entropy of system X, X owns n possible states in the whole system, and the p_i is the probability of state i, p_i ≥ 0, $\sum_{i = 1}^{n} p_{i} = 1$ .

In a mixed-model assembly line, how to define the state and the number of states is the base to determine its complexity degree. Different concerns for the system will select different states and theirs numbers. In this paper, we mainly consider that the complexity degree of a system whose state rapidly changes is the higher than those whose states change a time within an interval of hours or days. In the PBAL, the setup times always change with the different sequencing schemes and can be described as state value of the system. In addition, idle phenomenon and overload phenomenon are very easy to be caused and will lead the waste of human resource and work time because of the varieties of products. So, we consider the idle time and overload time as the other kind of state description.

According to above description, a definition of sequencing complexity is given as follows:

$\begin{matrix} E (X_{PBAL}) & = & - \sum_{j = 1}^{J} {pse}_{j} \times {log}_{2}^{{pse}_{j}} \\ - \sum_{j = 1}^{J} {pio}_{j} \times {log}_{2}^{{pio}_{j}} \end{matrix}$ (4)

Where: pse_j expresses the state probability of setup times on the jth workstation and can be modeled according to the following equations: ${pse}_{j} = \frac{\sum_{i = 1}^{I} \sum_{m = 1}^{M} \sum_{r = 1}^{M} x_{imr} t_{jmr}}{\sum_{j = 1}^{J} \sum_{i = 1}^{I} \sum_{m = 1}^{M} \sum_{r = 1}^{M} x_{imr} t_{jmr}}$ (5)

Subject to: $\sum_{i = 1}^{I} \sum_{r = 1}^{M} x_{imr} = d_{m}, \forall m;$ (6) $\sum_{m = 1}^{M} \sum_{r = 1}^{M} x_{imr} = 1, \forall i;$ (7) $\begin{matrix} \sum_{m = 1}^{M} x_{imr} = \sum_{p = 1}^{M} x_{(i + 1) rp}, \\ i = (1, 2, \dots, I - 1), \forall r; \end{matrix}$ (8) $\sum_{m = 1}^{M} x_{imr} = \sum_{p = 1}^{M} x_{1 rp}, \forall r;$ (9) $x_{imr} = 0 or 1, \forall i, m .$ (10)

If product m is the ith position and product r is the (i + 1)th position in the product sequence, thenx_imr = 1, else x_imr = 0. Equation (6) expresses the number of product in a MPS. Equations (7) and (8) ensure that each position in product sequence has only a product. Equation (9) considers the linkage problem when the MPS repeats.

The pio_j expresses the state probability of idle time and overload time on the jth workstation and can be modeled according to the following equations: ${pio}_{j} = \frac{\sum_{i = 1}^{I} {idl}_{ji} + \sum_{i = 1}^{I} {ovt}_{ji}}{\sum_{j = 1}^{J} \sum_{i = 1}^{I} {idl}_{ji} + \sum_{j = 1}^{J} \sum_{i = 1}^{I} {ovt}_{ji}}$ (11)

Subject to: ${idl}_{ji} = max (0, C - E_{ji});$ (12) ${ovt}_{ji} = max (0, S_{ji} + \sum_{m = 1}^{M} x_{mi} t_{mj} - \frac{L_{j}}{V_{c}});$ (13) $E_{ji} = min (S_{ji} + \sum_{m = 1}^{M} x_{mi} t_{mj}, \frac{L_{j}}{v_{c}});$ (14) $S_{j, i + 1} = max (0, E_{ji} - C);$ (15) $\begin{matrix} x_{mi} = 0 or 1, \forall m, i, m = 1, 2, \dots, M, \\ \sum_{m = 1}^{M} x_{mi} = 1, \forall i . \end{matrix}$ (16)

The Equation (14) expresses that the assembly time of each station for one product cannot exceed the transition time of the corresponding station. The Equation (15) expresses that the workers should return to the starting point of the station when the current product has finished processing at a station. The Equation (16) expresses that each task can be assigned to only one workstation.

2.3 Stratified idea in terms of index importance

In traditional multi-objective optimization methods, the weighted sum method is one of the most widely used algorithms, which is simple, easy to understand and efficient. But it has three disadvantages:

The unit among different target is inconsistent and difficult to compare;

The weight value for each target is assigned with great subjectivity;

It can’t find solutions that lie in the nonconvex regions of the Pareto front.

It is known to all, the uncertainty and unpredictability of manufacturing system is greater if it’s state complexity is greater. We need to understand and master more information on the system, otherwise, the state of system will be difficult to manage and control. But this does not mean that the complexity of the manufacturing system must be bad for organizations and operation of manufacturing, in fact, it is a “double-edged sword” regard to a manufacturing system. If complexity is too large, it is easy to cause the system out of control. If complexity is too small, the manufacturing system may lack sufficient flexibility and not be suited for hybrid flow production. This means we cannot arbitrarilyminimize the complexity index of a manufacturing system under common conditions. On the other hand, the delivery date is the most important index for a ship is built for order. It means that the importance of delivery date is higher than the importance of the complexity.

Through the above analysis, this paper uses a stratified optimal method to solve the multi-objective optimization problem on the proposed model. On the basis of this idea, the satisfaction ratio of delivery date is set as the scheduling index of the first layer and it’s the optimal solution should be found firstly. And then, we should give some tolerance on the solution of the first layer and set the complexity as the index of the second layer. The optimal solution of the second layer should be calculated based on the tolerance solution set of the first layer. Thus, the method not only uses effectively the production flexibility of mixed-model assembly but also controls effectively the complexity of PBAL.

The specific solution tactic is described as follows:

Firstly, the scheduler should set the f (x) as the first layer and set the E (X_PBAL) as the second layer according to their importance.

Secondly, a single-objective intelligent algorithm should be used to find the optimal solution of the first layer target. Furthermore, the allowable width of the solution is set to obtain the optimal solution set of the first layer and the location of the corresponding solution.

Finally, the optimal value of the second layer can be calculated according to the location of each solution in the optimal solution set of the first layer. It is obvious that the feasible solution region of the second layer must locate within the scope of a wide capacity on the first layer solution. Thus, we will find the optimal solution of the whole model and effectively avoid the conflict between the above indices.

3 The proposed PSO-based algorithm

3.1 Basic theory of PSO algorithm

Kennedy and Eberhart [6] first introduced the PSO algorithm. It was developed through simulation of social behaviour such as bird flocking and fish schooling. As an evolutionary algorithm, PSO algorithm can be easy to implement and generate higher-quality solutions within a shorter calculation time. To achieve above scheduling tactic, this paper uses the improved PSO algorithm as the main algorithms of hierarchical optimal method.

The basic theory of PSO is as follows.

There is a swarm which consists of M particles in a D-dimensional searching space. All particles have velocities and fitness values. Each particle represents a potential solution to the optimization problem flying in the searching space and moves with a certain velocity according to its own pervious best position and its swarm’s previous best position. The modification of velocities and positions can be calculated as follows:

$\begin{matrix} v_{id} (t + 1) & = & {wv}_{id} (t) + c_{1} r_{1} (p_{id} (t) - x_{id} (t)) \\ + c_{2} r_{2} (p_{gd} (t) - x_{id} (t)) \end{matrix}$ (17) $x_{id} (t + 1) = x_{id} (t) + v_{id} (t + 1)$ (18)

where v_id is the dth dimension element of velocity of particle i, i = 1, ⋯ , M, d = 1, ⋯ , D, t is the iteration number, c₁ and c₂ are learning factors, r₁ and r₂ are uniform random numbers between [0,1], p_id is the best previous position of the ith partcle, p_gd is the best position among the whole swarm, and w is the inertia weight that exerts the effect of the old velocity on the new one.

One of the most commonly used methods to decide the value of inertia weight is linear decreasing in which w is update by the following formula: $\begin{matrix} w & = & w_{1} + (w_{1} - w_{2}) \times (t / Maxgen)^{2} \\ + (w_{2} - w_{1}) \times (2 t / Maxgen) \end{matrix}$

where w₁ and w₂ are the final and initial values of weighting coefficient, respectively, and Maxgen is the maximum number of iterations [16].

3.2 Encoding and decoding scheme

Scheduling of hull assembly line is a typical discrete optimization problem. Since each particle is defined with a continuous position in the D-dimensional space, it is very necessary to develop an encoding scheme to link the continuous position with the discrete information of sequences. In this paper, an encoding scheme of task-oriented assignment is designed for representing the scheduling sequences of product [12].

In this encoding scheme, the ith particle can be represented by an integer vector x_i = {x_i1, x_i2, …, x_in}, where n is the overall number of assembly tasks. Using this method, an assembly task in position j (j = 1, ⋯ , n) of the vector will be assigned to a workstation before the task in position j + 1 of the vector. Therefore, the vector represents a scheduling sequence of assembly tasks. Since PSO works with floating-point vectors, the random-keys method is utilized to map the linkage between these vectors and encoding scheme. To explain exactly the method, an example for encoding and decoding is described as follows.

Assume that there are four kinds of block types (such as A, B, C and D) which will be assembled in a minimum production cycle, their production quantities are 4, 3, 2 and 1 respectively. It is clear that there are ten products to be assembly through the hull assembly line. Firstly, we can use the integer 1, 2, 3 or 4 to stand for one product of the A, 5, 6 or 7 to stand for one product of the B, 8 or 9 to stand for one product of the C and 10 to stand for the D. Secondly, a real-coded vector including 10 floating-point numbers should be generated by the calculating of the PSO. Each floating-point number corresponds with one integer of the encoding scheme according to random-keys method. Thirdly, these floating-point values should be sorted in an ascending order and the ranked order value represents the ordered position in the sorted ascending order. The integer number corresponding to the ordered floating-point value will occupy its ordered position in the decoding vector. Finally, we can find the production order of products A, B, C and D according to the integer permutation. The encoding and decoding procedure of this example is shown in Fig. 2 to further explain above method.

3.3 The dynamic mutation operator

Mutation operation is intended to prevent solutions in the population falling into a local optimum of the solved problem and also to find more uncovered spaces of the search space. In this paper, the mutation operation and mutation probability can be expressed as follows: $x_{i} = 3 θ \times (1 - rand) \times v_{i} + x_{i}$ (19) $p (t) = 1 - \frac{t}{Maxgen}$ (20)

Where θ is 1 or –1 and its sign expresses the direction of particle velocity, rand is a random number between [1,0] and t is the iteration number. For each particle in a swarm, if rand < p (t), then it will implement the mutation operation, else, it will not do it. It can be seen that the mutation probability is very large at the initial time of algorithm iteration. The purpose of this treatment is to expand the search area of particles and to increase the diversity of solution. With the increase of the iterations number, the mutation probability of particles will be dynamically reduced to accelerate the convergence rate of algorithm.

Furthermore, to further help particle escape from local optima, this research introduced the chaos ideas to the PSO for its stochastic and ergodic characteristics. If the difference value of the adjacent global optimum is less than 0.01 and the position of the particle corresponding to the global optimal solution does not change during the particle iterates, then some particle will be selected to implement the chaos mutation with the probability p_c. The chaos operation uses the Logistic model and is shown as follows. $x_{k + 1} = 4 x_{k} (1 - x_{k}), x_{k} \in (0, 1) .$ (21)

3.4 Population decomposition tactics

If a PSO algorithm converges too fast, the particles are easy to decrease diversity during the iterative process and may fall into a local optimal solution. In this paper, the population decomposition tactics is used in the early iterations of the particle. The method can increase the diversity of the particles and help particles to escape from local minimum. Its special implementation process is described as follows.

When two-thirds of the particle iteration times have reached, if the global optimum value of particle has not changed during five iterations in succession, then the population decomposition can be implemented following the below the steps a and b.

The population is divided into two groups A and B. In A group, all particles were randomly given new particle positions to increase the diversity of population.

In B group, all particles keep the original information elements without changing to make full use of previous experience.

3.5 Step by step algorithm

Steps of this proposed algorithm are as follows:

Step 1. Initialize the control parameters of PSO; including numbers of population (M), dimension of particle (D), maximal number of generations (Maxgen), maximum inertia weight (w₁), minimum inertia weight (w₂), learning factor (c₁ and c₂), speed limit (v_max).

Step 2. Generate randomly M initial positions of particles and let k = 1.

Step 3. Compute the fitness of individual and find the pbest and gbest according to its layer.

Step 4. Population update

Compute the fitness of each particle,

Update the velocity and position of each particle,

Do the dynamic mutation operation,

Update the pbest of each particle and gbest of the population.

Step 5. Implement chaos operation

Step 6. Implement population decomposition

Step 7. If t < Maxgen, then go to Step 4, else if k = 1, then find the minimum value f (x¹) and the optimal solution x¹ of the first layer, input the tolerance value δ > 0 and obtain the feasible region X² of the second layer: $X^{2} = {x | f (x) \leq f (x^{1}) + δ}$

generate randomly M initial positions of particles whose positions locate within X², let k = 2 and goto step3, else stop iteration and output optimization on results.

4 Experimental results

4.1 Problem data

The experimental examples we used in the paper are derived from a hull panel block assembly system in a recently built shipyard in China. This PBAL consists of 11 workstations which are shown in Fig. 1. Three kinds of blocks whose types are A, B and C respectively will be assembled through the PBAL. Some parameters of production are shown in the Tables 2–4.

4.2 Parameters setting and analysis

For IPSO, the parameters, the swarm size (M), the number of epochs (Maxgen), learning factors (c₁, c₂), initial inertia weight (w₁) and final inertia weight (w₂), have great effects on its test results. According to Kennedy and Eberhart [6] about setup of learningfactors, it suggested to set learning factors c₁ = c₂. Thus, we designed an experimental test of the PSO parameters which consist of five factors to find the best combination of values of the parameters. In the test, the five factors are denoted as P₁, P₂, P₃, P₄, and P₅, and the parameters setting for them each in four levels can be illustrated in Table 5. It is very obvious that all the possible combinations of factors are very time-consuming, so the Taguchi’s orthogonal array of L₁₆ (4⁵) (see Table 6)is selected as the best test design to execute theexperiments.

In order to evaluate the performance of the algorithm, the signal-noise ratio(S/N) is used and is expressed as follows. $S / N = - 10 \times log (\frac{1}{n} \sum_{i = 1}^{n} y_{i}^{2})$ (22)

where n is the number of experiments, y_i is the objective value of the experiment i. If a factor’s level has the biggest S/N ratio, it will become the most effective level of the factor.

For the stratified scheduling tactics, the difference about objective values of first layer is not obvious, so the complexity function is selected as the evaluated object. Each parameter set in orthogonal array is repetitively tested six times, and the corresponding S/N value is listed in Table 6. Figure 3 depicts the average S/N ratio obtained at each level. It can be seen that the parameter set of P₁ (4) P₂ (4) P₃ (4) P₄ (2) P₅ (4) performs the best response. As the results, the parameter set with M = 40, Maxgen = 400, c₁ = c₂ = 2, w₁ = 0.9 and w₂ = 0.2 can be determined as the best parameter set.

4.3 Case results

Firstly, the single-objective IPSO is selected to calculate the f (x) and E (X_PBAL) respectively in order to verify the effectiveness of the multi-objective stratified optimization method. Figures 4 and 5 demonstrate the simulation results for single-objective IPSO. From figures, it can be observed that the minimum value of f (x) is 478 and the minimum value of E (X_PBAL) is 3.3968.

And then, the scheduling tactic is determined to minimize the E (X_PBAL) on the basis of f (x) minimization. In this process, let δ = 60. The results that we used the multi-objective method to calculate are shown in Table 7. Nine results among calculating process are selected to distinctly demonstrate the stratified optimization method.

It is obvious that the 7th item is the best calculating results. Comparing with the single-objective method, the proposed method almost obtains the optimal value of two objects at the same time. It can be seen that the method makes an effort to find the minimum value of the second layer on the basis of giving priority to ensuring the optimal solution of the firstlayer.

As the results, the product sequencing of the 7th result is “A-B-A-C-A-A-C-A-A-A-A-C-C-A-A-C-A-A-B-A-A-C-A-C-A-A-A-B-C-A”.

4.4 Convergence analysis

In order to verify the performance of the algorithm in this paper, the simulation results among the proposed method, the genetic algorithm (GA) and standard PSO algorithm were compared.

Environment of simulation including: Intel(R) Core(TM)2 Duo CPU E8200 2.66 GHz, 2 GB memory, Windows 7.0.

Taking into account that the algorithm may be influenced by random characteristics, experiments are simulated 50 times in the same experimental environment. The average values of test results on different algorithm are shown in the Tables 8 and 9.

The average run time for single-objective IPSO to get the best f (x) and E (X_PBAL) for the real PBAL are 1.638 seconds and 6.684 seconds respectively. Comparing with the GA and traditional PSO, single-objective IPSO get optimistic results for 50 times among 50 experiments. So the proposed single-objective IPSO scheduler performs much better than GA and traditional PSO on computing speed and accuracy.

The average run time for multi-object PSO and the proposed multi-objective stratified IPSO to get the best scheduling solution is 25.709 s and 11.736 s respectively. The simulation results of multi-objective PSOare a solution set rather than the only solution. If you want to obtain an optimal solution, you must select a solution from the set according to some assessment rules. These rules are always subjective and difficult to accurately distinguish the importance of object. Therefore, it is very obvious that the proposed method is more reasonable and more efficient than traditional multi-object PSO when some index owns the characteristic of “double-edged sword”.

4.5 Different sized problems and sensitivity analysis

To further evaluate the efficiency of the proposed IPSO, twelve different problem sizes are considered. Moreover, sensitivity analyses were performed to evaluate the response of the IPSO algorithm to changes on its main parameters. Table 10 shows the basic information for 4 small-sized problems, 4 medium-sized problems and 4 large-sized problems. The results of the problem are presented in Table 11. It can be observed that the runtimes increase accordingly with the increase of the scale of the problem.

Because of the large difference between different problems in computational time and quality of the proposed IPSO algorithm, the parameters of algorithm should be tuned to find the effect of variation of parameters on the objective function. So to do this survey, we used twelve different problems for each problem size, and then we once change the value of one parameter in Table 5 while other parameters are fixed. Finally the following rules were found to be effective in terms of solution quality and diversity level.

The number of particles influences the convergence rate and problem-solving value of IPSO. If the higher the number of particles, the more time it takes to study. Through experiments, swarm size should be set to 20 in small sized problem and 40 in larger sized problems.

It is found that, when the problem size is increased, the IPSO requires more number of iterations to find near-optimal solution. For the small-sized problem, the IPSO with parameter M = 200 or M = 300 had almost the same solution. Similarity, we found the corresponding regular pattern on medium- and large-sized problems. So the IPSO should be terminated after 200 iterations in small sized problems, 300 iterations in medium-sized problems and 400 iterations in large sized problems.

The values of c₁ and c₂ certainly have an important role balancing convergence and coverage. The experimental investigations demonstrate the combination of c₁ = c₂ = 1.6 outperforms better other combinations in small-sized problems, while the combination of c₁ = c₂ = 2.0 is more suitable for medium- and large-sized problems.

The changed-weighted method has the advantage that it gives the algorithm a tendency to show a variable search direction. If the initial and final values of weighting coefficient are adjacent, the population diversity can become too low. According to the experiments, w₁ = 0.9 and w₂ = 0.2 are suitable for different sized problems.

5 Conclusions

In this paper, we consider the sequencing problem for PBAL. We first established the optimal indices of the system including the minimizing the satisfaction ratio of delivery date and minimizing sequencing complexity in a PBAL. Considering the importance difference of two indices as well as the “double-edged sword” characteristic of manufacturing complexity, the stratified scheduling tactics are provided that calculates the optimal solution of the second layer based on the tolerance solution set of the first layer. Then, in order to make better scheduling performance, we proposed a novel PSO scheduler. In the IPSO, the discrete input sequences of products are used as particle position, mutation operators in GA is introduced to simulate collaboration and competition of particle individuals, population decomposition tactics and chaos ideas are introduced to algorithm to further help particle escape from local optima. Therefore, it is also a universal algorithm, and has great potential to address different scheduling problems of hull shipbuilding system. Through the experiments, we found that the proposed discrete PSO scheduler can provide obvious improvements comparing with some classic meta-heuristic methods.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation of China (No. 51275104) and supported in part by the Specialized Research Fund for the Doctoral Program of Higher Education (No. 20132304120021).

References

Mohtashami

, A new hybrid method for buffer sizing and machine allocation in unreliable production and assembly lines with general distribution time-dependent parameters, International Journal of Advanced Manufacturing Technology 74(9-12) (2014), 1577–1593.

Finetto

, Faccio

, Rosati

and Rossi

, Mixed-model sequencing optimization for an automated single-station fully flexible assembly system (F-FAS), International Journal of Advanced Manufacturing Technology 70(5-8) (2014), 797–812.

Ozturk

, Tunali

, Hnich

and Ornek

M.A.

, Balancing and scheduling of flexible mixed model assembly lines, Constraints 18(3) (2013), 434–459.

Al-Anzi

F.S.

and Allahverdi

, A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times, European Journal of Operational Research 182(1) (2007), 80–94.

ElMaraghy

, AlGeddawy

, Samy

S.N.

and Espinoza

, A model for assessing the layout structural complexity of manufacturing systems, Journal of Manufacturing Systems 33(1) (2014), 51–64.

Kennedy

and Eberhart

, Particle swarm optimization, IEEE International conference on Neural Networks-conferenceProceedings 4 (1995), 1942–1948.

Tong

K.N.

, Xu

K.L.

and Zheng

Y.Q.

, Sequencing mixed-model flexible assembly lines with variable launching intervals, J Shanghai Jiaotong Univ (Sci) 18(4) (2013), 460–467.

Vincent

L.W.H.

, Ponnambalam

S.G.

and Kannagaraj

, Differential evolution variants of schedule flexible assembly lines, Journal of Intelligent Manufacturing 25(4) (2014), 739–753.

Aghajani

, Ghodsi

and Javadi

, Balancing of robotic mixed-model two-sided assembly line with robot setup times, International Journal of Advanced Manufacturing Technology 74(5-8) (2014), 1005–1016.

10.

Salehi

, Fattahi

, Roshani

and Zahiri

, Multi-criteria sequencing problem in mixed-model synchronous assembly lines, International Journal of Advanced Manufacturing Technology 67(1-4) (2013), 983–993.

11.

Boysen

, Fliedner

and Scholl

, Sequencing mixed-model assembly lines: Survey, classification and model critique, European Journal of Operational Research 192(2) (2009), 349–373.

12.

Hamta

, Ghomi

S.M.T.F.

, Jolai

and Shirazi

M.A.

, A hybrid PSO algorithm for a multi-objective assembly line balancing problem with flexible operation times, sequence-dependent setup times and learning effect, International Journal of Production Economics 141(1) (2013), 99–111.

13.

Manavizadeh

, Tavakoli

, Rabbani

and Jolai

, A multi-objective mixed-model assembly line sequencing problem in order to minimize total costs in a Make-To-Order environment, considering order priority, Journal of Manufacturing System 32(1) (2013), 124–137.

14.

Papakostas

and Mourtzis

, An approach for adaptability modeling in manufacturing analysis using chaotic dynamics, CIRP Annals-Manufacturing Technology 56(1) (2007), 491–494.

15.

Kuzgnumkaya

and EIMaraghy

H.A.

, Assessing the structural complexity of manufacturing systems configurations, International Journal of Flexible Manufacturing System 18(2) (2006), 145–171.

16.

Chutima

and Chimklai

, Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimization with negative knowledge, Computers and Industrial Engineering 62(1) (2012), 39–55.

17.

Chutima

and Naruemitwong

, A Pareto biogeography-based optimization for multi-objective two-sided assembly line sequencing problems with a learning effect, Computers and Industrial Engineering 69(1) (2014), 89–104.

18.

Mansouri

S.A.

, A Multi-Objective Genetic Algorithm for mixed-model sequencing on JIT assembly lines, European Journal of Operational Research 167(3) (2005), 696–716.

19.

S.J.

, Ko

, Weyand

, ElMaraghy

H.A.

, Lien

T.K.

, Koren

, Bley

, Chryssolouris

, Nasr

and Shpitalni

, Assembly system design and operations for product variety, CIRP Annals-Manufacturing Technology 60(2) (2011), 715–733.

20.

Samy

S.N.

and EIMaraghy

, A model for measuring complexity of automated and hybrid assembly systems, International Journal of Advanced Manufacturing Technology 62(5-8) (2012), 813–833.

21.

Al-Hawari

, Ali

, Al-Araidah

and Mumani

, Development of a genetic algorithm for multi-objective assembly line balancing using multiple assignment approach, International Journal of Advanced Manufacturing Technology 77(5-8) (2015), 1419–1432.

22.

Liu

W.Q.

, Liu

, Zhang

C.Y.

and Shao

X.Y.

, Hybrid particle swarm optimization for multi-objective sequencing problem in mixed model assembly lines, Computer Integrated Manufacturing Systems 17(12) (2011)2591–2598 (in Chinese)

23.

Tian

, Liu

D.Y.

, Yuan

D.H.

and Wang

K.H.

, A discrete PSO for two-stage assembly scheduling problem, International Journal of Advanced Manufacturing Technology 66(1-4) (2013), 481–499.