改进遗传算法求解柔性作业车间调度问题

阳光灿，熊禾根

(武汉科技大学机械自动化学院，湖北 武汉 430081)

1 引言

作业车间调度问题(JSP，Job shop scheduling problem)是一类具有机器约束和顺序约束的组合优化问题，在数学上属于是典型的NP-Hard问题。与JSP相比，柔性作业车间调度问题(FJSP，Flexible job shop scheduling problem)减少了机器约束，是一类更符合实际生产情况的调度问题，但同时增加了机器分配问题，扩大了可行域空间，是更复杂的NP-Hard问题。文献[1]将FJSP分为部分柔性和全部柔性，部分柔性指每道工序仅可以在给定的机器集合加工，全部柔性指每道工序可以在所有机器上加工。通常，将FJSP的求解分为两个子问题：机器分配和加工顺序。对此，大多数文献对两个子问题分别进行编码，即采用两级编码方式。对于机器分配问题，目前主要有两类编码方式[2]，第一类是根据基于操作的编码的对应编码，第二类是按工件进行编码；对于加工顺序问题，通常采用基于操作的编码。对于机器编码，除随机编码外，相关研究还提出一系列编码策略[3-4]，比如平衡机器负荷、全局最小加工时间、局部最小加工时间。同机器编码一样，对于基于操作的编码，除随机编码外，相关研究也提出了一系列编码策略[3]，比如剩余加工时间最多、剩余工序数量最多、最短加工时间。对于两个子问题的编码方式，文献[5]还采用了基于知识的编码。基于两级编码方式，解码方式一般分为半主动解码和主动解码。半主动解码方式简单并直接产生一个可行调度方案，为大多数研究采用的解码方式。主动解码比半主动解码复杂，文献[6]提出一种主动解码方式，方法为在解码工序加工所选择的机器上找到一个介于解码工序前序工序的加工完成时刻与机器上的最大完成时间之间的相邻工序时间间隔大于解码工序加工时长的时间间隔，则将解码工序的加工开始时刻移至相邻工序中的左端工序的加工完成时间后。文献[6]的解码算法未考虑解码工序前序工序的加工完成时刻与时间间隔的开始、结束时刻之间的关系，因此该解码算法不能充分利用机器上的空闲时间，比如存在这样一个时间间隔，其开始时刻小于解码工序前序工序的加工完成时刻，但解码工序前序工序的加工完成时刻与时间间隔的结束时刻之间的时间间隔大于等于解码工序的加工时长，则也可以将解码工序插入其前序工序的加工完成时刻之后，进而更充分利用机器上的空闲时间。

对于NP-Hard类问题的求解，比如0/1背包问题、路径规划问题、旅行商问题、作业车间调度问题、柔性作业车间调度问题。多数研究均采用近似优化算法，如遗传算法[3-4，6-13]、蚁群优化[5]、粒子群优化[14]、灰狼优化算法[15]。其中遗传算法(Genetic algorithm，GA)具有鲁棒性好、全局寻优能力强等特点，在众多领域得到广泛应用。比如，文献[7]应用遗传算法求解了数值优化问题；文献[8]基于遗传算法求解了物流配送车辆路径问题，提出了一种贪婪自适应随机算法改进遗传算法的邻域搜索能力；文献[9]提出一种改进遗传算法求解了旅行商问题，简化了遗传算法；文献[10]基于遗传算法求解0/1背包问题，提出了一种二重结构编码，结合“贪心法”提高了遗传算法的搜索效率；文献[11]应用遗传算法求解无人机航迹规划问题，引入差分进化变异策略增加变异的多样性，结合模拟退火算法提高全局搜索能力。

也有大量研究将遗传算法应用于柔性作业车间调度问题。比如，文献[4]提出一种改进的遗传算法，采用了两级编码方式，机器编码采用第一类机器编码，并采取了不同的编码策略，根据机器编码和结合最早允许加工时刻再生成基于操作的编码，以保证生成的调度为主动调度，提高了求解效率；文献[12]结合年龄分层人口结构(Age-Layered Population Structure，ALPS)和遗传算法，并应用了自适应概率，提高了遗传算法的全局搜索能力；文献[13]提出了一种改进遗传退火算法，也采用两级编码方式，机器编码采用第二类机器编码，遗传操作中采用自适应交叉变异算子，同样提高了遗传算法的全局搜索能力。

本文以最小化最大完工时间为目标研究FJSP，编码方式为仅采用基于操作的编码，并提出一种解码算法。在解码算法过程中以最早完成时刻为规则选择工序的加工机器以可能达到优化目标，并充分利用机器上的空闲时间。与两级编码方式不同，遗传操作仅需对基于操作的编码进行，得到了极大的简化。

2 问题描述

柔性作业车间调度问题可描述为有n工件m机器，每个工件有ni道工序，每道工序有一个加工机器集合，安排工序的加工机器及每台机器上工件的加工顺序，以实现某个优化指标。

假设不同工件的工序之间没有顺序约束；同一时刻，一台机器只能加工一个工件；工件加工不允许抢占；所有工件在0时刻释放；所有机器在0时刻可用。

以4工件3机器，各工件的工序数量2～3为例，一个部分FJSP的例子如表1，其中，“-”表示工序不能在对应机器上加工。

表1 一个部分FJSP的例子

本文以最小化最大完工时间为优化指标，即最小化Makespan。

3 改进遗传算法

采用遗传算法进行求解柔性作业车间调度问题，改进了染色体编码方式，研究了一种解码算法。

3.1 编码与解码

与两级编码方式不同，对染色体编码仅采用基于操作的编码，每个工件i出现ni次。比如，以表1的数据为例，一条染色体的编码为[4，3，2，1，4，3，2，4，1，2]。

基于编码方式，提出一种解码算法。在解码过程中以最早完成时刻为规则选择工序的加工机器以可能达到优化目标，若存在多台机器具备相同的最早完成时刻，则采取随机策略。采用空闲时间段的开始时刻和空闲时长来记录每台机器上的空闲时间段，将满足空闲时间插入的条件分为两类：(一)机器上的空闲开始时刻大于等于当前解码工序的前序工序完成时刻(若不存在，则设置为0)，且空闲时长大于当前解码工序在对应机器上的加工时长。与文献[6]相似，区别在于未限制机器；(二)机器上的空闲开始时刻小于当前解码工序的前序工序完成时刻(若不存在，则设置为0)，且前序工序完成时刻至当前解码工序对应机器的空闲结束时刻之间的时间间隔大于当前解码工序在对应机器上的加工时长。一个满足两类空闲时间插入条件的例子如图1。从图1中可看出，机器上的空闲时间能得到充分利用。

图1 一个满足两类空闲时间插入条件的例子

以表1的一个部分FJSP数据为例，染色体编码以[4，3，2，1，4，3，2，4，1，2]为例，进行解码，得到图2的调度结果。

图2 一个解码算法的调度结果

对应的主要解码过程如表2。

表2 一个解码算法的主要过程

3.2 遗传操作

遗传操作中，选择操作基于精英策略的轮盘赌选，变异操作采用两点交换变异。在JSP、FJSP中，POX是最常用的交叉操作，文献[16]分析指出POX交叉在迭代初期具有较快的收敛速度，但在迭代后期种群中的个体会变得相似的缺点，并采用了错位操作。采用改进的POX。与POX不同，改进的POX选择的是一系列离散的工序集合，且最大工序集合选择数量在编码长度的20%～50%之间，提高了交叉的灵活性，其步骤如下：

步骤一：从父代中随机选择相同的工序集合；

步骤二：保持工序集合在父代中的位置不变，按顺序交换剩余工序集合。

交叉操作的一个例子如图3，其中选择的工序集合为{O4，2，O2，1，O3，2，O1，2}。

图3 改进POX交叉操作的例子

终止条件为达到最大滞留代数或达到算例的现有下界值。

4 仿真及结果分析

为验证改进遗传算法(Improvedgeneticalgorithm，IGA)的可行性和有效性，采用BRData基准算例进行实验，对每个算例独立运行10次。并与文献[14]所提的DPSO(2018年)、文献[15]所提的HGWO(2018年)、文献[17]所提的Heuristic(2014年)以及文献[12]所提的ALPS-GA(2019年)的最优Makespan进行对比。算法采用Python3编程。运行环境为Windows10系统，AMDE1-7010处理器，4GRAM。遗传算法参数设置：种群规模200，交叉概率0.85，变异概率0.05，最大迭代次数150，最大滞留代数100。

仿真结果及对比如表3。其中LB代表算例的现有下界值，Best表示算法的最优Makespan。RPD表示IGA的Best与其它文献所提算法的Best的相对百分比偏差，计算公式为RPD=100×(比较算法的Best-IGA的Best)/比较算法的Best。S.D.列的值表示运行10次，改进遗传算法得到最优解的标准差。

表3 实验结果及对比

从表3可以看出，IGA在5个算例上优于DPSO，在7个算例上优于HGWO，在9个算例上优于Heuristic及在9个算例上优于ALPS-GA；IGA的最优解与DPSO、HDWO、Heuristic以及ALPS-GA的相对百分比偏差如图4，从中可以看出相对百分比偏差的值多数为正值、平均相对百分比偏差均为正值且较大，表明与DPSO、HDWO、Heuristic以及ALPS-GA相比，IGA在解的质量上具有较大优势。

图4 相对百分比偏差

各算例结果的箱形图如图5，用*标记改进POX的仿真结果，与POX进行比较。从中可以看出，改进POX的仿真结果中mk1～3、mk6～9的解较为集中；mk4～5、mk10的波动程度较小，且其表3中对应的S.D.值均较小；与POX相比，mk1～mk2、mk6～mk7、mk9的解更集中、平均值更优，mk4～mk5、mk10的平均值更优，表明与POX相比，IGA具有更好的求解效率和稳定性。

图5 各算例结果的箱形图

以上分析表明改进遗传算法在编码方式与解码算法上是正确的、可行的和有效的，且具有较高的求解效率和较好的稳定性。

求解mk1、mk2的一个最优调度甘特图分别如图6、7。

图6 求解mk1的一个最优调度甘特图

5 结束语与展望

以最小化最大完工时间为目标研究了柔性作业车间调度问题，仅采用了基于操作的编码，极大简化了遗传操作，并提出了一种解码算法。采用标准算例进行了实验，通过对比验证了改进遗传算法在编码方式与解码算法上的正确性、可行性和有效性，且具有较高的求解效率。考虑企业生产的实际需求，对于柔性作业车间调度问题的研究，通常包含多个目标，比如交货期、加工成本、人力成本等。因此，在今后的研究中，可以研究多目标FJSP的求解，且考虑启发式编码和在解码过程中实施不同的规则以可能实现多目标优化。

图7 求解mk2的一个最优调度甘特图