考虑运输时间的分布式柔性作业车间绿色调度

张洪亮 徐公杰 鲍 蔷 潘瑞林

安徽工业大学管理科学与工程学院，马鞍山，243032

0 引言

在中国，制造企业消耗了全国50%以上的电能，并产生了至少26%的二氧化碳排放量[1]。通过研发节能设备或采用新的加工技术减小节能减排压力的方法通常需要大量的投入，而绿色调度能在不增加企业成本的情况下有效减少碳排放并提高能源效率[2]。

随着信息技术以及全球化的飞速发展，许多制造企业从传统的单工厂模式逐渐向能降低人工成本、提高生产效率[3]的分布式多工厂模式转变。分布式柔性作业车间调度问题(distributed flexible job shop scheduling problem，DFJSP)作为分布式车间调度问题的重要形式之一，重点关注多个柔性作业车间类型的工厂协同生产。现在对该问题的研究主要分为单目标DFJSP和多目标DFJSP。单目标DFJSP主要以完工时间为优化目标，对应研究中，GIOVANNI等[4]设计了一种包含局部搜索策略的遗传算法；LIU等[5]将概率融入实参数编码方法，设计了一种改进的遗传算法；吴锐等[6]提出一种改进的人工蜂群算法；MENG等[7]提出了4种混合整数线性规划模型和1种约束规划模型。对于多目标DFJSP，吴秀丽等[8]设计了一种改进的差分进化算法来优化总成本和提前/延期惩罚；LI等[9]设计了一种基于Pareto的混合禁忌搜索算法来优化完工时间、机器负荷和提前/延期惩罚。

上述研究存在以下不足：①要求同一工件的所有工序必须在同一工厂内完成，没有考虑工件在工厂之间的转移。实际上，分布式生产系统中，一些工件可能在不同的工厂加工。②要求工件在前道工序加工完成后立即执行下一道工序，忽略了工序之间的运输时间。实际上，工件在工序之间流转需要运输时间，且加工时间和运输时间之间有较强的耦合关系。③主要关注时间相关的目标且以单目标为主，没有考虑能耗相关的目标。随着绿色制造的推进，在生产调度决策中考虑与能耗相关的目标变得至关重要。

综上所述，考虑运输约束的DFJSP研究具有重要意义，尽管一些学者在单个工厂的车间调度问题中考虑了运输时间[1，10-13]，但考虑运输时间的DFJSP研究还很少。此外，尚未有学者在DFJSP的研究中考虑能耗相关目标。因此，本文以考虑运输时间的分布式柔性作业车间绿色调度问题(distributed flexible job shop green scheduling problem with transportation time，DFJGSPT)为研究对象，建立最小化完工时间和总能耗的混合整数规划模型，并设计一种改进的非支配排序遗传算法(improved non-dominated sorting genetic algorithm Ⅱ，INSGA-Ⅱ)。通过测试45个算例，以及与常用的多目标进化算法的对比来验证本文提出的INSGA-Ⅱ的有效性。

1 问题描述及数学模型

1.1 问题描述

DFJGSPT可以描述为：N个工件需要在F个类型为柔性作业车间的分布式工厂内进行加工。每个工件有ni道工序，每个工厂有Mf台机器。工件需要通过运输工具在工厂以及机器之间运输。工件的加工时间，工件在机器、工厂间的运输时间，以及机器的相关能耗信息已知。调度目标为最小化最大完工时间和总能耗。假设：①所有工件和机器0时刻可用；②每台机器同一时刻只能加工一道工序；③每个工件同一时刻只能在一台机器上加工；④不考虑中断情况；⑤同一工件不同工序之间有顺序约束；⑥有足够的运输工具完成工件的转移；⑦不考虑装卸载时间。

1.2 数学模型

基于以上描述可得DFJGSPT的数学模型：

minCmax=min(max(Ci))

(1)

minTEC=min(PE+TE+IE)

(2)

(3)

(4)

(5)

αilk+βifu≤1

(6)

cijkf=sijkf+pijkfxijkf

(7)

cijkf≥cghkf+pijkf-M(1-yijghkf)

(8)

(9)

(10)

(11)

式中，Cmax为最大完工时间；Ci为工件i的完工时间；TEC为总能耗；PE为所有机器的加工能耗；TE为所有运输任务的运输能耗；IE为所有机器的空闲能耗；xijkf为0-1决策变量，如果Oij在工厂f的机器k上加工，则xijkf为1，否则为0；F为工厂数量；Mf为工厂f中机器的数量；yijghkf为0-1决策变量，工厂f的机器k加工完Ogh后加工Oij，则yijghkf为1，否则为0；n为工件数量；ni为工件i的工序数量；αilk为0-1决策变量，如果工件i从机器l运送到机器k，则αilk为1，否则为0；βifu为0-1决策变量，如果工件i从工厂f运送到工厂u，则βifu为1，否则为0；cijkf为Oij在工厂f的机器k上的加工结束时间；sijkf为Oij在工厂f的机器k上的加工开始时间；pijkf为Oij在工厂f的机器k上的加工时长；M为一个足够大的正数；pekf为工厂f中机器k的单位加工能耗；iekf为工厂f中机器k的单位空闲能耗；fte为工厂之间的单位运输能耗；TTfu为工件从工厂f到工厂u的运输时间；mte为机器之间的单位运输能耗；ttlk为工件从机器l到机器k的运输时间；i、g为工件索引；j、h为工序索引；l、k为机器索引；f、u为工厂索引。

式(1)、式(2)为优化目标——最小化最大完工时间和最小化总能耗；式(3)保证每道工序只能在一个工厂的一台机器上加工；式(4)、式(5)表示每道工序的紧后或者紧前工序最多只有一道；式(6)确保每个工件不能同时在机器和车间之间进行运输；式(7)表示工序的完工时间等于开始时间加上加工时长；式(8)确保机器不能同时加工多个工件；式(9)～式(11)分别表示机器加工能耗、机器空闲能耗和运输能耗。

2 改进NSGA-Ⅱ

NSGA-Ⅱ是一种有效求解多目标优化问题的进化算法，但在求解多目标柔性作业车间调度问题时，存在早熟和易陷入局部最优的不足。本文针对DFJGSPT的特性，对NSGA-Ⅱ进行以下改进：①设计了同时考虑加工时间和能耗的初始化方法，以提高初始种群的质量；②设计了考虑运输时间的贪婪插入解码方法，将染色体转换为可行有效的调度方案；③采用多父代交叉和两点插入及随机选择的变异方式进行种群更新；④设计了一种变邻域搜索策略来提高Pareto前沿的质量。

2.1 基于工序和机器的双层编码

本文采用基于工序和机器的双层编码方式对染色体编码，工厂的分配则通过解码策略确定。以表1所示的数据为例，编码方案示例见图1。

表1 MODFJGSPT示例

图1 编码示例

2.2 考虑加工时间和能耗的种群初始化

本文设计了一种考虑加工时间和能耗的种群初始化方法：工序层的编码通过随机的方式产生；机器层编码通过设计的全局选择(globalselection，GS)、局部选择(local selection，LS)、随机选择(random select，RS)3种策略产生。参考文献[14]，通过全局选择、局部选择和随机选择产生的初始解数量比例设为6∶3∶1。种群初始化的伪代码如下。

算法1:种群初始化 ∥ Gr、Lr和Rr分别为通过全局选择、局部选择和随机选择所产生的初始解数量在种群占比,其值分别为0.6、0.3和0.11:采用随机的方式产生工序层的编码OS2:创建两个值为0的数组分别记录所有机器的加工时间PTk和加工能耗PEk(1≤k≤m)3:If n<=Nind*(1-Rr)4:随机选择一个工件i ∥每个工件只被选择一次5: For j=1 to ni6: TempPTk=pijk +PTk;TempPEk=pijk×pek + PEk(k∈K_use) ∥ K_use:Oij的可用机器集7: 根据TempPTk和TempPEk计算Pareto支配关系8: 选择具有非支配TempPTk和TempPEk的机器k的索引放入机器层编码MA中9: 更新PTk和PEk10: End For11: If n>Nind*Gr&&n <=Nind*(Gr+Lr)12: 将数组PTk和PEk的值设为013: End If14: 转到步骤5,直到所有作业都被选中一次15:Else16:采用随机的方式产生机器层编码MA17:End If

2.3 考虑运输时间的贪婪插入解码方法

通过编码建立了工件和机器的映射关系，为进一步确定工件在对应机器上的开工时间，本文设计了一种考虑运输时间的贪婪插入解码方法。首先通过机器编码确定工件所在的工厂，然后考虑运输时间并引入贪婪的思想，将工件尽可能地插入机器的空闲时段内，以减少机器的空闲时间和能耗，提高生产效率。解码方法的伪代码如下。

算法2:解码方法 ∥ TO:工序总数;ts/tf:第一个满足插入条件的空闲时间段的开始/结束时间1:NOMk=∅(k=1,2,…,m) %机器k上已经安排的工序数量2:For h=1 to TO3: Oij=OS(h)4: 获取Oij的加工机器k,pijk和运输到达机器k的时间ta5: If j==1 &&NOMk==∅6: sijk=0;cijk=sijk + pijk7: Else If j ～=1 &&NOMk==∅8: sijk=ta;cijk=sijk+pijk9: Else If j==1 &&NOMk～=∅10: Ins=find(IDk>=pijk)11: If Ins==∅12: sijk=max{TMk,ta};cijk=sijk+pijk13: Else14: sijk=ts;cijk=sijk+pijk15: End If16: Else If j ～=1 &&NOMk～=∅17: Ins=find(IDk>=pijk)18: NIns=find(tf-max{ts,ta} >=pijk)19: If NIns==∅20: sijk=max{TMk,ta};cijk=sijk+pijk21: Else22: sijk=max{ts,ta};cijk=sijk+pijk23: End If24: End If25: 更新机器k的空闲时间时段IDk、NOMk和TMk26:End For

2.4 多父代交叉操作

为了融合多父代的信息，获得更高质量的子代，并增加种群的多样性，本文采用多父代交叉方式[15]更新种群。工序层和机器层的交叉方式分别如图2、图3所示。

图2 工序层交叉

图3 机器层交叉

工序层交叉的步骤如下：

(1)随机选择父代个体P1、P2和P3；

(2)将工件索引集合Job={1，2，…，n}随机划分为2个互不包含的集合Job1和Job2；

(3)将P1中包含集合Job2的元素复制到子代C1，将P3中包含集合Job1的元素复制到子代C1；

(3)将P2中包含集合Job1的元素复制到子代C2，将P3中包含集合Job2的元素复制到子代C2。

机器层交叉的步骤如下：

(1)随机选择父代个体P1、P2和P3；

(2)随机产生一个长度与工序总数一致且由 0、1 组成的集合R；

(3)在P2和P3中随机选出与R中的1位置对应的编码，复制到子代C1中的相应位置上；

(4)在P1和P3中随机选出与R中的1位置对应的编码，复制到子代C2中的相应位置；

(5)将P1和P2中其他的编码分别保留到子代C1和C2中。

2.5 变异操作

对工序层和机器层编码分别采用不同的变异方式：①工序层，采用两点插入变异方式，随机选择2个互不相邻的位置l1和l2(l1

图4 工序层变异

2.6 变邻域搜索

为进一步提高个体的质量，本文设计了一种用于Pareto前沿的变邻域搜索策略。通过以下两种邻域结构获得新解：①随机选择工序层编码方案的2个位置，将这2个位置之间的编码进行翻转；②获取运输时间最长的2道相邻工序，将后一道工序换到另一台运输时间短的机器上进行加工。如果新解更优，则更新。

2.7 算法整体步骤

INSGA-Ⅱ的主要步骤如下：①初始化参数，产生初始种群；②交叉变异产生子代；③解码并对种群进行非支配排序；④对Pareto前沿进行变邻域搜索；⑤通过对非支配排序和拥挤距离计算，获得下一代种群；⑥如果满足终止条件则输出Pareto前沿，否则转到②。

3 实验分析

本文算法基于MATLAB语言实现，并在Intel CPU E3-1240 V5、8 GB RAM的电脑上运行。

3.1 算例生成及评价指标

鉴于目前尚没有DFJGSPT测试算例，本文对文献[16]中的基准算例进行拓展，生成了45组测试算例。具体方式如下：对每个基准算例分别考虑2、4和6个工厂的场景，工厂内机器间的运输时间在[1，5] min内随机产生，工厂间的运输时间在[10，15] min内随机产生。机器单位加工能耗pek∈[10，15]kW，机器单位空闲能耗iek∈[1，3] kW，机器间的单位运输能耗mte=2 kW，工厂间的单位运输能耗fte=5 kW。采用多目标优化问题中广泛应用的覆盖率C[3]和反世代距离IGD[17]评估算法性能，具体含义和公式如下：

(12)

(13)

式中，A、B分别为需要对比的两种算法的Pareto前沿；|B|为集合B的大小；|PF*|为第一前沿的非支配解集PF*的大小；d(x，y)为x点与y点之间的欧氏距离。

C(A，B)越大，A越好；IGD(A，PF*)越小，A越好。在本文研究中，各实例的PF*由每一种算法运行10次得到的非支配解集综合形成。

3.2 算法参数

本文提出的INSGA-Ⅱ有4个参数：种群规模(Nind)、交叉率(Pc)、突变率(Pm)和最大迭代次数(Maxit)。为保证参数设置的合理性，参考文献[13]，采用正交试验确定最佳的参数组合。每个参数选择4个水平，各个水平的值如表2所示。根据参数和水平的个数，选择L16(45)正交表进行试验。针对算例Mk2-01，算法在每种参数组合下运行10次，以IGD作为各种参数组合的评价指标，计算结果如表3所示。

表2 参数水平表

表3 正交试验表

根据表3的结果绘制出参数水平的趋势，见图6。可知，当Nind为第一水平、Pc为第四水

(a)Nind的水平趋势图

平、Pm为第二水平、Maxit为第三水平时，IGD最小。因此，最终确定的参数组合为Nind=50，Pc=0.9，Pm=0.1，Maxit=300。

3.3 改进策略的有效性

为验证本文设计的种群初始化策略和变邻域搜索策略的有效性，本文将INSGA-Ⅱ(A1)与采用随机初始化策略的INSGA-Ⅱ(A2)和不包含变邻域搜索策略的INSGA-Ⅱ(A3)进行对比。

参考文献[7]，以Mk01、Mk04、Mk09、Mk12和Mk15在不同工厂数下对应的15组算例为测试算例，对这3种算法进行测试。每种算法运行10次，采用C和IGD比较算法的性能。在15组算例测试结果中，C(A1，A2)=C(A1，A3)=1，C(A2，A1)=C(A3，A1)=0，说明算法A1可以获得更优的Pareto解集。此外，IGD(A1)均为0，IGD(A2)、IGD(A2)如表4所示，可以看出IGD(A1)远小于IGD(A2)和IGD(A3)，进一步表明算法A1获得的Pareto解集更优。测试结果可以证明本文设计的种群初始化策略和变邻域搜索策略的有效性。

表4 改进策略测试结果

3.4 与其他算法对比分析

为进一步验证本文算法的有效性，将其与以被广泛应用的多目标优化算法NSGA-Ⅱ、SPEA2和MOEA/D进行对比。对比算法的参数设置与INSGA-Ⅱ相同，其中，SPEA2和MOEA/D的外部存档大小设置为种群大小。每个算法运行10次，采用C和IGD比较算法的性能。所有算例下，C(INSGA-Ⅱ，NSGA-Ⅱ)=C(INSGA-Ⅱ，SPEA2)=C(INSGA-Ⅱ，MOEA/D)=1，C(NSGA-Ⅱ，INSGA-Ⅱ)=C(SPEA2，INSGA-Ⅱ)=C(MOEA/D，INSGA-Ⅱ)=0，这表明INSGA-Ⅱ得到的解优于另外3种算法得到的解。IGD(INSGA-Ⅱ)均为0，另外3种算法的IGD如表5所示，可以看出，IGD(INSGA-Ⅱ)远小于IGD(NSGA-Ⅱ)、IGD(SPEA2)和IGD(MOEA/D)，这与C值结果相互对应。此外，随着工厂数量的增加，IGD(NSGA-Ⅱ)、IGD(SPEA2)和IGD(MOEA/D)增大，而IGD(INSGA-Ⅱ)不变，这说明INSGA-Ⅱ能解决不同规模的分布式柔性作业车间调度问题。

表5 平均IGD值

本文设计的INSGA-Ⅱ之所以能够获得更优的解，主要因为：①考虑加工时间和能耗的初始化方法能产生更高质量的初始种群。该方法采用了新的全局和局部选择策略来产生机器层编码，均衡加工时间和能耗，同时，为提高种群多样性，应用随机选择方式产生部分机器层编码。②考虑运输时间的贪婪插入解码方法通过将工件插入机器的空闲时间内，合理地安排工件在机器上的加工顺序，能压缩机器的空闲时间，进而提高生产效率、降低能耗。③多父代交叉操作可以融合多父代的信息，获得更高质量的子代；新的变异操作不仅避免了算法陷入局部最优，并且增加了种群的多样性。④变邻域搜索策略能进一步提高Pareto前沿的质量，该策略的嵌入增强了算法的局部搜索能力。为了进一步展现本文算法的性能，以算例Mk2-01、Mk2-04、Mk2-09、Mk2-12和Mk2-15为例，绘制4种算法一次求解得到的Pareto前沿分布。

由图7可以看出，本文算法Pareto前沿均在另外3种算法Pareto前沿的左下方，表明本文算法可以得到更优的Pareto前沿，这与上文的C和IGD评价指标计算结果相符。Pareto前沿分布图进一步表明INSGA-Ⅱ能有效解决考虑运输时间的分布式柔性作业车间绿色调度问题。

(a)Mk2-01 (b)Mk2-04

图8～图15所示为MOEA/D、NSGA-Ⅱ、SPEA2和INSGA-Ⅱ对算例Mk2-09求解得到的调度方案，可以看出，INSGA-Ⅱ调度方案的完工时间最短，并且机器的总空闲时间明显也短于另外3种调度方案，这意味着INSGA-Ⅱ可以提高机器的利用率，进而提高生产效率、减少能源消耗。

图8 Mk2-09的MOEA/D调度方案(工厂1)

图9 Mk2-09的MOEA/D调度方案(工厂2)

图10 Mk2-09的NSGA Ⅱ调度方案(工厂1)

图11 Mk2-09的NSGA Ⅱ调度方案(工厂2)

图12 Mk2-09的SPEA2调度方案(工厂1)

图13 Mk2-09的SPEA2调度方案(工厂2)

图14 Mk2-09的INSGA Ⅱ调度方案(工厂1)

图15 Mk2-09的INSGA Ⅱ调度方案(工厂2)

4 结论

(1)本文研究了考虑运输时间的分布式柔性作业车间绿色调度问题，建立了最小化最长完工时间和总能耗的混合整数规划模型。

(2)提出了一种改进的快速非支配排序遗传算法，通过基于工序和机器的双层编码方式、考虑运输时间的贪婪解码方法、考虑加工时间和能耗的种群初始化方法、多父代交叉和变异操作及变邻域搜索策略来提高算法的寻优能力。

(3)设计了多组考虑运输时间的分布式柔性作业车间绿色调度问题的测试算例，实验结果表明本文设计的算法能够有效解决该问题。

本文假设运输工具无限，没有考虑运输资源的分配，因此，在未来的研究中将考虑运输资源的分配和机器故障等实际因素。此外，将进一步提炼分布式车间调度的启发式策略，以更好地提高算法性能。