考虑生产线平衡的多目标混流装配线排程问题研究*

黄 健，刘亮，齐二石

(天津大学 管理与经济学部，天津 300072)

0 引言

在大规模定制模式下，越来越多的制造商开始引入混流装配线以实现把产品定制和大批量生产结合起来，在降低成本、保证质量的同时，高效率地满足客户的个性化需求［1］。混流装配线(Mixed Model Assembly Lines，MMALs)是指可同时对产品结构相似、工艺路线接近的不同型号产品(同一产品族)进行装配的柔性装配生产线，在基本不改变生产线的前提下，生产不同数量、不同类型的产品。因此，在该装配线上既可以按照单一品种大批量的福特式生产方式生产，也可以进行多品种小批量生产，具有较高的灵活性和适应性。

排序问题是决定混流装配线能否高效运作的关键问题之一，国内外已有很多学者从不同角度研究了混流装配线的产品排序问题。1963 年Wester 和Kilbridge［2］首次提出混流装配线的排序问题(Mixed Model Sequencing Problem，MMSP)，MMSP 已被证明为典型的NP 难题。随着研究的深入，研究者普遍运用人工智能算法，Mansouri［3］用遗传算法对JIT 生产线的两个常见目标进行产品排序;Hyun 等［4］考虑三个目标并设计改进的遗传算法和选择机制(Pareto stratum-niche cubicle)来求解排序问题，并证明得到结果优于现存的遗传算法;曹振新等［5］针对两个目标运用Pareto 理论和小生境单元的适应度函数及选择算子构建遗传算法解决排序问题;Kim 等［6］提出一种改进的进化算法针对三个目标对U 型混流装配线的平衡和排序进行研究。宋华明和马士华［7］证明工作站中不同产品操作时间的差异性对排序结果有显著影响;苏平等［8］对两个目标采用改进混合遗传算法求得最优排序方案，有效解决了GA 收敛过早的缺点;朱华炳等［9］考虑两个目标采用改进多目标粒子群优化算法和仿真结合的方法来对模型进行求解。

目前大多文献都集中在对生产系统的建模分析运用智能算法求解，然而在实际的生产过程中，生产系统一般都属于复杂的离散事件系统，具有不确定性、动态性、复杂性等特点，依靠传统的解决方案进行分析求解，很难做到真实反映生产系统的诸多特性。混流线的平衡和排序问题是设计混流装配线必须要考虑的，但很多学者都把这两方面问题孤立开来研究，在实际应用中很可能不能实现装配线整体优化。

针对上述研究的不足和更加准确、客观地反映企业的生产实际状况，本文在研究排序问题时考虑了生产线平衡，尽可能在让排序所得结果满足生产线平衡条件而不产生忙闲不均的情况，把遗传算法和系统仿真结合起来，综合优化得到最优解。仿真模型中的各参数设置可按照生产实际作相应调整，具有较强的通用性。

1 数学模型的建立

1.1 混流转配线模型描述

假设一条混流装配线上需加工M中产品，每种产品的需求量记作D1，D2，...，DM，生产采用最小生产循环(Minimal Production Set，MPS)模式:设g为D1，D2，...，DM的最大公约数，那么一个MPS中M种产品的生产数量整个生产过程投放g次MPS即可完成，混流装配线的排序问题就是确定一个MPS中产品的投产顺序。该装配线有S个工作站，每个工作站的长度是固定的且是封闭的，操作工不能越过自己的工位。假设不同类型产品之间不存在零部件共享，且生产线平衡问题已经解决。

s表示工作站编号，共有S个工作站;

n表示产品编号，共有N个产品;

k表示产品类别编号，共有K类产品;

xnk是一个0，1 变量，表示排产序列中第n个产品是否为第k类产品，如果变量值为1 ，则表示排产顺序中第n个产品种类为k，否则不是第k种产品;

vc表示传送带的恒定的运行速度;

Ls表示第s个工作站的长度;

w表示两相邻产品的距离;该值等于产品投放时间间隔CT与传送带速度vc的乘积，因为CT是恒定的，我们可以认为w也是恒定不变的;

dk表示生产计划中第k种产品的需求量;

Uns表示排产顺序中第n个产品在s工作站上因超载而需额外补充的工作量，用超载的作业时间来衡量这里的工作量;

SPns表示投产顺序中的第n个产品在第s个工作站上的起始位置;

tsk表示第k类产品在工作站s上的装配时间;

xnkr表示排产顺序中第n和(n +1)个产品的种类是否分别为k品种和r品种，如果是则值为1，否则值为0;

tskr表示在s工作站上产品由k品种切换到r品种所需要的准备时间。

1.2 零部件消耗速率保持均匀模型

生产的均衡化，是在准时制生产方式JIT 中，为了实现“将必需的物品，在必需的时候，仅生产必需的数量”这样的准时生产理念最重要的必要条件。也就是说为了消除不必要的零部件的库存和不必要的产品库存，以及避免因产品装配线和零部件组装线发生生产线停线所需要的多余劳动时间所产生的劳务费浪费，作为前提而必须满足的核心必要条件［10］。对于当下许多实施丰田生产方式企业来说，保持零部件和原材料使用量的均匀消耗是首先要考虑的目标。参照Miltenburg 等提出的生产均衡化模型，得到最终装配线上物料消耗波动最小模型［11］:

1.3 工作站超载量最小化模型

在一次计划排序问题中，每个工作站工作的时间长度为Ls/vc，装配线上的工作站可能会出现如下两种情况，一种情况是一单位产品加工完成后，下一单位的产品尚未进入工作站，操作工回到工作站起点等待产品到来，产生闲置，造成资源浪费;另一种情况是操作工尚未完成一个单位产品的加工，下一单位产品就已进入工作站，这时需要线外工人来帮助完成，产生超载，必将引起成本增加，所以我们要设法减少这样的情况产生。此过程我们可以用图1 表示。

图1 闲置和超载示意图

目标函数2 是为使各工位上超载时间最小化。其中式(6)是为确定投产序列中的第(n +1)个产品在第s个工作站上的起始位置;式(7)为排产顺序中第n个产品在s工作站上因超载需额外补充的工作量。

1.4 总调整变换时间最小化模型

在实际生产中，总的切换时间往往跟产品的投放顺序有关，一般组内调整时间少，组间调整时间大。过于频繁的产品切换将导致操作工出错的可能性变大、生产效率降低等问题。所以这也是很多制造型企业在混流装配线中考虑的一个因素，建立模型如下:

目标函数三是使切换时间最小化。式(10)限定每一工作站对应唯一在制品;式(11)、(12)是为了确保每个MPS 中产品都按照相同的投产顺序进行生产;式(13)是为了满足需求量dk。

最后采用加权法将三个独立的目标函数联合起来进行优化。根据企业自身的情况不同，对各目标函数分配不同的权重系数w1w2w3，经归一化后得到优化模型:

该目标函数的约束为综合以上三个目标函数约束。

2 仿真的建立运行与优化求解

2.1 生产线模型构建

对某500 强企业进行调研，该企业主要生产先进的高、中压开关设备以及满足中国快速发展的输电网络市场对高品质开关设备的需求。本文将针对该公司的中压开关装配线展开研究。企业生产是按照订单进行的，基本实现了定制化。由于产品种类过多，为简化研究过程，假定在一个计划期内，总装线上需要加工的开关柜有CCF、CFC、CCVV、CCCCF、CCCCCC 五种型号，产量分别为120 台、120 台、80 台、160 台和40 台。目前装配线上共有4 个工作站，分别为内部装配(包括背板焊接)、气密耐压试验、侧板装配、总装。

混流装配线仿真模型建立如图2 所示，装配线由内装、背板焊接、侧板装配、总装四个工作站组成，每个工作站旁都有相应的线边协作区，分别为S1、S2、S3、S4。工件在各工作站停留时间是固定的，为实现这一要求，工件从进入工作站就流向相应的传送带，分别为Line、Line4、Line1、Line2，工件在传送带上流动时间即为在此工作站停留时间，生产工人必须再次时内完成本工位操作，如果不能实现，将由线边协作人员帮忙完成，以避免装配线停线。由于个工作站之间的距离是相等的，模型中工作站之间紧挨着，即产品在上一工位加工完成后紧接着就流向本工位。假定传送带的速度vc=0.1m/s，各装配站长度为12，14，12，11。

图2 仿真运行界面

在该模型中，安排生产的产品共有5 种，一个MPS中有15 件产品，其中的产品数可以在全局变量Innumber 中根据不同的生产计划安排自由设定。产品按照模型中表格Schedule 安排的顺序以固定间隔时间50s进入装配线，BF1、BF2、BF3、BF4 表示线边暂存区，产品从传送带上流入到暂存区BF 中等待工作站出现空闲，进入工作站加工。不同类型产品在各工作站上需要的切线准备时间在A1Setup、A2Setup、A3Setup、A4Setup 中设定。对应的每种产品在各工作站上的生产装配时间及工作的长度如下表所示，后分别记录在Assembly1、Assembly2、Assembly3、Assembly4 中，线边作业人员操作时间根据超载时间在程序中设定。在Method 对 象 BF1in-BF4in，BF1out-BF4out，A1OUTA4OUT、S1in-S4in 等中编写的程序，控制各个产品按照设定的逻辑在各工作站中的流动加工，并将加工信息记录在TableFile0、TableFile1、TableFile2、TableFile3中，然后根据所建立的数学模型和统计的信息求得以上三模型的目标函数值。

表1 工作站装配时间和工作站长度

表2 各工作站准备时间

2.3 遗传算法的设计

在本文研究中采用数字串表示基因，每个数字表示各个不同型号的产品。在此例中有A、B、C、H、P 五种型号产品，一个MPS 中各型号数量分别选用(A，B，C，H，P)=(3，5，2，4，1)共15 个，在该实验中，一个染色体由15 个基因组成，并分别用数字1～15 表示。初始种群的产生采用完全随机方法。

适应度是个体选择过程中的评价标准，具有高适应度的个体在进化过程中被保留下来。根据第三部分建立的目标函数模型，根据数学模型在Method、UT 和setuptime 对象中编写SimTalk 程序语言，生成相应的统计数据，然后得到需要的目标函数值，根据制造企业实际情况设定三个单一目标的权重w1w2w3，在此模型中我们分别假定各目标权重为分别为0. 4，0. 2，0.1，以此来确定总目标函数值。考虑到整个过程加工时间也是企业不得不顾及的因素，在仿真中加入加工过程时间最小化即Eventcontroller. SimTime 最小约束，并赋予权重0.3。

因为目标函数O1 值相比于其他三项过小，所以在此模型中将此值乘以10 后加权。

交叉方法采用部分匹配交叉(PMX):随机选取两个交叉点，交换附带个体交叉点之间的片段，对于交叉点外的基因，若它不与换过来的片段冲突则保留，若冲突则通过部分映射来确定，直到没有冲突的基因为止，从而获得后代个体。变异采用随机变异方法。

图3 PMX 交叉操作

2.4 遗传算法求解和筛选

实验采用的遗传算法初始条件如下:种群大小为20，终止迭代次数为100，交叉概率为0.8，变异概率为0.2。仿真运行后得到遗传算法的报告文件，其进化曲线如图4，从图中可以清楚地看出遗传算法的优化过程，在运行到第84 代得到了收敛的结果，得到以加工过程总时间产品变化率、超载时间和总切换时间、周期时间最小化为优化目标的4 个满意解，并在Schedule中的Opt1-Opt4 列生成，所对应的适应度函数值分别为598.205、606.915、610.515 和616.875，均能在以上目标中表现出优秀的性状。

在混流装配线的排程过程中必须兼顾另一个方面是装配线的平衡问题，它与装配线排序问题不能孤立开来研究。按照新的顺序投产不能以损失装配线的平衡为代价，否则也会造成人员、固定资产的浪费，那优化后的产品排产顺序就会失去价值。为此，在得到的满意解中综合考虑装配线平衡的目标从而得到最优排序。

图4 进化曲线

本文算法的4 个满意解整体表现都能满足优化要求，但就生产线平衡来衡量的话，按照方案二Opt2 顺序安排生产所得装配线平衡率最高，且其切线时间也有较好的表现，由此可以得出Opt2 是最优投产顺序。此外，本文是为验证此方法的实用性，所以在对一个MPS 中产品种类、数量、在各工位上加工时间等的数据进行反复调整仍然可以得到符合要求的排产。在此例中我们得到一个 MPS 内产品的投产顺序为AAABBBBCCHPHHHB。另外多目标遗传算法求的结果是一组非劣解集合，这为管理者提供了较好的选择空间。在仿真运行过程中，还可设定各装配工站的故障发生率等生产过程中可能出现的随机因素，从而更贴近生产实际，而这也是现有的数学模型很难实现的。

图5 Opt1-Opt4 中各工作站负荷图

表3 仿真结果比较

3 结束语

在本文的研究中，我们考虑了四个在生产中常见的目标，像超载时间最小化、总加工时间最小化、零部件消耗速率均匀化和调整时间最小化，这些目标对于混流装配线的有效运行来说是非常重要的，特别是当生产线建成后短时期内不会做大规模调整，单纯建立数学模型求解可能无法照顾到生产实际的方方面面，所以有必要对这些生产线的运行做尽可能真实的模拟，通过内置的遗传算法优化，基本可以按照实际生产的要求进行优化，得到满意的产品排序方案，最后结合装配线平衡方面的考量，得出最优排序方案，对混流装配线的排程问题的解法提出了新的思路。

［1］苑明海，李东波，于敏建. 面向大规模定制的混流装配线平衡研究［J］. 计算机集成制造系统，2008，14(1):79 -83，131.

［2］Wester L，Kilbridge M. The assembly line model-mix sequencing problem［C］. Proceedings of the third international conference on Operations Research， Oslo， 1963:247 -260.

［3］Mansouri S A. A multi-objective genetic algorithm for mixedmodel sequencing on JIT assembly lines［J］. European Journal of Operational Research，2005，167(3):696 -716.

［4］Hyun C J，Kim Y，Kim Y K. A genetic algorithm for multiple objective sequencing problems in mixed model assembly lines［J］. Computers ＆ Operations Research，1998，25(7-8):675 -690.

［5］曹振新，朱云龙. 多目标遗传算法在混流装配线排序中的应用［J］. 计算机工程，2005，31(22):1 -3，142.

［6］Kim Y K，Kim J Y，Kim Y. An endosymbiotic evolutionary algorithm for the integration of balancing and sequencing in mixed-model U-lines［J］. European Journal of Operational Research，2006，168(3):838 -852.

［7］宋华明，马士华. 考虑流水线平衡的混合装配线排序［J］. 中国机械工程，2006，17(11):1138 -1147.

［8］苏平，于兆勤. 基于混合遗传算法的混合装配线排序问题研究［J］. 计算机集成制造系统，2008，14(5):1001 -1007.

［9］朱华炳，王龙，涂学明，等. 随机型混流装配线动态排序问题研究［J］. 组合机床与自动化加工技术，2013 (11):114 -118.

［10］门田安弘，著，王瑞珠，李莹，译. 新丰田生产方式［M］.保定:河北大学出版社，2008.

［11］Miltenburg J. Level schedules for mixed-model assembly lines in just-in-time production systems［J］. Management Science，1989，35(2):192 -207.