改进的离散型萤火虫优化算法求解柔性作业车间调度问题

郑 捷，潘大志,2

(1.西华师范大学数学与信息学院，四川 南充 637009; 2.西华师范大学计算方法与应用研究所，四川 南充 637009)

0 引 言

自柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)由Brucker等[1]提出以来，就一直受到各个领域专家学者的关注[2-8]。与经典的JSP不同，FJSP中的每一道工序可以在多台机器上加工，且不同的机器上加工时间不相同，已被证明为NP-hard问题。其调度目标是以某个加工性能指标为目标函数来确定各个工件的工序在各机器上的加工顺序，通常以最小化最大完工时间、最小化最大能耗、最迟完工时间等为目标函数。

张桐瑞等[9]以最小化最大完工时间为目标，提出了混合竞争群优化算法求解柔性作业车间调度问题，以混合竞争优化算法为基础，加入POX交叉与环形拓扑结构相结合，引入邻域搜索，增加算法的全局搜索能力和局部搜索能力；戴月明等[10]提出了一种骨干双粒子群算法求解柔性作业车间调度问题；姜天华[11]提出了一种混合灰狼优化算法求解柔性作业车间调度问题；谢锐强等[12]以最小化最大完工时间为目标函数建立模型，提出了一种求解柔性作业车间调度问题的两段式狼群算法；陶婷婷等[13]针对最大完工时间最小化为目标，提出了一种改进离散型飞蛾扑火优化算法求解柔性作业车间调度问题；张捷等[14]提出了基于郊狼优化算法求解柔性作业车间调度问题；Wang等[15]提出了改进的ACO算法求解FJSP；Li等[16]提出了基于Pareto的离散人工蜂群算法求解多目标柔性作业车间调度问题。但是，目前尚未找到可以求得所有问题的最优解的算法。因此国内外的学者们仍在积极地探索，以寻求更为丰富和有效的方法。

本文将FA应用到柔性作业车间调度问题中，首先对FJSP进行描述和建模；然后根据FJSP的特点，提出一种改进的离散的萤火虫算法(DFA)；利用标准算例对算法进行仿真，验证DFA求解FJSP的有效性；最后，通过与传统算法进行仿真对比，验证DFA求解FJSP的优越性。

1 柔性作业车间调度问题

1.1 问题描述

FJSP可描述为：有n个待加工的工件和m台机器，每个工件有ni(1≤i≤m)道工序，且工序间必须遵循一定的加工顺序。与JSP不同，FJSP问题中每道工序可以在多于一台机器上进行加工，且已知每道工序在每台加工机器上的加工时间。FJSP需解决2个问题：机器选择和工序排序。机器选择是为每道工序选取合适的加工机器。工序排序是确定在同一机器上各个工序的加工顺序。FJSP需要满足以下条件：

1)同一时刻同一机器只能加工一道工序。

2)一旦工件的某一工序开始加工，它就不能被中断，直至该工序加工完成。

3)任何工件都不具有加工优先级。

4)不同工件的各个工序没有加工顺序的约束，同一工件的各个工序有加工顺序的约束。

5)任何工件在零时刻都能被加工。

1.2 变量定义

变量定义如下：

M={Mk|1≤k≤m}，表示机器集；

J={Ji|1≤i≤n}，表示工件集；

Oi={Oij|1≤j≤ni}，表示Ji的工序集；

Mij={Mk|Xijk=1}表示工件Ji的工序Oij的可用机器集；

Ci表示工件Ji的完工时间；

Pijk表示工件Ji的第j道工序Oij在机器Mk上的加工时间；

Sijk表示工件Ji的第j道工序Oij在机器Mk上的开始加工时间；

Eijk表示工件Ji的第j道工序Oij在机器Mk上的结束时间；

1.3 数学模型

本文以最小化最大完工时间为优化目标，目标函数f为：

f=min{max(Ci)},i=1,2,…,n

(1)

约束条件：

Eijk+Pijk≥Eegk,Rijegk=1,Xijk=1

(2)

Sijk+Pijk=Eijk,Xijk=1

(3)

Eijk≤Si(j+1)h，Xijk=Xi(j+1)h=1

(4)

其中式(2)表示1.1节中条件1)的约束；式(3)表示1.1节中条件2)的约束；式(4)表示同一工件的加工顺序必须按照工艺顺序进行。

2 萤火虫算法

萤火虫算法(FA)是由剑桥大学的Yang[17]于2008年提出的一种基于群体智能的随机搜索算法。为构建FA的数学模型，使用以下3个理想化准则：

1)所有的萤火虫都不分雌雄。

2)萤火虫之间的吸引力与距离成反比，与亮度成正比。

3)萤火虫的亮度与待优化的目标函数值有关。

根据上面的理想化准则可知，亮度与吸引度是FA中2个重要的影响因子，假设问题空间规模为d维，第i只萤火虫在d维空间中的位置表示为xi=(xi,1,xi,2,…,xi,d)。

定义1 萤火虫的亮度：

(5)

式(5)中，I0为萤火虫的初始亮度，取决于需要寻优的目标函数值，一般用式(6)表示；γ为光强吸收因子；rij为萤火虫i与萤火虫j之间的欧氏距离，一般用式(7)表示。

I0=f(x)

(6)

(7)

定义2 吸引度：

(8)

式(8)中β0为最大的吸引度。

定义3 位置更新公式：

(9)

式(9)中，α为随机步长因子，取值范围为(0,1)；rand为服从在(0,1)上均匀分布的随机数。

3 改进的离散型萤火虫算法

3.1 编码与解码

由于FJSP需解决工序排序与机器分配这2个问题，因此编码应该包括工序编码和机器编码2个的部分。本文采用两段式编码方式[18]，编码长度为工序总数目，假设工序数目为l，则编码的总长度为2l。示例编码如图1所示。

图1 示例编码

图1中，第一段为基于工序顺序的编码，记为工序向量Xprocess[l]。第二段为基于机器分配的编码，记为机器向量Xmachine[l]。对于工件序列，可以表达加工的序列为(O1,1,O3,1,O2,1,O4,1,O3,2,O2,2,O1,2,O4,2,O3,3,O2,3)，其对应的加工机器为(M4,M3,M2,M1,M2,M3,M2,M1,M4,M1)。即O1,1在机器M4上进行加工，O3,1在机器M3上进行加工。

解码方法：本文采用插入式贪婪解码[19]的方法，获得主动调度解。首先通过机器向量编码来获得每道工序的机器选择方案，然后确定工序在对应加工机器的加工时间，最后根据工序向量确定工序加工顺序，依次进行解码，在不推迟其他已经安排好工序的开工时间的条件下，将工序插入到对应机器上最早可行的加工时刻进行加工[20]。

3.2 种群初始化

由于初始种群对种群的多样性以及算法的求解效率有着极其重要的影响，因此，在生成初始种群的机器向量时，种群中50%的个体使用本文提出的机器选择策略进行生成，另外50%的个体的机器向量采用随机选择的方式生成，而对于工序序列，则采用完全随机的方式生成。

3.3 机器选择策略

本文采用根据工序最小完工时间来选择机器的策略。记工序可选择的设备集为C，可选择的设备个数为λ，该工序选择加工机器上的前一工序的完工时间为ti1，该工序对应工件的前一工序的完工时间为t，工序所选取的机器上的加工时间为ti2。则按照工序的加工顺序在每个工序的可选设备集中选取使得当前完工时间tc最小的机器。将其存入机器向量Xmachine[l]中，并更新工序的完工时间表。具体的机器选择策略如公式(10)和公式(11)所示。

tc=min(tCi), 1≤i≤λ

(10)

(11)

3.4 局部搜索算法

为了增强算法的局部搜索能力，对种群适应度排名前5%的个体进行局部搜索。首先生成一个0～1之间的随机数r，若r>0.5，则采用最优插入操作[21]；否则采用最优交换操作[21]。

1)最优插入操作。

首先记录当前工序序列以及其对应的目标函数值，其次在[0,l]之间产生一个随机整数，在原工序向量中将对应位置的元素删除，得到一个工序序列。然后将此元素从左到右依次插入原工序序列中，并更新机器向量，然后计算新生成序列的目标函数值，当新生成序列的目标函数值比原序列的目标函数值更优时，则退出循环，并更新个体的编码序列，否则继续进行插入操作，直到循环结束。其示意图如图2所示。

图2 最优插入操作

2)最优交换操作。

首先记录当前工序序列以及其对应的目标函数值，其次在[0,l]之间产生一个随机整数，在工件序列中将对应位置的工件号记录下来，然后与其他位置的工件号从左到右依次进行交换，并更新机器向量，然后计算新生成序列的目标函数值，当新生成序列的目标函数值比原序列的目标函数值更优时，则退出循环，并更新编码序列，否则，继续最优交换操作，直到循环结束。其示意图如图3所示。

图3 最优交换操作

3.5 改进的离散型萤火虫算法

由于标准的萤火虫算法适用于解决连续优化问题，而FJSP是一种典型的离散优化问题，因此有必要针对FJSP的特点，提出一种改进的离散型萤火虫优化算法(DFA)。此时，萤火虫的位置更新如公式(12)所示：

(12)

图4 改进的离散型萤火虫算法

图5 交叉操作

Step1将工件集随机分为2个集合A1和A2。

3.6 改进的离散型萤火虫算法流程

本文针对FJSP问题的特点，提出一种改进的离散型萤火虫算法DFA。由于本文以最小化最大完工时间为目标函数，因此目标函数值越小，代表个体的亮度越高。DFA的算法步骤如下：

Step1设置种群规模、最大迭代次数、工件数量、机器数量等。

Step2对种群进行初始化。

Step3计算种群中每个个体的适应度值，标记适应度最高的个体为Xbest。

Step4若I(i)

Step5使用改进的离散型萤火虫算法更新个体的工序向量，使用机器选择策略更新个体的机器向量，并更新个体的适应度值。

Step6对种群适应度排名前5%的个体进行局部搜索，并更新Xbest。

Step7判断是否达到终止条件，如果达到，则跳转到Step8，否则跳转到Step4。

Step8输出结果。

4 仿真实验与结果分析

为了验证DFA算法是否能够有效求解FJSP，选取一个8×8的标准算例[22]对DFA在柔性作业车间调度问题中的应用进行可行性验证，算例原始数据如表1所示。同时也对Kacem[23]标准测试数据集进行仿真实验。

表1 算例原始数据

设置种群规模NIND=40，迭代次数MAXGEN=50，仿真结果如图6所示，仿真软件为Matlab R2018a，硬件如下：计算机内存为8 GB，处理器为Inter(R) Xeon(R) E3-1240 v5，主频为3.50 GHz。

图6 仿真结果

对于Kacem数据集，设置种群规模NIND=40，迭代次数MAXGEN=50，每个算例独立运行10次。测试结果如表2所示。

表2 算法求解结果(最小化最大完工时间)

表1中，Oi,j为第i个工件的第j道工序，M1～M8为各加工机器。由图6中的调度甘特图可知，调度结果满足表1算例的加工要求，验证了DFA在柔性作业车间调度问题中的可行性。表2验证了DFA在柔性作业车间调度问题中的准确性。

将DFA与求解FJSP中应用最为广泛的2种传统算法——遗传算法(GA)和粒子群算法(PSO)进行仿真对比。各算法的种群规模均为40，迭代次数均为50，得到各算法种群收敛对比图如图7所示。

图7 算法种群收敛对比图

由图7可知，GA与PSO算法在寻优过程中容易陷入局部最优，从而导致收敛的效果不佳。DFA通过局部搜索可有效地避免算法陷入局部最优，同时也增强算法的寻优能力。

5 结束语

各种群智能优化算法广泛应用于柔性作业车间调度问题，但由于传统的群智能优化算法的寻优能力不足，容易陷入局部最优。本文针对柔性作业车间调度问题，将DFA引入FJSP，提出了一种全新的离散方式，并在此基础上引入了局部搜索算子。通过对建立的柔性作业车间调度问题的模型进行仿真实验，验证了DFA在求解FJSP问题的可行性。通过与GA和PSO算法进行对比，表明了DFA在求解FJSP问题的优越性。