具有机器可利用性的双目标置换流水车间调度

轩 华， 李海云， 李 冰

(郑州大学 管理学院， 河南 郑州 450001)

0 引言

流水车间调度是制造业较为关注的一类研究问题，在工业和许多其他实践中有着广泛的应用[1]。作为其中一类典型问题，置换流水车间调度问题(permutation flow shop scheduling problem，PFSSP)首次由Johnson[2]提出,并已被证明是一类典型的NP-hard组合优化问题[3]。在现实生产中，由于机器故障或检修等原因导致机器在一定的时间段内是不可用的，这就产生了本文所研究的具有机器可利用性的PFSSP。

在单目标流水车间调度问题(flow shop scheduling problem，FSSP)的研究中，为最小化最大完工时间(makespan)，Mosheiov等[4]研究了带单一维修时间窗的2台机器流水车间和开放车间调度，对于流水车间，维修发生在第2台机器，对于这2类问题提出了3/2近似算法；为求解m(m>2)个机器的FSSP，Miyata等[5]提出了构造启发式算法求解带预防性维修和顺序相关设置时间的无等待FSSP；Aggoune等[6]针对带有限机器可利用性的FSSP，结合两工件的临时几何方法和禁忌搜索算法提出了启发式算法。

在多目标FSSP的研究中，周炳海等[7]考虑了机器的衰退，提出了改进双目标人工蜂群算法用于同时最小化makespan和维护成本；Zhang等[8]针对带预防性和正确性维修的装配式PFSSP，提出了新的迭代Pareto贪婪算法，用于同时最小化makespan和维护成本；Boufellouh等[9]针对带预防性维修和全局资源约束的PFSSP，提出了非支配排序遗传算法和粒子群优化，用于同时最小化makespan和总生产成本。

求解PFSSP的优化算法多以启发式算法或元启发式算法为主获取问题近优解。为最小化makespan，Abdel-Basset等[10]结合局域搜索策略和鲸鱼优化算法提出了混合鲸鱼优化算法；Zhao等[3]提出了一种混合高效作业序列映射方案和变邻域搜索的和声搜索算法；Liu等[11]结合NEH启发式算法和局域搜索提出了一种混合差分进化算法；Xie等[12]提出了一种基于教学-学习的混合优化算法用来分别最小化makespan和最大延迟。作为一种智能优化算法，遗传算法已广泛应用于求解车间调度[8]等领域，而遗传算法与其他算法的结合通常会提高求解性能，因此，在解决双目标PFSSP时如何设计有效的遗传算法还要进一步探讨。

就目前查阅的文献而言，关于带机器可利用性的双目标PFSSP的研究较为有限，因此，为解决此类PFSSP，本文引入CDS启发式算法、局域搜索、遗传参数随迭代数而变化的自适应调整机制提出了一种改进遗传算法(improved genetic algorithm, IGA)，用于解决问题同时最小化总加权完成时间和总加权拖期。

1 问题描述及建模

1.1 问题描述

所研究的PFSSP可描述如下：n个待加工工件须经m台不同的机器进行加工，即每个工件i有m道工序，以相同的加工顺序依次在机器M1，机器M2，…，机器Mj，…，机器Mm上加工eij个时间段。每台机器j有T个不可用时间窗，且不可用时间窗(Gjo,Hjo)事先已知且固定，工件在各机器的加工须在该机器的可利用时间段内进行。每台机器一次至多处理一个工件，而每个工件一次只能在一台机器上加工,工件一旦开始在一台机器上加工，则该工序不允许中断。

1.2 数学模型

minF=μF1+λF2;

(1)

(2)

(3)

Cπ1j=aπ1+eπ1j,j=1;

(4)

Cπ1j≥Cπ1j-1+eπ1j,j∈(2,3,…,m);

(5)

Cπi1≥Cπi-11+eπi1,i∈(2,3,…,n);

(6)

Cπij≥max(Cπij-1,Cπi-1j)+eπij,i∈(2,

3,…,n),j∈(2,3,…,m);

(7)

Si1≥ai,i∈(1,2,…,n);

(8)

Cij≥Sij+eij,i∈(1,2,…,n),j∈(1,2,…,m);

(9)

Cij≤Gjo+M(1-Xijo),i∈(1,2,…,n),

j∈(1,2,…,m),o∈(1,2,…,T);

(10)

Cij≥eij+Hjo(1-Xijo)，i∈(1,2,…,n),

j∈(1,2,…,m),o∈(1,2,…,T);

(11)

(12)

(13)

Cij,Sij≥0,i∈(1,2,…,n),j∈(1,2,…,m);

(14)

Xijo,Yik∈(0,1),i,k∈(1,2,…,n),
j∈(1,2,…,m),o∈(1,2,…,T)。

(15)

其中，式(1)为所研究问题的目标，即最小化总加权完成时间和总加权拖期的线性组合，两部分分别由式(2)和式(3)计算得到，其中μ、λ分别为与完成时间和拖期相关的系数，且μ+λ=1；δi为工件i的目标权重；Sim、Cim、eim分别为工件i在机器m上的开始时间、完工时间和加工时间;di为工件i的交货期。对于序列π中的第一个工件π1,约束(4)定义了在第一台机器上的完成时间，其中aπ1为工件π1的释放时间。约束(5)表示在相邻工序间的加工优先级关系。对于工件加工序列的其他工件πi(i=2,3,…,n),约束(6)表示在第一台机器的加工紧随工件πi-1之后进行。约束(7)描述了在后续机器上工件πi的完成时间由它在前道工序的完成时间以及其紧前工件πi-1在该机器的完成时间来决定。约束(8)确保了工件在第一台机器的开始时间须在其释放时间之后。约束(9)说明了同一个工件的开始和完成时间的关系。约束(10)和(11)确保了从工件开始加工到结束加工的整个时间段在机器的可用时间段内，其中M为一个无穷大的数，Xijo为二元变量，当工件i在机器j的第o个不可用时间窗之前加工时，Xijo=1，否则，Xijo=0。约束(12)表示序列的任一位置只能安排一个工件，其中Yik为二元变量，当工件i分配到加工序列的位置k时，Yik=1，否则，Yik=0。约束(13)表示每个工件只能分派到序列内的一个位置。约束(14)和(15)定义了变量取值范围。

上述模型虽与文献[13]类似，但也有不同：文献[13]针对的是两机FSSP，机器不可用时间段仅发生在第一台机器，目标是最小化最大完工时间，而本文研究的是多机问题，每台机器均须考虑机器可利用性约束，目标的最小化总加权完成时间和总加权拖期。

2 改进遗传算法

2.1 PFSSP的编码及解码

采用工件编号的整数编码对工件加工序列进行编码。基于该加工序列调度工件用来解码，从机器M1至机器Mm，安排各机器上的工件加工时，检查每个工件从Sij开始的eij个时间段是否出现在(Gjo,Hjo)内，如没有，则确定该Sij值;否则，需将Sij延后，直至(Sij,Sij+eij)在机器可利用时间段内。

P个工件加工序列即构成初始工件加工序列群。利用CDS启发式算法产生40%的初始工件加工序列群，其余的则通过随机程序产生。CDS启发式算法实现过程如下。

Step1将m台机器进行临近两两分组，构成m-1个的虚拟两机组合：[1,m]、[(1,2),(m-1,m)]、[(1,2,3),(m-2,m-1,m)],…,[(1,2,…,l),(m+1-l,…,m)]。

Step2对每一个虚拟两机组合，分别计算工件i在虚拟两机的总加工时间作为其在相应虚拟机器的模拟加工时间，再利用文献[2]算法获得最优加工序列，从而得到m-1个最优加工序列。

Step3若(m-1)<40%P,则将上述过程产生的加工序列重复，以填补40%P-(m-1)个加工序列。

2.2 适应度计算

由于本文优化的目标是最小化总加权完成时间和总加权拖期的加权和，故第π个工件加工序列的适应度函数表示为

(16)

采用轮盘赌规则选择适应度值较高的工件加工序列执行后续的交叉变异算子。

2.3 交叉和变异

设计自适应交叉概率Pc和自适应变异概率Pm以改善算法的搜索能力和收敛效果。定义当前工件加工序列群的平均适应度值fv：

(17)

令MG为最大迭代次数，g为当前迭代次数，fx为最大适应度值，Pcmax和Pcmin为交叉概率的最大值和最小值，Pmmax和Pmmin为变异概率的最大值和最小值。

(1)当fπ≥fv时，即当前加工序列的适应度值较大时，Pc和Pm的取值随当前迭代次数的变化而变化。

(18)

(19)

(2)当fπ

对轮盘赌规则选择操作之后产生的序列群选择连续的两个父代工件加工序列A和B，从(0, 1)随机产生一个数γ，当γ

图1 单点交叉Figure 1 Single-point crossover

对交叉操作后得到的新序列群内的每个工件加工序列，从(0,1)随机生成一个数u，若u

图2 翻转逆序变异Figure 2 Reverse order mutation

2.4 局域搜索

对执行上述操作后目标值仍未改进的工件加工序列Z依次执行基于如下邻域搜索机制的局域搜索，当变换之后的邻域解优于当前解时，记录最佳解，搜索结束，否则保留当前解。

(1)两两交换。随机选择工件加工序列的2个工件编号，将其进行交换，如图3所示。

图3 两两交换Figure 3 Pair-wise exchange

(2)单工件插入。随机产生工件加工序列的2个工件位，将工件位靠前的工件编号插入到工件位靠后的工件编号的前面，如图4所示。

图4 单工件插入Figure 4 Single-job insertion

(3)多工件插入。随机选择工件加工序列的1个工件片段，从除去该工件片段外的部分工件加工序列里随机选择1个工件位，将所除去的工件片段插入至该位置，如图5所示。

图5 多工件插入Figure 5 Multiple-job insertion

2.5 改进遗传算法的计算流程

改进遗传算法具体描述如下。

Step1算法参数初始化。工件加工序列群规模P，最大迭代次数MG，交叉概率Pc，变异概率Pm。

Step2工件加工序列群初始化。由CDS启发式算法和随机程序的两阶段过程构造初始加工序列群。

Step3计算每个工件加工序列的适应度值，应用轮盘赌规则选择出优秀的工件加工序列。

Step4基于自适应交叉概率Pc进行单点交叉。

Step5基于自适应变异概率Pm进行翻转逆序变异。

Step6判断经交叉和变异后的工件加工序列的适应度值较原工件加工序列是否有所改善，对未改善的工件加工序列依次基于两两交换、单工件插入和多工件插入产生邻域解，若发现邻域解优于当前解或3种邻域搜索机制执行完毕，结束局域搜索。

Step7判断当前迭代数是否超过MG，如超过，输出最佳目标值；反之，更新当前迭代数，转至Step 3。

3 仿真实验

为了公平起见，将所提出的结合CDS启发式算法和局域搜索的改进遗传算法(IGA)与求解PFSSP的混合遗传算法(HGA)[14]、不考虑自适应遗传参数设置的改进遗传算法(N-IGA)、结合NEH启发式算法的自适应遗传算法(AGA&NEH)[15]进行比较。所有实验均利用MATLAB 2020a编译，在内存为4.00 GB，处理器为AMD A10-9600P，主频为2.4 GHz的计算机上运行。经实验测试，将N-IGA的交叉概率Pc和变异概率Pm分别设为0.65和0.02，所有算法的工件加工序列群规模均为100，以HGA运行1 500代且最大运行时间不超过120 s作为其他3种算法的停止条件。

用仿真实验对随机数据测试不同Pc和Pm取值，将得到的最佳解所对应的Pc和Pm值作为其最终取值：(Pcmin,Pcmax)=(0.4,0.8)，(Pmmin,Pmmax)=(0.05,0.1)。

3.1 参数设置

借鉴文献[16]，μ取2个不同值，分别为μ=0.3，μ=0.7。令R表示交货期的松弛度，取3个不同值，分别为R=0.5，R=1.0，R=1.5[17]。n=(50,100,150)，m=(5,10)，ai、δi和eij分别在(1,5)、(1,4)、(1,20)随机产生。简单起见，假定每台机器有一个不可用时间段，即o=1，但所提出的算法也可以求解机器有多个不可用时间段的情况。

3.2 IGA的效果分析

为说明CDS启发式算法和基于3种邻域搜索机制的局域搜索对IGA的影响，取n=(50,100,150)，m=10，μ=0.3，R=(0.5,1.0,1.5)，将IGA、不采用局域搜索的结合CDS启发式和自适应遗传参数的遗传算法(CDS-AGA)和利用随机程序产生初始加工序列群的结合局域搜索和自适应遗传参数的遗传算法(LS-AGA)进行对比。上述参数共产生了9个问题组合，取每个组合10次运行结果的平均值作为该组合的测试结果，因此，本实验共测试了90组实验数据。以CDS-AGA算法运行1 500代且最大运行时间不超过120 s作为其他2种算法的停止条件。测试结果如表1所示，其中加粗显示的为最佳目标值。

表1 IGA、LS-AGA、CDS-AGA算法的测试结果Table 1 Test results of IGA,LS-AGA,CDS-AGA

由表1可看出，IGA的目标值均优于CDS-AGA和LS-AGA，说明在相同运行时间下，嵌入的3种邻域搜索机制可产生更佳邻域解，应用CDS启发式算法能够获得更好的初始加工序列群。

3.3 测试结果与分析

(n,m,μ,R)的不同取值共产生了36个问题组合，每个组合随机运行10次，取其平均值作为该问题组合的测试结果，因此，本实验共测试了360个实例。定义γ1、γ2、γ3为目标改进率分别为

γ1=(FHGA-FIGA)/FIGA×100%;

γ2=(FN-IGA-FIGA)/FIGA×100%;

γ3=(FAGA&NEH-FIGA)/FIGA×100%。

式中：F表示目标值。

(1)对不同规模问题的测试结果见表2。由表2可知，在平均计算时间77.65 s内，HGA、N-IGA、AGA&NEH、IGA的目标值分别为148 349.00、145 529.86、151 117.96、140 666.61，IGA相较于HGA改进了5.05%，较N-IGA改进了3.09%，较AGA&NEH改进了7.33%。

表2 不同规模问题的测试结果Table 2 Test results of different scale problems

(2)为了对实验结果进行统计意义下的分析和比较，取n=(50,100,150)且m=(5,10)的不同规模问题，对IGA相较于其他3种算法的目标改进率进行统计学检验，如图6和图7所示，IGA相较于其他3种算法均有明显改进。

图6 不同μ取值下的目标改进率区间图(95%的置信区间)Figure 6 Interval diagram of target improvement rate for different μ value (95% confidence interval)

图7 不同R取值下的目标改进率区间图(95%的置信区间)Figure 7 Interval diagram of target improvement rate for different R value (95% confidence interval)

取n=(50, 100, 150)，m=10，μ=0.3，R=0.5的4个算例在最大迭代次数1 500的限制条件下运行上述4种算法，得到如图8的趋势图，说明在相同迭代数内，IGA得到的目标值更优。

图8 随迭代次数变化的目标值变化趋势Figure 8 Trend of the target value changing with the number of iterations

4 结束语

本文研究了具有机器可利用性和工件释放时间的PFSSP。为尽可能最小化总加权完成时间和总加权拖期的加权和，提出了IGA进行求解不同规模的PFSSP，通过仿真实验说明了IGA能够在可接受的计算时间内得到较好的近优解。未来研究可将所提算法推广以求解FSSP或研究其他启发式算法(人工蜂群算法等)求解具有机器可利用性的PFSSP。