一种求解柔性作业车间的改进遗传算法

王玉芳，葛嘉荣，缪 昇，马铭阳

(1.江苏省大气环境与装备技术协同创新中心， 南京 210044；2.南京信息工程大学 自动化学院， 南京 210044；3.江苏省大数据分析技术重点实验室， 南京 210044)

柔性作业车间调度问题(flexible job shop scheduling problem，FJSP)是一种经典车间调度问题，其作为传统作业车间调度问题(job shop scheduling problem，JSP)的延伸，具有更广泛的使用环境和更复杂的求解空间。超过3台机器的JSP已被证明是NP问题[1]。因此，作为延伸问题的FJSP也具有NP困难。FJSP问题中包含2个子问题：机器选择和工序排序问题。2个决策空间增加了求解难度。

多年来，如禁忌搜索[2]、遗传算法[3]、粒子群算法[4]、人工蜂群算法[5]等的许多智能算法被用于解决车间调度问题。李明等[6]引入殖民同化和革命策略的新型帝国竞争算法在解决多目标FJSP中取得了高质量的解；Zhang等[7]通过加强局部搜索弥补遗传算法“易早熟”的缺陷；Maroua等[8]结合实际生产活动，提出了双步粒子群算法，保持了算法的鲁棒性；顾九春等[9]提出基于记忆池的离散个体更新方法，使多目标算法的适用性更强。但这些算法大多从算法本身或模型入手，未采取启发式规则，难免造成算法性能冗余。另外，如何跳出局部最优解一直都是求解FJSP的重点和难点，还存在很大的改进空间。针对上述问题，提出一种改进遗传算法(new improved genetic algorithm，NIGA)求解FJSP。

1 问题描述

FJSP问题描述：工件集{J1，J2，…，Jn}中的n个工件要在机器集{M1，M2，…，Mm}中的总计m台机器上进行加工，每个工件包含若干道工序，每道工序有若干台机器可以选择，工序的加工时间也因机器的选择不同。

根据实际生产情况，FJSP问题需要满足以下约束条件：

1) 每个工件的每道工序只能同时由1台机器加工；

2) 同一机器在同一时间只能加工1个工件；

3) 工序一旦开始加工就不能停止；

4) 所有工件工序无优先级配置；

5) 同一工件的工序具有先后约束，不同工件之间没有先后约束。

为方便后续描述，进行符号定义，见表1。

表1 符号定义

目标函数分别为最大完成时间、总机器负载和最大机器负载。

Cmax=min{maxCi}

FJSP模型约束条件为：

Sij+Xijk×Tijk≤Cij

(1)

Ci(j-1)≤Sij

(2)

Cij≤Cmax

(3)

Sij+Tijk≤Sxy+H(1-Yijxyk)

(4)

Ci(j-1)≤Sij+H(1-Yijxyk)

(5)

(6)

Sij≥0，Cij≥0

(7)

式(1)和式(2)表示同一工件的工序必须按照顺序逐步加工；式(3)表示任意工序的完工时间都不得超过最大完工时间；式(4)和式(5)表示任一时刻的任一机器只允许同时处理一道工序，其中H是一个很大的数；式(6)表示在某一时刻一道工序只能同时由1台机器加工；式(7)表示任意工序的开始时间和完成时间均为非负，且任意工件都可以从0时刻开始加工。

2 算法设计

遗传算法是由Holland[10]在1970年提出的一种基于自然选择和遗传学原理的智能算法。其通过模拟自然环境，对种群进行选择、交叉和变异操作，得到下代种群，经过若干代的进化获得最终结果。因其鲁棒性好、隐性并行性和全局搜索能力强等特点，被广泛应用于各领域。本文中根据FJSP模型和遗传算法的特点，提出NIGA算法以求解FJSP问题。

2.1 编码和解码

考虑到FJSP的2个子问题——工序排列和机器选择，采用并行双链式进行编码。第1层为基于工序的编码层(operation sequence，OS)，第2层为基于机器选择的编码层(machine sequence，MS)。如图1所示，OS层的数字表示工件号，出现的次数为当前工件的工序号；MS层按照工件工序顺序排列，在本图中的4表示3号工件的第1道工序在4号机器上加工。OS层和MS层的长度相等，均为PS。这种编码方式保证了后续的交叉、变异和局部搜索等策略产生的解仍然是可行解，并对工件的工序长度和工件数量无任何要求，简单灵活；另一方面，对一层的单独操作不会影响到另一层，具有很强的并行性能。

图1 编码示意图

解码的主要目标是根据编码层的形式获得空间范围内优质的解。提出一种最优插入法(optimal insertion method，OIM)，以实现染色体解码对解空间的高效搜索。其步骤如下：

步骤1判断是否为该工件的第一道工序，如果是第1道工序，空闲起点判断为0；否则，空闲起点为该工件上一道工序的完工时间；

步骤2寻找空闲起点之后的空闲时间段，选择其中大于等于待加工工序的加工时间的时间段。如果不存在满足条件的插入空闲，则按顺序正常加工；

步骤3选择与待加工工序加工时间最接近的空闲插入；

步骤4重复步骤1～3，直到所有工序加工完成；

步骤5计算最大完成时间。

OIM插入过程如图2所示。工序Oih将在机器Mb上加工，根据当前加工情况，有3段空闲可供选择，空闲1、2、3均大于等于Oih的加工时间。空闲1的起始时间大于工序Oi(h-1)的结束时间，不满足约束条件；空闲2和空闲3都满足插入条件，且空闲2的空闲时间更接近Oih的加工时间，因而选择空闲2插入。相对于一般的贪婪插入方法，该策略能够为后续工序的插入提供更多的空间，减少空闲时间从而获取更优质的解。

2.2 初始化

遗传算法中，种群初始化是关键的一步，初始解的质量直接影响种群在整个搜索空间的分布程度及算法收敛速度。已有研究通常采用随机初始化方法，使得解的质量偏低，往往需要更多的迭代次数才能获得更优的种群质量。本文中针对单目标及多目标问题分别设计不同的初始化方法。

图2 OIM插入过程示意图

2.2.1面向单目标的种群初始化

单目标部分采用文献[11]的GLS初始化方法。该方法将MS编码层初始化分为3部分：全局选择(global selection，GS)、局部选择(local selection，LS)和随机选择(random selection，RS)；OS编码层采取完全随机的方式产生。

2.2.2面向多目标的种群初始化

多目标部分对GLS方法进行改进，在MS编码层初始化部分添加完全最小化(global load minimization，GLM)和部分最小化(local load minimization，LLM)，以加快最大负载机器负载的收敛速度，OS编码层不变。GLM为所有工件的工序选择候选机器负载最小的机器进行加工，LLM为部分工件的工序选择候选机器负载最小的机器进行加工。

2.3 交叉操作

交叉的目的是经过一系列操作之后产生新的个体，在尽量保持优良基因的前提下高效地搜索解空间，因而交叉操作必须满足可行性、继承性、信息非冗余等特性。针对编码方式和遗传算法的特点，采用两种交叉方式：针对OS层染色体的IPOX[12]交叉和针对MS层染色体的多点交叉。因IPOX交叉具有低约束和良好基因继承等特性，用其完成OS层的交叉操作；MS层采取顺序编码方式，对交叉的要求较高，故而采用不破坏基因有效序列的多点交叉方式。

多点交叉步骤如下：

步骤1随机选择2个父代个体father1和father2；

步骤2随机产生1组维度与MS染色体一致的0、1数组L；

步骤3子代个体child1继承father1对应L数组为1位置的基因，子代个体child2继承father2对应L数组为1位置的基因；

步骤4将father2中未选中的基因按顺序插入到child1的空白位置，将father1中未选中的基因按顺序插入到child2的空白位置。

2.4 多重变异操作

变异操作是指通过对染色体进行小幅度扰动形成新的个体，以维持种群多样性，在一定程度上影响遗传算法的局部搜索能力。常用的变异操作有互换、逆序、插入等，但用于FJSP问题都无法取得理想效果。在FJSP中，机器选择往往比工序排列对结果影响更大，因此采用多种机器的多重变异策略——随机机器和最小加工时间机器选择，以维持种群多样性。

多重变异伪代码如下：

2.5 变邻搜索策略

虽然引入基于MS染色体的变异操作在一定程度上能够增加种群的多样性，但OS染色体部分未做改进，算法仍然可能陷入局部最优。针对这一问题，设计了针对OS编码的变邻搜索策略，该策略包括3种操作。

操作A：几何排列出1段染色体的所有情况，其步骤如下：

步骤1随机选择1条OS染色体；

步骤2随机从n个工件中选择若干个工件；

此外，现场施工期间未见钢拱架发生明显变形现象，围岩的承载能力和稳定性显著提高；采用全站仪对拱顶60°及拱底45°范围内的测点进行观测，对比分析拱顶的围岩变形情况，发现围岩变形量值不大，新增变形量不超过10 mm，收敛速度趋缓；在后续TBM掘进过程中，未出现明显的涌水、塌方现象。可见，采用化学灌浆加固强蚀变岩洞段，对掌子面和护盾位置进行超前预注浆并及时封闭围岩，并依据注浆模拟试验成果对注浆及支护参数进行优化，是一种有效的堵水和加固围岩的实用方法。

步骤3从被选中的每个工件随机选择一道工序；

步骤4未被选中的OS染色体基因保持原位不动，对选中的部分进行枚举排序，得到一组新的OS染色体；

步骤5对新得出的OS染色体组进行适应度计算，如果存在适应度大于原OS染色体的新个体，则替换原解；否则，不做任何操作。

操作B：将1段OS染色体随机打乱顺序。

操作C：随机交换OS编码层中2个位置的元素。

3种操作方法对OS编码层的扰动程度逐渐降低，以应对迭代过程中过度收敛的情况。在种群初期，采取扰动小的策略A，随着迭代的进行，继而采用B、C两个策略以维持种群在后期的多样性。

2.6 算法流程

根据上述改进策略，提出解决柔性作业车间问题的NIGA算法求解步骤：

步骤1根据2.2节中提出的规则进行种群初始化并设置相关参数；

步骤2通过OIM对种群进行适应度计算；

步骤3通过锦标赛选出要进行后续操作的群体；

步骤4对被选中的群体的OS层进行IPOX交叉，MS层进行多点交叉；

步骤5对MS层进行2.4节中提出的多重变异操作；

步骤6对OS层进行2.5节中提出的局部搜索操作；

步骤7得到的新一代种群进行适应度计算并根据适应度降序排序，保存这一代的最优个体；

步骤8循环终止判断，如果满足跳至步骤9；否则，跳转至步骤3；

步骤9最优解输出，算法结束。

算法流程如图3所示。

3 结果与分析

NIGA采用Matlab编程实现。程序在Windows 10系统，主频为2.6 GHz、内存为8 G的计算机上运行。各项参数设置：种群数量pop=2*n*m；交叉概率pc=0.8；变异概率pm=0.05；最大迭代次数gen=100；多重变异A、B和C三种操作的概率为[iter/gen； iter/(2*gen)； iter/(2*gen)]，其中iter为当前迭代次数。

图3 NIGA算法流程框图

3.1 算法复杂度分析

算法的复杂程度主要从时间复杂度和空间复杂度2个方面进行评价。

NIGA的时间复杂度主要取决于种群初始化及适应度计算。适应度排序采取快速排序，其复杂度为O(pop2)；解码部分最坏情况的复杂度为O(m*PS)；锦标赛选择的复杂度为O(pop)。迭代次数为gen，算法的时间复杂度为O(gen*pop(pop+m*PS))。

空间复杂度是指算法在运行过程中占用计算机的内存空间，一般为正常占用之外的额外开销。NIGA采用的编码占用PS*pop 的数组存储空间，后续操作均未占用额外的空间，所以算法的空间复杂度为O(1)。

3.2 NIGA单目标测试分析

为了验证NIGA的可行性和有效性，从单目标和多目标2个方面进行测试分析。其中单目标为最小化最大完成时间，初始规则比例为0.6∶0.3∶0.1。采用Brandimarte中的10个算例，与文献[13-16]进行对比测试。

从表2的运行结果可以看出，所提出的算法在解决Brandimarte系列算例时，除了MK02外，其他9个算例均取得了4个算法中最优解，证明NIGA在解决不同机器和不同工件的问题时都具备良好的性能。

表2 算法结果

以MK04为例，其收敛曲线如图4所示，每代解在总体上呈现明显下降，尤其在20代之前下降速度明显，说明采取的初始化策略能够有效加快收敛速度，在60代附近找到最优解并保持稳定；另外，种群的均值虽然也存在明显下降趋势，但与当代最优解仍然存在较大差距，说明NIGA算法采取的变邻域策略有效地维护了种群的多样性。MK04的调度甘特图见图5。每个方块的第1个数字为工件号，第2个数字为工序号。

3.3 NIGA多目标测试分析

为进一步探究NIGA的性能，进行多目标对比试验。求解多目标问题仍然采用Brandimarte系列算例，初始化规则比例为0.6∶0.1∶0.1∶0.1∶0.1，以最小化最大完成时间、最小化机器总负载和最小化最大机器负载为目标函数。为适应不同规模的算例，迭代次数调整为gen =2*n*m，交叉概率调整为Pc=0.8*(1-iter/gen )，变异概率调整为Pm=0.05+0.1*(1+iter/gen )，其他参数与单目标保持一致。NIGA的运行结果如表3所示。表中每个算例都得出了若干个非支配解，决策者可根据实际生产需求选择具体的调度方案。

图4 MK04收敛曲线

不同于单目标的衡量指标，多目标调度不能简单地从单方面判断性能，解的数量是衡量性能的重要指标之一。表4中，将NIGA与其他3个算法[17-19]进行对比。其中，N表示得到的非支配解个数，time为算法的运行时间。可以看出，NIGA在其中6个算例中均取得了最高数量的Pareto解，可给予决策者更多的选择。在实际调度生产中，同时需要更快的处理速度，NIGA在解决同类问题时具有较快的处理速度，虽然在维数较低的问题上比MOGA稍有不足，但在处理多工件多机器的算例时，速度提升的同时未减少支配解的数量，可以证明NIGA具有良好的求解质量和响应速度。

表3 NIGA Brandimarte算例结果非支配解

表4 NIGA与其他算法的解的数量及运行速度

4 结论

针对柔性作业车间调度问题，建立了以最小化最大完成时间、最小化机器总负载和最小化最大负载机器为目标的数学模型，提出了改进的遗传算法进行求解。初始解采用多种方式混合产生，提高了初始种群的质量；使用OIM插入的解码方式，实现了解空间的高效搜索，加快了收敛速度；针对不同编码层使用不同策略维持种群的多样性，避免算法陷入局部最优；采取变邻域搜索增强局部搜索能力。通过运行Brandimarte算例，从单目标和多目标2个方面对比验证了本文中算法的有效性和寻优性能。后续将研究以效率和碳排放为目标的多工厂多目标分布式调度。