新型蛙跳算法求解总能耗约束FJSP

杨冬婧 雷德明

武汉理工大学自动化学院，武汉，430070

0 引言

柔性作业车间调度问题(flexible job shop scheduling problem,FJSP)是经典作业车间调度问题(job shop scheduling problem,JSP)的延伸，每个工件的每道工序都可以在给定机器集中的任一机器上进行加工，比JSP更接近实际生产，具有灵活性。FJSP是典型的NP-hard问题[1]，在汽车装配、纺织、化工材料加工以及半导体制造等方面得到了广泛的应用。自BRUKER等[2]首次研究FJSP以来，出现了大量的相关研究成果。目前，智能算法已广泛应用于各类FJSP的求解，其中关于多目标FJSP，在KACEM等[3]提出基于遗传算法(genetic algorithm,GA)和局部方法的混合算法之后，研究者大量应用GA[3-7]、粒子群算法[8-9]、人工蜂群算法[10]、禁忌搜索[11-12]、变邻域搜索(varible neighborhood search,VNS)[13]、帝国竞争算法[14]和分布估计算法[15]等求解FJSP。近年来，低碳制造和低碳生产调度受到工业界和学术界的广泛关注。关于低碳FJSP，LIU等[7]运用GA求解双目标低碳FJSP。TANG等[16]考虑FJSP的能耗并运用遗传模拟退火算法对问题进行求解。HE等[17]提出了一种节能优化算法，它通过机床选择来减少机器加工能耗和操作序列调整来减少机器闲置时的能源浪费。PIROOZFARD等[18]提出了一种多目标遗传算法(multi-objective genetic algorithm,MOGA)，同时最小化碳排放量和总拖期。蒋增强等[19]提出了基于血缘变异的改进非劣排序遗传算法NSGA-Ⅱ[20]。唐立力[21]提出了一种改进型候鸟优化算法。YIN等[22]运用MOGA来求解具有产能、能源效率和噪声减少等目标的FJSP。LEI 等[23-24]分别利用一种新型蛙跳算法(shuffled frog leaping algorithm,SFLA)和一种新的教学优化算法求解低碳FJSP。

如上所述，尽管低碳FJSP研究取得了一些进展，但其研究仍不够深入。例如，对于总能耗约束FJSP，该问题中总能耗不是目标函数，总能耗只需不超过给定的阈值即可。由于总能耗约束经常无法得到满足，故需要根据问题的特点采用新策略对问题求解。作为一种模拟青蛙活动的智能算法，SFLA已成功应用于车间布局[25]、装配序列规划[26]、电网规划[27]、旅行商问题[28]和生产调度[29]等方面，但它在低碳FJSP方面的应用[29]还不充分。根据SFLA概念简单、参数少、计算速度快且全局寻优能力强等特点和相关应用[30]，有必要探索SFLA在求解低碳FJSP方面的搜索优势，为问题的解决提供新的途径。对于所研究的总能耗约束FJSP，由于该问题的能耗约束经常无法得到满足，为了有效地解决该问题，本文首先将问题转化为两目标FJSP，以简化对能耗约束的处理；然后在模因组构建新策略、模因组搜索新过程以及模因组最好解的强化搜索基础上，构建一种新型SFLA以直接优化两目标FJSP；最后，选择MOGA[18]和VNS[13]作为比较算法，通过大量仿真实验，验证新型SFLA的搜索性能和优势。

1 问题的描述

总能耗约束FJSP描述如下：存在n个工件的工件集J={J1,J2,…,Jn}和m台机器的机器集M={M1,M2,…,Mm}，工件Ji具有hi道工序，工序oij为工件Ji的第j道工序，该工序可由相容机器集Sij中的任何一台机器加工，Sij⊂M。每台机器具有d种速度，速度集合V={v1,v2,…,vd}。每个工件在加工过程中，机器加工速度一旦确定就不能改变。机器Mk∈M具有两种状态：加工状态和空闲状态。当机器Mk不加工工件时，处于空闲状态，该机器单位时间能耗为Ek；当机器Mk以速度vl加工时，加工模式下单位时间能耗为Ekl。每道工序oij在机器Mk上有一个给定的标准加工时间ηijk，当工序oij在机器Mk∈M上以速度vl加工时，相应的加工时间pijkl=ηijk/vl。关于pijkl与Ekl的关系，DING等[31]提出以下假设：加工速度变快，则加工时间变短，能耗增大。

存在一些与机器和工件相关的约束，包括：不同工件的工序之间没有先后关系的约束；同一时刻一台机器最多只加工一道工序；同一时刻一个工件最多只能在一台机器上加工且加工过程不可中断；准备时间和清理时间包含在加工时间内，等等。另外，考虑总能耗约束ETC≤QEC，其中，ETC为总能耗，QEC为总能耗阈值，有

(1)

其中，yijkl(t)为二进制量，如果在时刻t机器Mk∈Sij处于加工状态，则yijkl(t)=1；否则，yijkl(t)=0。如果机器Mk在时刻t处于准备状态，则zk(t)=1；否则，zk(t)=0。Cmax为最长完成时间。

总能耗约束FJSP包括调度子问题、机器分配子问题和速度选择子问题，其中，速度选择子问题是确定工件在所分配机器上的加工速度，其目的是在所有约束满足的条件下，最小化如下目标函数：

(2)

其中，Ci、Di分别为工件Ji的完成时间和交货期；目标函数f为总延迟时间。

上述机器和工件的相关约束，在解码时都能得到满足，而总能耗约束往往难以满足，需要单独处理总能耗约束。目前约束处理的方法很多[32]，其中最常见的方法包括多目标法[33]，该方法将单目标约束优化问题转化为双目标问题，其中一个目标为原问题的目标函数，另一个目标为约束违背程度。因此，采用多目标法处理总能耗约束问题，但新增的目标不是约束违背程度，而是直接将总能耗作为新的目标。

2 蛙跳算法描述

SFLA[34]中，青蛙的位置即问题的解x，虚拟青蛙的集合即为可能的解的集合，将这些青蛙均分为若干个小组，这些小组称为模因组，对每个模因组执行搜索过程，当每个模因组达到指定的迭代次数后，将它们结合成新的种群，这个过程称为种群重构。模因组搜索和种群重构循环进行直到终止条件得到满足。

SFLA的步骤如下：①初始化以下参数：模因组个数s，种群规模N。②产生初始种群P。③对种群中的解按适应度值降序排序，将种群划分为s个模因组。④对每一个模因组执行搜索过程。⑤对进化后的模因组执行种群重构。⑥如果终止条件得到满足，则输出最优解；否则转到步骤③。

将种群划分为s个模因组的过程如下：将第1只青蛙分入第1个模因组，第2只青蛙分入第2个模因组，第s只青蛙分入第s个模因组，第s+1只青蛙分入第1个模因组，依此类推。

(3)

式中，R为区间[0,1]上服从均匀分布的随机数。

(4)

3 新型SFLA

对于总能耗约束FJSP，除能耗约束之外的其他约束(如同一时刻一台机器最多只加工一道工序)在智能算法的解码过程中都可以得到满足，只有能耗约束经常无法得到满足。针对这类约束优化问题，为了处理总能耗约束，将总能耗约束从原问题中剔除，同时增加第2个目标g=ETC，将原问题转化为具有f、g的双目标FJSP，然后应用新型SFLA对转化后的FJSP进行求解，则在算法优化过程中，无需处理能耗约束，简化了对能耗约束的处理。

3.1 编码方式与初始化

调度串中,θi∈{1,2,…,n},1≤ri≤hθi,二元组(θi,ri)对应工序oθiri，这样整个串对应一个有序工序表[oθ1r1,oθ2r2,…,oθiri,…oθhrh]。机器分配串中，基因ρij∈Sij表示用于加工工序oij的相容机器。第3个串中，uij为ρij加工oij时的速度。上述编码方法能保证除总能耗约束ETC≤QEC之外的其他约束总是成立，但无法保证能耗约束总是成立。

随机生成初始种群，确定算法参数：种群规模、模因组个数、最大迭代次数，令ρi=1,∀i=1,2,…,N。

3.2 模因组的构建

非劣排序根据Pareto支配对种群内的所有解进行比较。Pareto支配是多目标优化的基本概念，假设优化问题的目标总数为G且都是最小化目标，如果解x和y满足∀i∈{1,2,…,G},fi(x)≤fi(y)且∃i∈{1,2,…,G},fi(x)

与现有模因组构建方法[29,35]不同，上述过程首先为模因组分配一个最好解和最差解，然后顺序分配剩余的解。由于转化后的问题为双目标FJSP，上述构建过程可以让组成各模因组的解具有相近的收敛程度，有助于各模因组在搜索过程中同步改进，从而提高搜索效率。

3.3 模因组搜索

模因组搜索是SFLA产生新解的主要方式，通常以组内的最差解xw为优化对象，也有文献以组内的最好解xb为搜索对象[35]，现选择一种新的优化对象。

步骤⑤中的全局搜索过程如下：产生随机数R，如果R<0.7，则利用两个解的调度串交叉产生新解；如果0.7≤R<0.85，则执行机器分配串的交叉操作；如果R≥0.85，则通过速度选择串交叉获得新解。步骤⑥的全局搜索过程如下：产生随机数R，如果R<0.8，则对y与x的调度串进行交叉，否则对两个解的机器分配串执行交叉。上述2个步骤中，0.7、0.8、0.85三个数根据实验确定，交叉操作作用在两个解x和xb(y)之间，3种交叉操作的具体描述见文献[29]，和文献[29]一样，每次交叉只产生一个解，在交叉过程中，xb(y)保持不变。

采用4种邻域结构产生新解。根据调度子问题复杂性更高的特点，给出了两种邻域结构。邻域结构insert用于改变解x的调度串[(θ1,r1),(θ2,r2),…,(θi,ri),…,(θh,rh)]，首先随机确定一个元素(θj,rj)和一个位置k≠j，并将元素(θj,rj)插入新位置；然后重新确定所有ri以得到新的调度串。邻域结构swap通过互换一些二元组和为每个θi重新确定新的ri来产生新解。邻域结构change用于改变部分被选中工序的机器分配。change的详细步骤如下：首先从机器分配串中随机选择ρij，它对应工序oij，确定可以加工该工序的所有机器集合Θ，从集合Θ中随机选择一台与ρij不同的机器替代ρij。邻域结构speed用于改变部分被选中机器的加工速度，其具体过程如下：首先从速度选择串中随机选择uij，它对应工序oij和加工机器ρij，从ρij的加工速度集合V中随机选择一档与uij不同的速度替代uij。令N1、N2、N3分别表示insert、change和speed,Ni(x)为执行Ni所产生的x的邻域解集。

外部档案Ω的更新过程如下：将新解加入集合Ω之后，对于集合内的所有解，根据目标f、g进行Pareto比较，保留非劣解，剔除受支配解。

3.4 局部搜索

若经过较多迭代次数的模因组搜索，组内的最好解始终无法得到改善，则将导致组内其他解与最好解的相似度增大，种群多样性下降，算法可能陷入局部最优，为此，对每个模因组的最好解执行局部强化搜索。

最好解质量较高，对其进行局部搜索产生更高质量解的可能性较大，这样可以利用最好解引导算法的搜索，避免算法陷入局部最优。

3.5 算法描述

改进算法的详细步骤如下：①初始化参数：模因组个数s，种群规模为N。②产生初始种群P。③对种群内的所有解进行非劣排序，确定每个解x受其支配的其他解的数量η。④将种群分为s个模因组。④对每一个模因组执行搜索过程。⑥对模因组内的最好解执行搜索过程。⑦对进化后的模因组执行种群重组。⑧如果满足终止条件，输出外部档案；否则转到步骤③。⑨剔除Ω中的非可行解，输出目标f最小的可行解。终止条件为最大目标估计次数max_it。

新型SFLA对由原问题转化后的两目标FJSP进行求解，而不是直接优化原问题，这样简化甚至避免了对总能耗约束的处理，另外，新算法采用新的策略构建模因组，选择新的优化对象和新方式进行模因组搜索，并加强对模因组的最好解的强化搜索，以上策略能有效地实现探索和利用之间的良好平衡，有助于算法获得高质量的解。

4 计算实验

(5)

其中，δ的值见表1。

表1 δ的设置

选用VNS算法[13]和MOGA[18]作为对比算法，这两种算法很容易应用于双目标低碳FJSP的求解。用文献[13]所设计的VNS算法来解决具有加权目标的FJSP，加入speed、外部档案更新策略和新旧解替换条件后，VNS算法可用于求解双目标FJSP。PIROOZFARD等[18]应用MOGA解决双目标低碳FJSP，将速度选择串交叉和speed作为变异加入后，该算法能够直接用来解决双目标FJSP。

通过大量计算实验，获得新型算法参数设置如下：N=40,s=5,max_it=105。MOGA[18]的参数设置如下：种群规模为100，交叉概率为0.7，变异概率为0.4，选择概率为0.45，终止条件也为max_it。关于VNS算法[13]，nmax=350由文献[13]给出，max_it与新型SFLA相同。对每个实例，随机运行10次，每次当目标函数估计次数达到30 000时，根据外部档案Ω中解的最大g值确定阈值QEC。

每个实例随机运行3种算法各10次，3种算法的运算结果见表2，3种算法的运算时间对比见表3， 3种算法的收敛曲线对比见图1。其中，关于总延迟时间，若外部档案或者MOGA的种群的非劣解都不可行，则选择违背约束程度最小的解的总延迟时间；否则，在可行的非劣解中选择总延迟时间最短的解。

表2 三种算法计算结果

表3 三种算法的运算时间

图1 三种算法关于实例mtxx和setb4xx的收敛曲线Fig.1 Convergence curves of three algorithms on mtxx and setb4xx

如表2所示，SFLA获得了16个实例的最好解，MOGA仅获得5个实例的最好解；另外，新型SFLA关于15个实例获得了优于MOGA的平均解，仅在最差解方面，新型SFLA优势不明显，关于实例11产生的最差解优于MOGA。新型SFLA的结果几乎全部优于VNS。如表3所示，新型SFLA与另两种算法的运算时间相近。SFLA的性能优于另外两种算法的主要原因在于该算法兼顾了全局搜索和局部搜索的协调和平衡，增强了算法性能，因此，新型SFLA是解决总能耗约束FJSP具有较强竞争力的算法。

5 结论

尽管FJSP已得到较充分的研究,但总能耗约束FJSP的研究相对较少,随着绿色制造和低碳制造的应用不断深入,需要进一步研究低碳FJSP。本文提出了一种新型SFLA，在总能耗不超过给定的阈值条件下最小化总延迟时间。将原问题转化为包括总能耗的两目标FJSP后，利用新型SFLA优化转化后的双目标FJSP。计算结果表明，新型SFLA具有较强的搜索性能和优势。未来将继续深入研究具有总能耗或峰值能耗约束的调度问题，并进一步研究帝国竞争算法在低碳生产调度方面的应用；另外，分布式调度也是未来研究的主题之一。