基于改进模拟退火算法的大规模置换流水车间调度

黎 阳，李新宇+，牟健慧

(1.华中科技大学 数字制造与装备技术国家重点实验室，湖北 武汉 430074；2.烟台大学 机电汽车工程学院，山东 烟台 264000)

0 引言

生产调度是在某些生产条件约束下，合理确定每个加工对象的加工路径、加工时间和操作等，以实现某些生产目标，可以定义为“把有限的资源在时间上分配给若干任务，以满足一个或多个目标”[1]。生产调度问题大量存在于制造业中，在智能制造的趋势下，越来越多的生产企业将生产重点集中到生产调度问题上，通过开发更好的调度算法、努力追求更优的解决方案，来实现降低成本、提高生产效益的目标。传统的“模型+算法”式车间调度已经十分成熟[2]，人们在相关领域取得了非常丰富的成果。然而随着智能化和柔性化车间的发展，车间数据量越来越庞大，相应的启发式算法和元启发式算法的解空间变得越来越复杂，对算法本身的性能提出了更高的挑战。

本文研究的置换流水车间调度问题(Permutation Flowshop Scheduling Problem, PFSP)属于经典的NP-hard问题，从问题的求解层面看，该问题具有指数爆炸、工序相关性等复杂性；从现实层面看，很多工厂都采用了PFSP的生产模式，因此其研究具有重要的学术意义和工程应用价值。

起初对PFSP的研究集中在寻找精确的求解算法，如解析法[3]、分枝定界法[4]、整数规划法[5]等，目的是找到该类问题的精确最优解。精确算法只适用于求解某些特例或者小规模问题，随着研究的深入，需要求解稍大规模的PFSP问题时，这类算法显得无能为力。因此，对PFSP的研究重心逐渐转移到寻找能够快速得到近似最优解的启发式算法，如Palmer法、CDS(Campbell-Dudek-Smith)法[6]、Gupta算法[7]等。启发式算法在求解PFSP时能够快速求得问题的解，但是一般不能得到全局最优解，这类方法适用于求解小规模问题，对大规模问题的求解效果通常较差。Nawaz在1983年提出NEH(Nawaz-Enscore-Ham)算法[8]，这是目前对PFSP求解性能最好的启发式算法。

精确算法和启发式算法在求解大规模调度问题上存在一定局限性，随着计算机技术的快速发展，智能优化算法开始被引入求解调度问题，有效解决了启发式算法的不足。此后，新的智能优化算法不断涌现，并得到了迅速发展，有力促进了PFSP的研究。比较经典的智能优化算法包括遗传算法[9](Genetic Algorithm, GA)、模拟退火[10](Simulated Annealing, SA)算法、禁忌搜索[11](Tabu Search, TS)算法、粒子群优化[12](Particle Swarm Optimization, PSO)算法等，这类算法编码简单，可以很方便地应用到其他优化问题上，而不只局限于PFSP。智能优化方法的出现为调度问题的求解提供了一个全新的思路[13]。

虽然这些算法简单有效，但是在面临大规模生产调度问题(工件数>100)时，依然普遍面临参数敏感、容易早熟陷入局部最优等缺陷，导致科研成果无法与实际生产结合，难以产生实际工程价值。为解决这一问题，本文针对大规模PFSP，在SA算法框架下，改进该方法的初始参数设计和降温函数，使算法精度大幅上升，能够为实际生产制造提供准确的建议与指导。

1 问题描述

1954年，Johnson[14]首次提出PFSP，并对该问题做了初步研究。自此以后，PFSP得到广泛关注，许多学者相继对其进行研究，并取得了丰硕的研究成果[15-16]，大量优秀算法被提出以解决这类问题[17-18]。

PFSP研究n个工件在m台机器上加工的过程，每个工件在各台机器上的加工顺序一致，同时限制每个工件只能在各台机器上加工一次，每台机器一次只能加工一个工件，各工件在各台机器上的加工时间已知。调度的最终目的是求得各工件在机器上的加工顺序，使某项优化指标达到最优。PFSP在其基础上增加了一个约束条件，即每台机器上各工件的加工顺序相同[19]。除此之外，流水车间调度问题还有一些其他的一般性假设条件：

(1)一个工件在同一时刻不能在两台或两台以上机器上加工。

(2)加工过程中，工件采用平行移动方式，即加工完上一道工序后立即将工件送去加工下一道工序。

(3)每个工件在每台机器上的加工时间固定，与工件的加工顺序无关。

(4)工件在加工过程中不允许中断，即工件的某个工序一旦开始加工，就必须等到完工后才能离开，中途不能停止或插入其他工序。

(5)允许工件等待和机器闲置。

Cσ1,1=tσ1；

Cσ1,j=Cσ1,j-1+tij,j=2,3,…，m；

Cσi,1=Cσi-1,1+ti1,i=2,3,…，n；

Ci,j=max(Cσi-1,j,Cσi,j-1)+tij,

i=2,3,…，n,j=2,3,…，m。

(1)

最大完工时间Cmax=Cσn,m，置换流水车间调度的目标是确定使Cmax最小的最优工件加工顺序π=(σ1,σ2,…,σn)[21]。

流水车间调度的根本目的是在约束条件的限制下，充分利用现有资源，合理安排资源调度，使成本最小化或者效益最大化，因此经典的流水车间调度问题以最大完工时间为主要调度目标。

尽管置PFSP是流水车间调度的特例，但是它仍然是一个非常复杂的组合优化问题，本文改进了现有SA算法的性能以求解PFSP。为了检验和比较算法的精度，以最大完工时间作为唯一的优化目标。

2 基于改进模拟退火优化算法的PFSP方法

SA算法的思想起源于Metropolis等于1953年提出的Metropolis准则，用于判断SA算法的解是否被接受。1983年，Kirkpatrick等成功地将退火思想引入组合优化领域。在之后的大量研究表明，SA算法是一种以概率1收敛于全局最优解的全局优化算法[22]，因此被广泛应用于组合优化问题，如NP、旅行商问题(Traveling Salesman Problem，TSP)等，而且在实际生活的车辆路径规划[23]、枢纽选址[24]、光纤网络设置[25]等众多优化问题中，SA算法均发挥了巨大的作用。

2.1 编码和解码

编码方式采用自然数编码，即对于n个工件，分别采用n个互不相同的自然数一一对应进行标记和编号，其中最小值为1，最大值为n，从而方便简洁地利用数字表示每个工件的序号。在解码上，根据最开始的编码顺序，重新将自然数对应为相应的工件号。

2.2 初始化

SA算法的初始解状态S为NEH算法生成的1～n序列。选择控制参数初值时，一般要求初始值T0的值要充分大，一开始即处于高温状态，且Metropolis的接收率约为1。

常规SA算法的初始温度均为随机设定，但是常会影响算法的最终收敛性能。因此，本文随机产生一组状态，确定两两状态间的最大目标值差|Δmax|，然后根据差值，利用初始接受概率确定初温，相关的表达式为

T0=-|Δmax|/p0。

(2)

式中p0为初始接受概率。其余各参数值的设定与标准方法相同。

2.3 新解的生成与终止条件

在大规模问题下，单一的搜寻方式极易陷入局部最优解，从而使解的质量下降。为了提升算法在大规模问题下的普适性，本文采用基于概率选择的多邻域搜索操作协同的方式生成新解。3种邻域搜索操作如下：

(1)二交换 在编码序列中随机选择两点，颠倒两点间所有工件的顺序。

(2)三交换 在编码序列中随机选择三点，交换三点之间的两段序列位置。

(3)点交换 在编码序列中随机选择两点，交换这两点的工件位置。

为了提升算法的运算速度，若按照上述方法所生成新解的最优适应度在σ代内仍未改变，则判定算法结束，完成当前温度下的搜索。

2.4 协同并行搜索

标准SA算法在同一温度下仅采用单序列进行循环搜索，缺少个体或种群间的协同，在大规模环境下很难得到最优解。为了提高最终解的质量，本文引用GA种群的思想，在同一温度下对初始序列进行3次独立搜索，选择最优值进入下一阶段。

2.5 执行Metropolis准则与记忆功能

该步骤与标准SA一致，通过Metropolis准则判断是否接受新解。在判断完后，额外设置变量E_best保存全局最优解，该解不受Metropolis准则判定的影响，以免在之后的迭代中被取代[26]。

2.6 温度衰减函数

与标准SA算法不同，本文启用多普勒型衰减函数代替原本的指数函数，这种新型衰减函数可以提升大规模环境下解的收敛速度。多普勒效应型温度递减曲线表达式为[27]

(3)

式中：k为迭代次数，K为总降温次数。利用该函数不断衰减温度T，达到终止温度时停止迭代，温度衰减完毕，返回最优目标函数值，结束程序。

2.7 算法流程

改进SA算法流程如图1所示，在初始化之后，算法通过新解生成、协同搜索、执行Metropolis准则与记忆功能、温度衰减等多个阶段的不断循环完成退火，最终得到满意解。

3 案例验证和分析

本文选择两个数值Benchmark案例集和一个工程实际案例，用于测试改进SA算法的性能。两个数值案例集主要用于评价该算法的性能，并将结果与最新算法进行对比；工程案例用于验证该算法解决实际问题的能力。

改进SA算法采用MATLAB编程，运行环境为2.2 GHz主频的CPU，Intel Core i7处理器。为了便于比较算法性能，数据集的评价指标为平均相对百分偏差ARPD，

(4)

式中：n为算法运行次数，Ci为算法第i次运行结果，UB为当前已知最优解。

3.1 TA数据集测试

Taillard教授在1993年提出了TA数据集，其中包括260个不同的车间调度案例[28]，如今已经成为调度领域应用最广的测试集之一。因为本文主要解决的是大规模PFSP，所以选择案例集中工件数大于100的所有案例进行测试(TA61～TA120)。所有问题的确定加工时间及其已知最优解请参考网址http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html。

本文选择的对比算法有混合遗传算法(Hybrid Genetic Algorithm, HGA)[29]、利用禁忌搜索改进的贪婪迭代法(Tabu-Mechanism Improved Iterated Greedy, TMIIG)[30]、离散的自组织迁移算法(Discrete Self-Organizing Migrating Algorithm, DSOMA)[31]、离散水波算法(Discrete Water Wave Optimization algorithm, DWWO)[32]、改进的贪婪迭代算法(Improved Iterated Greedy Algorithm, IIGA)[33]、反向差分进化算法(Opposition based Differential Evolution algorithm, ODDE)[34]、扩展的人工染色体遗传算法(extended Artificial Chromosomes Genetic Algorithm，eACGA)[35]，具体结果如表1所示。

表1 TA数据集实验结果

续表1

续表1

3.2 VRF数据集测试

VRF数据集由Vallada等于2015年提出[36]，是目前最新的测试集，一共包括48个不同规模的PFSP。相对于TA数据集而言，VRF数据集包含的规模种类更多，问题规模也更加庞大，其最大规模问题可达800个工件60台机床。因为当前针对VRF数据集的文献均未给出每一个案例的计算结果，所以本文仅给出每一种规模问题下的ARPD值。所有问题的确定加工时间及其已知最优解请参考网址http://soa.iti.es/problem-instances。针对数据集中240个大规模算例，利用改进SA算法计算10次，求得相应的ARPD值，然后将相同规模算例的ARPD值合并求平均值。

本文选择的对比算法有NEH，TBD，TBKK1，TBKK2，TBFF，TBLJP1(算法均为Liu等于2017改进后的结果[37])，具体结果如表2所示。表中PRSKE和PRD+为Liu等[37]使用的初始化算法。

表2 VRF数据集实验结果

续表2

综合表1和表2可见，本文所提改进SA算法在整体精度上优于其他算法，在大规模车间调度问题下，本算法能够给出相应的满意解，具有实际工程价值。

3.3 车间调度优化实例中的应用

3.3.1 连杆部件制造的置换流水车间调度问题

某汽车发动机零部件公司的生产车间准备制造100种不同型号的发动机连杆部件，该连杆部件的加工工艺主要有9道加工工序，不同型号的连杆部件在不同工序上的加工时间不同，相关的加工参数见文献[38]。加工过程中，工件采用平行移动方式，即加工完上一道工序后立即加工下一道工序；工件在加工过程中不允许中断，即工件的某个工序一旦开始加工，就必须等到完工后才能离开，中途不能停止或插入其他工序；所有工件必须依次完成9道工序。表中给出的加工时间已经包括运输、等待、机器准备和调试等全部相关时间。因为该实例是采用试制样件进行具体型号的发动机研发测试，所以暂不考虑批量生产的问题。

根据上述工程实例分析可知，该连杆部件制造为经典的PFSP。将加工数据整理为加工时间矩阵T(见附录)，目标是求解这100种不同型号连杆的加工顺序，使得总完成时间最短。

3.3.2 优化分析

在未进行优化前，加工顺序为1～100,依次加工，总完工时间为6 284 s。利用本文提出的改进SA算法优化后，调度方案的总完工时间均为5 333 s，最优调度序列为S2，最优调度方案的部分甘特图如图2所示。

S2=[69 46 65 98 62 95 24 12 60 57 27 49 54 35 87 20 73 90 96 72 66 64 50 61 59 45 34 26 86 33 48 53 11 16 89 19 40 32 77 83 28 17 52 7 43 23 21 42 99 84 18 37 82 3 1 88 67 8 29 25 55 6 80 58 13 38 91 85 81 51 92 5 30 9 74 70 56 14 71 76 44 31 68 22 36 15 10 75 39 78 93 94 41 63 2 47 97 100 4 79]。

因此在进行工序调整优化后，总加工时间缩短了15.1%左右，大幅提高了车间的生产效率，增强了企业的核心竞争力。

3.4 算法改进分析

相对于元启发式算法SA，本文所提改进SA算法的主要优势是，通过参数控制达到全局搜索与局部搜索相结合的目的。正是因为两种搜索方式并行推进，所以算法在数值和工程案例中都取得了较好的结果。其中，设置初始温度及设计温度衰减曲线是为了增强算法的全局搜索能力，温度越低，Metropolis算法保留劣解的概率就越低，这样不利于跳出局部最优解。因此通过临时提升劣解的接受概率来提高算法的全局搜索能力。

协同并行搜索和记忆机制是为了提升局部搜索能力。以同一个初始解为基础，进行策略不同的并行搜索可以提升找到满意解的概率，记忆功能是为了避免后续劣解覆盖已经生成的满意解。

4 结束语

本文提出一种改进的SA优化算法，通过设计初始温度的计算公式、采用基于概率选择机制的多操作协同搜索、加入记忆功能保存最优解及改进温度衰减函数等方法，提升了算法在大规模问题下的性能。通过分别对TA算例和VRF算例进行统计分析，验证了算法在大规模调度问题下的优势。在工程应用方面，将算法引入实际生产，结合具体的PFSP案例进行优化，成功提高了车间的生产效率，证明该算法具有实际工程意义。该算法未来可以在解决大规模问题及其他调度指标的优化、多个调度目标的协同优化等方面做进一步研究。