基于多目标优化的汽车混合流水线平衡方法研究

曹守启，朱雅雯

（上海海洋大学 工程学院，上海 201306）

0 引言

自从1913年福特公司开发出了世界上第一条流水线起，流水线作业逐渐成为汽车行业生产的唯一生产方式。随着而来的便是流水线的平衡问题，这一问题最早由B.Bryton于1954年在他的硕士论文中提出，而在1955年Salveson首先建立了单品种装配流水线的数学模型，并给出了模型的解法[1]，而自从20世纪80年代起，主要应用于飞机、汽车制造业的多品种的混合流水线得到了迅速发展[2]。这使得汽车行业从大批量、单一品种的生产方式，转变为中多品种、小批量的精益生产方式。但由于混合流水线多品种的特点使得流水线平衡成为复杂的多目标问题。因此，流水线平衡成为混合流水线使用行业重要的关注点。流水线平衡系统由流水线平衡及流水线排产组成，用以协调各工位中不同型号车辆工艺数及各型号车辆投放顺序来解决混合流水线效率问题的主流方法。目前对于混合流水线平衡的研究多着重在于流水线平衡而忽视流水线排产，在完成各工作站的车辆工艺平衡后直接根据各型号汽车需求量排产。但平衡与排产问题存在相互影响，单独考虑平衡问题会降低优化效果。因此，目前对于平衡系统的研究多是独立研究。而本文提出的合作性协同进化算法是一种能够体现子目标间相互协作关系的多目标问题协同求解算法。其能够有效，精确的解决如汽车混合流水线平衡系统这样存在平衡与排产协作关系的多目标问题。

1 汽车混合流水线的多目标平衡

随着汽车行业竞争与市场需求的变化，混合流水线的诞生时的流水线平衡问题变得更加复杂化。半个多世纪以来，混合流水线在汽车领域的使用已普及开来。但对于汽车混合流水线乃至所有混合流水线的设计，都将流水线的平衡与产品的投产排序分开作为两种单独的问题来考虑，但这样的方式往往使得设计出现缺陷，无法得到最优解。这导致了混合流水线的使用停滞不前。现今的解决方式是将平衡设计与排产设计进行串联考虑，在完成平衡设计后再参开排序设计。但这种方式并不能完全解决缺陷，如要得到全局最优解应把两种设计并行考虑，在平衡的同时考虑排产，即将平衡问题看作多目标的优化问题。

1.1 以工作站负荷为基础的混合流水线平衡

混合流水线的平衡只要分为三类：在流水线节拍已知的情况下，求得最少的线上工作站数；在已知不变的工作站数的条件下计算最小节拍；以及在节拍与工作站数都确定不变的基础上均衡每个工作站的负荷。一般情况下，对于前两类的平衡计算较少，这是由于如需对前两者进行设计则设计投资、设备购买、场地规划等等问题，属于长期决策，一般在流水线建造设计之初就已确定。因此，本文中我们对于流水线的平衡问题主要考虑的是工作站的平均负荷，但汽车混合装配流水线相较于普通生产单一产品的流水线，其平衡特点在于即使当平均负荷未超出标准的情况下单个型号产品也会出现超节拍的情况。而对于流水线平衡问题来说，其工作就是合理分配工作站工序，并使得每个工作站作业时间最大限度接近平均节拍，同时又能减少工作站的闲置时间与超载时间。

其中K为流水线负荷系数，F表示流水线上有效作业时间的总和，N表示流水线中的工作站数，C表示流水线的节拍（即流水线上生产两件产品间的时间间隔）。

以一个拥有N个工作站的汽车混合流水线为例，线上共生产M种产品，产品的生产总量为D，每种型号汽车的需求产量为dm（m=1,2,3,…,M），对于以优化汽车混合流水线工作站负荷为目标的平衡工作来说，在满足流水线节拍的条件下，在完成分配后希望其空闲时间最小，即使用节拍计算得到的理论工作时间与实际有效作业时间的相对误差，用算式表达为：

其中：

tmn为型号为m的产品在工作站n上的的作业时间；式(3)表示计算空闲时间的前提条件要求实际有效平均作业时间必定不能超过已定节拍值。

1.2 以工作站负荷为基础的混合流水线排产

汽车混合装配线的排产排序是属于平衡系统的重要组成部分，随着投产顺序的改变，每种型号产品在同一工作站的节拍不尽相同，时常导致工作站中出现闲置或者超载的情况发生。而汽车混合装配线的排产设计是基于流水线平衡的重要步骤，其决定了不同型号的产品在同一流水线上的投放顺序，目的是保证产品的均衡化。对于汽车混合流水线排产，简单的说来就是把各种型号的产品按照合理排序投送到流水线上，用算式可以这样表达：在与平衡设计相同条件下，假设a为各型号产品生产dm的最大公约数，使得即M种类型产品在单次循环中每种类型产品的投产数量，一般情况下，对于流水线的排产就是对这单次循环中F个产品的排序。这样循环a次，便是一条混合流水线的的排产结果。而在单次循环中的m种产品排序就要根据工作站最少空闲与超载的原则来计算。假设一条汽车混合流水线的移动速度为v，工作站n（n=1,2,…,N）的流水线长度为Ln，产品投产间隔为e，假设单次循环中第f位置的产品为m，m在工作站n的的工作时间tmnf流水线小于投产间隔则可能出现空闲状态，考虑操作者走动速度vp，则空闲时间为：，假设混合流水线上第一辆汽车的起始位置为lml0=0，则第f位置车辆在工作站n上的位置为，考虑操作人员走动时间后的超载时间为：。则可用闲置与超载费用来体现排产效果，即目标函数为：

从上述模型公式中可以看到，汽车混合流水线的排产是基于产品在工作站中的工作时间进行计算的，即tmnf。而tmnf是根据流水线的平衡决定的各型号车辆在工作单元的作业要素决定的。因此，在一定程度上，流水线的平衡结果决定了排产结果。

2 汽车混合流水线平衡系统算法

2.1 汽车混合流水线独立优化算法

汽车混合流水线平衡系统的两个子目标为流水线平衡与流水线排产，两者之间存在一定影响，一个子目标的改善会引起另一个子目标的变化。在一定程度上，流水线的平衡结果决定了排产结果，同时不同车型有着不同生产工艺，投产排序的不同会影响工作站上的工作时间，从而影响平衡效果，反之亦然。这样的相互影响使得两个子目标无法同时达到最优，只能协调子目标达到尽可能的最优化[3]，因此这是典型的多目标问题。

解决多目标问题的传统方法有一个共同特征，即将多目标问题转化为单目标问题进行求解，常见的化多目标为单目标的方法有加权和法、目标规划法、E-约束法、目标满意法等[4]。但多目标问题很难简化为单目标问题，在简化过程中难免收到主观因素影响，这会大大影响优化结果。

而在20世纪50年代末，出现了一种进化算法，以模拟自然界的生物进化过程来进行优化的方法，之后在20世纪90年代中期得到迅速发展，是相较于传统算法更为优秀的优化算法。其主要原理为，从随机生成的种群出发，通过选择、交叉、变异等进化来提高个体适应度。以此逐步逼近多目标优化问题的最优解集[3]。相较于传统多目标优化方法，多目标进化算法在运行效率、精确度、分布型等方面都有了大大的提高，在工业、工程、科学等领域都有了大量的运用。但多目标进化算法无法完全满足汽车混合流水线平衡系统的优化要求，由于平衡系统由两个子系统组成，多目标进化算法无法体现两个子系统之间的相互作用，单独求解或者串行求解都无法得到系统整体最优解集。因此，考虑一种协同进化的算法，利用子系统间的系统关系进行并行求解。

2.2 汽车混合流水线协同优化算法

在1996年，Ehrlich和Raven在其发表的有关植物和昆虫之间的协同进化时首次提出了协同进化遗传算法(Coevolutionary Genetic Alorithm, CGA)[5]的概念。其将大型复杂问题分解，以子问题的形式存在，这些子问题存在协同关系，并行计算求解。这种算法模拟实际生态环境，各物种的进化过程具有一定关联性而非独立，物种间的进化相互影响，存在共生关系或者竞争关系，以这种角度考虑生物进化过程，即协同进化[6]。协同进化算法特点在于子系统间在相互作用下求得最优解，而汽车混合流水线的平衡系统是由流水线平衡与流水线排产共同组成，两者相互影响，同时考虑才能得到最优解，因此适合使用协同进化算法进行求解。而协同进化算法又因为子种群间的不同协同关系分为基于生物间相互共生的合作型协同进化算法和基于种群间竞争的竞争型协同进化算法。其中竞争型系统优化算法体现了种群之间的对抗关系，以竞赛的形式迫使种群进化；而合作型协同进化算法是模拟了种群之间的共生关系，即一方的进化需要另一方的帮助，这符合汽车混合流水线的平衡系统的实际情况。图1为合作型协同进化基本框架。

图1 合作型协同进化基本框架

1994年Potter等提出了合作型协同进化算法，用来解决函数优化问题。由于该算法是以遗传算法为基础,所以称其为合作型-协同遗传算法[7](Cooperative Coevolutionary Genetic Algorithm, CCGA)。汽车混合流梳线使用合作型协同进化的核心思想是子群体间的协同合作关系，即将系统分解为2个变量组成的2个子群体，将一个子群体中的个体与另一个子群体中的代表体组成完整解，根据解的优劣评价个体与另一子群体的协同合作能力，如图2所示。

图2 合作型协同进化图

2004年Kuntinee Maneeratana[8]及AntonyW Iorio[9]等人将合作型协同进化算法引入已有的包括MOGA、NPGA、NSGA、CNSGA、NSGA -Ⅱ的多目标优化进化算法中。研究发现，使用合作型协同进化算法可以提高普通进化算法在多目标问题中的搜索效率。

3 结束语

随着市场的需求变化，汽车混合流水线的应用变得迫切起来，混合流水线的平衡优化问题一直是其广泛运用的困难之一。传统的单独对流水线进行平衡而忽略排产问题的算法存在一定问题。混合流水线排产与平衡是相互影响的两部分，单独考虑其中之一或串行的求解方式难以得到真正的最优解集。本文考虑将两者进行并行求解，使用合作型协同进化算法对混合流水线这一多目标优化问题，为解决这一复杂优化问题提供了一个解决途径。

[1] Kroo I Altus S,Braun R,eta.l Multidisciplinary optimization methods for aircraft preliminary design[R].AIAA,1994,94-4325-CP.

[2] Gokcen H,Erel E.A Goal Programming Approach to Mixed Model Assembly Line Balancing Problem[J].International Journal of Production Economics,24 January 1997,48(2)：177-185.

[3] 肖晓伟,肖迪,林锦国,肖玉峰.多目标优化问题研究概述[J].计算机应用研究,2011,3：28(3)805-808,827.

[4] Deb K,Agrawal S, Pratap A and Meyarivan T.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization： NSGA II.[A].Parallel Problem Solving from Nature[C].(PPSN VI),Berlin,2000.

[5] Ehrlieh P R,Raven P H. Butterflies and plants：a study in coevolution[J].Evolution,1964,18(4)：586-608.

[6] 王磊.并行与双系统协同差异进化算法及其应用[D].大连理工大学,2011.12.

[7] Potter M, De Jong K. A cooperative co evolutionary approach to function optimization[J].Lecture Notes in Computer Science, 1994,866(1994)：249-257.

[8] Kuntinee Maneeratana, Kittipong Boonlong and Nachol Chaiyaratana. Multi- objective Optimization by Co-operative Co-evolution[A].In Xin Yao eta.l editors, Parallel Problem Solving from Nature-PPSN VIII,Springer-Verlag, Lecture Notes in Computer Science[C].Birmingham, UK,September 2004,3242：772-781.

[9] AntonyW Iorio and Xiaodong Li A Cooperative Co evolutionary Multiobjective Algorithm Using non-dominated Sorting[A].In Kalyanmoy Deb eta.l editors,Proceedings of the Genetic and Evolutionary Computation Conference, Part I,Springer-Verlag, Lecture Notes in Computer Science[C].Seattle,Washington,USA, June 2004,3102：537-548.