改进模拟退火算法在柔性调度中的应用*

黄海松，刘 凯，初光勇

(1.贵州大学 现代制造技术教育部重点实验室，贵阳 550025；2. 铜仁职业技术学院 工学院，贵州 铜仁 554300)

0 引言

现代制造方式不仅追求快速、高效地完成加工任务，更加追求低碳生产[1]。合适的车间调度策略不仅可以提高产品质量、缩短生产时间，优化加工方案，从而减少加工过程中的能源消耗，进而控制碳排放。

在传统作业车间调度问题中，对加工机器的数量进行限制，柔性作业车间调度问题(Flexible job-shop scheduling problem ,FJSP)是其扩展，增加了车间调度的灵活性，使其更加贴近生活领域[2]。但由于FJSP减少对加工设备的约束，扩大搜索范围，故问题的求解更加复杂。针对FJSP的复杂性，目前常用的求解方法有:遗传算法(GA)[3]、粒子群优化算法(PSO)[4]、模拟退火算法(SA)[5]等智能优化算法。其中模拟退火算法稳定性好，应用范围广阔。Laarhoven等[6]于1992年最早将模拟退火算法应用于求解车间作业(Job Shop)调度问题。Dai等[7]将遗传算法与退火算法结合对柔性作业车间的能源消耗进行优化。蒋增强等[8]使用改进的NSGA-II算法求解多目标，求解过程中考虑到设备状态和能耗分布。Xia等[9]采用了混合例子群算法来优化FJSP中的生产管理和组合优化问题，通过引入模拟退火的思想实现局部搜索，避免算法陷入局部最优解。张其亮等[10]等利用基于NEH算法解决工件加工顺序问题。刘爱军等[11]针对客户满意度和完工时间为目标求解FJSP问题。梁旭等[12]提出一种求解车间调度问题的新遗传退火算法。

本文以某工厂生产车间为例，建立了以最大完工时间和碳排放为目标的柔性作业车间调度模型，运用改进的模拟退火算法进行求解，验证了所提出的算法在加入低碳要求的车间调度中的可行性和有效性。

1 柔性作业车间模型建立

FJSP问题可以描述为：n个代加工工件的集合为J={J1，J2…Ji，…Jn}(i∈[1,n]),m台机器集合为M={M1，M2…Mj，…Mm}(j∈[1,m])，且满足的约束条件有：①第i个工件Ji的第k道工序加工机器选择不止一台机器，但不能再多台机器上加工。②任何工件的任何工序加工一次性完成，不能中断。③第j台机器Mj在任意时刻最多只能有一个工件在上面加工。④第i个工件Ji工件的准备和移动时间包含在加工时间内。⑤加工过程中的机器在工件没有运送到达时间限制，允许各个工序之间存在等待。为方便讨论，引入如表1所示的数学符号。

表1 数学符号定义

本文调度模型研究的两个目标是加工时间和碳排放量，用T表示工序的加工时间，用C表示碳的总排放量。问题的数学模型建立如下。

(1)加工时间。FJSP的计算总完成时间计算方法。

(1)

(2)碳排放量。碳排放量只考虑加工过程中的碳排放，不考虑材料在运输中等环节的能源消耗。

(2)

(3)评价函数

minf(x)=α·T+β·C

(3)

假设在这个问题中，存在一个可行域，则这个可行域中的任意一个点都有对应的x，y的值，x，y值对应就是T,C的值乘以各自的权重，比较所有的方案，f(x)的值越大，此方案的适应度值越低，方案越差，故f(x)的值最小的方案即是所选择的方案。如图1所示。

图1 可行域方案集

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

改进的模拟退火算法(Modified Simulated Annealing，MSA)将粒子群(PSO)中的编码方式引用到机器编码中，在选择机器时采用了随机位置法与轮盘赌[13]的两种不同的方法进行编码，通过算例验证证明轮盘赌的机器编码可以大大减少运行时间。并采取两种不同的局部搜索方法建立领域结构。

2.1 编码方法

解决柔性作业车间调度问题，需要确定每个工件的加工路径，即工件的每一道加工工序的机器选择，本文通过两种不同的编码方法(随机位置和轮盘赌)对加工机器人进行选择，进而确定工件的加工路径。

(1)随机位置的个体编码

随机位置的个体编码需要对规定位置的取值范围，一般是取值范围是正数。首先随机生成一个数x，对其进行取整操作，通过一定的函数关系得到每道工序加工的机器，进而得到工件的加工路径，最后生成调度方案。

(2)轮盘赌的个体编码

柔性作业车间调度问题的特性是一道工序可以在多个机器上加工，但不是所有的机器可以加工这道工序，故采用随机位置的个体编码并不能确保每一次的机器的选取都能选到备选机器的范围。如果选取不在备选区域内，则需要进行二次选取，这样会大大增加系统算法的工作时间。因此采用轮盘赌的编码方法进行编码，该方法可以确保每一次的机器选取都有唯一的一台机器与之对应，因此该方法编码大大减少了算法的运行的时间，加快算法的搜索的效率。以3台机器为例具体流程如表2所示。

表2 二维机器编码

①根据上述表2中加工时间的大小，从小到大排序，同时相应的调整第一位机器号码的次序。

②计算所有的机器号码对应加工时间的总和∑Tj，并计算每个工件j所对应的比例pj，即有：

(4)

③工序O产生一个随机数并满足一下O(0，1)，如果0

2.2 局部搜索

模拟退火算法特性要求需要较高的初始温度和较慢的温降速率等特点，并且如果参数选取不当会陷入局部最优。故避免这种情况的发生在算法中引入了两种局部搜索方法，具体如下:

(1)个体调换的局部搜索。个体调换的局部搜索步骤如下：①在当前解的序列中随机选取两个位置a、b，调换a、b的位置得到一个新的序列。②对这个新的序列进行解码并计算其适应度值，若适应度高于旧序列则替换旧序列，否则仍用旧序列。③返回①继续操作。直到达到终止条件。

(2)局部颠倒的局部搜索。局部颠倒的局部搜索步骤如下：①在当前解的序列中随机选取两个位置a、b，颠倒a、b之间的序列得到一个新的序列。②对这个新的序列进行解码并计算其适应度值，若适应度高于旧序列则替换旧序列，否则仍用旧序列。③返回①继续操作。直到达到终止条件。

2.3 算法流程

参数初始化，包括设置初始温度T0、温降速率q、结束温度Te、以及迭代步长L。改进的模拟退火算法的流程图如图2所示。

图2 改进模拟退火算法流程图

3 实例仿真实验

某制造车间生产过程可以简化为一个6个工件在6台机器上加工的柔性作业车间调度问题。在制定生产调度计划的时候需要考虑到最大完工时间和碳排放量这两个目标。该制造车间的加工数据如表3所示，其中第一列代表工件，第二列代表工序，之后的代表该工序可以在哪台机器上加工，有数字的代表该机器可以加工该工序，没有数字的代表该工序不能再这台机器上加工。例如：O11不可以在第一台机器上加工，可以在第6台机器上加工，加工时间为15，单位时间的碳排放为1.1。

表3 实例数据

本文算法采用Matlab编程实现，其中初始温度T0=1000、温降速率q=0.98、迭代步长L=200、终止温度Te=0.001。实验结果分为三个部分：两种编码方式的运行时间、两种局部搜索方式的优劣度和不同权重系数下生产调度最优结果。

3.1 两种不同编码方式的运行时间

采用上文提及的两种不同的编码方式分别运行该实例，通过20次的运行去取平均运行时间。具体如4所示。从表4可以清楚看到采用轮盘赌的编码方式可以大大减少该算法的运行时间。

表4 不同编码方式的运行时间

3.2 两种不同的局部搜索的优劣度

采用个体调换和局部颠倒的两种不同的局部搜索方式，其它的参数完全相同，进行20次的仿真运行，结果如图3所示。

图3可以看出采用个体调换的局部搜索方式所对应实线位于采用局部颠倒的局部搜索方式对应的虚线下方。根据公式(3)可以知道当适应值越低，方案越优越。故可以得到采用个体调换的局部搜索优于局部调换的局部搜索。

图3 两种局部搜索适度值折线图

3.3 不同权重系数的调度结果

依据上面所得到的结果，采用轮盘赌编码方式以及个体调换的局部搜索，分别对3种不同情况进行求解，如表5所示。图4～图6为不同方案的调度甘特图。图中横坐标代表完工时间，纵坐标代表机器号，O1,2、O4,1代表第一个工件的第二道工序，第四个工件的第一道工序。

表5 不同权重系数的目标值

方案1代表生产工厂在碳排放量满足国家要求的情况下，侧重最大完工时间对应的调度甘特图为图4。从图4得出：为了缩短加工时间，工序安排尽可能分散，使机器的利用率达到最大。方案2代表生产工厂对最大完工时间和碳排放重视力度一样，对应的调度甘特图为图5，从图5得出：工序分布比较分散，故加工时间较长。机器6处理的工序较多，故机器6能耗较低。方案3代表生产工厂重视节能环保故需要牺牲完工时间，对应的调度甘特图为图6。 从图6得出：为了降低碳排放，花费的大量的加工时间，故工序分布非常分散，并且机器的使用率分布不均。

综上，决策者可以依托本文算法，根据生产实际情况，对目标设置不同权重系数，从而得到最优的调度方案。

图4 方案1调度甘特图

图5 方案2调度甘特图

图6 方案3调度甘特图

4 结论

对具有低碳要求的柔性车间资源调度问题进行分析，建立了以最大加工时间和碳排放量为优化目标的调度模型。并提出了一种基于改进模拟退火算法的调度策略，改进了模拟退火算法的编码方式和局部搜索方式，从而降低了算法的运行时间。最后以车间生产实际案例为背景，通过设置不同的权重系数代表不同的工厂对生产目标的要求，生成不同的调度方案。实验结果证明本文所提出的基于改进模拟退火算法的调度策略在实际车间资源调度中是可行的。

[1] 姚立国,黄海松,田野,等. 云模式的机床供应链运作流程建模与计算[J]. 组合机床与自动化加工技术,2017(2):108-111.

[2] 朱夏,李小平,王茜.基于总空闲时间增量的无等待流水调度混合遗传算法[J].计算机研究与发展,2011,48(3):455-463.

[3] 张腾飞,马跃,胡毅,等.基于遗传算法的多目标车间调度问题的研究[J].组合机床与自动化加工技术,2016(5):43-45,50.

[4] 刘韵,胡毅,罗企,等.一种解决柔性车间作业调度问题的粒子群优化算法[J].组合机床与自动化加工技术,2015(12):144-147.

[5] 周鑫,马跃,胡毅.求解车间作业调度问题的混合遗传模拟退火算法[J].小型微型计算机系统,2015(2):370-374.

[6] Laarhoven P J M V,Aarts E H L,Lenstra J K.Job Shop Scheduling by Simulated Annealing[J].Operations Research,1992,40(1):113-125.

[7] Dai M,Tang D,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(5):418-429.

[8] 蒋增强,左乐.低碳策略下的多目标柔性作业车间调度[J].计算机集成制造系统,2015, 21(4):1023-1031.

[9] Xia W,Wu Z.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems[J].Kongzhi Yu Juece/control & Decision, 2005,48(2):409-425.

[10] 张其亮,陈永生.基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论与实践,2014,34(3):802-809.

[11] 刘爱军,杨育,邢青松,等.多目标模糊柔性车间调度中的多种群遗传算法[J].计算机集成制造系统,2011,17(9):1954-1961.

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

[13] 向万里,马寿峰.基于轮盘赌反向选择机制的蜂群优化算法[J].计算机应用研究,2013,30(1):86-89.