考虑准备时间的分布式两阶段混合流水车间调度

蔡劲草，雷德明

(武汉理工大学 自动化学院,湖北 武汉 430070)

0 引言

混合流水车间调度问题(Hybird Flow-shop Scheduling Problem, HFSP)结合流水车间调度问题和并行机调度问题的特征，与流水车间调度问题的区别在于其有多个阶段，每个阶段至少有一台机器且至少一个阶段存在多台并行机。作为一种常见的车间调度问题，HFSP已广泛应用于纺织、化工和半导体等领域[1]。

两阶段HFSP为一种常见的HFSP，其研究受到人们的广泛关注[2-8]，常见的优化目标包括总延迟时间[2]、平均延迟时间[3]和最大完成时间[4-8]等。Zhong等[4]设计了两个多项式时间逼近算法；Chen[5]给出了三组启发式算法；Azami等[6]建立了离散时间混合整数线性规划模型，其利用分支定界法求解中小规模问题，采用改进的遗传算法求解大规模问题，改善了复合航空元件的制造过程；蒋凯丽等[7]提出基于最长加工时间规则和最小化机器松弛时间的构造式算法来处理周期预防性维护问题；Tan等[8]利用迭代分解算法解决了考虑准备时间且具有批处理机的问题。然而同时考虑最大完成时间和总延迟时间的研究较少，由于多目标优化问题更接近现实，有必要对其进行研究。

随着经济全球化，公司因发展需要在不同的地方建立了多个工厂，以提高对市场的反应能力，给车间调度研究带来了新的挑战[9]。分布式制造可以利用不同工厂的资源，通过合理配置改善整个制造过程来降低最大完成时间、总延迟时间和加工成本等[10]。近年来，分布式车间调度问题受到工业界和学术界的广泛关注，分布式并行机调度问题[11-12]、分布式作业车间调度问题[13-15]及分布式流水车间调度问题(Distributed Flow-shop Scheduling Problem, DFSP)[16-30]的研究都取得了较大进展。

DFSP包括分布式装配流水车间调度[22]、分布式置换流水车间调度[23-27]和分布式装配置换流水车间调度[28-30]等，主要采用的方法有变邻域搜索(Variable Neighborhood Search, VNS)[16]、生物地理学优化算法[17]、迭代贪婪算法[18-20]和启发式算法[21]等，且以优化最大完成时间为主。作为分布式HFSP的特例，DFSP的研究取得了一些进展，但分布式HFSP本身的成果却非常少，仅有Ying等[31]研究了考虑多处理机的分布式HFSP，建立了混合整数线性规划模型，提出了一种自适应迭代贪婪算法，并利用自适应混合解码机制优化了最大完成时间。以上对分布式调度问题的研究很少考虑依赖顺序的准备时间(Sequence-Dependent Setup Times, SDST)，作为车间调度问题中一种常见的约束条件，结合SDST的调度研究具有重要意义。

VNS[32]是一种基于局部搜索的元启发式算法，它采用当前解的邻域结构搜索解空间，并利用逐步搜索到的更优解更新当前解来完成整个搜索过程。VNS已广泛应用于各种车间调度问题[33-35]，并显示了较强的搜索优势。

本文研究考虑SDST的多目标分布式两阶段混合流水车间调度问题(Distributed Two-stage Hybrid Flow shop Scheduling Problem, DTHFSP)，该问题通常包括工厂分配、机器分配和调度3个子问题，其中工厂分配将工件分配到合适的工厂，机器分配为工件确定合适的加工机器，调度用于确定工件的加工顺序。DTHFSP广泛存在，例如在晶圆制造领域中拥有多个晶圆厂的半导体制造公司[31]；在钢铁和食品加工业中[36]，许多企业将单一的工厂生产系统升级为具有类似功能的多工厂分布式生产系统[22-30]。DTHFSP虽然广泛存在，但是研究较少。

DTHFSP的子问题众多，而且子问题之间的耦合关系复杂，为此本文首先提出一种有效策略来减少子问题数量，以降低求解难度；然后在简化DTHFSP的基础上，提出一种双变邻域搜索(Double Variable Neighborhood Search, DVNS)算法，该算法包括两个相互协作的变邻域结构，每个变邻域结构都加入了常规VNS所没有的全局搜索以协调全局搜索和邻域搜索，并利用外部档案内的解周期性更新当前解，相互协作的两个变邻域结构在增加DVNS全局搜索能力的同时保证了局部搜索能力，周期性更新解使算法有可能跳出局部最优；最后运用大量实例进行对比，并以两个著名的带精英策略的快速非支配排序遗传算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)[37]和强度Pareto进化算法2(Strength Pareto Evolutionary Algorithm2, SPEA2)[38]作为对比算法，结果表明DVNS在求解DTHFSP上具有较强的性能。

1 问题描述

约束如下：一个工件同一时刻最多只能在一台机器上加工；一台机器同一时刻最多只能加工一个工件；所有工件的加工过程不能中断；所有机器在任意时刻都可用。

DTHFSP的工厂分配、机器分配和调度3个子问题之间存在强耦合关系，如果不能将工件分配到合适的工厂，即使其他两个子问题获得了最优结果，整个问题的解也很难为最优。由于每个工厂的机器均固定，只考虑第一阶段的机器分配，在工件分配到第一阶段的并行机后，通过所有并行机分配的工件即可确定每个工厂分配到的工件及其数量，解决了工厂分配子问题，由此只需考虑第一阶段的机器分配子问题，无需单独解决工厂分配子问题，从而降低了子问题的数量，使问题得以简化。图1所示为DTHFSP的多工厂系统。

简化DTHFSP能够有效降低问题的复杂性，减少求解难度，然而简化只是一种处理复杂问题的方式，并不会影响该问题本身的特性，简化后的DTHFSP仍是一个分布式调度问题。

DTHFSP的目的为给每个工件分配合适的机器并确定各阶段机器上工件的加工顺序，以最小化如下两个目标：

(1)

(2)

式中：Ci为工件Ji的完成时间；Cmax为最大完成时间；Ttot为总延迟时间；di为工件Ji的交货期。

2 应用DVNS解决考虑SDST的DTHFSP

2.1 编码与解码

DTHFSP可以简化为第一阶段机器分配和调度两个子问题，为此给出一种新的编码方案，对具有n个工件和第一阶段总共有W台并行机的DTHFSP，采用双串编码方法描述问题的解，其中第一个串为机器分配串[M1,h1,M1,h2,…,M1,hn]，第二个串为调度串[q1,q2,…,qn]。机器分配串中，机器M1,hi与工件Ji对应，调度串为实数串，qi与工件Ji对应，hi∈[1,W]，qi∈[0,1]。

解码时，首先由机器分配串确定工件Ji第一阶段的加工机器M1,hi，如果sf

表1所示为DTHFSP的一个实例，包括20个工件和3个工厂，其一个可能的编码为：机器分配串为[M1,4,M1,4,M1,8,M1,2,M1,1,M1,2,M1,6,M1,7,M1,7,M1,1,M1,3,M1,5,M1,3,M1,6,M1,5,M1,3,M1,4,M1,1,M1,8,M1,2]，调度串为[0.22,0.44,0.67,0.66,0.28,0.31,0.77,0.72,0.65,0.6,0.29,0.69,0.32,0.72,0.74,0.53,0.35,0.34,0.67,0.04]。

根据解码过程，工件J5,J10,J18分配到工厂F1第一阶段的机器M1,1上，工件J4,J6,J20分配到工厂F1的机器M1,2上，工件J4,J5,J6,J10,J18,J20分配到工厂F1的机器M2,1上。由于q20

表1 20个工件在3个工厂两个阶段的加工时间

双串编码方法降低了编码的复杂度，因为两个串彼此独立，所以可以更加方便地进行邻域搜索和全局搜索，而且不会产生非法解。

2.2 邻域搜索和全局搜索

根据考虑SDST的DTHFSP的特点，设计了8个邻域结构，应用2个全局搜索算子来增强DVNS的全局搜索能力，并通过合理配置使其能够协同工作。

由于最大完成时间makespan主要由第一阶段的机器分配决定，通过调整第一阶段的机器分配可以有效降低makespan，为此设计4个针对机器分配的邻域结构。

邻域结构NSM1在单工厂内转移工件，随机选择一个工厂Ff，从该工厂第一阶段负荷最大的机器M1,l上任选一个工件Ji，将其转移到工厂Ff负荷最小的机器M1,g上，机器负荷为机器准备时间和加工时间之和。工件在第一阶段的机器分配直接影响第二阶段加工的开始时间，因此该邻域结构可降低makespan。图2工厂F1中第一阶段负荷最大的机器为M1,2，负荷最小的机器为M1,1，可选择工件J4，将其从机器M1,2转移到机器M1,1上，机器分配串的第4个基因相应地由M1,2变为M1,1。

NSM2在两个工厂间转移工件，随机选择工厂Ff1和Ff2，分别确定两个工厂第一阶段负荷最大的机器M1,li和负荷最小的机器M1,gi(i=1,2)，若M1,l1的负荷大于M1,l2的负荷，则选择一个工件从M1,l1转移到M1,g2上，否则选择工件从M1,l2转移到M1,g1上。两个工厂之间转移工件可有效降低某一工厂中工件的最大完成时间，从而优化makespan。

NSM3在两个工厂间互换工件，随机选择工厂f1和f2，确定负荷最大的机器M1,li和负荷最小的机器M1,gi(i=1,2)，若M1,l1的负荷大于M1,l2的负荷，则在机器M1,l1和M1,g2之间互换选中的一对工件，否则在M1,l2和M1,g1之间互换选中的工件。两个工厂中互换工件可以平衡各工厂中机器的负载，有可能改善makespan。

NSM4在两个工厂间转移工件，从完成时间最大的工厂f1中随机选择一个工件，将其转移到完成时间最小的工厂f2中。工件转移到f2时，将其分配到任意选择的并行机上，其中工厂的完成时间为第二阶段机器最后加工工件的完成时间。

每个工厂的第二阶段只有一台机器，改变第二阶段的加工顺序对最大完成时间的影响较小，对总延迟时间影响却较大。若优先加工交货期较小或第二阶段加工时间较短的工件，则很有可能降低总延迟时间。因此，采用与机器分配类似的方式为调度串设计了4种邻域结构。

邻域结构NSS1从调度串中随机选择两个基因进行互换，NSS2将从调度串中随机选择的基因插入一个随机选择的新位置。

NSS3在所有工厂内重新排列调度串，先将分配到每个工厂的工件按其在第二阶段的加工时间升序排序，然后使与这些工件对应的ql的排序与加工时间升序排序的结果一样。图2中工厂3加工工件J9,J3,J19,J8,J14,J7在第二阶段的加工时间分别为69,71,66,64,62,65，按加工时间将工件升序排序为J14,J8,J7,J19,J9,J3，对应调度串的顺序为q14,q8,q7,q19,q9,q3。所获得的新的调度串为[0.22,0.44,0.72,0.66,0.28,0.31,0.72,0.77,0.67,0.6,0.29,0.69,0.32,0.65,0.74,0.53,0.35,0.34,0.67,0.04]。

NSS4也在所有工厂内重新排列调度串，过程与NSS3一样，只是根据交货期而非加工时间进行排序。

传统的VNS很少用到全局搜索，为了进一步增强VNS的全局搜索能力，在DVNS中引入全局搜索，使其与邻域搜索有效地结合在一起。全局搜索GS1改变当前解x的机器分配串，对于解x和从外部档案中随机选择的解x′(x′≠x)，随机确定位置k1,k2(k1

2.3 算法描述

DVNS的具体步骤如下：

步骤1初始化。随机产生一个解x，初始化外部档案Ω，令t=1，g1=1，g2=1。

步骤2g1=1时产生新解z∈NSM1(x)，g1=2时得到新解z∈NSS1(x)，g1=3时使用NSM3得到新解z，g1=4时运用GS1获取新解z。如果新解z不受解x支配，则z替代x更新外部档案并令g1=1；否则g1=g1+1，若g1=5，则赋值g1=1。

步骤3对x执行NSM4得到新解z，判定新解z能否满足步骤2的替代条件，是则替代x并更新外部档案。

步骤4对当前解x执行NSS1(g2=1)，NSS2(g2=2)，NSM2(g3=3)或GS2(g1=4)，获得新解z。如果新解z满足步骤2的替代条件，则z替代x，更新外部档案并令g2=1；否则g2=g2+1，若g2=5，则赋值g2=1。

步骤5对当前解x依次应用NSS3和NSS4，根据步骤2的替代条件确定每次产生的新解z能否替换x，若满足替换条件，则更新外部档案。

步骤6t=t+5，若t能被β整除，则从外部档案中选择一个与当前解距离最远的解，替换当前解。

步骤7如果t>max_it，则结束搜索，否则返回步骤2。

步骤8输出外部档案Ω。

其中：max_it为目标函数评估次数的最大值，β为给定的一个整数，NSM1(x)是对x执行NSM1获得的邻域解的集合。

如果解x′和x满足条件Cmax(x′)≤Cmax(x)Ttot(x′)≤Ttot(x)，Cmax(x′)

外部档案Ω保留DVNS搜索过程中产生的非劣解，更新时将新解添加到Ω中，进行基于Pareto支配的比较，保留非劣解并删除受支配解。

DVNS引入全局搜索，对8个邻域结构和2个全局搜索算子进行了合理配置，并利用两个VNS的协同作用使全局搜索和邻域搜索的有效协调成为可能，而周期性替换当前解进一步提高了DVNS的全局搜索能力，总之DVNS具有较强的搜索能力。

3 计算实验

为了测试DVNS在解决考虑SDST的DTHFSP方面的性能，进行了大量计算实验。实验采用Microsoft Visual Studio C++ 2015编程，运行于8.0 G RAM 2.3 GHz CPU的计算机上。

3.1 测试实例、评价指标和对比算法

实验共产生了38个DTHFSP的测试实例，相关信息如表2所示。这些实例中，加工时间pifs∈[50,70]，准备时间ujifs,u0ifs∈[5,10]，交货期

(3)

式中d∈[1,n/F+1]。

表2 实例的相关信息

采用两个指标DIR和C评价算法的性能。DIR衡量当前算法的非劣解集Ωl相对于参考集Ω*的距离，

(4)

式中：参考集Ω*由所有算法非劣解集并集中的非劣解组成；sxy表示解x与参考集Ω*中元素y在归一化目标空间内的距离。显然，算法的非劣解集Ωl越靠近参考集Ω*，说明算法越好，即DIR的值越小算法越好。

C指标衡量两个算法非劣解集之间的支配关系，C(L,B)指解集B被解集L中的解支配的解在解集B中所占的比例，

(5)

式中l≻b表示l支配b，如果对于所有目标最小化的问题，则表示解l的多个目标值均小于或等于解b对应的目标值，且解l至少有一个目标值小于解b。

选择NSGA-Ⅱ[36]和SPEA2[37]作为对比算法，这两种算法是求解多目标问题的经典算法，并具有较强的搜索能力。NSGA-Ⅱ的主要步骤包括非劣解排序和拥挤距离计算;SPEA2的复制、交叉和变异与NSGA-Ⅱ类似，其主要特征体现在适应度赋值、个体密度值计算和外部档案维护。

NSGA-Ⅱ和SPEA2采用与DVNS相同的编码和解码方式，通过实验确定使NSGA-Ⅱ和SPEA2性能最好的交叉操作和变异操作：从8个邻域结构中选择5个邻域结构NSM1,NSM2,NSM3,NSS1,NSS2作为变异操作，对机器分配串和调度串分别执行两点交叉，而且交叉和变异按顺序进行。

3.2 参数设置

DVNS的参数为max_it和β。为了确定合适的参数，构建9种组合，其中max_it=5 000，60 000，70 000，β=9 000，10 000，12 000。通过一系列实验发现，max_it=60 000,β=10 000是使算法获得最佳结果的一组值。

NSGA-Ⅱ和SPEA2的参数包括种群规模N、交叉概率pc、变异概率pm、进化代数G。根据实验得到如下最合适的参数：N=100，pc=0.55，pm=0.02，G=600。

3.3 结果与分析

3种算法关于每个实例各自独立运行20次，其计算过程如图3所示，计算结果如表3和表4所示，表5所示为算法的计算时间。配对样本均值t检验的结果如表6所示，t-test(A,B)表示一次配对，用来判断算法A是否给出了优于B的样本均值，假设显著水平为0.05，若p-value<0.05，则说明算法A优于算法B。图4所示为实例5和实例32的非劣解分布图。

如表3所示，DVNS在指标DIR方面优势明显，DVNS在38个实例中的29个实例中所得的DIR均优于SPEA2和NSGA-Ⅱ，其中10个实例DVNS的DIR=0，表明这10个实例的参考解集Ω*全部由DVNS提供。另外，DVNS在13个实例中的DIR值至少比两个对比算法的对应值小10。

表3 3种算法关于指标DIR的计算结果

续表3

表4 3种算法关于指标C的计算结果

表5 3种算法的计算时间对比

续表5

表6 配对样本t检验

表4描述了指标C的计算结果，在27个实例中C(D,N)>C(N,D)，其中18个实例的C(N,D)=0，说明DVNS求解这些实例获得的非劣解不受NSGA-Ⅱ的任何解支配。对于28个实例来说，C(D,S)>C(S,D)，14个实例中C(D,S)=1，即SPEA2产生的所有解均受DVNS的非劣解支配。

如表6所示，4组t检验的p-value均为0，说明统计意义上DVNS的优势显著，表5的计算时间进一步表明DVNS可以在相似时间内获得更好的结果。因此，DVNS在求解具有SDST的DTHFSP时具有较大的优势。

4 结束语

DFSP和两阶段HFSP研究均取得了一定的进展，但是考虑SDST的DTHFSP研究还处于探索阶段，为此本文提出DVNS，以同时最小化总延迟时间和最大完成时间。根据DTHFSP的特征，将工厂分配和机器分配合并来降低子问题的数量。DVNS包括两个协同的变邻域结构，通过对邻域结构和全局搜索进行协调并对邻域结构进行合理配置，可以产生高质量的解。仿真实验表明DVNS在求解考虑SDST的DTHFSP方面具有较强的搜索优势。

随着经济全球化的发展，多工厂的生产模式越来越普遍，车间调度问题的复杂度越来越高，求解的难度不断加大，未来将进一步研究如何根据问题特性降低问题的复杂度；另外，为了满足实际加工环境的需要，如何解决更复杂的问题也是今后研究的方向。