一种面向FJSP的混合优化遗传算法

侍守创，江 浩，韩占港，蒋馨宙

(1.中国船舶重工集团公司第七一六研究所，江苏 连云港 222002；2.哈尔滨工程大学计算机科学与技术学院，黑龙江 哈尔滨 150001)

1 引言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem，FJSP)是一类满足任务配置需求和顺序约束要求的组合优化问题，属于NP-hard范畴[1]。

近年来，针对FJSP问题，国内外学者进行了许多相关研究，并取得了一些成果。目前代表性研究方法有粒子群算法、遗传算法、邻域搜索算法等，同时学界提出可采用启发式算法如禁忌搜索算法[2]、模拟退火算法[3]、遗传算法[4]以及蚁群算法[5]等解决该问题。魏巍等人[6]以加工质量、加工成本和加工工期为多目标，并采用一种改进的Pareto算法进行优化，缺陷是不适合数据规模较大的问题，并且FJSP是NP-hard问题，其求解时间随着数据规模增大而迅速增长，而近似方法可以在确定时间内得到一个较优解。针对FJSP的求解方法大致分为精确方法和近似方法两类，精确方法适用于小规模FJSP问题，当问题规模增大时，便不再适用[7]。基于智能优化算法的解决方案能够在可行时间内求得大规模FJSP问题的近优解，现已成为解决柔性作业车间调度问题的主流方法以及研究热点。Xia和Wu[8]提出了使用粒子群和模拟退火相结合的方式来解决FJSP，但是多次运行结果方差较大，不能有效得到一个较优解。Fattah和Mehrabad[9]提出一个数学模型并采用禁忌搜索和模拟退火算法来解决实际生产环境中的作业调度问题，然而对约束情况较多、情况较复杂的柔性作业车间问题解决能力差。Gao和Sun[10]提出一种解决 FJSP 的混合遗传算法，使用邻域下降和改进染色体结构相结合的方式，提高种群中个体的适应性，但是编码方法过去复杂。Yao和Hu[11]提出了一个优化蚁群算法，通过改进适应性参数和交叉算子等来提高算法效果。其中，遗传算法以其隐式并行处理能力、鲁棒性强的特点，在FJSP问题上得到了广泛应用。然而，传统遗传算法存在收敛速度过快、容易陷入局部最优的缺陷，应用效果并不是十分理想，因此，学界对遗传算法进行了不同程度的改进[12]。刘胜等人[13]采用非线性排序法重新设计了轮盘赌选择算子，以及工序编码段和机器编码段双变异的互换变异算子;张国辉等[14]设计一种局部搜索、全局搜索及随机产生相结合的初始化种群的方法，提高种群初始解的质量，缺陷是算法处理时间过长;张超勇等[15]提出一种改进的基于工序的编码以及主动调度的解码机制，不能有效解决多目标问题。Jin Wang等[16]提出并实现了其实时化基于实时制造数据的调度，为了得到一个可行解，采用了无限次重复博弈优化方法，缺点是需要较长的时间才能得到一个近优解。Robert L等[17]提出了一种改进的元启发式算法，增加了资源分配染色体和改进了用于抢占处理和资源分配的扰动操作符。

本文提出一种混合优化的遗传算法，从染色体选择、变异等多个步骤入手进行优化，在确定的时间内，对多目标柔性作业车间调度可以得到一个有效的近优解，且收敛速度更快。

2 问题描述

2.1 柔性作业车间调度

对在柔性作业车间调度问题中，任务由一系列工序组成，每台机器所需处理的工序不确定。对每一道工序，都有一组具有不同处理时间的机器可用。问题描述涉及的变量符号定义如下：

● 任务集：J={J1，J2，J3，…，JN}，其中Ji∈J(i=1，2，…，N)为第i个任务

● 机器集：M={M1，M2，M3，…，MR}，其中Mr∈M(r=1，2，…，R)为第r个机器

● 工序集：O={O1，O2，…，ON}，Oi∈{O1，O2，…，ON}为第i个任务的工序

● 工序数目：ni，任务Ji的工序数，每一个任务Ji由ni道工序组成

● 工序子集：Oi={Oi1，Oi2，…，Oini} ，其中Oij，(j=1，2，…，ni)表示任务Ji的第j道工序

● 完成工序Oij的机器集合：Zij

● 参与处理工序Oij的机器：Mk∈Zij⊆M

● 加工时间：pijk，任意的机器mk∈Zij处理工序Oij的加工时间

给定N个加工任务J={J1，J2，J3，…，JN}，由R台机器M={M1，M2，M3，…，MR}完成；其中每个任务Ji∈J包含ni道工序{oi1，oi2，…，oini}，每道工序Oij可由机器集合Zij中的机器完成。

且该问题需满足以下约束条件：

1)初始状态约束：所有机器在0时刻可用，所有任务0时刻可进行；

2)机器占用约束：一台机器同一时刻最多只能进行一道工序；

3)任务进行约束：任一任务在每一时刻仅能在一台机器上进行，并且任务的不同工序需按给定的先后顺序进行，不同任务的工序之间是独立的，没有先后约束；

4)工序连续加工约束：任一工序一旦开始，便不允许中断。

则柔性车间作业调度问题可分解为：

1)任务分配问题：合理分配每一道工序Oij给机器Mk∈Zij。

2)资源调度问题：动态规划某台机器上分配的任务，以获得一个全局优化的解，使得适应度函数尽可能的小。

2.2 适应度函数

本文基于四种约束条件：最少等待时间，优先级优先，最少超期任务和强制保障，定义以下适应度函数：

1)最少等待时间

(1)

其中，Ci为任务Ji的实际完成时间。最少等待时间即找出实际完成时间最长的任务，最小化其所需花费时间。

2)优先级优先:预先为N个任务制定优先级，优先级高的需优先完成。

3)最少超期任务

(2)

式中，vi表示任务Ji的权重，Ti定义为任务未在预期时间内完成的超期惩罚，ei表示任务Ji的预期完成时间，并且有

Ti=max{0，Ci-ei}

(3)

4)强制保障：任务集中，存在某些任务是必须要保障完成的，称为强制保障。

3 mGAs算法

3.1 算法优化

本文提出的混合优化遗传算法，在个体选择阶段采用量子粒子群算法优化个体选择算子，并采用精英保留策略筛选出适应度最大的个体；在交叉和变异阶段，使用了交叉概率和变异概率动态变化的方式，并且设计了机器链段编码基于贪心算法的单点变异算子。总体算法流程图如图1所示。

图1 混合优化遗传算法基本流程图

3.1.1 染色体编码及适应度函数确定

本文采用分段编码方式，第一段编码为工序排序，对工序的加工顺序进行编码，第二段编码为对每道工序所需机器进行编码。此种编码方式可将工序和机器相对应，不仅能保证产生可行调度，还可避免死锁问题。

设某一任务的适应度由最晚完工时间、优先级优先和最少超期任务三个约束条件约束，其适应度函数为

(4)

式中，FullFillTime为最晚完工时间，Tardiness为超期惩罚，定义如下：

(5)

式中，Ci为任务Ji的预期完成时间，ei为任务Ji的预期完成时间。

3.1.2 初始化种群及个体选择

对使用随机生成方式进行初始种群的产生，可保证初始种群个体的多样性，使个体尽可能地分布在解空间的大部分区域。

个体选择阶段，首先根据建立的种群，将单个染色体作为粒子，开始粒子的寻优迭代，继而对粒子最优位置以及粒子群的最优位置进行计算并对结果进行分析，选出若干个体，最后使用精英策略从选出的个体中筛选出适应度最大的若干个体。其竞争选择过程如图2所示。

图2 个体竞争选择示意图

3.1.3 交叉与变异

本文测试了三种交叉算子：顺序交叉(OX)、循环顺序交叉(COX)、混合顺序交叉(MOX)，以及两种变异算子：逆转变异(OBM)、互换变异(SBM)，根据测试结果，最终采用效率最高的顺序交叉算子产生子代染色体。

变异的作用是使算法能探索新的解空间，跳出局部最优解。变异算子的选择对算法能否求得全局最优解有很大的影响。对于工序段的变异，是以互换变异实现的，即随机交换工序段序列两个不同位置处的值，如图3所示。

图3 染色体工序段变异示意图

对机器段序列的变异则使用贪心算法：随机产生一个变异点，再根据变异点对应工序的加工机器集，对该点的值进行更新。若存在一个机器Mi，对于同一道工序Ok，其加工时间少于当前变异点值所指向机器Mj的加工时间，则更新当前基因值为i，其中，Mi与Mj都属于实现工序Ok的机器集。

如图4所示，随机产生的变异点为最后一位，对应任务3的第二道工序，并且存在机器M2加工时间少于当前指向机器M1，则更新当前机器编码变异点值为2。

图4 染色体机器段变异示意图

3.1.4 染色体解码及其优化

解码染色体包括任务分配以及工序调度两步。

完成任务分配，需顺序遍历染色体的工序段，根据当前遍历的工序进行任务分配和适应度函数的求解。例如，设当前工序段基因序列为

[3，2，1，3，1，1，2，3，2]

则据此序列以及机器段编码，依次将工序分配给指定的机器加工队列进行加工。然而在实际任务分配过程中，常常存在机器工序序列的间隔过大的问题，也就是存在两个相邻工序，其间的等待时间过长，完全可以将后续的符合一定约束条件的工序提前，进行“插队”操作。实现“插队”操作的伪代码如下：

算法1 染色体解码及优化伪代码

输入 待插入工序p，机器任务队列MissionQueue

输出 处理完的机器任务队列MissionQueue

1)BEGIN:

2)Initialize:gapBegin=0，gapEnd=0

3)for m in MissionQueue do

4)gapEnd=m.Start;

5)if gapEnd-gapBegin >=p.costTime

&&gapEnd-costTime>=preProcessFinishTime do

∥工序“插队”需要满足的约束条件

6)if preProcessFinishTime>=gapBegin do

7)p.Start=preProcessFinishTime

8)else

9)p.Start=gapBegin;

10)end if

∥更新工序的开始和结束时间

∥preProcessFinishTime是p的前置工序结束时间

11)p.End=p.Start+p.costTime

12)insert(m，p)

13)return MissionQueue

14)end if

15)gapBegin=m.End;

16)end for

∥更新工序的开始和结束时间

17)update(p.start，p.end)

18)enQueue(MissionQueue，p);

19)return MissionQueue

20)END

3.2 算法描述

算法2：算法整体框架伪代码

输入 数据集，算法参数：初始种群大小(PS)，交叉率(CR)，变异率(MR)

输出 调度方案

1)BEGIN:

2)Initialize:initial population

3)Evaluate population

4)while not reach the termination condition do

5)while not yield enough individual do

∥量子粒子群和精英策略相结合进行个体选择操作

6)Select individuals from population by QPS and elite strategy

7)if reach crossover condition do

8)update(CR)

9)Crossover individuals which were selected

∥工序段：顺序交叉

10)Procedure sequence:OX

∥机器段：两点交叉

11)Machine sequence:two-point crossover

12)end if

13)end while

14)if reach mutation condition do

15)update(MR)

∥工序段：两点交换

16)Procedure sequence:two-point swapping

∥机器段：基于贪心算法选择变异机器

17)Machine sequence:choose the machine with least process time

18)end if

19)yield new population

20)Evaluate new population

21)end while

22)output a optimized schedule

23)END

在设置完算法参数之后，接着随机产生初始种群。初始种群中的每一个个体的工序段基因序列和机器段基因序列都是在编码的规则下随机产生的。在个体选择时加入量子粒子群算法，提升了收敛速度和最终产生的解的质量。算法最终会在达到预设的最大迭代次数时，或者产生预期的解时，终止循环，最后输出结果。

4 实验验证

4.1 实验设计

本文选用Bradimarte[18]提出的若干个不同测试实例集(Mk01(10*6)、Mk03(15*8)、Mk05(15*4)和Mk08(20*10)等)对提出的混合优化遗传算法进行实验验证。

算法运行环境如表3所示。

表3 运行环境参数

本文测试所选择的混合优化遗传算法运行参数如表4所示，表中n为任务数，m为机器数。

表4 算法运行参数

4.2 实验及结果分析

在最大完工时间的约束条件下，本文采用的混合优化遗传算法，与GANCE[19]和eGAs[20]同时使用Bradimarte提出的基准测试数据进行测试并比较。

由图5所示，分别使用文献[20]和本文提出的算法在Mk04数据集上运行了5次，其中包含了15个任务和8台机器，记录了平均最大完工时间随着种群迭代次数的增加而减少的折线。从折线可以看出，在数据集相同、最终结果相近的情况下，本文所提出的算法在收敛速度上更具有优势。

图5 mGAs与其它遗传算法在Mk04上的对比

图6中，本文所提出的算法与文献[19]和文献[20]中的算法在若干个数据集上的运行时间之间的对比。根据数据集的复杂程度，初始种群数在50到300之间，运行次数为5次，最终取平均值作为结果。

图6 mGAs与其它算法在运行时间上的对比

图7中，在Mk02、Mk04和Mk06上运行本文算法，从运行结果可以看出在迭代一定次数后，算法可以得到一个较好的近优解。

图7 mGAs在Mk0等测试集上的对比

图8 Mk01测试数据运行结果甘特图

5 结束语

本文在基于传统遗传算法解决柔性作业车间调度问题的研究基础上，使用动态调整交叉和变异概率的方式优化传统遗传算法的交叉和变异算子，有效解决了遗传算法过早收敛的问题；使用量子粒子群优化传统遗传算法的选择算子，使得算法在运行结果上更加可靠。最后，通过在测试集上对本文算法以及其它算法进行对比实验，证明本文所提出的混合优化遗传算法可以在更短的时间内获得一个有效的近优解，并且验证了该算法的有效性。