1 引言
近年来，能源需求不断增加和环境影响日益突出，制造业正面临着巨大的环境挑战和经济压力，减少能源消耗、提升能源利用效率逐渐成为制造业关注的核心问题.在这种情况下，低碳生产调度问题应运而生，该问题旨在通过生产调度，最大限度地减少生产过程中的能源消耗和碳排放量，从而提升企业的能源利用效率，达到节能降耗的目的.
作为一种常见的制造车间类型，混合流水车间广泛存在于各个行业，如造纸、纺织、制药、化工和半导体制造业.它是传统流水车间调度与并行机调度的综合，并且要求至少有一个阶段存在两台或两台以上的并行机.加入这些并行机可以提高系统的性能，如引入柔性、提高生产能力和避免瓶颈等.
混合流水车间低碳调度以减少碳排放为目标，通常它可以分解为3个子问题：(1) 确定各工件的加工顺序；(2) 为工件分配合适的机器；(3) 确定工件在所分配机器上的加工速度. 3个子问题相互影响、相互制约，其中任意一个子问题的解的改变都会对最终的优化结果产生影响.该问题比一般的混合流水车间调度问题(HFSP)更复杂，属于NP-hard问题.
关于HFSP，现有研究主要关注时间目标[1-7]. Behnamian等[1]提供了一种三阶段混合方法以最小化最大完成时间和总提前或延迟时间.张其亮[2]提出一种混合粒子群求解算法以解决带阻塞限制的HFSP并最小化最大完成时间. Tran和Ng等[3]运用混合流水算法求解含有有限缓冲区和多目标的HFSP. Bozorgirad和Logendran[4-5]讨论了一个或多个阶段存在变速机的混合流水车间成组调度问题，并提出了4种基于禁忌搜索(TS)的解决方法.他们还比较了局部搜索算法和群体算法在求解考虑实际特征和双目标线性组合的HFSP的性能差异[5]. Su等[6]研究了以最小化最大完成时间和总延迟时间为目标的HFSP，并提出了分布协同进化算法. Lei[7]提出了一种两阶段邻域搜索算法以解决双目标HFSP.
考虑碳排放的HFSP研究以多目标为主，重点关注能耗或碳排放与延迟时间等指标之间的冲突关系. Dai等[8]在柔性流水车间环境下提出了一种遗传—模拟退火算法，研究了最大完成时间和总能耗之间的冲突关系. Luo等[9]针对考虑电力消耗成本的混合流水车间调度提出了一种新的蚁群优化. Lin等[10]建立了一种针对加工参数优化和流水车间调度的集成模型，提出了教—学优化算法以最小化最大完成时间和碳排放.
另外，现有研究还关注考虑碳排放或总能耗的流水车间[11-14]和作业车间[15-18]调度问题.杨海东等[11]以高效低碳为目标，研究了置换流水车间中的能效优化问题. Liu等[12]针对置换流水车间调度提出了一种分支定界算法以最小化总浪费能耗. Mansouri等[13]运用混合整数线性多目标优化模型和启发式算法解决了考虑最大完成时间和总能耗的双机流水车间调度. Ding等[14]运用两种多目标算法优化置换流水车间低碳调度的两种子问题：调度和速度选择. Lei和Guo[15]利用一种动态邻域搜索解决了具有区间加工时间和包括碳排放在内的双目标双资源作业车间调度.唐立力[16]提出了一种改进型候鸟优化算法以求解柔性作业车间低碳调度问题. Zhang等[17]运用结合改进局部搜索的多目标遗传算法解决了作业车间低碳调度问题.龙田等[18]研究了基于调度规则和免疫算法的作业车间多目标调度问题.
以上研究具有如下特点：(1) 目前关于HFSP的研究大多考虑最大完工时间、加权总完工时间等时间性指标；(2) 现阶段考虑碳排放或能耗的HFSP多与其他目标综合考虑，如探讨最大完成时间与碳排放之间的冲突关系，很少单独以碳排放或总能耗为目标对问题进行优化；(3) 考虑碳排放的HFSP还需要进一步深入研究，现有研究[8-10]中每台机器的速度是固定的，没有考虑机器存在多种加工速度的情形，速度选择子问题也未考虑，实际上，速度选择已在流水车间[14]和作业车间[17, 19]环境下得到优化，而机器存在多种加工速度的场合较多，例如文[19]描述的铸铁平板的加工机器存在5种切割速度，有必要考虑速度选择，即在工件的加工机器存在多种加工速度的条件下，选择其中一种.
本文研究以碳排放为目标的HFSP，与现有研究不同，每台并行机存在多种速度，因此，在工件排列和机器分配这两个子问题的基础上，增加了速度选择.选择不同的加工速度将影响每台机器加工模式运行时间长短，进而影响总碳排放量.本文提出了一种结合记忆和全局交换的邻域搜索(NSMG)，通过全局搜索和邻域搜索的有效协作，充分利用两种搜索的特点，以提高算法搜索效率和解的质量.通过大量的实例，将NSMG与改进的遗传—模拟退火算法(IGSA)[7]和变邻域搜索(VNS)进行了比较.实验结果表明，NSMG对所研究的问题具有良好的优化能力，取得了不错的优化结果.
2 问题描述考虑碳排放的HFSP可描述为：n个工件J1，J2，…，Jn按照相同的加工顺序依次进入m个加工阶段进行加工，m≥2.每个阶段k所有变速机的集合为Sk，至少有一个阶段，存在一台以上的变速机，机器Mkj∈Sk表示阶段k的第j台机器，j=1，2，…，|Sk|.假设每台变速机具有d种速度，速度集合为V={v1，v2，…，vd}，机器的加工速度在工件的加工过程中不能改变.在生产过程中，机器存在两种不同状态：工作状态和备用状态.机器Mkj∈Sk不加工工件时，处于备用状态，单位时间的该机器瞬时能耗为SPkj；当机器Mkj以速度vl加工时，工作状态下单位时间的能耗为PPkjl.
每个工件Ji在机器Mkj∈Sk上有一个给定的标准加工时间pijk，当工件Ji在机器Mkj∈Sk上以速度vl加工时，相应的实际加工时间pijkl等于pijk/vl.一个工件至少在一个阶段上加工，根据加工路径，它可能跳过其中一个或几个阶段.当工件Ji跳过阶段k时，它在阶段k的加工时间pijkl等于0.
关于pijkl和PPkjl的关系，Ding等[13]给出了一种假设，其描述如下：
如果一个工件Ji在机器上以一个更高的速度加工，它的加工时间将缩短但能耗上升.这意味着如果∀vl > vg，l，g∈{1，2，…，d}，则
|
(1) |
除了以上条件，还应满足如下约束：所有机器和工件从零时刻起可用；每个工件同一时刻只能在一台机器上加工；每台机器同一时刻只能加工一个工件；准备时间包含在加工时间内；工件在机器上的加工一旦开始，不容许中断；缓冲区大小没有限制；同一工件在两个阶段之间的加工不能重叠等.
问题的目标函数为总碳排放量(TEC)：
|
(2) |
|
(3) |
其中，TEC为总能量消耗，ε为能耗与碳排放量之间的转换系数，通常取0.755 9[20]. ykjl(t)和zkl(t)均为二进制变量.如果机器Mkj∈Sk在时间t以速度vl加工，则ykjl(t)等于1；否则ykjl(t)等于0.如果机器Mkj∈Sk在时间t处于备用状态，zkl(t)为1，否则为0.
速度选择影响每台机器处于加工状态的时间长短，机器分配和调度决定每台机器处于备用状态的时间，根据式(2) 和式(3)，综合考虑3个子问题，合理分配每台机器处于加工模式和备用模式的时间，进而降低TEC和TCE的值，达到降低总碳排放的目的.
3 基于NSMG的混合流水车间低碳调度针对问题的特点，提出了一种结合记忆和全局搜索的邻域搜索方法.
3.1 初始解关于HFSP，机器分配通常根据工件排列中工件的顺序[21]或者贪婪策略[22]进行；如上所述，现有研究未考虑速度选择子问题，这样将难以产生一些高质量的解.本文考虑3个子问题之间的相互影响，对3个子问题进行单独编码，这样可以针对每个子问题灵活设计邻域结构和全局交换方法.
针对具有n个工件m个加工阶段的HFSP，采用一个机器分配矩阵、一个速度选择矩阵和一个工件排列表示问题的解，如图 1所示，πi∈{1，2，…，n}，θik表示分配给工件πi用于阶段k加工的机器，ρik表示工件πi在所分配机器上的加工速度.
|
| 图 1 机器分配、速度选择及工件排列的示意图 Figure 1 Schematic diagram of machine assignment, speed selection and job sequence |
在机器分配矩阵中，第一行的m台机器用于工件J1总共m阶段的加工，第二行的m台机器用于工件J2所有阶段的加工，依此类推.速度分配矩阵中的元素与机器分配矩阵中的元素一一对应，第一行的m种速度表示工件J1在各阶段所分配机器上的加工速度，第二行的m种速度表示工件J2在各阶段所分配机器上的加工速度，依此类推.
初始解是随机产生的，其解码过程如下：根据工件排列{π1，π2，…，πn}，首先安排工件π1在阶段k=1，2，…，m的机器θπ1k上以速度ρπ1k加工，然后安排工件π2在阶段k=1，2，…，m的机器θπ2k上以速度ρπ2k进行加工，依此进行，直到所有工件加工完毕为止.
3.2 邻域结构与全局交换在NSMG中，邻域结构和全局交换是产生新解的主要途径.本文定义了4种邻域结构，其中两种用于改变工件排列，第3种为选中的工件产生新的机器分配，最后一种用于改变被选中机器的加工速度.
针对当前解x的工件排列为{π1，π2，…，πn}，第一种邻域结构swap的描述如下：随机选择一对工件πi和πj(i≠j)并将它们交换.邻域结构insert定义如下：随机选择一个工件πi和一个位置j，将工件πi插入到位置j.
对于当前解x的机器分配矩阵，邻域结构change用来产生新的机器分配，其描述为：首先从矩阵中随机选择一个元素θik，根据元素所在的行和列确定它所对应的工件Ji和阶段k，然后从阶段k的机器集合中，随机选择一台能加工Ji的机器替代θik.
对于当前解x的速度选择矩阵，邻域结构select为工件在机器上的加工确定新的加工速度，其描述如下：首先从矩阵中随机选择一个元素ρik，找到机器分配矩阵对应的θik，从θik所有可能的加工速度中随机选择一种替代ρik.
通常邻域搜索只利用一个当前解，而全局交换往往在两个不同解之间进行，为了进行全局交换和保留精英解，本文利用记忆Ω保留NSMG搜索过程中碳排放最小的一部分解.
全局交换通过随机选择的y∈Ω和当前解x之间的信息交换产生新解.本文提出了3种全局交换策略.
第1种针对x和y的工件排列，其描述如下：随机选择一个成员y∈Ω，然后再随机决定两个位置1≤l < h≤n，x中位于l和h之间的工件保持不变，x中位于k < l或k > h的工件用y∈Ω的工件按顺序代替，这些工件与x中位于l和h之间的工件不同.针对10个工件问题的工件排列的全局交换操作如图 2所示.
|
| 图 2 工件排列的全局交换 Figure 2 Global exchange on job permutation |
第2种针对两个解的机器分配矩阵，其描述如下：对于x和y∈Ω，随机确定工件πl和πh(l < h)所对应的两行以及两列kl和kh，并将x的机器分配矩阵中位于第l行kl列之后所有元素、第h行kh列之前的所有元素以及两行之间的所有元素，用y的机器分配矩阵中对应位置上的元素替代.图 3给出了第2种全局交换的一个实例.
|
| 图 3 机器分配矩阵的全局交换 Figure 3 Global exchange of machine assignment matrix |
第3种针对两个解的速度选择矩阵，其过程与第2种类似，对于x和y∈Ω，随机确定工件πl和πh(l < h)所对应的两行以及两列kl和kh，并将x的速度选择矩阵中位于第l行kl列之后所有元素、第h行kh列之前的所有元素以及两行之间的所有元素，用y的速度选择矩阵中对应位置上的相应元素替代.显然，上述全局交换中y≠x；否则就没有意义.
执行全局交换操作时，产生一个随机数s，若s < α，采用第1种全局交换操作；否则分别执行第2种和第3种.其中α为执行第1种全局交换操作的概率，s为[0, 1]上均匀分布的随机数.
在解x上实施邻域结构或全局交换产生新解z.如果解z的总碳排放量小于等于x，z成为新的当前解；否则，当前解仍为x.设记忆的最大容量为N，初始记忆由N-1个随机产生的解和初始的当前解组成，在搜索过程中记忆的容量始终为N，这样可以简化记忆的更新过程并确保执行全局交换时至少可选出一个解y≠x.
记忆更新过程如下：当前解被新解替代后，将x与记忆中的解进行比较，若x能替代Ω中最差解，则直接替代，每次最多替代记忆中的一个解.从上述过程可以看出，精英解一定保留在记忆中.
3.3 算法描述NSMG的详细过程如下所示：
Step 1 随机产生一个初始解x并构造一个初始记忆Ω，t=1，k=1.
Step 2 如果k=1，2，3，4，则随机产生一个新解z∈Nk(x)；如果k=5，解x通过全局交换产生新解z.
Step 3 判断当前解x能否被z替代，若x被替代，则更新记忆Ω；否则k←k+1，如果k=6，令k←1.
Step 4 t=t+1，如果t < itmax，转到步骤(2)；否则终止搜索.
Step 5 输出记忆中的精英解.
其中，N1，N2，N3，N4分别表示swap，insert，change和select. Ni(x)表示对解x执行Ni得到的邻域解的集合，itmax为最大迭代次数.
与模拟退火和TS等算法不同，NSMG有如下新特征：
(1) 记忆用来保留搜索过程中产生总碳排放量最少的解，记忆的目的是为全局交换提供合适解并保留精英解.
(2) 考虑了全局搜索与邻域搜索的协作以有效地提高NSMG的搜索能力.
4 计算实验为了测试NSMG的性能，运用一系列实例进行了大量的实验.所有实验在Microsoft Visual C++6.0实现，程序运行环境为4.0 G RAM，2.50 GHz CPU的个人计算机.
4.1 测试实例和对比算法考虑具有n=20，30，40，50，60，80，90，100，120和m=5，8，10的27个实例，这些实例的数据如表 1所示.
本文选择IGSA[8]和VNS作为对比算法.为了解决本文所考虑的HFSP，对IGSA做如下扩展：由于原算法没有对速度选择进行编码，所以添加速度选择矩阵，并对速度选择矩阵采用两点交叉，具体过程与第3种全局交换类似，邻域结构select作为变异操作.
VNS作为一种元启发式算法，已成功地用于解决各种调度问题，并显示出较强的搜索性能[23-24]，为此，利用3.2小节所描述的4种邻域结构构造VNS，其具体描述如下：
Step 1 随机产生一个初始解x.
Step 2 重复如下过程直到达到最大迭代次数，随机产生一个新解z∈Nk(x)，若x和z满足3.2小节所述的条件，则z替代x，k←1，否则k←k+1，若k=5，则k←1.
4.2 结果分析NSMG具有3个参数：α，itmax和记忆容量N.根据大量实验，获得如下的参数：α=0.5；若n≥100，itmax=8×104，否则itmax=5×104；N=10.
VNS迭代次数与NSMG完全相同.
对于IGSA，基于大量实验得到如下参数：最大遗传代数为itmax/100，种群规模为100，交叉概率为0.8，变异概率为0.1.模拟退火的参数采用Dai等[7]给出的设置.
评价指标为相对百分比偏差(RPD)，RPD=100(f-f*)/f*，f*为3种算法获得的最好解.为了更好地比较NSMG、VNS及IGSA，每种算法对每个实例随机运行20次.表 2~表 4显示了3种算法的的计算结果.其中ARPD表示20组RPD的平均值，XRPD和NRPD表示在20次运行中得到的最大RPD和最小RPD.
|
对结果进行了统计分析，表 5描述了NSMG，VNS和IGSA的配对样本t检验结果.表中“t-检验(A，B)”表示A与B之间的一个配对t检验，用来判断算法B是否比算法A提供了一个更好的样本均值.假设显著水平为0.05，如果p-值小于0.05表明在统计意义上A的性能优于B.
为了更直观地描述3种算法的迭代过程，图 4描述了3种算法关于实例50×8的收敛曲线.
|
| 图 4 NSMG，IGSA与VNS关于实例50×8的收敛曲线对比 Figure 4 Comparison of the convergence curves among NSMG, IGSA and VNS on case 50×8 |
如表 2所示，NSMG关于24个实例获得了优于VNS的XRPD，NSMG所获得的最差解明显优于IGSA的相应解.表 3的结果显示，NSMG获得了所有实例的最好解，而VNS和IGSA未获得任何实例的最好解.从表 4可以看出，NSMG的平均性能也优于VNS和IGSA.图 4的结果也显示NSMG的优良性能.
NSMG的优良性能主要在于它引入了全局交换以及全局搜索和邻域搜索的协作.而VNS缺乏全局搜索和邻域搜索很好的协调，从而导致它的性能较差. IGSA结合了全局搜索和局部搜索，结果显示它这种分阶段的结合方式明显不如NSMG中的结合方式有效.综上所述，NSMG是解决以碳排放为目标的HFSP一种有竞争力的方法.
5 结论混合流水车间低碳调度问题研究具有非常重要的现实意义.本文针对以碳排放为目标的HFSP，在对其3个子问题单独编码后，运用一种新的邻域搜索算法NSMG对问题进行求解.该算法运用记忆保留搜索过程中的最优解，并通过全局交换与邻域搜索协作提高解的质量.最后，通过实例验证了NSMG算法的有效性和可行性.
全局搜索和邻域搜索的融合可能是一个很好的思路.我们仍将关注全局搜索和邻域搜索的新的结合策略，并应用新算法解决各种调度问题.同时为了满足严格的环保要求，将继续深入研究节能或低碳调度问题.
| [1] | Behnamian J, Fatemi-Ghomi S M T, Zandieh M. A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic[J]. Expert Systems with Applications, 2009, 36(8): 11057–11069. DOI:10.1016/j.eswa.2009.02.080 |
| [2] |
张其亮, 陈永生.
带有阻塞限制的混合流水车间调度问题的混合粒子群求解算法[J].信息与控制, 2013, 42(2): 252–257.
Zhang Q L, Chen Y S. Hybrid particle swarm optimization algorithm for hybrid flow shop scheduling problem with blocking[J]. Information and Control, 2013, 42(2): 252–257. |
| [3] | Tran T H, Ng K M. A hybrid water flow algorithm for multi-objective flexible flow shop scheduling[J]. Engineering Optimization, 2013, 45(4): 483–502. DOI:10.1080/0305215X.2012.685072 |
| [4] | Bozorgirad M A, Logendran R. Bi-criteria group scheduling in hybrid flowshops[J]. International Journal of Production Economics, 2013, 145(2): 599–612. DOI:10.1016/j.ijpe.2013.05.015 |
| [5] | Bozorgirad M A, Logendran R. A comparison of local search algorithms with population-based algorithms in hybrid flow shop scheduling problems with realistic characteristics[J]. International Journal of Advanced Manufacturing Technology, 2016, 83(5/6/7/8): 1135–1151. |
| [6] | Su S, Yu H J, Wu Z H, et al. A distributed co evolutionary algorithm for multi objective hybrid flowshop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2014, 70(1/2/3/4): 477–494. |
| [7] | Lei D M. Two-phase neighborhood search algorithm for two-agent hybrid flow shop scheduling problem[J]. Applied Soft Computing, 2015, 34(C): 721–727. |
| [8] | Dai M, Tang D B, Giret A, et al. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J]. Robotics and Computer-Integrated manufacturing, 2013, 29(2): 418–429. |
| [9] | Luo H, Du B, Huang G Q, et al. Hybrid flow shop scheduling considering machine electricity consumption cost[J]. International Journal of Production Economics, 2013, 146(2): 423–439. DOI:10.1016/j.ijpe.2013.01.028 |
| [10] | Lin W W, Yu D Y, Zhang C Y, et al. A multi-objective teaching-learning-based optimization algorithm to scheduling in turning process for minimizing makespan and carbon footprint[J]. Journal of Cleaner Production, 2015(101): 337–347. |
| [11] |
杨海东, 郑庆仁, 刘国胜, 等.
基于差分遗传算法的置换流水车间低碳调度模型[J].中南大学学报:自然科学版, 2013, 44(11): 4554–4560.
Yang H D, Zhen Q R, Liu G S, et al. Low-carbon scheduling in permutation flow shop problem by differential genetic algorithm[J]. Journal of Central South University: Science and Technology, 2013, 44(11): 4554–4560. |
| [12] | Liu G S, Zhang B X, Yang D D, et al. A branch-and-bound algorithm for minimizing the energy consumption in the PFS problem[J]. Mathematical Problems in Engineering, 2013(2): 388–400. |
| [13] | Mansouri S A, Aktas E, Besikc U. Green scheduling of a two-machine flowshop: Trade-off between makespan and energy consumption[J]. European Journal of Operational Research, 2016, 248(3): 772–788. DOI:10.1016/j.ejor.2015.08.064 |
| [14] | Ding J Y, Song S J, Wu C. Carbon-efficient scheduling of flow shops by multi-objective optimization[J]. European Journal of Operational Research, 2016, 248(3): 758–771. DOI:10.1016/j.ejor.2015.05.019 |
| [15] | Lei D M, Guo X P. An effective neighborhood search for scheduling in dual resource constrained interval job shop with environmental objective[J]. International Journal of Production Economics, 2015, 159(1): 296–303. |
| [16] | 唐立力. 求解低碳调度问题的改进型候鸟优化算法[J/OL]. 计算机工程与应用, 2016, 52(17): 166-171. Tang L L. Improved migrating birds optimization algorithm to solve low-carbon scheduling problem[J/OL]. Computer Engineering and Applications, 2016, 52(17): 166-171. |
| [17] | Zhang R, Chiong R. Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption[J]. Journal of Cleaner Production, 2016(112): 3361–3375. |
| [18] |
龙田, 王俊佳.
基于调度规则和免疫算法的作业车间多目标调度[J].信息与控制, 2016, 45(3): 278–286.
Long T, Wang J J. Multi-target job-shop scheduling based on dispatching rules and immune algorithm[J]. Information and Control, 2016, 45(3): 278–286. |
| [19] | Fang K, Uhan N, Zhao F, et al. A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction[J]. Journal of Manufacturing Systems, 2011, 30(4): 234–240. DOI:10.1016/j.jmsy.2011.08.004 |
| [20] |
赵敏, 张卫国, 俞立中.
上海市能源消费碳排放分析[J].环境科学研究, 2009, 22(8): 984–989.
Zhao M, Zhang W G, Yu L Z. Carbon emissions from energy consumption in shanghai city[J]. Research of Environmental Sciences, 2009, 22(8): 984–989. |
| [21] | Ruiz R, Vazquez-Rodriguez J A. The hybrid flow shop scheduling problem[J]. European Journal of Operational Research, 2010, 205(1): 1–18. DOI:10.1016/j.ejor.2009.09.024 |
| [22] | Rashidi E, Jahandar M, Zandieh M. An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines[J]. International Journal of Advanced Manufacturing Technology, 2010, 49(9/10/11/12): 1129–1139. |
| [23] | Vanchipura R, Sridharan R, Subash-Babu A. Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time[J]. Journal of Manufacturing Systems, 2014, 33(1): 65–75. DOI:10.1016/j.jmsy.2013.07.003 |
| [24] | Chen Y Y, Cheng C Y, Wang L C, et al. A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems-A case study for solar cell industry[J]. International Journal of Production Economics, 2013, 141(1): 66–78. DOI:10.1016/j.ijpe.2012.06.013 |