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

摘要

“工业4.0”智能制造模式下的多品种混流生产线各工装/夹具、工具/量具和系统用例切换频繁，极易导致生产突发异常致使工作站出现短暂停歇风险。通过分析多品种混流生产线产品多态性引起的不确定性因素，提出了平均停歇时间（MRT），研究考虑MRT的多品种混流生产线最小生产循环周期，建立了基于产品进入生产线顺序的产品作业时间表，通过引入MRT关键变量至最小循环周期优化目标，构建了智能排序数学模型，并利用Palmer原理设计了改进遗传算法，实现了多品种混流生产线智能排序问题的高效求解，最后实例验证了该方法的可行性和有效性。

关键词

智能制造; 多品种混流生产; 智能生产排序; 改进遗传算法; 生产停歇时间

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

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

$$T_i=R_i{P}_i,i=\mathrm{1,2},\mathrm{3},\dots ,S$$

（1）

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

$$P_i=\left(x_{\mathrm{11}},x_{\mathrm{12}},x_{\mathrm{13}},\dots ,x_{\mathrm{1,10}}\right)\mathit{A}{\left(y_{\mathrm{11}},y_{\mathrm{21}},y_{\mathrm{31}},\dots ,y_{\mathrm{10,1}}\right)}^{\mathrm{T}},i=\mathrm{1,2},\mathrm{3},\dots ,S$$

（2）

式中：$\left(x_{\mathrm{11}},x_{\mathrm{12}},x_{\mathrm{13}},\dots ,x_{\mathrm{1,10}}\right)$与${\left(y_{\mathrm{11}},y_{\mathrm{21}},y_{\mathrm{31}},\dots ,y_{\mathrm{10,1}}\right)}^{\mathrm{T}}$均为只有一个元素为1的0-1向量；矩阵A为一个10$\times$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 ( min )

产品	工作站1	工作站2	工作站3	工作站4
A	18	8	12	23
B	24	16	9	33
C	20	40	28	12

一个最小生产循环周期中，$d_{\mathrm{A}}=\mathrm{2},d_{\mathrm{B}}=\mathrm{1},d_{\mathrm{C}}=\mathrm{3}$，$d_{\mathrm{A}}$表示在一个最小生产循环周期中需要生产产品A的个数，以此类推。由此可知最小生产循环内的生产总数为$d=\mathrm{6}$，d表示在一个最小生产循环周期内的生产产品总数。若生产排序为${\delta }_{\mathrm{1}}=\left(\mathrm{A},\mathrm{B},\mathrm{A},\mathrm{C},\mathrm{C},\mathrm{C}\right)$，则该排序的最小生产循环周期时间为${\displaystyle \sum _{k=\mathrm{1}}^d}{\mathrm{C}}_k=\mathrm{40}+\mathrm{28}+\mathrm{18}+\mathrm{23}+\mathrm{40}+\mathrm{40}=\mathrm{189}\mathrm{m}\mathrm{i}\mathrm{n}$。与${\delta }_{\mathrm{1}}$对应的各个工作站的作业时间及子周期见表2。

表2 对应于${\mathit{\delta }}_{\mathrm{1}}=\left(\mathbf{A},\mathbf{B},\mathbf{A},\mathbf{C},\mathbf{C},\mathbf{C}\right)$的各个工作站的作业时间及子周期

Tab. 2 Working times and cycles in the sequence of ${\mathit{\delta }}_{\mathrm{1}}=\left(\mathbf{A},\mathbf{B},\mathbf{A},\mathbf{C},\mathbf{C},\mathbf{C}\right)$ ( min )

排序	工作站1	工作站2	工作站3	工作站4	子周期
A	18(A)	40(C)	28(C)	12(C)	40
B	24(B)	8(A)	28(C)	12(C)	28
A	18(A)	16(B)	12(A)	12(C)	18
C	20(C)	8(A)	9(B)	23(A)	23
C	20(C)	40(C)	12(A)	33(B)	40
C	20(C)	40(C)	28(C)	23(A)	40

若生产排序为${\delta }_{\mathrm{2}}=(\mathrm{C},\mathrm{A},\mathrm{C},\mathrm{B},\mathrm{C},\mathrm{A})$，该排序下最小生产循环周期时间${\displaystyle \sum _{k=\mathrm{1}}^d}{C}_k=\mathrm{33}+\mathrm{40}+\mathrm{28}+\mathrm{40}+\mathrm{28}+\mathrm{40}=\mathrm{209}\mathrm{m}\mathrm{i}\mathrm{n}$，则该排序下的各个工作站对应的作业时间及子周期见表3。

表3 与${\mathit{\delta }}_{\mathrm{2}}=(\mathbf{C},\mathbf{A},\mathbf{C},\mathbf{B},\mathbf{C},\mathbf{A})$对应的各个工作站的作业时间及子周期

Tab. 3 Working times and cycles in the sequence of ${\mathit{\delta }}_{\mathrm{2}}=(\mathbf{C},\mathbf{A},\mathbf{C},\mathbf{B},\mathbf{C},\mathbf{A})$ ( min )

排序	工作站1	工作站2	工作站3	工作站4	子周期
C	20(C)	8(A)	28(C)	33(B)	33
A	18(A)	40(C)	12(A)	12(C)	40
C	20(C)	8(A)	28(C)	23(A)	28
B	24(B)	40(C)	12(A)	12(C)	40
C	20(C)	16(B)	28(C)	23(A)	28
A	18(A)	40(C)	9(B)	12(C)	40

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

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

表4 短暂停歇情况下对应于${\mathit{\delta }}_{\mathrm{1}}=\left(\mathbf{A},\mathbf{B},\mathbf{A},\mathbf{C},\mathbf{C},\mathbf{C}\right)$的各个工作站的作业时间及子周期

Tab. 4 Operating time and sub-cycles of each workstation corresponding to ${\mathit{\delta }}_{\mathrm{1}}=\left(\mathbf{A},\mathbf{B},\mathbf{A},\mathbf{C},\mathbf{C},\mathbf{C}\right)$ with short pauses ( min )

排序	工作站1	工作站2	工作站3	工作站4	子周期
A	18(A)	40(C)	28(C)	12(C)	40
B	24(B)	8(A)	28(C)	12(C)	28
A	故障修复	16(B)	12(A)	12(C)	600+18
C	20(C)	8(A)	9(B)	23(A)	23
C	20(C)	40(C)	12(A)	33(B)	40
C	20(C)	40(C)	28(C)	23(A)	40

则${\delta }_{\mathrm{1}}$排序下最小生产循环周期为

$${\displaystyle \sum _{k=\mathrm{1}}^d}{C}_k=\mathrm{40}+\mathrm{28}+\mathrm{600}+\mathrm{18}+\mathrm{23}+\mathrm{40}+\mathrm{40}=\mathrm{789}\mathrm{m}\mathrm{i}\mathrm{n}$$。

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

表5 短暂停歇情况下对应于${\mathit{\delta }}_{\mathrm{2}}=(\mathbf{C},\mathbf{A},\mathbf{C},\mathbf{B},\mathbf{C},\mathbf{A})$的各个工作站的作业时间及子周期

Tab. 5 Operating time and sub-cycles of each workstation corresponding to ${\mathit{\delta }}_{\mathrm{2}}=(\mathbf{C},\mathbf{A},\mathbf{C},\mathbf{B},\mathbf{C},\mathbf{A})$ with short pauses ( min )

排序	工作站1	工作站2	工作站3	工作站4	子周期
C	20(C)	8(A)	28(C)	33(B)	33
A	故障修复	40(C)	12(A)	12(C)	600+18
C	20(C)	8(A)	28(C)	23(A)	28
B	24(B)	40(C)	12(A)	12(C)	40
C	20(C)	16(B)	28(C)	23(A)	28
A	18(A)	40(C)	9(B)	12(C)	40

则${\delta }_{\mathrm{2}}$排序下最小生产循环周期为 ${\displaystyle \sum _{k=\mathrm{1}}^d}{C}_k=\mathrm{33}+\mathrm{600}+\mathrm{18}+\mathrm{28}+\mathrm{40}+\mathrm{28}+\mathrm{40}=\mathrm{787}\mathrm{m}\mathrm{i}\mathrm{n}$。

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

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

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

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

表6 基于排序的作业时间表

Tab. 6 Working timesheet based on sequence ( min )

排序	工作站1	工作站2	…	工作站i	…	工作站S
1	t1,1	t1,2	…	t1,i	…	t1,S
2	t2,1	t2,2	…	t2,i	…	t2,S
︙	︙	︙	︙	︙	︙	︙
K	tK,1	tK,1	…	tK,i	…	tK,S
︙	︙	︙	︙	︙	︙	︙
d	td,1	td,1	…	td,i	…	td,S

若产品进入生产线的顺序为$\left(\mathrm{1}\mathrm{2}\mathrm{3}\cdots K\cdots d\right)$，$K\left(\mathrm{1}\le K\le d\right)$表示第k个进入生产线的产品，该产品在第i个工作站的作业时间为$t_{K,i}$；同理K+1表示第k+1个进入生产线的产品，该产品在第i个工作站的作业时间为$t_{K+\mathrm{1},i}$。

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

表8 生产排序与各个工作站不同型号产品作业时间的关系(d<S)

Tab. 8 Working timesheet based on the relation of d<S

排序	工作站1	工作站2	…	工作站i	…	工作站S
1	t1,1	td,2	…	td-(i-2),i	…	td-(S-2),S
2	t2,1	t1,2	…	td-(i-3),i	…	td-(S-3),S
︙	︙	︙	︙	︙	︙	︙
K	tK,1	tK-1,2	…	td-(i-K-1),i	…	td-(S-K-1),S
︙	︙	︙	︙	︙	︙	︙
d	td,1	td-1,2	…	td-(i-d-2),i	…	td-(S-d-1),S

注：

min

表7　生产排序与各个工作站不同型号产品作业时间的关系(d>S)

Tab. 7　Working timesheet based on the relation of

d>S

min

表8 生产排序与各个工作站不同型号产品作业时间的关系(d<S)

Tab. 8 Working timesheet based on the relation of d<S ( min )

排序	工作站1	工作站2	…	工作站i	…	工作站d	…	工作站 s-mod(s,d)*d+1	…	工作站S
1	t1,1	td,2	…	td-(i-2),i	…	t2,d	…	t1,1	…	td-(S-int(S/d)d)+2,S
2	t2,1	t1,2	…	td-(i-3),i	…	t3,d	…	t2,1	…	td-(S-int(S/d)d)+3,S
︙	︙	︙	︙	︙	︙	︙	︙	︙	︙	︙
K	tK,1	tK-1,2	…	td-(i-K-1),i	…	tK+1,d	…	tK,1	…	td-((S-int(S/d)d)-K-1),S
︙	︙	︙	︙	︙	︙	︙	︙	︙	︙	︙
d	td,1	td-1,2	…	td-(i-d-1),i	…	t1,d	…	td,1	…	td-((S-int(S/d)d)-d-1),S

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

$$T_{k,i}=t_{d-(i-\mathrm{i}\mathrm{n}\mathrm{t}\left(\frac{i}{d}\right)d+k+\mathrm{1},i},k=\mathrm{1,2},\cdots ,K,\cdots ,d;i=\mathrm{1,2},\cdots ,S$$

（3）

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

$$\mathrm{m}\mathrm{i}\mathrm{n}J={\displaystyle \sum _{k=\mathrm{1}}^d}{C}_k$$

（4）

约束条件为

$$t_{k,i}={\displaystyle \sum _{m=\mathrm{1}}^M}{\theta }_{m,k}{P}_{m,i},k=\mathrm{1,2},\cdots ,K,\cdots ,d;i=\mathrm{1,2},\cdots ,S$$

（5）

$$C_k=\underset{\mathrm{1}\ll j\ll s}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{T_{k,j}+{\mathrm{T}}_{\mathrm{j}}\right\}=\underset{\mathrm{1}\ll j\ll s}{\mathrm{m}\mathrm{a}\mathrm{x}}\left\{t_{d-(i-\mathrm{i}\mathrm{n}\mathrm{t}\left(\frac{i}{d}\right)d+k+\mathrm{1},i}+T_j\right\}$$

（6）

$$T_j=R_j{P}_j,j=\mathrm{1,2},\mathrm{3},\dots$$

（7）

$$P_j=\left(x_{\mathrm{11}},x_{\mathrm{12}},x_{\mathrm{13}},\dots ,x_{\mathrm{1,10}}\right)\mathit{A}{\left(y_{\mathrm{11}},y_{\mathrm{21}},y_{\mathrm{31}},\dots ,y_{\mathrm{10,1}}\right)}^{\mathrm{T}},j=\mathrm{1,2},\mathrm{3},\dots ,S$$

（8）

$${\displaystyle \sum _{m=\mathrm{1}}^M}{\theta }_{m,k}=\mathrm{1},k=\mathrm{1,2},\cdots ,K,\cdots ,d$$

（9）

$${\displaystyle \sum _{k=\mathrm{1}}^d}{\theta }_{m,k}=d_m,m=\mathrm{1,2},\cdots ,M$$

（10）

$${\theta }_{m,k}\in \left\{\mathrm{0,1}\right\},m=\mathrm{1,2},\cdots ,M;k=\mathrm{1,2},\cdots ,K,\cdots ,d$$

（11）

式中：i为工作站编号；j为机器编号；m为产品型号；k为投产顺序。式（4）为优化目标。约束条件（5）用于计算一个最小生产循环中，排在第K个位置的座椅在第i个工位上的操作时间，其中$P_{m,i}$表示第m种型号座椅在第i个工位上的操作时间。约束条件（6）用于计算子周期。约束条件（9）保证在生产线上的每一个工作站有且仅有一个产品在被加工。约束条件（10）保证在一个最小生产循环中，第m种型号产品投入生产线的数量为$d_m$。约束条件（11）中${\theta }_{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启发式算法主要应用于流水车间生产排程问题中，是基于工件的加工时间按斜度顺序指标排列工件的启发式算法。按机器的顺序，加工时间趋于增大的工件被赋予较大的优先权；反之，加工时间趋于减小的工件被赋予较小的优先权。工件的斜度指标定义为

$${\delta }_i={\displaystyle \sum _{j=\mathrm{1}}^m}\left[j-\left(m+\mathrm{1}\right)/\mathrm{2}\right]t_{ij},i=\mathrm{1,2},\cdots ,d$$

（12）

式中： m为机器的数目；i为工件编号；j为机器编号；

$t_{ij}$为第i个工件在第j台机器上的加工时间；${\delta }_i$按非增的顺序排列。

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

（1） 根据${\delta }_i={\displaystyle \sum _{j=\mathrm{1}}^m}\left[j-\left(m+\mathrm{1}\right)/\mathrm{2}\right]t_{ij},i=\mathrm{1,2},\cdots ,d$，求得每个工件在所有装配站上的斜度指标，${\delta }_i$按非增的顺序排列。此时的排序作为种群第一个个体$C_{\mathrm{1}}$，C代表。

（2） 根据

${\rho }_i=\left[j-\left(m+\mathrm{1}\right)/\mathrm{2}\right]t_{ij},i=\mathrm{1,2},\cdots ,d$，求得工件在每个装配工作站的斜度指标。对于第一个工作站，将工件在该工作站上的斜度指标${\rho }_i$以非增的顺序排列，得到排列顺序为染色体种群中的第二个个体$C_{\mathrm{2}}$，以此求得$C_{\mathrm{3}},C_{\mathrm{4}},\cdots ,C_m$。

（3） 若设置的种群大小大于工作站数，则随机选择$C_{\mathrm{1}},C_{\mathrm{2}},\cdots ,C_m$中一个个体，随机选择两个基因座进行基因值交换生成新的基因串，以此类推直到满足种群大小。

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

作业编号	作业名称	作业时间/min				作业编号	作业名称	作业时间/min
		Model K	Model S	Model O				Model K	Model S	Model O
1	安装左侧围板	40	45	40		24	安装右A柱内板总成	60	60	60
2	安装左A柱内板总成	60	60	60		25	安装左中柱内板加强件	60	60	60
3	安装左中柱内板加强件	60	60	60		26	安装隔音胶	30	40	40
4	安装隔音胶	30	40	40		27	安装右后门锁闩加强件	45	50	45
5	安装左后门锁闩加强件	45	50	45		28	安装右车身外侧板下接件	40	60	40
6	安装左车身外侧板下接件	40	45	40		29	安装右后尾灯支架总成	80	120	100
7	安装左后尾灯支架总成	80	100	100		30	安装油箱加油管罩总成	60	80	60
8	初焊	45	50	50		31	初焊	45	50	50
9	取焊枪焊接结合件	80	100	100		32	取焊枪焊接结合件	80	120	100
10	安装左后门门槛加强件	54	60	54		33	安装右后门门槛加强件	54	60	54
11	安装左后轮罩内下板	50	60	60		34	安装右后门门槛加强件	50	80	60
12	安装左中柱内板总成	50	60	70		35	安装右中柱内板总成	50	80	70
13	安装左后三角柱内板总成	60	65	60		36	安装右后三角柱内板总成	60	80	60
14	在做后轮罩内下板涂胶	100	120	100		37	在做后轮罩内下板涂胶	100	120	100
15	安装左后轮罩内板总成	60	60	60		38	安装右后轮罩内板总成	60	60	60
16	初焊	60	70	60		39	初焊	50	50	45
17	取焊枪焊接结合件	100	120	120		40	取焊枪焊接结合件	100	120	120
18	左侧围板外板总成涂胶	120	120	120		41	右侧围板外板总成涂胶	120	120	120
19	安装左侧围板	40	50	40		42	安装右侧围板	40	50	40
20	初焊	50	60	50		43	初焊	50	60	50
21	机器人焊接	120	120	120		44	机器人焊接	120	120	110
22	检查焊点	100	100	100		45	检查焊点	100	100	100
23	安装右侧围板	40	50	40		46	分总成下料	30	30	30

表10 作业任务分配及站内排序表

Tab. 10 Task allocation and sequence

执行次序	工作站编号
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	35	6	33	13	7	26	29	14	37	32	17	16	18	42	20	21
2	5	23	28	25	2	11	3	30	38	15	9	40	41	19	45	22
3	1	24	10	36		31	4				39			43		46
4	12	27				34	8							44

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

图3 排序问题模型图

Fig. 3 Modeling of sequence problem

由于本文中排序问题的研究更加依赖于仿真模型，排序问题中的目标函数，最小生产循环周期是依赖于仿真模型执行的时间，因此在排序问题中需要将生产实际模型完善地建立起来。Plant Simulation数据存储区的Jobs为各个产品进入焊装线顺序，将初始进入焊装线顺序定为：｛K-K-K-K-S-S-O-O-O-O-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所示的各个产品在工作站上的总作业时间。

表11 产品在各个工作站上作业时间

Tab. 11 Working time in each workstation of three models ( min )

产品	工作站编号
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Model K	208	232	205	210	220	203	233	236	224	220	246	220	270	264	220	262
Model S	228	252	237	235	240	258	288	276	244	260	286	240	270	294	240	262
Model O	248	232	205	210	240	248	268	236	224	240	281	235	270	254	230	262

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

图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-K-K-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智能制造生产模式下，考虑不确定性因素实现生产线柔性智能排序极其重要，这将极大提升面向批量个性化生产的产品多品种混流生产效率。

刘晋飞：负责本研究智能排序问题定义、模型及算法设计等。 李杰林：负责本研究案例分析与验证、数据质量把控等。 马学明：负责本研究的论文构思、论文表述与后期修改等。 林浩：负责本研究问题提出、模型及算法优化，案例验证等。

作者贡献声明

申明：