物料不齐套引起的混流装配线重排序问题

刘 琼，范正伟，张超勇+，朱可人，刘炜琪，，饶运清

（1.华中科技大学 数字制造装备与技术国家重点实验室，湖北 武汉 430074；2.湖北工业大学 机械工程学院，湖北 武汉 430068）

0 引言

在企业生产实际中，装配过程中出现的物料不齐套往往是影响装配计划顺利执行的主要因素。物料齐套性检查就是要求在装配工作开始前将所需零部件全部准备到位。若产品在物料不齐套的情况下开始装配，则可能导致生产时间变长、在制品增加和生产能力下降［1］。企业在面对物料不齐套的情况时，实际上往往通过停线来处理，或采用人工启发式规则对调度方案进行调整，尽管该方法可在一定程度上解决重排序问题，但很难得到期望的良好排序性能，因此在物料不齐套的情况下对初始生产排序进行重排序，就变得极其重要［2］。

Boysen定义重排序为按照排列可行性的一些约束，对目标排序的重新安排，以优化某些目标函数［2］。近年来，研究人员已开始对汽车重排序问题进行研究，Gusikhin等［3］在涂装车间后面设置了一个自动存取系统AS／RS（automated stroage and retrival system），提出一个生成车身被送入涂装车间的投放序列的启发式重排序规则。Ding等［4］引入简单填充和释放策略，研究移出涂装车间之后恢复初始排序和进入涂装车间之前考虑涂装批量的两种情况的重排序。Gujjula等［5］研究准时化顺序供应（just-in-sequence）环境下的重排序方法。在汽车实时生产过程中，Lahmar等［6］建立了一个联合重排序模型，用来最小化切换成本并进行特征分配。在作业车间调度领域，张超勇等［7］采用滚动窗口再调度技术实时处理原材料延迟到达、加工时间延误和装配延误等突发事件；Zhou等［8］提出受影响操作的重排序方法，有效处理了生产过程中的扰动。目前尚未见到对混流装配线重排序问题进行研究的报道。然而，目前作业车间再调度和汽车重排序的研究方法并不适用于多品种、小批量的混流装配线重排序问题的求解，因为汽车重排序问题是基于维持主计划不变的情况下，重排序零部件、总成进入总装线的投放顺序，由选装规则控制时域内产品的变化率；作业车间调度的特点是工件流经工作站的顺序不确定，而混流装配线排序完成后，产品通过工作站的顺序相同，二者是不同类型的模型。而且汽车重排序和作业车间再调度的研究主要针对实时情况下扰动的响应，属于计划执行层上的调度问题，而本文所研究的混流装配线重排序问题为计划已下达、上下游部门已按初始计划进行作业准备和物料安排，但计划尚未被执行，在尽可能维持计划不变的情况下，为得到优化的排序性能而进行的重排序。目前，对由物料不齐套引起的混流装配线重排序问题还未见报道。因此，本文研究多品种、小批量生产过程中由物料不齐套引起的混流装配线重排序问题，为了便于分析与对比，首先根据实例企业的实际情况建立混流装配线初始排序多目标优化模型；为保证从初始排序切换到重排序时生产准备过程的稳定性，提出基于最小化排序偏差指标的混流装配线重排序多目标优化模型；为充分利用装配线的生产能力，提出两周期联合优化策略和基于装配能力的分解策略。

1 混流装配线重排序建模

1.1 混流装配线重排序研究框架

初始排序为给定生产计划所生成的具体装配计划，在生产之前的准备过程中，若无物料不齐套事件发生，则按照初始排序执行生产；若装配前出现待装配产品的零部件不齐套，则为混流装配线重新生成新的排序方案。由于重排序时要去掉不齐套的产品，导致当前周期生产能力剩余等，为解决由此产生的生产能力波动和充分利用装配能力的问题，采用两周期联合优化；为充分利用当前周期装配线的生产能力、得到当前周期上的排序方案，提出基于装配能力分解的混流装配线重排序方法，该方法的研究框架如图1所示。

1.2 问题描述

本文描述的混流装配线以常速vc移动，相似度较高的M 种产品以固定的投放间隔γ 投放到装配线上；装配线被分成J 个闭式工作站，每个工作站的工位长度为Lj；正规工人只能在工作站限定的范围内工作，不能穿越其所在工作站的上游边界和下游边界，未完成的工作交给辅助工人完成，避免由工作负载引起生产线的停线；工人对一个产品执行装配任务并随传送带一起移动到下游，完成装配工序或移动到工作站边界后，工人移向上游继续装配下一个产品。采用Bard［9］提出的最小工作循环（Minimal Product Set，MPS）策略组织生产，（d1，d2，…，dm）=（D1／h，D2／h，…，Dm／h）。其中：dm表示装配线在一个时间周期内生产m 类型产品的数量；Dm表示在整个生产计划中所有最小工作循环周期内m类型产品的装配数量，由计划部门下达的日计划或周计划确定；h 为D1，D2，…，Dm的最大公约数。MPS总需求记为。在装配过程中，次品、物料短缺，物料投放不及时会引起零部件不齐套，导致原有的排序方案不能执行，为保证生产的正常进行，需要对混流装配线进行重新排序。本文将生成的车间要执行的排序称为初始排序，物料不齐套发生且导致初始排序性能变差和不能执行时重新生成的排序称为重排序。

1.3 初始排序多目标优化模型

根据对某空调混流装配线进行调研发现，实际上企业侧重于减少停线时间、平衡工作站负载，保持稳定和连续的零部件供应，以及减少生产过程中频繁更换刀具和夹具，因此选取最小化辅助工作时间、最小化总产品变化率和最小化产品间总切换时间的指标进行优化。

（1）最小化辅助工作时间

为避免工作站因为负载过高而引起停线，引进了辅助工人。最小化辅助工人工作时间不仅能够减少劳动力成本，还能够减小生产线的停线风险［9］。

式中：f1为初始排序最小化辅助工作时间，Uij为产品加工序列中第i个位置产品在工位j 上的超载时间，Zij为第i+1 个产品在工位j 上的初始加工位置。

（2）最小化总产品变化率

连续和稳定的零部件供应能够减小产量波动对其他生产部门的影响并减少产品的库存量［10］。

式中：f2为初始排序最小化总产品变化率，Xlm表示产品序列中第1位到第l位产品m 的累积数量。

（3）最小化产品间总切换时间

不同产品间的切换需要调整刀具和夹具，从而增加操作失误的几率，降低生产效率［11］。

式中：f3为初始排序最小化产品间总切换时间，cimr表示工作站J 上从m 类型产品调整到r 类型产品的转换成本；若m 类型产品和r 类型产品分别分配给第i 个和第（i+1）个工作，则ximr=1，否则ximr=0。

1.4 重排序多目标优化模型

装配车间实际生产过程中，零部件不齐套经常影响生产的正常进行。若按照初始计划进行生产，则可能造成装配线停线、机器空转、员工闲置和生产线停线等资源浪费。企业在实际生产过程中一般采用人工启发式规则对排序方案进行调整，但这种方法往往得不到优化的排序方案。同时车间物料的投放依靠稳定的排序计划，如果重排序与初始排序有很大差异，则会打乱供应商的生产计划，造成物料供应困难［5］。为了帮助实例企业处理物料不齐套造成的影响，得到企业所要求的指标上性能优越、生产准备过程稳定的重排序计划，提出基于最小化排序偏差指标的重排序优化模型。

（1）最小化辅助工作时间

式中fr1为重排序的最小化辅助工作时间。

（2）最小化总产品变化率

式中fr2为重排序的最小化总产品变化率。

（3）最小化排序偏差

为了衡量重排序与初始排序的相似程度，采用Jaro-distance［12］计算任一重排序染色体ri=（bi1，bi2，…，bin）（i=1，2，…，PopSize）与基准排序染色体s0=（a1，a2，…，am）之间的相似度，算法的最后得分越高，说明相似度越大，0 分表示没有任何相似度，1分表示完全匹配。最小化排序偏差指标如下：

式中：fr3为重排序的最小化排序偏差，Jaro（s0，ri）为字符串s0和ri之间相似度的得分，c为匹配的字符数，t为换位字符数的一半。假设字符串s1和s2分别为MARTHA 和MARHTA，可以得到c=6，s1和s2的长度为|s1|=|s2|=6，两组字符串中TH 和HT 进行了换位操作，t=2／2=1；字符串s1和s2的相似度得分为=0.944。

2 第二代非支配排序遗传算法

本文采取非支配排序遗传算法（Non-dominating Sorting Genetic Algorithm，NSGAⅡ）［13］求解初始排序和重排序，其流程如图2所示。

2.1 基于工件的染色体编码及两周期联合优化策略

基于工件的编码方法采用数字或字母表示产品，染色体每个数字或字母的个数等于每个工作周期中产品的需求数目，如计划装配四种产品，每个产品的数量分别为1，2，1，2，可在染色体中用A，B，C，D 表示对应的产品，染色体中某字符出现的次数表示对应产品的生产数量，因此染色体中有1个A、2个B、1个C、2个D，DDABBC是一个可行的编码。

若在装配准备过程中，某种产品因物料不齐套不能按初始计划进行生产，则将该产品从当前生产周期中移除，放在下一周期进行生产。当前周期若不添加物料已齐套的产品，只对移除后剩下的产品进行重排序，则会造成当前周期装配能力过剩、下一周期要生产的产品增加、装配能力不足的装配能力波动现象。为了既充分利用装配线的生产能力，又便于物料准备，采用两周期联合优化策略，即在重排序过程中将两个相邻周期内齐套的物料产品组合在一起进行重排序。假设装配车间按照DDABBC 进行生产物料准备时发现产品B 不齐套，需要进行重排序，而下一周期需要生产A，B，D，E，F五种产品，MPS为（2，1，2，1，1）。采用两周期联合优化策略，将前后两个周期进行组合，删除不齐套的产品B，即生产A，C，D，E，F，MPS为（3，1，4，1，1），则AAACDDEFDD 为一个可行的重排序编码。

2.2 交叉操作

采用单点交叉再组合的交叉操作［14］，将选中进行交叉操作的两个父代染色体分别分成头部和尾部两个部分，父代个体1，2 分别表示为（H1，T1），（H2，T2）。删除父代个体2中与父代个体1尾部相同的基因，将保留的基因作为子代个体的头部，父代个体1的头部作为子代个体的尾部，得到子代个体染色体。具体操作如图3所示。

2.3 变异操作

采取倒序的变异操作，任意选取个体染色体片段，执行倒序操作，如图4所示。

2.4 基于Pareto排序—拥挤距离的选择操作

基于Pareto排序—拥挤距离选择技术如图5所示。种群记为P（t）=｛p1，p2，…，ppopSize｝，当前种群记为Pu，排序层次为v的个体记为p（v）。

步骤1 初始化参数，Pu=P（t），u=1，由于尚未对种群进行Pareto排序，此时所有个体的排序层次v=0。

步骤2 对种群个体进行Pareto排序，分成若干个Pareto分层，并计算每一个Pareto分层的拥挤距离。

步骤3 寻找第u 个Pareto分层PSu，PSu=｛（pi，bi）｝，其中：pi为种群Pu的非支配解，bi为pi的拥挤距离。

步骤4 按照bi降序的方式排序PSu中的个体，将rank（v+s）分配给第s个个体，其中s=1，2，…，|PSu|。

步骤5 v=v+|PSu|，u←u+1，Pu=Pu-1-PSu-1。如果Pu≠∅，则返回步骤3，否则转步骤6。

步骤6 通过式prob（p（v））=q（1-q）v-1（v=1，2，…，popSize）确定每一Pareto分层中个体选择到下一代中的概率，式中q 为选择概率参数，q=3／popSize。

采用拥挤距离保证非支配解的分布性和多样性。同一Pareto分层内拥挤距离大的个体周围的解空间密度小，赋予较大的被选概率。

2.5 基于生产能力的分解策略

采取两周期联合优化后，为得到当前周期上的排序计划且充分利用当前周期的装配能力，本文提出了基于混流装配线生产能力的分解策略，分解两周期联合编码，以得到当前周期上具体的产品生产计划。

确定解码位置的具体步骤如下：

例如2.1节两周期联合优化的例子中，可行编码AAACDDEFDD 在分解时发现，排序AAACD就能较充分地利用车间装配能力，而分解成排序AAACDD 则超过了车间的装配能力，因此重排序后当前周期上的排序计划为AAACD。

3 实例验证及结果分析

为了验证研究的有效性，测试了某空调企业混流装配线在物料不齐套情况下的重排序问题。所有算法的运行环境为2.0 GHz Pentium CPU，1 G RAM，Windows XP，采用VC++6.0编程。装配线上产品的投放间距L0=775 mm，装配线的移动速度为Vc=10 mm／s。需要装配6 种四出风室内机产品，日计划产量分别为A 产品45台、B产品90台、C产品75台、D 产品60台、E产品60台、F产品90台，最小生产循环MPS为（3，6，5，4，4，6）。经过简单的作业规划合并后，该混流装配线包括装电机、装风轮、装电控、装蒸发器、装送风部件和主打包（贴标签、装附件）6个主要工位。各机型在每个工位上的加工时间经过多次测量求平均值，以确保数据的准确度，各工位的长度和操作时间如表1所示，表2所示为产品间的切换时间。车间每个工作循环的装配能力W=280s。

表1 装配线的模型数据

表2 产品间的平均切换时间 s

表3列出了算法运行的初始排序部分非支配解结果。

表3 初始排序Pareto最优解集

选取加粗黑色的排序方案BBBAAAECCFFDDFECFFECDBBFECDB作为基准排序方案。

实例企业在应对物料不齐套的情况时采取的启发式规则为：若产品mi的物料出现不齐套，则从当前周期删除该产品，依次生产该周期中非mi的产品；为了避免浪费生产能力，生产下一个周期中的非mi类型产品，直到满足该车间的装配能力为止。在生产准备过程中，发现产品C，E 的零部件不齐套，采用该启发式规则重排得到的重排序列为BBBAAAFFDDFFFDBBFDBBBBAAAFF，对应的函数目标值分别为74，32.41，0.63。若采取所提重排序方法，则经过基于生产能力分解后得到的最终重排序Pareto最优解集如表4所示，NSGAⅡ的参数设置为种群大小450，迭代次数300 次，交叉概率0.75，变异概率0.15。

表4 重排序后的Pareto最优解集

如图6所示，在笛卡尔三维坐标系中，星号几乎呈带状分布，且两两之间互不支配，即一点的两坐标值若小于第三点对面的坐标值，则另外一个坐标值必大于另一点坐标值，星号构成Pareto解集。星号的三坐标值均小于或近似小于圆圈的对应坐标值。由图6可知，物料不齐套的情况下，所提重排序方法得到的结果在排序偏差目标上明显优于启发规则得到的结果，且在最小化辅助工人工作时间和最小化零部件消耗速率两个指标的目标值上也分别优于启发式规则得到结果的对应指标，表明所提方法得到的Pareto最优解集优于一般启发式规则重排序结果。由此可知，本文提出的重排序性能优于目前企业实际采用的启发式规则，该方法能减小辅助工人的工作时间和正规工人的闲置时间，充分利用装配线的生产能力，平衡工作站的负载，降低生产过程中的物料需求波动，平顺物料供应，为企业解决物料不齐套问题引起的重排序问题提供了有效的方法。

4 结束语

本文针对混流装配线因物料不齐套引起的初始排序性能恶化或排序方案不可行的问题，提出混流装配线重排序方法来响应物料不齐套问题；提出基于最小化排序偏差的混流装配线重排序多目标优化模型，以得到性能良好的排序方案和提高装配线的生产效率；同时最小化重排序与基准排序之间的偏差来保证生产准备过程的稳定性，以便将物料及时投放到装配线上。为充分利用装配线生产能力和得到当前周期的排序方案，采用两周期联合优化策略和基于装配线生产能力的分解策略。与实例企业解决物料不齐套情况下采用的启发式规则结果相比，本文提出的重排序方法在排序偏差、最小化辅助工人时间和最小化零部件的消耗波动目标上，其结果中的最大值分别小于启发式规则得到的对应目标值，验证了模型与算法的有效性。然而本文没有深入研究物料不齐套产品占总排序产品的比率对重排序性能影响。其次，所调研的实例企业物料不齐套的比例较小，两周期联合优化可以有效求解物料不齐套引起的重排序问题。然而当物料出现较大面积不齐套时，可能需要联合三个或三个以上周期进行求解。同时实例企业相邻两个周期的产品交货期相近，且均能满足交货期的要求，因此两周期联合优化时没有考虑交货期的影响。两周期联合优化扩大了算法的搜索空间，但是增加了算法的复杂度。在下一步工作中，将探讨物料不齐套对重排序性能的影响，将两周期联合优化策略扩展为多周期联合优化策略，研究降低算法搜索空间，提高算法有效搜索的方法的新算法，同时可以在优化目标中考虑交货期的影响。

［1］RONEN B.The complete kit concept［J］.International Journal of Production Research，1992，30（10）：2457-2466.

［2］BOYSEN N，SCHOLL A，WOPPERER N.Resequencing of mixed-model assembly lines：survey and research agenda［J］.European Journal of Operational Research，2012，216（3）：594-604.

［3］GUSIKHIN O，CAPRIHAN R，STECKE K E.Least in-sequence probability heuristic for mixed-volume production lines［J］.International Journal of Production Research，2007，46（3）：647-673.

［4］DING F Y，SUN H.Sequence alteration and restoration related to sequenced parts delivery on an automobile mixed-model assembly line with multiple departments［J］.International Journal of Production Research，2004，42（8）：1525-1543.

［5］GUJJULA R，GUNTHER H.Resequencing mixed-model assembly lines under Just-In-Sequence constraints［C］／／Proceedings of International Conference on Computers &Industrial Engineering.Washington，D.C.，USA：IEEE，2009：668-673.

［6］LAHMAR M，ERGAN H，BENJAAFAR S.Resequencing and feature assignment on an automated assembly line［J］.IEEE Transactions on Robotics and Automation，2003，19（1）：89-102.

［7］ZHANG Chaoyong，LI Xinyu，WANG Xiaojuan，et al.Multiobjective dynamic scheduling optimization strategy based on rolling-horizon procedure［J］.China Mechanical Engineering，2009，20（18）：2190-2197（in Chinese）.［张超勇，李新宇，王晓娟，等.基于滚动窗口的多目标动态调度优化研究［J］.中国机械工程，2009，20（18）：2190-2197.］

［8］ZHOU Y，LI B，YANG J，et al.Study on an affected operations rescheduling method responding to stochastic disturbances［C］／／Proceedings of the 3rd International Asia Conference on Industrial Engineering and Management Innovation.Berlin，Germany：SpringerVerlag，2013：117-125.

［9］BARD J F，DAR-ELJ E，SHTUB A.An analytic framework for sequencing mixed model assembly lines［J］.International Journal of Production Research，1992，30（1）：35-48.

［10］MILTENBURG J.Level schedules for mixed-model assembly lines in just-in-time production systems［J］.Management Science，1989，35（2）：192-207.

［11］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.

［12］JARO M A.Probabilistic linkage of large public health data files［J］.Statistics in Medicine，1995，14（5／6／7）：491-498.

［13］DEB K，AGRAWAL S，PRATAP A，et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization：NSGA-Ⅱ［C］／／Proceedings of the Parallel Problem Solving from NatureⅥConference.Berlin，Germany：Springer-Verlag，2000，1917：849-858.

［14］LEU Y，MATHESON L A，REES L P.Sequencing mixedmodel assembly lines with genetic algorithms［J］.Computers&Industrial Engineering，1996，30（4）：1027-1036.