柔性作业车间调度优化的改进模拟退火算法

李 俊,刘志雄,张 煜,贺晶晶

(1.武汉科技大学汽车与交通工程学院，湖北 武汉，430081；2. 武汉理工大学物流工程学院，湖北 武汉，430063)

柔性作业车间调度优化的改进模拟退火算法

李 俊1,刘志雄1,张 煜2,贺晶晶1

(1.武汉科技大学汽车与交通工程学院，湖北 武汉，430081；2. 武汉理工大学物流工程学院，湖北 武汉，430063)

针对柔性作业车间调度问题，提出一种改进模拟退火算法来进行求解。该算法引入粒子群算法中的基于位置取整和基于轮盘赌两种个体编码方法，并采用3种不同的局部搜索方法来构造个体的邻域结构。算例计算表明，改进模拟退火算法在求解柔性作业车间调度问题时，比粒子群算法、混合粒子群算法以及模拟退火算法具有更好的求解性能，其中采用轮盘赌编码时，算法的求解性能要优于采用位置取整时的求解性能，且基于互换的局部搜索方法要优于其他两种局部搜索方法，能更有效地改善算法的求解性能。

柔性作业车间调度;job shop;模拟退火算法;轮盘赌;局部搜索

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem，FJSP)与其他生产调度问题相比更为复杂，也更加贴近实际的生产情况。在传统的作业车间调度问题(Job-shop Scheduling Problem，JSP)中，每个工件的每道工序只能在指定的机器上进行加工，而FJSP中每个工件的每道工序均可选择多台机器来进行加工，并且在不同机器上的加工时间也不同。但由于FJSP减少了对加工设备的约束，扩大了可行解的搜索范围，所以问题的求解也更加复杂。

针对FJSP的复杂性，目前常用的求解方法有遗传算法(GA)、模拟退火算法(SA)、演化算法(EA)、禁忌搜索(TS)、粒子群算法(PSO)等智能优化算法，其中模拟退火算法由于稳定性较好，得到了广泛的应用。Laarhoven等[1]于1992年最早将模拟退火算法应用于求解车间作业(Job Shop)调度问题。Jamili等[2]将模拟退火算法与仿电磁学算法杂交来求解周期作业车间调度问题；Zhang等[3]提出了一种基于块属性的模拟退火算法来求解考虑总权重拖期的Job Shop问题；Dai[4]等使用一种改进的遗传-模拟退火算法来对柔性作业车间进行能源有效性调度优化，对作业车间的能源消耗和环境影响等因素进行了考虑；Elmi等[5]针对考虑工作单元间物料流动和可重入的作业车间调度问题，运用模拟退火算法进行了求解，为了提高算法的搜索效率，提出了基于块概念的邻域结构；Zhang等[6]基于一种新的免疫机制提出了一种求解作业车间调度问题的混合模拟退火算法，对其总权重拖期进行了优化；Jolai等[7]针对无等待的两阶段柔性作业车间调度问题提出了一种双目标的模拟退火算法，该算法混合了田口法以及多目标决策方法；Shahsavari-Pour等[8]将遗传算法与模拟退火算法混合提出了一种新的混合亚启发式算法，来求解多目标柔性作业车间调度问题；梁旭等[9]提出了一种求解车间调度问题的新遗传退火混合策略，将遗传算法与模拟退火算法相结合；蓝萌等[10]提出了一种混合邻域搜索算法来求解多目标柔性作业车间调度问题，该算法融合了模拟退火算法、遗传算法以及免疫机制。综上可见，在求解作业车间调度问题，尤其是柔性作业车间调度问题时，大多数学者都将模拟退火算法作为一种局部搜索方法来对其他算法进行改进。但模拟退火算法在参数设置不当时容易陷入局部最优。为此，本文考虑以模拟退火算法作为主体，加入其他的局部搜索策略来改善算法跳出局部最优的能力，对其进行改进，并通过对几个不同规模的FJSP算例进行试验计算，以验证改进模拟退火算法求解FJSP的有效性。

1 柔性作业车间调度问题

柔性作业车间调度问题的优化目标可以描述为最小化最大完工时间MakeSpan。假设有n个工件，m台机器，工件i有Ji道工序。在某一确定的加工序列中，Sijk、Tijk、Cijk分别为工件i的第j(j∈Ji)道工序在机器k上的开始加工时间、加工过程时间、加工完成时间，而Tegk、Cegk则分别为机器k的上一加工任务的加工过程时间和加工完成时间，Cendk为机器k上加工的最后一道工序的加工完成时间，CTk为机器k上所有工件的加工完成时间，CTend为所有工件的加工完成时间。则最大作业完工时间最小的目标函数为：

Min{CTend}=max{CTk}

(1)

约束条件为：

Sijk+Tijk=Cijk

(2)

Sijk=max{S(i-1)(j-1)k+

T(i-1)(j-1)k,Ci(j-1)(k-1)}

(3)

Cegk-Cijk≥Tegk

(4)

CTk=Cendk

(5)

CTend=max{CTk}

(6)

2 求解FJSP的改进模拟退火算法

改进的模拟退火算法(ModifiedSimulatedAnnealing，MSA)是将粒子群算法(PSO)中粒子编码方法引入到模拟退火算法中来，采用基于位置取整和基于轮盘赌[11]两种不同的编码方法，并利用3种不同的局部搜索方法来构造个体的邻域结构。

2.1 个体编码方法

在柔性作业车间调度问题中，需要确定每个工件的加工路径，将粒子群算法中的两种粒子编码方法(基于位置取整和基于轮盘赌的方法)引入到模拟退火算法中，以此来进行工序加工机器的选择，进而确定工件的加工路径。

(1)基于位置取整的个体编码。

基于位置取整的编码方法需要限定个体位置在正数范围内，然后对其进行取整操作，通过映射对应的机器号得到每道工序所对应的加工机器，从而得到每个工件的加工路径，最后根据工件的有序加工序列和加工路径来生成调度方案。

(2)基于轮盘赌的个体编码。

由于柔性作业车间调度问题存在部分柔性的情况，即工序并不能在所有机器上进行加工，因此采用基于位置取整的编码方法进行个体编码时，取整后的个体位置对应的机器号可能并不在该工序的备选机器范围内，此时需要对该工序的个体位置进行重新生成，这样就会增加算法的计算时间。因此考虑一种基于轮盘赌的编码方法，该方法采用轮盘赌概率选择来进行机器选择，每次生成的个体位置一定会有唯一的一台备选机器与之一一对应，因此在求解部分柔性作业车间调度问题时能明显比基于粒子位置取整的编码方法更加节省时间，加快算法的搜索效率。

基于轮盘赌的编码方法限定个体位置在(0,1)区间内随机生成，得到每道工序选择机器的轮盘赌概率，然后看其概率落在哪台机器的概率区间内，就选择哪台机器来进行加工。从而得到每个工件的加工路径，最后根据工件的有序加工序列和加工路径来生成调度方案。

2.2 局部搜索方法

模拟退火算法要求较高的初始温度、较慢的降温速率、较低的终止温度以及各温度下足够多的抽样次数，同时，如果在参数选取不恰当时，算法容易陷入某个局部最优值。为了使算法在合适的参数设置下能够顺利地找到最优的调度解，且能相应地降低算法的运行时间，改进模拟算法中考虑加入局部搜索的算法。

(1)基于互换的局部搜索方法。基于互换的局部搜索方法按以下步骤来实现：①针对当前解随机选择个体编码中的两个不同位置p、q(p

(2)基于逆序的局部搜索方法。基于逆序的局部搜索方法按以下步骤来实现：①针对当前解随机选择个体编码中的两个不同位置p、q(p

(3)基于插入的局部搜索方法。基于插入的局部搜索方法按以下步骤来实现：①针对当前解随机选择个体编码中的两个不同位置p、q(p

以上各种局部搜索方法均设置一定的次数进行重复操作。

2.3 改进模拟退火算法的实现

在设定的性能指标为最小化最大完工时间时，求解FJSP的改进模拟退火算法可以按以下步骤来实现：

(1)控制参数的初始化。设置初始温度T0、降温速率Q、结束温度Te以及每个温度下的迭代次数(即Metropolis链长)L。

(2)初始解S1的编码。采用粒子群算法中的编码方法对初始解进行个体编码。

(3)当前解S1的局部搜索。设置一定的局部搜索次数对当前解S1的邻域进行搜索，找到新的解S2。

(4)Metropolis准则判断。设最大完工时间计算函数为f(S)，则当前解的最大完工时间为f(S1)，新解的最大完工时间为f(S2)，时间差为df=f(S2)-f(S1)，若df<0，则接受S2作为新的当前解，即S1=S2。否则计算新解S2的接受概率exp(-df/T)，其中T为当前迭代温度，若exp(-df/T)>rand(rand表示(0,1)之间的随机数)，也接受S2作为新的当前解，即S1=S2。否则保留当前解S1。

(5)降温迭代。利用降温速率Q对当前温度T进行降温，降温方法为T=Q×T。

(6)迭代终止。当前温度小于结束温度，即T

3 算例分析

3.1 算例计算

选用经典FJSP算例Hurink算例中的car1～car8问题[12]来进行计算。这8个算例的规模分别为car1(11×5)(11×5为算例规模，表示有11个工件，5台加工机器，其他算例类似)、car2(13×4)、car3(12×5)、car4(14×4)、car5(10×6)、car6(8×9)、car7(7×7)、car8(8×8)。

对于改进模拟退火算法(MSA)，分别采用基于位置取整和基于轮盘赌的编码方法，其参数设定为初始温度T0=1000、降温速率Q=0.98、结束温度Te=0.001，每个温度下的迭代次数L=300，基于互换操作的局部搜索次数为3次。对于car1～car8问题，连续优化20次，将改进模拟退火算法(MSA)的求解结果分别与SA、采用惯性权重线性递减的基本粒子群算法(PSO)和混合粒子群算法(HPSO)的求解结果进行比较分析。其中，SA的参数设置与MSA的参数设置保持一致。PSO和HPSO均采用基于轮盘赌的编码方法，且HPSO为加入了基于互换操作的局部搜索方法的粒子群算法。其中，考虑到FJSP算例的复杂性，为了算法能获得更好的求解性能，将PSO的参数设置为种群数量为20，最大迭代次数为1000次，将HPSO的互换次数设置为3次。

采用Matlab对上述问题进行编程求解，以优化最大作业完工时间为目标，找出各方法在求解不同问题时得到的最优解、最差解以及平均解，结果如图1所示，其中适应值表示设定的优化目标，即最大作业完工时间。

从图1中可以看出，在8个car类FJSP算例的计算中，MSA无论是最优解、最差解还是平均解都要优于PSO、HPSO以及SA的相应值，而且基于轮盘赌编码的MSA比基于位置取整的MSA具有更好的求解性能。

图1 不同算法解的比较

Fig.1 Comparison of solutions by different algorithms

3.2 MSA算法控制参数设置分析

对于MSA算法，一般设置初始温度T0=1000，而Te、Q以及L的设置则比较灵活。在T0确定了以后，这3个参数的设置直接与算法的求解性能相关。以下以car1问题为例，以优化最大作业完工时间为目标，采用基于轮盘赌编码的MSA算法，对Te、Q及L的参数选择进行分析。

(1)Te的设置。设置T0=1000、Q=0.98、L=300，互换操作次数为3次，连续优化20次，Te分别设置为0.0001、0.001、0.01和0.1来进行试验计算，结果如表1所示。从表1中可以看出，Te的值并不是越小越好，当Te=0.001时，虽然求解时间比前两者要长，但算法有更好的寻优性能和稳定性能，且求解时间也在可接受的范围之内。因此Te的值选择0.001较佳。

(2)Q的设置。设置T0=1000、Te=0.001、L=300，互换操作次数为3次，连续优化20次，Q分别设置0.90、0.93、0.95和0.98来进行试验计算，结果如表2所示。从表2中可以看出，当Q=0.9、0.93、0.95时，虽然算法的耗时明显少于Q=0.98时，但其求解结果却要差的多，因而设置Q=0.98更为合理。

(3)L的设置。设置为T0=1000、Te=0.001、Q=0.98，互换操作次数为3次，连续优化20次，L分别设置为100、200、300和400来进行试验计算，结果如表3所示。从表3的结果可以看出，在

表3 不同Metropolis链长时的计算结果

Table 3 Calculation results at different lengths of Metropolis

可接受的求解耗时范围内，当L=300时，算法取得了更好的求解结果。

综上所述，MSA算法的控制参数设置为T0=1000、Q=0.98、Te=0.001、L=300较为合理。

3.3 局部搜索方法的比较

采用不同的局部搜索方法会使MSA算法得到不同的求解结果。对于上述car1～car8问题，运用基于轮盘赌编码的MSA算法，分别采用3种不同的局部搜索方法来进行求解。其参数设置均为T0=1000、Q=0.98、Te=0.001、L=300，局部搜索次数为3次，连续优化20次，找出不同局部搜索方法下的最优解、最差解以及平均解，结果如图2所示。从图2中可以看出，在采用3种不同局部搜索方法的MSA算法中，基于互换的局部搜索方法有更好的求解性能，尤其是在算例规模更大的时候，比如car6问题。同时，基于互换的局部搜索方法在编程实现时代码更加简单，具有更快的求解速度。

图2 不同局部搜索策略下算法解的比较

Fig.2 Comparison of solutions by the algorithm under different local searches

3.4 局部搜索次数的确定

在局部搜索过程中，局部搜索次数的设置是一个很重要的参数。局部搜索次数过少，则搜索的效果不明显，无法体现局部搜索的作用，而次数过多则会加大MSA算法的搜索空间，影响算法的求解效率。为此，需要确定一个合适的局部搜索次数，既能保证MSA算法的有效性，又能保证MSA算法的求解效率。

针对规模较大的car6问题，参数设置为T0=1000、Q=0.98、Te=0.001，L=300，连续优化20次，分别设置局部搜索次数为1～10次来进行试验计算，结果如表4所示。从表4中可以看出，算法的求解结果并不完全是随着互换操作次数的增加而变得更好，但求解时间却随着互换操作次数的增加而变得越来越长。设置合理的互换操作次数不仅可以获得更好的求解结果，而且可以缩小算法的搜索空间，节约算法的求解时间，加快算法的求解效率。从表5可以看出，无论是最优值、最差值还是平均值，从提高算法的寻优性能和稳定性能角度出发，互换操作次数设置为3次最为合理。

4 结语

本文在研究了柔性作业车间调度问题的基础上，将PSO算法中基于位置取整和基于轮盘赌两种不同的编码方法引入到模拟退火算法中来，并采用了3种不同的局部搜索方法，提出一种改进模拟退火算法(MSA)来求解柔性作业车间调度问题。然后通过对几个不同规模的FJSP算例的试验计算，分析了不同局部搜索方法的有效性，确定了合理的参数，说明了基于轮盘赌编码的MSA算法在求解FJSP问题时具有更好的求解性能，且采用基于互换的局部搜索方法能有效改善算法的求解性能。

[1] Laarhoven P J M，Aarts E，Lenstra J K．Job shop scheduling by simulated annealing[J]．Operations Research，1992，40(1)：113-125．

[2] Jamili A，Shafia M A，Tavakkoli-Moghaddam R．A hybridization of simulated annealing and electromagnetism-like mechanism for a periodic job shop scheduling problem[J]．Expert Systems with Applications，2011，38：5895-5901．

[3] Zhang R，Wu C．A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective[J]．Computers & Operations Research，2011，38：854-867．

[4] 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：418-429．

[5] Elmi A，Solimanpur M，Topaloglu S，et al．A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts[J]．Computers & Industrial Engineering，2011，61：171-178．

[6] Zhang R，Wu C．A hybrid immune simulated annealing algorithm for the job shop scheduling problem[J]．Applied Soft Computing，2010，10：79-89．

[7] Jolai F，Asefi H，Rabiee M，et al． Bi-objective simulated annealing approaches for no-wait two-stage flexible flow shop scheduling problem[J]．Scientia Iranica E，2013，20(3)：861-872．

[8] Shahsavari-Pour N，Ghasemishabankareh B．A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling[J]．Journal of Manufacturing Systems，2013，32：771-780．

[9] 梁旭，黄明，常征．求解车间调度问题的一种新遗传退火混合策略[J]．计算机集成制造系统，2005，11(6)：851-854．

[10]蓝萌，徐汀荣，黄斐．使用混合邻域搜索算法求解多目标柔性JSP问题[J]．计算机工程与设计，2011，32(1)，293-296．

[11]刘志雄，杨光祥．基于轮盘赌概率分配编码方法的并行机调度优化[C]//Proceedings of the 29th Chinese Control Conference，Beijing，2010：1775-1780．

[12]Monaldo Mastrolilli．Flexible job shop problem[DB/OL]．http: //people.idsia.ch/～monaldo /fjsp.html.

[责任编辑 郑淑芳]

Modified simulated annealing algorithm for flexible job-shop scheduling problem

LiJun1,LiuZhixiong1,ZhangYu2,HeJingjing1

(1. College of Automobile and Traffic Engineering, Wuhan University of Science and Technology, Wuhan 430081, China; 2. College of Logistics Engineering, Wuhan University of Technology, Wuhan 430063, China)

A modified simulated annealing algorithm was put forward to resolve the flexible job-shop scheduling problem, which used two kinds of individual encoding method respectively based on particle position rounding and roulette probability assignment in particle swarm algorithm.Three different local search methods were employed to constitute the neighborhood structure. The computational results show that the modified simulated annealing algorithm is more effective than particle swarm algorithm, hybrid particle swarm algorithm and simulated annealing algorithm in resolving the flexible job-shop scheduling problem. Compared with the position rounding encoding method, the roulette-probability-assignment-based encoding method can render the algorithm more effective, and the local search method based on crossing-over operation is better than the other two search methods in improving the solving performance of the algorithm.

flexible job-shop scheduling problem; job shop;simulated annealing algorithm; roulette selection; local search

2014-09-05

国家自然科学基金资助项目(70801047,71372202)；中央高校基本科研专项基金资助项目(2013-IV-057).

李 俊(1989-)，男，武汉科技大学硕士生.E-mail:286485135@qq.com

刘志雄(1975-)，男，武汉科技大学教授，博士.E-mail:lzx_brad@126.com

TP18

A

1674-3644(2015)02-0111-06