A sequencing approach of models in mixed-model assembly lines/Laipsnisko priartejimo modelis naudojimas misraus tipo surinkimo linijose.

Yongqian, Zheng ; Yunpeng, Wang ; Bo, Hu 等

1. Introduction

Manufacturers nowadays are increasingly facing the challenge of providing a rich product variety at very low cost. This typically requires the implementation of cost efficient, flexible production systems [1, 2]. Often, so called mixed-model assembly lines are employed. However, the diversity of mixed-model lines makes a thorough sequence planning essential for exploiting the benefits of assembly line production [3 - 5]. To sequence mixed-models in assembly lines some criteria have been considered in the literature [6, 7], two main sequencing objectives are the Just-In-Time(which pursues the constant rate of part usage) and the leveling of work load. The criterion of minimizing work overload is more meaningful for some small-medium manufacturing companies.

The impacts of idle time and over time on the production costs are different in actual production,, so it is necessary to figure them separately. The company can estimate the production costs of waste on the assembly line accurately by the introduction of the cost factors. Our approaches are focused on the sequences of mixed-model assembly line that affect this aspect. Accordingly a sequence planning approach based on PSO is devised, and an immune mechanism is introduced into it. According to antibody affinity and concentration calculation, replace the particles timely in order to maintain the population diversity and prevent premature convergence and particles into local extreme. Finally, the algorithm is proved to be effective and superior through simulation examples. Although our study is inspired by a single real-world case, the underlying problem setting is highly relevant in practice.

2. Problem definition

A traditional assembly line consists of multiple stations arranged along some kind of transportation systems [8]. As shown in Fig. 1, the station in this paper is considered as a time-service window, where time is the length of the station. If the worker can not return to the left-hand border before the next workpiece has arrived, this finally results to a work overload whenever the operations of a workpiece can not be finished within the station's boundaries, and the operation time by other workers out of the line can be called overtime. On the other hand, if the next workpiece hasn't arrived after the worker return to the left-hand border, the time for the worker to wait for the workpiece can be called idletime.

In the proposed sequencing model we assume: The planning horizon is divided into R production cycles (with r = 1, 2, 3, ..., R) in a and for each model m [member of] M the demand dm at the end of the planning horizon is given and has to be met. It follows that the sum over model demands is equal to the number of production cycles available

[FIGURE 1 OMITTED]

The assignment decision is represented by binary variables [x.sub.mr] [member of] {0,1},[for all] m [member of] M, r = 1,2,..., R, which indicate whether a copy of model is m is produced in cycle r. According to the definition of idletime and overtime on the assembly line, the sequencing model of minimizing total idletime and overtime cost can be described as follow

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

s.t. [s.sub.k,r+1] [greater than or equal to] [s.sub.kr] + [summation over m [member of] M] [t.sub.mk] [x.sub.mr] - C + [idlet.sub.kr] (2)

[s.sub.kr] + [summation over m [member of] M] [t.sub.mk] [x.sub.mr] - [overt.sub.kr] [less than or equal to] [l.sub.k] (3)

[x.sub.mr] [member of] {0,1}, [for all] m [member of] M, r = 1,2,...R (4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

[s.sub.kt] [greater than or equal to] 0, [s.sub.kl] = 0 (6)

The objective function (1) minimizes the total cost on the line, and the [idlet.sub.kr] and [overt.sub.kr] indicate the idletime and overtime of the product r on the station k. [alpha] and [beta] are the cost trade-off parameters, which can be used to adjust the impact from different time cost, satisfied that [alpha] + [beta] = 1. The constraints (2) guarantee that processing of a model copy in cycle r + 1 by station k can not start before this station has completed the preceding unit in cycle r. Work is restricted to the stations' borders by constraints (3). Constraints (4) and (5) ensure that there must be a definite product in each sequence position, the total quantity demand of the product must be met. Some parameters are initialized in constraints (6).

3. The immunity particle swarm optimization algorithm

The original PSO maintains a population of particles, let M be the size of swarm. For each particle i, its status can be shown as follow

Position: [x.sup.t.sub.i] = [([x.sup.t.sub.i1], [x.sup.t.sub.i2],..., [v.sub.id]).sup.T]

Velocity: [v.sup.t.sub.i] = [([v.sub.i1], [v.sub.i2],..., [v.sub.id]).sup.T]

Individual best position: [p.sup.t.sub.i = [([p.sup.t.sub.i1], [p.sup.t.sub.i2],..., [p.sup.t.sub.iD).sup.T]

Group best position: [p.sup.t.sub.g] = [([p.sup.t.sub.g1], [p.sup.t.sub.g2],..., [p.sup.t.sub.gD]).sup.T]

So the position [x.sub.i] on t+1 can be updated in the following manner

[v.sup.t+1.sub.id] = [omega] [v.sup.t.sub.id] + [c.sub.1][r.sub.1]( [p.sup.t.sub.id] - [x.sup.t.sub.id]) + [c.sub.2][r.sub.2] ([p.sup.t.sub.gd] - [x.sup.t.sub.id]) (7)

[x.sup.t+1.sub.id] = [x.sup.t.sub.id] + [v.sup.t+1.sub.id] (8)

The inertia weight [omega] is employed to control the impact of the previous history of velocities on the current velocity, thus to influence the trade-off between global and local exploration abilities of the particles. [r.sub.1], [r.sub.2] represent uniform random numbers between 0 and 1. [c.sub.1], [c.sub.2] are two positive constants, called the cognitive and social parameter, respectively. PSO algorithm is easily to be applied, and have the features of fast convergence, but it's also easily trapped into local extreme point at the same time. The search accuracy is not high, and the convergence will become slower at the time of late evolution. A new algorithm is applied based on the original particle swarm optimization algorithm, the information processing framework in the immune system is used to improve the performance of the algorithm when the particle may be premature convergence in local optimum too early, which will be applied to solve the mixed-model assembly line sequencing problem.

In the biological immune system, antibodies produced by the lymphocytes to recognize and resist the attack of various antigens. Feasible solution of target problem can be seen as the antibodies in the immune system, and the antigen will be the optimal solution. Affinity is used to indicate the level of similarity between antibody and antigen, described as follow

Affinity([x.sub.i]) = 1/1 + f (9)

f in formula (9) is the objective function value. The smaller f is the higher level of antibody affinity in solving the minimization problem, which also shows that the particle is nearer away from the optimal particle.

In order to distinguish the level of difference between two antibodies, the degree of similarity needs to be computed, which can be indicted by the different fitness function value between antibodies. The similarity between [x.sub.i] and [x.sub.j] that expressed as g([x.sub.i], [x.sub.j]) can be defined as formula (10)

g ([x.sub.i],[x.sub.j]) = abs (fitness([x.sub.i]) - fitness([x.sub.j])) (10)

The antibody concentration is an important indicator of the measure of antibody diversity [9]. The concentration of antibody i have relations with the similarity between antibody i and other antibodies in the system [10]. The threshold value of the similarity is expressed as Distance, so the concentration of antibody i can be figured as the ration of the antibody number between the antibodies whose similarity are smaller than that of antibodies i and total antibodies. As the number of total antibodies is N, so the concentration of antibody i can be figured as formula (11)

D([x.sub.i]) = count ([N.summation over j=1] g([x.sub.i],[x.sub.j]) [less than or equal to] Distance) / N (11)

In the immune system, the high concentration of low-affinity antibodies should be suppressed, while low concentrations of high-affinity antibodies should be promoted. To ensure the effectiveness and diversity of antibodies, part of the antibodies with high concentration and low-affinity should be eliminated, and the corresponding number of new antibodies will be produced to replace randomly. Selection probability will be decided by both the concentration and affinity

[P.sub.g]([x.sub.i]) = 1 - affinity ([x.sub.i]) / [N.summationover i=1] affinity([x.sub.i]) (12)

[P.sub.d]([x.sub.i]) = D([x.sub.i]) / [N.summationover i=1] D([x.sub.i]) (13)

[P.sub.s]([x.sub.i]) = [alpha][P.sub.g]([x.sub.i]) + (1 - [alpha])[P.sub.d]([x.sub.i]) (14)

[P.sub.g] is the selection probability based on affinity, and [P.sub.d] is the selection probability based on concentrations, [alpha] is a random number between 0 and 1. Formula (14) shows that the replacing rate will increase with lower affinity and higher concentration. [P.sub.r] is the pre-set rate of replacing, antibody i will be replaced when [P.sub.s]([x.sub.i]) [greater than or equal to] [P.sub.r], on the other hand, i will be preserved. The method jointed with immune system not only makes antibodies to retain a high degree of individual adaptation, but also maintains the diversity of antibodies, avoids falling into local optimal, improves the ability of global search.

4. The application of immunity particle swarm algorithm in mixed-model assembly sequencing problem

A random number between 0 and 1 is used to code each particle, sequenced by the particle size of each dimension, so we can indicate a corresponding product sequence type according to predefined initial product sequence.

Assume that the product A, B, C three products, ration of 1:2:3 in a product sequence cycle. The dimension is the number of products put into a production cycle, Dim = 6. The initial product sequence is A-B-B-C-C-C, so the way of encoding and decoding can be defined as Table 1.

In Table 1, the value of particle [X.sub.i] is used for particle swarm optimization iterative process, whose location and velocity is updated, while the decoded sequence is used to calculate the corresponding function. The assembly sequencing problem can be converted to a continuous problem with the way of encoding. The method not only show the characteristics that the particle swarm optimization algorithm is easy to implement and fast convergence in solving the problem of continuous function, but also revert to the practical problems to choose the best solution for the function.

The basic optimization process of immunity particle swarm optimization designed in this paper can be shown as follows.

STEP 1: Particle population parameters initialization.

Determine the number of particles popsize and dimension Dim, the max velocity [v.sub.max], the cognitive and social parameter [c.sub.1], [c.sub.2], the start value and end value of inertia weight [[omega].sub.start] and [[omega].sub.end], max number of alternative [T.sub.max]. The threshold value of the similarity distance, and the pre-set rate of replacing [P.sub.r].

STEP 2: Initial particles location xi and velocity vi randomly.

Compute particle fitness, set current location as individual extreme [P.sub.best], set the location of particle with smallest fitness as global extreme [G.sub.best]. Make the number of not optimizing of [G.sub.best] n = 0.

STEP 3: Update particle state.

Update the location and velocity of each particle according to formula (7) and (8). The speed is limited under pre-set range. Update the value of cognitive and social parameter, inertia weight. To improve the algorithm's global search ability and convergence performance, a method of inertia weight update based on the strategy of linear differential decreasing is develop in this paper, shows as formula (15).

d[omega](t) / dt = 2([[omega].sub.start] - [[omega].sub.end]) / [t.sup.2.sub.max] x t (15)

STEP 4: Update individual extreme [P.sub.best] and global extreme [G.sub.best]. Judge whether [G.sub.best] is optimized, Yes, set [G.sub.best] to the particle location, n = 0, otherwise, n = n + 1.

STEP 5: Determine whether it's time to update particles with antibody replacement mechanism. If n = N, immunity process starts, turn to STEP 6, otherwise, turn to STEP 8.

STEP 6: Calculate the affinity and concentration of each particle according to formula (10), (11), determine the selection rate [P.sub.g] based on affinity and selection rate [P.sub.d] based on the concentration.

STEP 7: Replace particles based on immunity mechanism. Determine replace rate of each particle according formula (14), if [P.sub.s]([x.sub.i]) [greater than or equal to] [P.sub.r], replace particles with new particles produced randomly, return to STEP 3.

STEP 8: Judge whether stopping criterion is satisfied. If the current iteration number reaches [T.sub.max], or the satisfied value of the problem is achieved, iteration stops, results output, otherwise, turn to STEP 3.

5. Experimental results

Four similar parts of different products are produced in a mixed-model assembly line in an automobile parts manufacturing plant, distinguished by A, B, C, D. Demand for the four products are 1200, 1200, 1800 and 2400 pieces. Each workstation operation time of product shows in Table 2.

The product cycle time C = 77 min, length of work station L = 80 min. Determine minimum product cycle is {2:2:3:4} according to the rate among the demands of each product. The cost trade-off parameters are designed based on the situation of company, [alpha] = 0.4, [beta] = 0.6 . In the optimization process, maximum number of iterations [T.sub.max] = 500, size of popsize Popsize = 10, the value of cognitive and social parameter [c.sub.1], [c.sub.2] are updated with the strategy of linear adaptive according to the number of iterations, range from 0.5 to 2.5. The stare value of inertia weigh [[omega].sub.start] = 0.9, end value [[omega].sub.end] = 0.4, maximum velocity [v.sub.max] = 5, the threshold value of the similarity Distance = 1, pre-set replacing rate [P.sub.r] = 0.4. In order to illustrate that the optimization algorithm is more efficient and effective in solving mixed-model assembly line sequencing problem, try to solve the problem with immunity PSO, original PSO and traditional heuristic method [9]. Results shown in Table 3 are the mean value after calculating 50 times repeatedly. Compared with other methods, immunity PSO in this paper gets better results, with the lowest total idle-over time cost.

As Fig. 2, the dotted line stands for immunity PSO, while the solid line stands for original PSO. It's seen that both two algorithms showed inherent characteristics of convergence of particle swarm optimization in the early iterations (50 generations ago), but the original PSO presented the phenomenon of prematurity and converges in local optimum too early at 100 generation, and the local optimum wasn't revolted until 500 generation. The immunity PSO in this paper not only inherited the advantages of fast convergence of original PSO, but also jumped out of the local optimum by the immunity information processing adaptive mechanisms at middle of iteration (100-200 generation), which makes better solution than that of original PSO.

[FIGURE 2 OMITTED]

6. Conclusions

Mixed-model assembly line sequencing problem is crucial for the line efficiency. An improved particle swarm optimization algorithm was proposed to solve sequencing problem in order to minimize the total idle-over cost. In order to avoid prematurely trapped in local optimal and the satisfactory solution can not be obtained, original PSO was optimized with the information processing mechanism in immune system. Compute affinity and concentration of each particle and replace in time. Through the analysis of simulation example and comparison with original PSO, the immunity PSO was proved better in avoiding premature convergence and value of objective functions, and it can solve the mixed-model assembly line sequencing problem effectively and quickly.

Acknowledgment

This research is supported by the Shanghai Natural Science Foundation (No.10ZR1431700).

References

[1.] Joaquin Bautista, Jaime Cano. 2008. Minimizing work overload in mixed-model assembly lines [J], Production Economics 112: 177-191

[2.] Song Huaming, Han Yuqi, Yang Hui. 2003. Mixed-model assembly line balancing design [J], China Mechanical Engineering 3(6): 68-73.

[3.] Lin Xian-kun, Li Ai-ping, Chen Bin-sen. 2006. Scheduling optimization of mixed model assembly lines with hybrid particle swarm optimization algorithm, Industrial Engineering and Management, 1K. Elissa, "Title of paper if known," unpublished.

[4.] Gao Ying, Xie Shengli. 2004. Particle swarm optimization algorithms with immunity, Computer Engineering and Applications, 6.

[5.] John Miltenburg. 1989. Level schedules for mixed-model assembly lines in just-in-time production systems, Management Science,

[6.] Nils Boysen, Malte Flidner, Armin Scholl. 2009. Sequencing mixed-model assembly lines: Survey, classification and model critique, European Journal of Operational Research 192.

[7.] Kennedy J, Eberhart R.C. 1995. Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks. Perth, Australia: IEEE Piscataway, 1995: 1942-1948 Australia: IEEE Piscataway, 1995: 1942-1948

[8.] Wei Jianxiang, Sun Yuehong, Su Xinning. 2007. A novel particle swarm optimization based on immune selection, Journal of Nanjing University (Natural Science) 23.

[9.] Zhu Zongqian. 1997. A new optimization method for working sequence of putting into operation of products on multi-assortment mixed-stream production line, Journal of UEST of China 4.

[10.] Shen Huihui, Han Shenglian. 2004. An kind of calculating diversity about the affinity of immune algorithm. Journal of Chongqing Vocational & Technical Institute 10.

[11.] Rat, N.R.; Neagoe, M.; Diaconescu, D.; Stan, S.D. 2011. Dynamic simulations regarding the influence of the load-rigidity correlation on the working accuracy of a medical triglide parallel robot, Mechanika 17(2): 178182.

Received March 31, 2011

Accepted August 22, 2011

Zheng Yongqian, Tongji University, Siping Rd 1239, 200092 Shanghai, China, E-mail: xiyuanxy@yahoo.com.cn

Wang Yunpeng, Tongji University, Siping Rd 1239, 200092 Shanghai, China, E-mail: wyp227@126.com

Hu Bo, Tongji University, Siping Rd 1239, 200092 Shanghai, China, E-mail: hbmail612@yahoo.com.cn

Wang Yongsheng, Tongji University, Siping Rd 1239, 200092 Shanghai, China, E-mail: wysbest@126.com

Table 1
Encoding and decoding of particles

Particle Xi         0.72    0.03    0.19    0.75    0.14    0.12

InitialSequence     1(A)    2(B)    3(B)    4(C)    5(C)    6(C)
Sorting             5       1       4       6       3       2
DecodingSequence    C       A       C       C       B       B

Table 2
Product time

Product            Work station number
 number    1     2     3      4      5      6

   A       50    65    120    70     86     0
   B       70    80    75     40     113    41
   C       100   97    0      135    0      72
   D       95    55    90     34     91     135

Table 3
Simulation results

   Methods        Sequencing       Objective
                                 function value

Immunity PSO      DBDCACACDBD    922.8
Original PSO      ACDBDBDCDCA    927.9
Reciprocal of     DCDABCDABCD    938.8
product ratio