基于平均停歇时间的多品种混流生产线智能排序策略

刘晋飞，李杰林，马学明，林浩

（1.同济大学中德工程学院，上海201804；2.中国航空无线电电子研究所，上海200241；3.同济大学机械与能源工程学院，上海201804；4.特斯拉（上海）有限公司，上海201306）

“工业4.0”智能制造背景下，产品的大批量个性化定制生产需要在工业物联网动态环境下依靠多品种混流生产线完成，相对传统生产线，这种多品种混流生产线应具有更有效的异构设备共享和重用机制，灵活快速的资源配置服务能力、高效的任务动态协调和控制能力，可靠的自治和服务协同能力［1-2］。由于其能够在不占用大量库存的情况下，实现大批量定制生产以快速响应市场变化，故成为汽车、航天航空等生产领域技术升级改造的热点。随着产品多样性需求的日益增加，通过对多品种混流生产线上多种产品的投产顺序进行编排设计，使得生产线得以效率最大化，成为企业降低生产成本、提高生产效率的关键问题。目前，关于多品种混流生产线排序问题的研究主要集中在数学模型构建和智能算法优化求解两方面。

排序问题数学模型构建方面，目前关于目标函数的研究工作中，学者更多地考虑到现实影响因素，优化目标从过去的单目标向多目标发展。陈明等［3］提出了以完工时间、设备最大负荷、设备总负荷以及制造成本为目标的生产线动态调度数学模型；Noda等［4］以生产绩效成本和最大完工时间为优化目标，并利用遗传算法求解排序问题数学模型；Allahverdi等［5］建立了考虑工作站准备时间和产品生产成本的多目标模型，并对不同的产品层赋予不同的权值；Rabiee 等［6］分析了柔性生产线并行工作站、排序设置时间、返工准备时间等要素，构建了无等待两阶段柔性流水车间调度数学模型并利用混合帝国竞争算法进行求解；李爱平等［7］基于准时制生产方式提出了对混流生产线进行工作组划分及物流调度优化方法；Shao等［8］考虑到实际的生产中，工件在等待加工的过程中会占用线边库存，从而增加了线边库存成本的建模。王炳刚等［9-10］提出了一条带有限缓冲区的混流生产线和一条带有限缓冲的加工线以及多条加工线组成的加工-装配混流复杂排序系统，从混流生产线平顺化部件消耗和加工线最小化最大完工时间的角度对问题进行建模。

智能算法优化求解方面，Siala 等［11］采用约束规划方法对生产序列进行排序，以保证总装生产负荷平衡；Dervis 等［12］提出了一类基于蜂群仿生的群智能优化算法（artificial bee colony，ABC），并验证了在求解混流装配关联排序问题的优越性能。Pan等［13］设计了一类离散ABC算法，分别对无等待和有等待的Flow-shop排序问题，围绕延期与提前指标进行了优化；Saif 等［14］提出了一类基于 Pareto 的多目标ABC 算法，对混流生产线排序问题进行了优化求解。Xu 等［15］提出了一种高效的教与学优化算法来求解柔性作业车间调度问题，并通过与其他算法的比较验证了算法的有效性；Chang 等［16］针对柔性作业车间调度问题的特点，借鉴田口实验方法，提出了一种田口遗传算法，并通过大量的测试分析验证了算法的有效性；Thammano 等［17］采用结合邻域搜索的混合人工蜂群算法对柔性作业车间调度进行研究；Yuan 等［18］采用一种混合和声搜索算法进行分析求解；Zhang 等［19］采用混合遗传算法来优化冲压车间的生产成本；Karthikeyan 等［20］针对柔性作业车间调度问题特点，提出了一种混合离散萤火虫算法进行优化求解；Sun 等［21］提出了一种贝叶斯进化优化算法来求解柔性作业车间调度问题，在贝叶斯算法的基础上，增加了群组优化的搜索特性，提升了算法的求解效率；Li 等［22］提出了一种基于 Pareto 优化求解的混合人工蜂群（HABC）算法和离散人工蜂群（DABC）算法，针对多目标柔性作业车间调度问题进行优化。

以上研究提出了许多有价值的思想和方法，多品种混流生产线排序问题数学建模也不断引入更多现实因素，如：订单变更、传送带中断、调整切换等，但都基于生产线能够全寿命工作这一前提条件，故而得出的产品排序都是理论情况，且研究的目标对象大多均为产品在工作站的加工时间，实际意义并不大。同时，“工业4.0”智能制造背景下的多品种混流生产线产品多态性特征引起的工艺流程更改、工装/夹具切换、工具/量具更换、系统程序用例调整等因素，极易导致工作站出现短暂停歇风险，国内外研究文献在排序问题研究中还鲜有考虑。针对上述问题，本文提出平均停歇时间（mean residence time,MRT），建立基于产品进入生产线顺序的产品作业时间表，引入MRT关键变量至最小循环周期优化目标构建多品种混流生产线智能排序数学模型，并利用Palmer 原理设计改进遗传算法，实现多品种混流生产线智能排序问题的高效求解。

1 面向MRT的智能排序数学模型

1.1 平均停歇时间定义

产品大批量个性化定制的智能制造模式中，各工装/夹具设备、工具/量具和系统程序用例均会在生产过程中频繁切换，容易出现突发异常，这些不确定因素不可避免地会对整个生产线的效率和平衡产生影响。因此，在生产线最小生产循环周期内，除了考虑产品作业时间外，此类不确定因素导致的生产停歇时间对生产线的整体运行效率影响巨大。

定义1 平均停歇时间（MRT）：智能制造多品种混流生产模式下，柔性智能化生产线产品多态性特征引起的工艺流程更改、工装/夹具切换、工具/量具更换、系统用例调整等因素，导致工作站生产短暂停顿的平均停歇时间。

生产线上各工作站的平均停歇时间Ti可以表示为

式中：Ti为生产线上各个工作站的平均停歇时间；Ri为生产线上各个工作站的计算平均停歇时间（计算平均间歇时间只有乘以概率才是有效的）；Pi为各个工作站发生突发事件的概率，表示为

式中：(x11，x12，x13，…，x1，10)与 (y11，y21，y31，…，y10，1)T均为只有一个元素为1 的0-1 向量；矩阵A为一个10×10 的［0，1］矩阵，当突发事件发生的概率为10%时，A中100个元素中10个为1，其余为0，且各元素随机排布。

1.2 考虑MRT的最小循环周期

假设某条柔性智能化生产线上生产A、B、C 三种产品，这三种产品均要依次通过4个工作站，每种产品在每个工作站上的作业时间见表1。

表1 三种产品在各个工作站上的作业时间Tab.1 Working times in each workstation of three products

一个最小生产循环周期中，dA=2，dB=1，dC=3，dA表示在一个最小生产循环周期中需要生产产品A 的个数，以此类推。由此可知最小生产循环内的生产总数为d=6，d表示在一个最小生产循环周期内的生产产品总数。若生产排序为δ1=(A，B，A，C，C，C)，则该排序的最小生产循环周期时间 为189 min。与δ1对应的各个工作站的作业时间及子周期见表2。

表2 对应于δ1=(A，B，A，C，C，C)的各个工作站的作业时间及子周期Tab.2 Working times and cycles in the sequence of δ1=(A,B,A,C,C,C)

若生产排序为δ2=(C，A，C，B，C，A)，该排序下最小生产循环周期时间40+28+40=209 min，则该排序下的各个工作站对应的作业时间及子周期见表3。

表3 与δ2=(C，A，C，B，C，A)对应的各个工作站的作业时间及子周期Tab.3 Working times and cycles in the sequence of δ2=(C,A,C,B,C,A)

通过比较δ1与δ2两种排序情况下最小生产循环周期发现，δ1排序下最小生产循环周期时间更短。因此，不同的产品排序对应的最小生产循环周期不同。以上案例认为在生产线正常工作状态下，δ1优于δ2的排序方案。但实际生产过程中由于突发事件的存在，δ1并不一定是优于δ2的排序方案。

假设在δ1=(A，B，A，C，C，C)排序当中，第3个子周期内，工作站1 发生工装夹具切换引起的短暂停歇，切换时间耗时10 min之后，工作站1继续完成产品A 的生产作业。该情况下，各个工作站作业时间及子周期见表4。

表4 短暂停歇情况下对应于δ1=(A，B，A，C，C，C)的各个工作站的作业时间及子周期Tab.4 Operating time and sub-cycles of each workstation corresponding to δ1=(A,B,A,C,C,C)with short pauses

则δ1排序下最小生产循环周期为

假设在δ2=(C，A，C，B，C，A)排序当中，第2个子周期工作站4发生因生产用例切换引起的短暂停歇，切换时间耗时10 min之后，工作站4继续完成产品C 的装配作业。该情况下，各个工作站作业时间及子周期见表5。

表5 短暂停歇情况下对应于δ2=(C，A，C，B，C，A)的各个工作站的作业时间及子周期Tab.5 Operating time and sub-cycles of each workstation corresponding to δ2=(C,A,C,B,C,A)with short pauses

则δ2排序下最小生产循环周期为

此时δ1排序下的最小生产循环周期时间要大于δ2排序下的最小生产循环周期。因此，在解决多品种混流生产线排序问题时，应考虑不同产品进入产线导致的平均停歇时间的影响，即在排序问题优化目标中，引入平均停歇时间变量至关重要。

1.3 基于MRT的智能排序问题数学模型

多品种混流生产线一般由多个工作站组成，且相邻站点的物料输送由相应的运输装置完成，如传送带，吊车等。本文对此类多品种混流生产线的柔性智能排序问题作以下假设：①工作站之间不设缓冲区；②生产线工人流水线操作，不能同时并行操作两个工件；③工作站所处位置不发生变动，站点所分配的作业不变；④生产线上产品的投产率保持一定，不考虑出现紧急订单的情况；⑤不同产品在各个工作站点的总作业处理时间不同；⑥以MRT代表生产线上某工作站因不确定因素造成的平均停歇时间，此时其他工作站正常工作；⑦各工作站中工人仅能在本站点工作，不能进入其他工作站；⑧各工作站所需的零部件及物料能及时满足生产需要。

最小化生产循环周期作为柔性智能化生产线排序问题的主要优化目标，能够有效地提高生产线的生产效率、减少投资成本、加快物流速度，同时改善生产线的平衡率，满足市场多样化的需求。多品种混流生产线需满足不同产品的生产制造需求，最小循环周期内不同产品的数量不同，通过建立一张基于产品进入生产线顺序的产品作业时间表（表6），来描述依次进入生产线时各产品在不同工作站的作业时间。

表6 基于排序的作业时间表Tab.6 Working timesheet based on sequence

若产品进入生产线的顺序为(12 3…K…d)，K(1≤K≤d)表示第k个进入生产线的产品，该产品在第i个工作站的作业时间为tK，i；同理K+1表示第k+1 个进入生产线的产品，该产品在第i个工作站的作业时间为tK+1，i。

当一个排序确定之后，根据某个排序上的产品类型，从基于产品的作业时间表中提取时间，这个时间就是该排序上的作业时间。为了推得最小生产循环周期，首先知道每个子周期当中，各工作站作业时间。在一个生产循环中，投产序列与各工作站上各个产品的作业时间的关系见表7、表8。表7表示d＞S的情况，即最小生产循环周期内，进入生产线的产品个数比工作站数多；表8表示d＜S的情况，即最小生产循环周期内，进入生产线的产品个数比工作站数少。

表7 生产排序与各个工作站不同型号产品作业时间的关系（d＞S）Tab.7 Working timesheet based on the relation of d＞S

为了方便计算产品子周期，用Tk，i来表示第i个工作站在第k个排序上所作业的产品作业时间。则Tk，i如公式（3）所示。

最小生产循环周期最短的目标函数为

表8 生产排序与各个工作站不同型号产品作业时间的关系（d＜S）Tab.8 Working timesheet based on the relation of d＜S

约束条件为

式中：i为工作站编号；j为机器编号；m为产品型号；k为投产顺序。式（4）为优化目标。约束条件（5）用于计算一个最小生产循环中，排在第K个位置的座椅在第i个工位上的操作时间，其中Pm，i表示第m种型号座椅在第i个工位上的操作时间。约束条件（6）用于计算子周期。约束条件（9）保证在生产线上的每一个工作站有且仅有一个产品在被加工。约束条件（10）保证在一个最小生产循环中，第m种型号产品投入生产线的数量为dm。约束条件（11）中θm，k只能在0，1中取值。

2 算法设计

多品种混流生产线智能排序问题属于组合优化问题中的非确定性多项式难题，随着问题规模的增大，搜索空间也急剧扩大，采用一般算法难以求解。遗传算法对所求解的优化问题没有太多数学要求，对于任意形式的目标函数和约束，无论是线性或非线性的，离散或连续性的都可处理，同时遗传算子的各态历经性使得遗传算法能够非常有效地进行概率意义的全局搜素。对于各种特殊问题可以提供极大的灵活性来构造混合领域独立的启发式，从而保证算法的有效性。然而由于遗传算法在进化搜索过程中，每代总要维持一个较大的群体规模，从而使计算次数呈非多项式时间增加，针对第1节提出的多品种混流生产线智能排序数学模型，此类超大规模的优化算法收敛缓慢。基于以上考虑，引入启发式Palmer算法原理，设计一种求解多品种混合生产线智能排序问题的改进遗传算法（图1）。

图1 排序问题算法流程图Fig.1 Flowchart of sequence problem algorithm

算法编码是构造遗传算法的第一步，一个好的编码方式可以清楚地表达问题特征。采用基于产品投产顺序的编码方式［23］。以一个基因串代表一种投产顺序，其每一个基因座上的基因值代表产品品种序号，基因串的长度等于一个最小生产循环中M种产品的总投入量d。例如ABC 混流装配，设其初始投入生产线的顺序为ABCABC，则用（1 2 3 4 5 6）来代表该投产顺序，若经优化后的投产顺序为ABBCCA，则基因值为（1 2 5 3 6 4）。采用基于产品投产顺序的编码方式，易于对多品种多数量的投产问题进行编码，且译码简单。

常规遗传算法的种群初始化常采用完全随机法，即在满足约束的前提下，随机生成n个基因串作为种群的个体。但是这种方式使初始种群的形成过于随意，以至于一开始就可能形成许多不可行的方案，之后要进行大量计算后才能得到优化的方案，这样很大程度上就降低了算法的运算效率。从Palmer算法原理出发，将其适当修改后作为一种启发式策略对染色体种群进行初始化，使得初始种群一开始就表现为一种较优的状态。其中Palmer启发式算法主要应用于流水车间生产排程问题中，是基于工件的加工时间按斜度顺序指标排列工件的启发式算法。按机器的顺序，加工时间趋于增大的工件被赋予较大的优先权；反之，加工时间趋于减小的工件被赋予较小的优先权。工件的斜度指标定义为

式中：m为机器的数目；i为工件编号；j为机器编号；tij为第i个工件在第j台机器上的加工时间；δi按非增的顺序排列。

考虑到palmer算法在流水车间生产排程中的广泛应用，以及常规遗传算法的局限性，将palmer算法的原理应用于遗传算法以提高算法在求解大规模问题运算效率。算法具体流程如下：

（3）若设置的种群大小大于工作站数，则随机选择C1，C2，…，Cm中一个个体，随机选择两个基因座进行基因值交换生成新的基因串，以此类推直到满足种群大小。

3 案例分析

以某混合动力新能源汽车的车身左/右侧围总成多品种混流生产线为例进行实例仿真与算法验证，系统由三部分组成：生产设备、物流系统和生产控制信息系统，如图2 所示。不同于传统的按计划生产方式，该混流生产线的生产计划采取市场订单驱动，每月各车型产量变化相对较大，以该生产线月生产产能为研究样本进行排序问题探讨。

图2 车身左/右侧围总成生产线系统Fig.2 Mixed model assembly line system

当月该生产线的Model K、Model S 及Model O的车身部分的生产件数分别为3 200、1 550、4 000，其客户需求周期约为5 min·件-1，其产量之比大约为4：2：5，虽然由于三种车型不同，但是其各自的装配作业内容仍然相同，所不同的是各车型在同一个作业中的作业时间不同。通过现场调研，3种车型的装配作业总共为46个。该三种车型的作业、及相应作业时间如表9所示。作业任务分配及站内排序如表10所示。

表9 三种车型的装配作业及时间Tab.9 Assembly tasks and times of three different models

表10 作业任务分配及站内排序表Tab.10 Task allocation and sequence

利用Plant Simulation建立生产线模型（图3），将该焊装线分为3块，即生产系统、信息系统以及物流系统。对应到则为物理模型区系统模型，数据储存区以及调度策略区。通过物流对象来仿真实际系统中的有形实体，如零件、各种机床等；通过信息流对象存储实际系统中所要收集、传递的信息，即为各个工作站针对每种产品的加工时间信息；通过一些系列的调度策略模拟各个工作站之间的产品传递关系，同时记录各个工作站中各个零件的加工时间信息。

图3 排序问题模型图Fig.3 Modeling of sequence problem

由于本文中排序问题的研究更加依赖于仿真模型，排序问题中的目标函数，最小生产循环周期是依赖于仿真模型执行的时间，因此在排序问题中需要将生产实际模型完善地建立起来。Plant Simulation数据存储区的Jobs 为各个产品进入焊装线顺序，将初始进入焊装线顺序定为：｛K-K-K-K-S-S-O-O-OO-O｝，如图4 所示。本文提出的改进遗传算法是基于产品进入生产线的顺序编码的，故而在图4中，对各个产品进行了1至11的编码。表示的就是各个产品进入生产线的顺序，从而初始进入生产线的顺序反映为编码则成为了｛1-2-3-4-5-6-7-8-9-10-11｝，在算法运行之后，最佳的进入生产线的次序将会发生变化，例如｛1-3-4-5-2-6-7-8-9-10-11｝，则表示的为初始排序中的第二个产品变化为第5个进入生产线。

图4 Jobs排序优化结果Fig.4 Optimization results of Jobs sequence

现将三种产品在16 个工作站中的作业时间进行整理，得出如表11所示的各个产品在工作站上的总作业时间。

由于输送线速率恒定，将产品在输送线上花费的时间合并计入产品的作业时间。同时，根据工厂现场情况，结合工程师经验将各个工作站的不确定性因素发生概率定为2%，停歇时间定为15 min，利用Plant Simulation物理模型区定义（图5）。

表11 产品在各个工作站上作业时间Tab.11 Working time in each workstation of three models

图5 工作站MRT定义Fig.5 Definition of workstation MRT

在算法求解区定义改进遗传算法。首先Palmer算法针对Jobs 中的产品信息进行排序，并将结果返回到遗传算法序列（GA sequence）当中作为初始种群，其后，遗传算法序列在遗传算法向导（GA wizard）的控制下进行遗传操作及适应值计算，得到最佳的排序结果。在图3 中的调度策略区中，存放的是各个工作站所需要的调度函数。各个调度函数通过读取数据存储区的数据，设置当前工作站的处理时间，同时当下个工作站空闲时将产品输送至下一个工作站。在图3 中的显示区中，存放的是整个生产线的GANTT 图以及各个工作站利用率情况图。

仿真得到排序优化方案为：｛1-3-4-2-9-10-8-6-5-7-11｝，反映为依次进入生产线的产品顺序为：｛K-KK-K-O-O-O-S-S-O-O｝。此时，最小生产循环周期时间为1：49：4，优化后的生产排序相对于之前的排序｛S-K-K-K-O-O-O-O-O-S-K｝，生产节拍提高了近5 min的时间。同时，尽管该生产线上三款产品的工序时间差异极大，经优化排序后各工作站的利用率仍能达到40%左右，且优化后生产线各工作站处于基本平衡状态，如图6所示。

图6 各工作站利用率Fig.6 Utilization of each workstation

4 结束语

针对工业4.0智能制造背景下多品种混流生产线产品多态性特征引起的工艺流程更改、工装/夹具切换、工具/量具更换、系统用例调整等因素导致的工作站易出现生产短暂停歇问题，通过分析不确定因素对多品种混流生产线排序问题的影响，给出了平均停歇时间的定义，建立了面向MRT的多品种混流生产线柔性智能排序问题数学模型，并设计了改进遗传算法实现模型高效求解。仿真实验结果表明，在工业4.0智能制造生产模式下，考虑不确定性因素实现生产线柔性智能排序极其重要，这将极大提升面向批量个性化生产的产品多品种混流生产效率。