求解柔性作业车间调度问题算法综述

2021-11-29田云娜

延安大学学报(自然科学版) 2021年3期

田园，田云娜，刘雪

(延安大学数学与计算机科学学院，陕西延安 716000)

在制造系统中，生产调度是非常重要的一个环节，直接影响企业的生产经济效益。经典的生产调度问题主要包括流水车间调度问题和作业车间调度问题。柔性作业车间调度问题(Flexible Job-shop Scheduling Problem,以下简称FJSP)是对经典作业车间调度问题的扩展，其主要特点是在FJSP中工件的加工路径并非唯一，而是具有柔性的，这一特点使得问题的灵活性和复杂性大幅增加。相对于作业车间调度问题(JSP)，FJSP具有更广泛的实际应用和更高的求解难度，这引发了研究者们极大的兴趣。

本文主要针对FJSP进行相关介绍。首先对现有的求解FJSP的方法进行综述，分别从精确、启发式和智能优化算法三个方面进行介绍，然后对FJSP的研究现状进行总结分析，并讨论其进一步的研究前景。

1 问题描述

FJSP通常描述如下：

n个工件在m台机器上进行加工，每个工件有k道工序，每道工序的可选机器若干，工件内工序加工顺序及每道工序在不同机器上所需加工时间一定。调度的主旨是确定每道工序加工所选择的机器及各机器上工序的加工次序，以使得所关心的主要指标尽可能最优。此外，对于FJSP还有以下约束和假设：

(1)所有工件和机器在零时刻均处于就绪状态；

(2)同一时刻一台机器只能加工一道工序；

(3)同一道工序在同一时刻只能在一台机器上进行加工且只能加工一次；

(4)工序加工次序的约束仅考虑在同一工件内；

(5)不考虑工件在加工过程中发生中断；

(6)不考虑机器故障；

(7)各工件加工优先级相同。

此处给出FJSP的数学模型。首先介绍相关符号。

模型参数：

n：工件总数

M：机器总数

Oij：工件i的第j道工序

Mij：工序Oij可选的机器集合Pijk：工序Oij在机器k上的加工时间

L：一个无穷大的正数

决策变量：

Ci：工件i的完工时间

Cmax：最大完工时间

Sijk：Oij在k上的开始加工时间

fijk：Oij在k上的完工时间

约束条件：

Cmax≥Ci,∀i

(1.1)

Spqk≥fijk-(1-yijpqk)×L

(1.2)

(1.3)

(1.4)

Ci≥0,∀i

(1.5)

Sijk>0,fijk>0,∀i,j,k

(1.6)

其中，约束(1.1)定义了最大完工时间；约束(1.2)表示同一时刻一台机器只能加工一道工序；约束(1.3)表示工序加工次序约束，即一个工件前一道工序结束后才能开始下一道工序；约束(1.4)表示每道工序会且仅会分配给一台机器；约束(1.5)和约束(1.6)限制了决策变量的取值范围。

目标函数：

minCmax=min max(Ci),1≤i≤n

(1.7)

2 FJSP求解方法

FJSP于1990年由Brucker和Schlie[1]提出，其求解方法大致可以分为精确算法、启发式算法和智能优化算法三类。

2.1 精确算法

精确算法是指可求出最优解的算法，主要包括分支定界法、割平面法、整数线性规划，混合线性规划等。针对柔性制造系统优化问题，Lloyd等[2]提出了一种基于Petri网建模和改进分支定界搜索的调度算法，该算法首先对系统的Petri网建模进行了讨论，然后采用改进的分支定界搜索算法实现调度算法；Jiang等[3]采用了0-1整数规划，同时考虑了运行调度问题和交替过程计划的生产路径；Torabi等[4]提出了一种新的混合整数非线性规划，对机器的分配、排序、批量大小和调度进行决策，以解决柔性作业车间中的公共周期多产品批量调度问题，其中问题的规划周期是有限的。

精确算法是为调度目标找到最优的调度解，而非近优解。当问题规模很小时，利用精确算法找到问题的最优解所需要的计算时间是可以接受的，然而当问题规模逐渐增加，计算复杂度逐渐变高时，依照现有的计算条件，想要求出问题的最优解就变得十分困难。

2.2 启发式算法

启发式算法实质上是一组带有建议性质的规则集[5]，这个规则集可以用于指导算法搜索方向。在此规则集的指导下，可求得问题的较优解，但不一定是最优解。现有启发式算法大部分以启发式规则为主，这些规则多来自于实际的调度问题。目前，包括调度规则在内的许多启发式算法已经应用于处理FJSP。

Panwalkar和Iskander[6]于1977年提出了113个分配规则，这些规则到今天仍然具有极为广泛的应用；Scrich等[7]在求解以最小化总拖期为优化目标的FJSP时，基于禁忌搜索提出了两种启发式算法，即分层过程和多重启动过程，该方法利用调度规则得到初始解，然后在析取图表示的关键路径所生成的邻域中搜索改进解；Shanker等[8]将启发式算法与精确混合整数规划进行比较，并结合FIFO，SPT，LPT以及MOPR四种调度规则，提出了系统性能评价的一种仿真模型；针对柔性制造系统，Chang等[9]提出了一种波束搜索启发式算法，虽然这一算法比较复杂，但是与传统的调度规则相比，其性能更好；针对以最小化生产订单的平均拖期为优化目标，且具有转移批次的FJSP，Calleja等[10]提出了一种具有一定优先级的调度规则的算法，该算法考虑了有序变量和随机变量两个变量，使得分配规则具有优先级，同时用户可以为优先级规则分配权重；Teymourifar等[11]设计了一种有效的调度规则来求解具有有限缓冲区的FJSP；针对动态调度问题，Ozturk等[12]通过模拟和基因表达式提出了两种新的调度问题复合优先级规则的提取方法，该方法能够根据问题的特点得到特定的优先级规则；Ortiz等[13]提出了一种解决实际FJSP的调度规则，并通过实例验证了算法的性能。

针对实际具体的问题，启发式算法能够较快地作出反应并给出可行的调度方案，更重要的是算法的求解复杂度对问题规模不敏感，即算法在问题规模很大时依然可行。因而在求解FJSP时启发式算法发挥了重要作用。

2.3 智能优化算法

智能优化算法作为求解FJSP问题的重要研究方法，又可以分为进化算法(Evolution Algorithm，EA)和群智能算法(Swarm Intelligence，SI)等。

2.3.1 进化算法

EA的提出是受到自然界进化的启发。经典的EA包括遗传算法[14](Genetic Algorithm，GA)、进化策略[15](Evolution Strategy，ES)、遗传规划[16](Genetic Programming，GP)和差分进化(Differential Evolution，DE)等。以上方法中，GA的研究与应用最为广泛和深入。

Yuan等[17]结合局部搜索提出了一种混合差分进化算法用以求解以最大完工时间最小化为优化目标的FJSP，算法首先通过转换机制完成了从连续域到离散空间的转变，然后在DE的基础上嵌入一种基于关键路径的局部搜索算法，通过算法局部搜索能力的增强来平衡搜索的广度与深度；Wang等[18]针对动态FJSP提出了一种动态重调度方法，算法引入了重调度策略，另外还提出了改进的遗传算法以优化调度目标；Cao等[19]选取多个优化指标建立模型，然后利用一种改进的差分进化算法求解多目标FJSP，算法通过使用帕累托非支配排序方法，并引入设计良好的变异算子和交叉算子对DE进行改进；Huang等[20]在求解FJSP时采用一种基于反对学习的遗传算法，算法采用双链结构完成对染色体的编码，然后在进行遗传操作时提出了两种有效的交叉方法和两种变异方法；Gu等[21]在进行复杂FJSP的求解时提出了一种基于模拟退火和遗传算法的混合算法，算法利用云模型理论中的X条件云生成器生成遗传操作中的变异概率，并将模拟退火操作作用于结果的变异性；赵诗奎[22]针对FJSP，将邻域搜索嵌入遗传算法然后进行求解；朱光宇等[23]针对多目标FJSP选取多个优化指标建立模型，并采用基于直觉模糊相似度集的遗传算法求解FJSP，首先为提高种群质量，算法设计了一种考虑权重的启发式规则，然后引入了一种新的染色体交叉方法以优化算法性能，最后将解集中相似度值最大的解作为最优解。

2.3.2 群智能算法

群体智能(Swarm Intelligence,SI)是指具有简单智能的个体通过相互协作和组织表现出群体智能行为的特性[24]。通过观察动物群体的机制或包括觅食、捕猎、求偶、飞行等在内的某些社会行为，研究者们设计出了相应的群智能优化算法，这类算法提出后为人们解决科学、工业等领域的实际问题提供了新思路、新方法，得到了极为广泛的应用。在FJSP的求解上，它们也发挥了重要作用。

蚁群优化(ant colony optimization，ACO)是由Dorigo等人受蚂蚁觅食启发于1991年提出的一种群智能算法，整个蚁群通过在所经路径上释放信息素寻找蚁穴和食物之间的最短路径。ACO的提出为解决FJSP提供了新思路。董蓉等[25]结合遗传算法和蚁群算法提出了一种混合算法用以求解FJSP，算法首先利用遗传算法给出信息素的初始分布，然后采取局部更新信息素的策略，最后利用交叉算子扩大解空间；Wang等[26]在利用蚁群算法对FJSP进行求解时，从五个方面对传统蚁群算法进行了改进，这五方面分别是机器选择规则、初始化机制、信息素引导机制、节点选择方法、信息素更新机制；赵博选等[27]针对FJSP的两个子问题提出了一种分层Pareto优化框架，并利用该框架构建了两个Pareto蚁群系统分别求解这两个问题。

粒子群优化(Particle Swarm Optimization，PSO)是由Kennedy等学者受鸟群捕食启发于1995年提出的一种群智能算法。Kato等[28]采用分层的方法将FJSP分为两个子问题，然后利用PSO算法和随机重启爬山算法分别求解这两个子问题，提升了新算法的寻优能力；Zhang等[29]在对多目标FJSP进行求解时，将禁忌搜索算法应用在粒子群优化中，并通过实验证明了该混合算法具有良好的性能；Tang等[30]在求解FJSP时，将模拟退火算法应用于PSO，并将PSO离散化，算法采用PSO进行全局搜索以避免过早产生局部最优解，并结合模拟退火完成局部搜索；丁舒阳等[31]在利用改进的PSO求解FJSP时，首先将PSO离散化以使其适用于离散型问题的求解，然后通过引入操作算子完成FJSP两个子问题的更新，以加快种群的收敛速度；李俊萱等[32]通过在量子粒子群算法中引入交叉算子及一种更新策略，设计了一种混合算法用以求解加工时间不确定的FJSP；贾兆红等[33]将粒子群优化和禁忌搜索相结合用以求解复杂的多目标FJSP。

Karaboga从蜂群通过相互协作完成采蜜这一行为中获得灵感于2005年提出了人工蜂群算法(artificial bee colony，ABC)；Gao等[34]在ABC的基础上应用启发式规则，提出了一种改进的人工蜂群算法求解具有模糊加工时间的FJSP，并通过实验对算法的性能进行了验证；孟冠军等[35]为求解多目标FJSP提出了一种混合算法，该算法由禁忌搜索和改进的人工蜂群算法构成；郑小操等[36]对人工蜂群算法进行了改进，然后用其求解模糊柔性作业车间调度问题，算法通过在ABC的框架内嵌入邻域结构以进行局部搜索，然后引入混沌理论，最后设计了一种交叉操作。通过模拟萤火虫的闪光行为，Yang等[37]于2009年提出了萤火虫算法(Firefly Algorithm，FA)；Karthikeyan等[38]提出一种改进的萤火虫算法用以求解资源受限的多目标FJSP，该问题中选取的优化指标为最大完工时间、关键机器的工作量和所有机器的总工作量，算法首先对萤火虫算法完成从连续空间到离散空间的转换，然后将离散的萤火虫算法与局部搜索相结合，使得萤火虫的搜索精度有所提升，同时更好地实现了信息共享。Mirjalili等[39]模拟灰狼内部的社会层级和捕猎行为于2014年提出了灰狼优化算法(Grey wolf optimizer，GWO)；根据Muro等[40]的说法，灰狼捕捉猎物主要有以下几个步骤：追逐和接近猎物；包围和骚扰猎物；攻击猎物。GWO自提出后，已被成功应用于FJSP的求解。姜天华[41]在求解FJSP时，通过嵌入变邻域搜索策略及引入遗传算子，提出了一种混合灰狼优化算法，该算法建立起了GWO连续空间和FJSP离散空间的映射，同时其局部搜索能力和全局搜索能力也得到了很大提升。Mirjalili[42]从自然界中飞蛾的导航方法获得灵感于2015年提出了飞蛾扑火算法；陶婷婷等[43]在求解以最小化最大完工时间为目标的FJSP时，提出了一种改进离散型飞蛾扑火优化算法，该方法首先通过集成法的求解思想，设计了两段式编码转化机制，建立起染色体连续空间与问题离散决策空间的映射关系，实现了算法的离散化，然后在种群初始化阶段采取有效的方法，保证了种群的多样性和质量，最后利用随机更新算子和基于Levy飞行轨迹的随机游走策略，以优化算法性能。Mirjalili等[44]于2016年提出了鲸鱼优化算法(Whale Optimization Algorithm，WOA)，其灵感来源于鲸鱼捕食。鲸鱼进行捕猎时有两种行为，一种是包围猎物，所有的鲸鱼都向着其他鲸鱼前进；另一种是汽包网，鲸鱼环形游动喷出气泡来驱赶猎物。在每一代的游动中，鲸鱼们会在这两种行为中随机选择并进行捕猎。鲸鱼在对猎物进行包围的过程中，它们将会随机选择是向着最优位置的鲸鱼游去还是随机选择一只鲸鱼作为自己的目标并向其靠近。王思涵等[45]针对FJSP提出了一种改进的鲸鱼优化算法，首先将鲸鱼算法离散化，为此算法设计了一种新颖的个体位置表达方式并给出了计算距离的方法，然后引入协同搜索机制以扩大搜索范围，最后将变邻域搜索算法应用于改进的算法中以提高算法的局部搜索能力。

除以上提及的几种算法外，还有多种群智能算法被应用于FJSP的求解。Mekni等[46]对入侵杂草优化算法进行了改进，用以求解多目标FJSP，算法使用启发式规则对算法进行离散化，然后通过实验对算法性能进行了验证；王新刚等[47]在求解FJSP时采用了细菌觅食算法(bacteriaforagingoptimization，BFO)，算法设计了一种改进的自适应步停条件，避免了局部最优和早熟问题。Ge等[48]针对以最小化最大完工时间为目标的FJSP提出了一种有效的人工鱼群分布估计模型，该算法首先设计了一种前原则和后原则的排列机制，通过调整不同顺序的机器分配和操作顺序来提高种群的多样性。在此基础上，将种群划分为两个子种群后采用两种排列机制；然后基于分布估计设计了一种捕食行为，使得算法性能有所提升；最后通过一种吸引行为以提升算法的全局搜索能力，并提出了一种基于公共因子的关键路径搜索策略来提高局部搜索能力。Xu等[49]对蝙蝠算法进行了改进用以求解FJSP，算法首先设计了一种基于双柔度的编码策略，然后设计了变异和交叉操作以增强算法的搜索能力，最后提出了线性减小惯性权重的策略以调整惯性权重的取值，从而解决BAT算法中参数固定带来的问题。Liang等[50]在求解FJSP时提出了一种混合免疫算法，另外，算法为避免过早产生局部最优解采用了模拟退火操作。Zheng等[51]提出了一种基于知识引导的果蝇优化算法，算法首先采用了两种基于置换的搜索算子分别对作业序列和资源分配两个问题进行基于气味的搜索，然后引入知识引导搜索阶段以提高搜索能力，最后通过设计两个新的搜索算子完成对操作顺序和资源分配的调整。通过结合知识引导搜索与基于气味的搜索，算法实现了全局搜索与局部搜索的平衡，并利用数值实验证明了算法的有效性。

群智能算法原理简单、鲁棒性强，可在相对较短的时间内寻得近优解且易于实现，是一类很好的求解FJSP的方法。

3 结论及展望

随着经济和社会的快速发展，制造业也必然会遇到越来越多的机遇和挑战。智能制造是工业4.0需求的结果，大数据和人工智能等先进技术不仅为应对这些挑战提供了强有力的工具，同时还可以进一步指导制造业的新发展趋势。而随着制造业的快速发展，FJSP的需求和模式也一定会随之发生改变。

3.1 FJSP的新模式

在将来，FJSP必然会有更多的模式，如动态调度、在线调度和实时调度等，与此同时，优化目标必然也会随之增加。因此，为满足实际需求，多目标的FJSP应该得到更多的关注。另外，个性化需求也变得越来越复杂，这使得现实的生产条件和客户需求等实际的生产环境也越发复杂。所以在建立FJSP的数学模型时，除了考虑到基本的限制条件外，还应考虑到如生产资源、缓冲区大小、批次大小和生产成本等更多的约束。

3.2 FJSP的新解决方法

如今，大数据的发展势头正猛，在遇到难以建立数学模型的工程优化问题时，数据分析、机器学习以及神经网络训练等技术方法为解决这些问题提供了新的有效的求解途径。例如，在优化问题的模型建立过程中，可以通过大数据和人工智能技术从生产数据中提取有效的信息用以指导模型的建立，联合数据模型驱动的求解方法可用于求解复杂的FJSP。同时这些技术还可以用于预测诸如机器故障、新订单到达等随机动态事件的发生，对于解决动态FJSP也有很好的效果。另外，多个案例证明，智能优化算法在求解FJSP时具有很大的优势，因此在将来，更多的研究可以集中在新智能优化算法的设计上，同时可以将不同的算法结合起来，充分利用每个算法的优势以便更好地解决FJSP。