多目标混流装配线再平衡模型与算法#
 

摘要：文章考虑混装线再平衡时的调整成本和生产效率，提出了度量调整成本的新方法，建立了混流装配线再平衡问题的多目标优化模型，并采用多目标遗传算法对该问题进行了求解。通过对经典问题的计算实验，以及与Merengo 等（1999）提出的混装线平衡算法的对比分析，结果表明多目标遗传算法可以有效地求解混装线再平衡问题。
 

关键词：混装线；再平衡；多目标优化；遗传算法

0 引言
近年来，为了满足人们个性化、多样化、定制化的需求，可以同时生产多种型号产品的混流装配线（简称：混装线）逐渐代替了传统的单一型号产品装配线。混流装配模式已广泛应用在汽车、消费电子、白色家电、家居、服装等产业中[1]。为了提高生产效率，降低瓶颈工位对生产速度的制约，在装配线设计阶段，需要在满足产品装配工序间先后顺序、市场需求量以及其它约束的情况下，将任务分配给各工作台，以使各工作台负荷的尽量均衡，即：装配线平衡设计问题。混装线平衡设计对生产效率具有重要影响，是中长期管理的关键决策。随着产品生命周期的不断缩短，为了保持竞争优势，企业不断推出新产品以满足多变的市场 需求。新产品往往需要新的装配工序或需要不同的加工时间，当新产品导入时，原来的平衡方案可能不再有效，混装线需要重新分配任务以保持各工作台负荷均衡，即混装线再平衡问题[2]。
 

从20 世纪60 年代开始，许多学者就对混装线平衡问题进行了大量研究。综观已有研究，大多只考虑混装线设计之初的平衡问题（初次平衡），而对再平衡关注较少[3]。许多研究者都指出再平衡的重要性[2,3,4]，但深入研究该问题的文献还非常少。任务的重新分配将引起人员、工具、在制品存储区域设置、物料配送等多方面的调整，从而造成调整成本。因此，再平衡时不仅要优化再平衡后的生产效率，还需要考虑原平衡方案与新平衡方案之间的协调问题，降低调整成本。实际中，这些调整成本很难直接测量，因此多数研究将再平衡当作任务分配约束条件下的平衡问题，并不考虑调整成本[5,6 ,7]。在目标函数中考虑再平衡成本的研究很少，Corominas 等考察了实际的摩托车装配线，研究了季节性需求导致的再平衡，主要考虑了新增临时工带来的人工成本[8]。该研究还考虑了正式工与临时工在技能熟练度上的差别，以及临时工应与正式工相邻（以获得帮助）的约束。Gamberini 等研究了任务时间随机的单产品装配线再平衡问题，并使用初始平衡与再平衡结果的平均相似度来衡量各项调整所带来的成本[9,10]。
 

本文提出了度量手工混装线调整成本的一种新方法，并在混装线再平衡过程中同时考虑调整成本和新平衡的生产效率。文章的内容安排如下：第一部分建立混装线再平衡的数学模型；第二部分给出了模型的多目标遗传算法思路；第三部分进行了数值分析；第四部分给出了文章的结论。

4 结论
本文对新产品引入导致的混装线再平衡问题进行了探索。在现代制造系统的整个生命周期中，新产品开发频繁，企业通常将新产品引入原有装配线混合生产，导致混装线的再平衡重复出现。再平衡意味着所有任务的重新分配，在手工装配线中，人员的调整和培训费用是再平衡的主要成本。因此，再平衡时不仅要优化再平衡后的生产效率，还需要考虑原平衡方案与新平衡方案之间的协调问题，降低调整成本。文章同时考虑了混装线再平衡的调整成本和新平衡的生产效率，提出了一种新的再平衡成本度量方法，采用调整任务的总作业时间近似反映再平衡成本，并设计了多目标遗传算法对该问题进行求解。通过算例测试分析，表明新的多目标遗传算法在求解过程中，解的质量优于相同目标的Merengo 算法。

[参考文献] (References)
[1] 李斌，陈立平，黄正东，肖人彬，钟毅芳. 面向大规模定制的装配系统优化调度研究[J]. 中国机械工程，2005，16（24）：2198-2202.
[2] Schofield NA. Assembly line balancing and the application of computer techniques[J]. Computers & Industrial
engineering, 1979, 3(1), 53-69.
[3] Boysen N, Fliedner M, Scholl A. A classification of assembly line balancing problems [J]. European Journal of
Operational Research, 2007, 183(2): 674-693.
[4] Falkenauer E. Line balancing in the real world [C]. Proceedings of the International Conference on product
Life cycle Management PLM 05, Lumiere Univeristy of Lyon, France, 2005.
[5] Watkins RE, Cochran JK. A line balancing heuristic case study for existing automated surface mount assembly line setups[J]. Computers and Industrial Engineering, 1995, 29(1): 681-689.
[6] Ramirez-Campos SM, Trevino LMT, Campos MGC, Leza JV. Assembly Line Reconfiguration Under
Disturbances: An Evolutionary Approach to Decision Making [C]. Proceedings of the 15th International
Conference on Computing, 2006.
[7] Miltenburg J. Balancing U-lines in a multiple U-line facility [J]. European Journal of Operational Research, 1998, 109(1): 1-23.
[8] Corominas A, Pastor R, Plans J. Balancing assembly line with skilled and unskilled workers[J]. Omega-The
International Journal of Management Science, 2008, 36(6): 1126-1132.
[9] Gamberini R, Grassi A, Riminia B. A new multiobjective heuristic algorithm for solving the stochastic
assembly line re-balancing problem [J]. International Journal of Production Economics,2006, 102(2): 226-243.
[10] Gebennini R, Grassi A, Regattieri. A multiple single-pass heuristic algorithm solving 315 the stochastic assembly
line rebalancing problem [J]. International Journal of Production Research, 2009, 47(8): 2141-2164.
[11] Decker M. Capacity smoothing and sequencing for mixed-model lines [J]. International Journal of Production
Economics, 1993, 30-31: 31-42.
[12] Domschke W, Klein R, Scholl A. Antizipative Leistungsabstimmung bei moderner Variantenflieb fertigung [J].Zeitschrift fur Betriebswirtschaft, 1996, 66:1465-1490.
[13] Merengo C, Nava F, Pozetti A. Balancing and sequencing manual mixed-model assembly lines [J].
International Journal of Production Research, 1999, 37: 2835-2860.
[14] Srinivas N, Deb K. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms[J].
Journal of Evolutionary Computation, 1994, 2:221-248.
[15] Konak A, Coit DW, Smith AE. Multi-objective optimization using genetic algorithms: A tutorial[J].
Reliability Engineering && System Safety, 2006, 91:992-1007.
[16] Murata T, Ishibuchi H, Tanaka H. Multi-Objective Genetic Algorithm and Its Applications to Flowshop
Scheduling[J]. Computers and Industrial Engineering, 1996, 30(4): 957-968.
[17] Ponnambalam SG, Aravindan P, Naidu GM. A Multi-Objective Genetic Algorithm for Solving assembly line Balancing Problem[J]. The International Journal of Advanced Manufacturing Technology, 2000, 16:341-352.
[18] Davis E. Applying adaptive algorithms to domains[C]. In Proceedings of the international joint conference on
artificial intelligence, 1985, 162-164.
[19] Moscato P, Norman M. A mimetic approach for the traveling salesman problem: Implementation of a
computational ecology for combinatorial optimization on message-passing systems[C]. In Proceedings of the international conference on parallel computing and transputer applications, Amsterdam, 1992.