is the number of machine type m purchased in period t.Abstract：To decrease the impact of shorter product life cycles, dynamic cell formation problems (CFPs) and cell layout problems (CLPs) were simultaneously optimized. First, CFPs and CLPs were formally described. Due to the changes of product demands and the limit of machine capacity, the existing layout needed to be rearranged to a high degree. Secondly, a mathematical model was established for the objective function of minimizing the total costs. Thirdly, a novel dynamic multi-swarm particle swarm optimization (DMS-PSO) algorithm based on the communication learning strategy (CLS) was developed. To avoid falling into local optimum and slow convergence, each swarm shared their optimal locations before regrouping. Finally, simulation experiments were conducted under different conditions. Numerical results indicate that the proposed algorithm has better stability and it converges faster than other existing algorithms.
Key words：dynamic cellular manufacturing system; cell formation and layout; communication learning strategy; dynamic multi-swarm particle swarm optimization algorithm
As one of the first applications of group technology (GT) to factory reconfiguration and shop floor layout design, cellular manufacturing systems (CMSs) are conducive to reducing material handling cost, set-up time, manufacturing lead time, tooling cost, work in process, lot sizes, throughput times, labor cost and production equipment cost. CMSs can also enhance manufacturing capability, workers’ satisfactions and flexibility along with many other advantages[1]. A study demonstrated that a suitable layout can reduce 10% to 30% of the manufacturing cost[2].
Cell formation (CF) and cell layout (CL) (including intra-cell machine layout and inter-cell layout) are two basic and important steps in the design of CMSs. Over the past decades, many researchers have predominantly focused on solving the static CFPs, the first stage in CMSs. Also, many analytical methods have been developed as a result of this massive movement. Bhandwale and Kesavadas[3] presented a new methodology to incorporate new parts and machines into existing cellular manufacturing. Nouri et al.[4] introduced a newly developed bacteria foraging algorithm based on operation sequences to solve CFPs. Ameli and Arkat[5] developed a pure linear integer program to solve CFPs in consideration of alternative process routings and machine reliability. Mahdavi et al.[6] solved the CFPs and minimized the number of voids and exceptional elements in a three dimensional machine-part-worker incidence matrix.
However, with shorter product life cycles in the competitive market, upcoming products are often ignored, which imposes subsequent unplanned changes onto the CMS of production disruptions and unexpected costs. Hence, product life cycle changes should be incorporated in the design of cells. This type of model is called the dynamic cellular manufacturing system (DCMS)[7]. Tavakkoli-Moghaddam et al.[8] developed a genetic algorithm (GA), simulated annealing (SA) and tabu search to solve CFPs under a dynamic condition. Ossama et al.[9] introduced a novel reconfiguration planning heuristic to group the parts into families.
Bagheri and Bashiri[10] developed a hybrid genetic and imperialist competitive algorithm for CFPs with dynamic uncertain demands and verified its efficiency by comparing with GA. Kia et al.[11] adopted a pure SA to simultaneously solve CFPs and CLPs in consideration of alternative routings and machine capacity. It is illuminating to propose a multi-rows layout strategy by assuming that the shape of cells is flexible, since such a strategy can increase the diversity and practical significance of the layout. However, as the feasible solution space of SA is easily influenced by its initial solution, the algorithm is of slow convergence and easily trapped into a local optimum. Izadinia et al.[12] first applied CLPs in multi-floor factory and developed a mixed integer programming robust model to solve the multi-floor layout problem. Mahdavi et al.13] presented a new integrated mathematical model considering cell formation and cell layout simultaneously. Wu et al.[14] proposed a hierarchical genetic algorithm (HGA) to solve the integrated cell formation, cell layout and group scheduling problems.
Among the literature mentioned above, most studies, however, have only addressed CFPs and CLPs in a dynamic environment sequentially or independently, despite these two decisions being interrelated and impacting each other. In fact, different cell formation solutions lead to different optimal cell layout solutions. Dealing with CFPs and CLPs sequentially or independently is unable to go through every feasible solution in the solution space, but solving CFPs and CLPs in an integrated way can overcome this issue. In this paper, an integrated CFPs and CLPs model is established in consideration of the variation of cell numbers and machine reliability. Subsequently, a dynamic multi-swarm particle swarm optimization algorithm based on the communication learning strategy (DMS-PSO-CLS) is proposed to solve the model.
Consider a dynamic cellular manufacturing system which produces N kinds of products using M different types of machines. Machines are located in a linear arrangement within cells, while cells themselves are located in some predetermined compulsory places in permutation and combination. Each part type has a number of operations and is processed based on its operation sequence. Each operation of a part type can be performed on different machine types with different processing times. A suitable sequence of machines within cells helps to shorten the total intracellular part movement distances and a proper cell choice for a machine group assignment can reduce the inter-cell movements.
The goal of this paper is to select machines for each operation of parts and to assign shares of demands of parts to the machines, which are arranged into locations and cells. The objective function is to minimize the total costs of intra-cell and inter-cell material handling, machine relocation, new machine purchase, machine overhead, machine processing, cell formation and machine breakdown.
The problem is formulated under the following assumptions:
1) The demand of each part type in each period is known.
2) Each machine type has identical duplicates for satisfying capacity requirements, and some machines can be purchased.
3) When a machine changes its location, the machine transferring cost includes uninstallation cost and installation cost, which are numerically equal.
4) Machine reliability follows an exponential distribution with a known failure rate.
5) The shape of cells can be flexibly configured. All machine types have the same dimensions and are placed in the locations with the same dimensions. A multi-row layout of facilities with equivalent areas is considered in the CMS. The distance between any two locations is known in advance.
6) The number of cells to be formed is variable with an upper limit. And the maximum and minimum of the cell size are predetermined.
p={1,2,…,P} is the index set of part types; k={1,2,…,kp} is the index set of operation indices for part type p; m={1,2,…,M} is the index set of machine types; c, c′={1,2,…,C} is the index set of cells; l, l′={1,2,…,L} is the index set of locations; and t={1,2,…T} is the index set of time periods. Dpt is the demand for part type p in period t. Tm denotes the capacity of one unit of machine type m. A1 and A2 are the inter-cell and intra-cell material handling cost per part type p pert unit of distance. αm,βm,γm,δm and μm are the overhead cost in each period, processing cost for each unit time, purchasing cost, transferring and repair cost for machine type m, respectively. hkpm is the processing time of operation k on machine m per part p. dl,l′ denotes the distance between location l and location l′. λm is the breakdown rate for machine m. BU and BL are the upper bound and lower bounds of the cell size.
Xkpmlt denotes the number of part type p processed by operation k on machine type m in location l in period t. Wmlct=1 if one unit of machine type m is located in location l and assigned to cell c in period t, otherwise 0. Ykpmlm′l′t means the number of part type p processed by operation k on machine type m located in l and moved to the machine type m′ which is located in l′ in period t. is the number of machine type m purchased in period t.
Material handling costs represent inter-cell and intra-cell material handling costs. An inter-cell part trip occurs, only when two consecutive operations of the same part need to be processed in more than one cell. An intra-cell part trip occurs when two consecutive operations of one part are allocated to the same cell, but to different machines. For different cell formation, the optimal layout is different. The material handling cost equation is described as follows:
Cmaterial=
(1)
To adapt to the change of demand in different periods, machines may have to be relocated for minimizing the total costs which leads to the machine relocation cost. The machine relocation cost equation is described as follows:
(2)
As the capacity of each machine is limited, more machines may have to be purchased for meeting increased demands of parts in the coming period. The machine purchasing cost equation is described as follows:
(3)
Costs caused by consuming power and labor resource should be counted in when the parts are processing. The machine overhead cost equation is described as follows:
(4)
Machine processing cost increases with the increase of processing time. The machine processing cost equation is described as follows:
(5)
The cell formation cost equation is described as follows:
(6)
In many existing publications, it is assumed that machines are reliable and can process parts without any breakdown. However, this assumption is not realistic in the modern manufacturing environment. In this paper, machine reliability is assumed to follow an exponential distribution with a known failure rate λ. Therefore, the machine reliability is r=exp(-λt) and the mean time between failures is tf=1/λ. The machine breakdown cost equation is described as follows:
(7)
Therefore, the objective of the model is as follows:
min C= Cmaterial+Crelocation+Cnew+Coverhead+Cprocess+
Ccell+Cfailure
(8)
The demand satisfaction constraint for all the part equations is described as follows:
∀p∈P,∀k∈K,∀t∈T
(9)
The total capacity of machines is no less than the total production time of parts. The total capacity constraint is described as follows:
∀m∈M,∀l∈L,∀t∈T
(10)
The number of total locations is no less than the number of total machines. The constraint is described as follows:
∀t∈T
(11)
The number of machines assigned to cells meets the requirement of the cell size. The constraint is described as follows:
∀c∈C,∀t∈T
(12)
Material flow conservation equations are described as follows:
∀k∈Kp,∀p∈P,∀m∈M,∀t∈T
(13)
∀k∈Kp,∀p∈P,∀m∈M,∀t∈T
(14)
The number of machine type m in the current period is equal to the number of the same type in the previous period plus the number of new machines of the same type purchased at the beginning of the current period. The detailed equation is described as follows:
∀m∈M,∀t∈T
(15)
King and Nakornchai[15] proved that solving the static integrated CFPs and CLPs model is an NP-hard problem. It should be noted that considering CFPs and CLPs in a dynamic environment does increase the complexity of the problem, and may consequently make the exact optimization methods become very difficult and sometimes impossible. Therefore, a novel DMS-PSO-CLS is proposed to solve the dynamic CFPs and CLPs.
In this paper, the code consists of two sections in each period.
The first section consists of P ingredients, as shown in Fig.1. The code of each ingredient represents the assignment of operations and demand quantity of each part for the utilized duplicates of each machine type. Suppose that the operations of part type i can be processed by ni1,ni2,…,niKpi types of machines respectively, and then the length of ingredient i is 
nij. The components of this section are all real numbers randomly generated from 0 to 1, and 
Mijk=1 ∀i∈P,∀j∈Kpi should be guaranteed. When encoding the first section, we should consider constraints (9) and (10).
Fig.1 Code used to select machines for operations of parts and to distribute capacity of machines
Based on the first section, the number of each machine type required to meet production capacity can be figured out. The second section, as shown in Fig.2, is related to the assignment of machines to locations and to cells. It consists of two pats. The lengths of both parts are equal to the number of machines. All the components are also real numbers generated from 0 to 1. When the code of the first layer is completed, we sort l11,l12,…, l1m1,…, lMmM which are codes for machines in a descending order, and based on the sort, corresponding machines are assigned to locations in sequence. In the second part of the second section, suppose that C cells can be chosen, and interval [0 1] will be averagely divided into C parts. If 
<Cmi<
, machine i will be selected into cell Ci+1. After finishing the second layer, the total number of machines in each cell 
Wmlct can be calculated, and this part should be returned for encoding until constraint (12) is satisfied.
Fig.2 Code used to arrange machine into locations and cells
The diversified initial solutions are randomly generated under corresponding constraints. The steps are described as follows:
Step 1 Initialize parameters. Set N as the population size and T as the total time period. Set n=1.
Step 2 Initialize period t=1.
Step 3 Generate the first ingredient code which consists of real numbers randomly generated from 0 to 1 according to the proposed coding rules, and make sure that 
Mijk=1.
Step 4 Compute the number of each machine type according to the first code and finish the second part code.
Step 5 If t<T, set t=t+1, and return to Step 3. Otherwise, an initial solution is generated by merging the T codes together based on its order.
Step 6 If n<N, set n=n+1, and return to Step 2. Otherwise, N initial solutions have been completed.
Although dynamic multi-swarm particle swarm optimization (DMS-PSO) can find the globally optimum solutions of problems more efficiently compared with PSO, there still remain some drawbacks. In DMS-PSO, as information among different sub-swarms cannot be exchanged until the population is regrouped, even after the globally optimal region is found, the particles will not converge rapidly to the globally optimal solution, leading to a long search time. Aiming to address this drawback, a communication learning strategy is integrated into the DMS-PSO, which is used to exchange information among different sub-swarms before the regrouping operation. In this strategy, for each sub-swarm, each dimension of the two worst particles learns from the better particle of two randomly selected sum-swarms using the tournament selection strategy. In the following parts, the steps of the intact improved PSO algorithm are introduced.
Step 1 Initialize particle swarm parameters. Set T as the total generation and H as the sub-generation in each sub-swarm required to update.
Step 2 Divide all the particles into n sub-swarms. Set h=1.
Step 3 Update the position and velocity of each particle according to its historical best location pbest and the best location achieved so far from its group lbest.
Step 4 If h< H, set h=h+1, and return Step 3. Otherwise, update all the particle swarms by executing Step 5 to Step 8.
Step 5 For each sub-swarm, we sort the fitness values of the particles and select the two worst particles to be updated.
Step 6 Select two sub-swarms randomly out of the whole groups which include the sub-swarm where the particle to be updated stays.
Step 7 Compare the fitness values of the two sub-swarms’ lbest and select the better one.
Step 8 Use the winner’s lbest as the exemplar to learn from for the corresponding dimension of the particle to be updated.
Step 9 If t<0.9T, set t=t+1, and return to Step 2. Otherwise, update all the particles based on their historical best locations and the whole group’s optimum location gbest by regarding all the sub-swarms as a whole group, then set t=t+1.
Step 10 If t<T, return Step 9, and set t=t+1; otherwise, end.
To validate the model and evaluate the performance of the proposed improved PSO, a benchmark example from the literature is solved. The numerical example is taken from Ref.[11], which consists of four part types, five machine types and two periods. Each part type is assumed to have three operations that must be processed in
sequence. Each operation can be processed on two alternative machines. The capacity of all machines is assumed to be equal to 500 h per period. Intra and inter-cell material handling costs per each part type are 5 and 50, respectively. The distance between any two locations can be found in Tab.1. Detailed information about machines and parts are depicted in Tab.2. The mean time between two consecutive failures of these five machine types is 600, 400, 350, 350 and 400, respectively. The cost for failure is 750, 800, 600, 750 and 850, respectively. The proposed algorithm is coded in MATLAB R2012a and solved using a PC with 2.67 GHz Intel Core processor and 2 GB of RAM.
Tab.1 Distances between different locations
LL1L2L3L4L5L6L7L8L9L10L10121232343L21012123234L32103214325L41230121232L52121012123L63212103214L72341230121L83232121012L94323212103L103452341230
Tab.2 Part-machine information
MachinenumberTmδmγmαmβmP1P2P3P4123123123123M150090018000180090.760.650.390.460.490.83M250075015000150070.790.990.330.74M350090018000180050.730.930.440.570.45M450085017000170090.460.800.14M550065013000130080.540.650.480.670.62Dpt2007003000500250700300
In this section, the SA proposed by Kia et al.[11], the standard PSO and the DMS-PSO-CLS proposed in this paper are used to solve the numerical example mentioned more than 100 times. The ranges of the optimum solutions obtained by the three algorithms when the number of cells is two are depicted in Fig.3.
Fig.3 Ranges of optimum solutions for DMS-PSO-CLS, PSO and SA
As seen from Fig.3, the overall solution obtained by the DMS-PSO-CLS is better than that of standard PSO. Although sometimes the quality of the optimum solution from SA is good enough, SA has a wide fluctuation. This means that the stability of SA is worse than that of the DMS-PSO-CLS. This can be explained by the fact that, when the feasible solution space of the problem is continuous, the update mode of SA cannot guarantee that the SA can travel over its every feasible solution, neither can the problem when it is discrete. Influenced by its initial solution, the neighbored solution generated according to the update mode is limited, and only in some occasional condition, the optimum solution obtained by the SA is as good as that obtained by the DMS-PSO-CLS.
Fig.4 shows that the time consumed by the DMS-PSO-CLS for finding the optimum solution is less than that by the PSO and SA. The communication learning strategy of the DMS-PSO-CLS, which is an improved form of the PSO, enhances the ability for searching for the global optimum solution and accelerates its convergence speed.
Fig.4 Running times of DMS-PSO-CLS, PSO and SA
Under constraint (2), the maximum number of cells to be formed is 5. In this part, the above three algorithms are used to solve the numerical example 10 times under different numbers of cells. The mean values of 10 optimum solutions are shown in Fig.5.
Fig.5 Optimum cost for DMS-PSO-CLS, PSO and SA under different numbers of cells
It is shown that the three algorithms acquire the best solution when the number of cells is 3. We may explain the phenomenon with the fact that when the number of cells is large, as the number of total machines is fixed, a cell will have fewer machines, which will lead to more inter-cell material handling cost when processing starts; and when the number of cells is small, more machines are arranged to a cell, due to the limit of physical space, the distance between machines increases, which will lead to more intra-cell material handling cost. Hence, a balanced number of cells will be employed for minimizing the total cost.
In order to analyze the influence of machine breakdown, the numerical example is solved under different machine breakdown rates.
As seen from Fig.6, with the decrease in the machine breakdown rate, the cost for cell formation and layout decreases. However, when the mean time between two consecutive failures is less than 1×tf, the total reduced cost is not strictly equal to the reduced machine breakdown cost. The results may be explained that when tf increases, more machines can be selected when processing parts, and the extra selection may increase the material handling cost, but also decrease the machine breakdown cost, which leads to a reduction of the total cost as a whole.
Fig.6 Optimum cost for DMS-PSO-CLS under different machine breakdown rates
In order to solve dynamic CFPs and CLPs with consideration of the number variation of cells and machine breakdowns, a DMS-PSO-CLS was proposed. The results of numerical examples demonstrate that the improved PSO can find good solutions in a reasonable time, showing good adaptation. Compared with other algorithms solving the same problem, the DMS-PSO-CLS consumes less time and shows better stability. With the communication learning strategy, the improved algorithm can effectively avoid stepping into the local optimum and slow convergence trap. Therefore, the DMS-PSO-CLS is feasible and effective. In the future, dynamic CFPs and CLPs with uncertain demands should be further discussed.
References
[1]Hearago S S. Group technology and cellular manufacturing [J]. IEEE Transactions on Systems, Man and Cybernetic, 1994, 24(2): 203-215. DOI:10.1109/21.281420.
[2]Tompkins J A, White J A, Bozer Y A, et al. Facilities planning [M]. 2nd ed. New York: John Wiley, 1996.
[3]Bhandwale A, Kesavadas T. A methodology to incorporate product mix variations in cellular manufacturing[J]. Journal of Intelligent Manufacturing, 2008, 19(1):71-85. DOI:10.1007/s10845-007-0046-4.
[4]Nouri H, Tang S H, Hang Tuah B T, et al. BASE: A bacteria foraging algorithm for cell formation with sequence data[J]. Journal of Manufacturing Systems, 2010, 29(2):102-110. DOI:10.1016/j.jmsy.2010.11.004.
[5]Ameli M S J, Arkat J. Cell formation with alternative process routings and machine reliability consideration[J]. The International Journal of Advanced Manufacturing Technology, 2008, 35(7/8):761-768. DOI:10.1007/s00170-006-0753-6.
[6]Mahdavi I, Aalaei A, Paydar M M, et al. A new mathematical model for integrating all incidence matrices in multi-dimensional cellular manufacturing system[J]. Journal of Manufacturing Systems, 2012, 31(2):214-223. DOI:10.1016/j.jmsy.2011.07.007.
[7]Kia R, Shirazi H, Javadian N, et al. A multi-objective model for designing a group layout of a dynamic cellular manufacturing system[J]. Journal of Industrial Engineering International, 2013, 9(1):1-14. DOI:10.1186/2251-712x-9-8.
[8]Tavakkoli-Moghaddam R, Aryanezhad M B, Safaei N, et al. Solving a dynamic cell formation problem using metaheuristics[J]. Applied Mathematics and Computation, 2005, 170(2):761-780. DOI:10.1016/j.amc.2004.12.021.
[9]Ossama M, Youssef A M A, Shalaby M A. A multi-period cell formation model for reconfigurable manufacturing systems [J]. Procedia CIRP, 2014, 17:130-135. DOI:10.1016/j.procir.2014.01.120.
[10]Bagheri M, Bashiri M. A hybrid genetic and imperialist competitive algorithm approach to dynamic cellular manufacturing system [J]. Proc IMechE Part B: Jounal of Engineering Manufacture, 2014, 228(3):458-470. DOI:10.1177/0954405413500662.
[11]Kia R, Baboli A, Javadian N, et al. Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings, lot splitting and flexible reconfiguration by simulated annealing[J]. Computers and Operations Research, 2012, 39(11):2642-2658. DOI:10.1016/j.cor.2012.01.012.
[12]Izadinia N, Eshghi K, Salmani M H. A robust model for multi-floor layout problem[J]. Computers and Industrial Engineering, 2014, 78:127-134. DOI:10.1016/j.cie.2014.09.023.
[13]Mahdavi I, Teymourian E, Baher N T, et al. An integrated model for solving cell formation and cell layout problem simultaneously considering new situations[J]. Journal of Manufacturing Systems, 2013, 32(4):655-663. DOI:10.1016/j.jmsy.2013.02.003.
[14]Wu X, Chu C H, Wang Y, et al. Genetic algorithms for integrating cell formation with machine layout and scheduling[J]. Computers and Industrial Engineering, 2007, 53(2):277-289. DOI:10.1016/j.cie.2007.06.021.
[15]King J R, Nakornchai V. Machine-component group formation in group technology: Review and extension [J]. International Journal of Production Research, 1982, 20(2):117-133 DOI:10.1080/00207548208947754.
摘要：为了降低产品生命周期缩短对生产系统的影响,对动态单元构建与布局问题同时进行了优化．首先介绍了单元构建与布局问题,考虑到不同阶段的产品需求变化及机器产能限制,适当地将单元进行重新布置．然后,以最小化物料搬运费用为目标函数,建立了数学规划模型．其次,提出了基于沟通学习策略的动态多种群粒子群算法,使各种群粒子重组之前以规定策略进行位置共享,避免陷入局部最优和收敛较慢的困境．最后,在不同条件下进行了仿真对比实验,结果表明,所提出的算法具有更好的收敛稳定性以及更快的收敛速度．
关键词：动态单元制造系统;单元构建与布局;沟通学习策略;动态多种群粒子群优化算法
中图分类号：TH165
DOI:10.3969/j.issn.1003-7985.2017.04.004
Received 2017-06-19，
Revised 2017-10-09.
Biography：Zhou Binghai(1965—), male, doctor, professor, bhzhou@tongji.edu.cn
Foundation item：The National Natural Science Foundation of China (No.71471135).
Citation：Zhou Binghai, Lu Yubin. Improved PSO for integrating dynamic cell formation and layout problems[J]．Journal of Southeast University (English Edition),2017,33(4):409-415．
DOI:10.3969/j.issn.1003-7985.2017.04.004.