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

Improved Genetic Algorithm for Solving Multiple Flexible Job Shop Scheduling Problems

摘要: 针对柔性作业车间调度问题，考虑机器预维护的情况，建立了最小化最大完工时间、关键机器负载以及机器总负载为目标的调度模型，并提出一种改进遗传算法进行问题求解。根据问题特点，设计了基于工序和机器的双层编码，并采用三种种群初始化策略来生成初始种群。为了将解转化为可行有效的调度方案，设计了考虑运输时间以及机器预维护的插入式解码。采用不同的个体更新方式，并引入了变邻域搜索来提高算法的局部搜索能力，以避免陷入局部最优解。最后，在对基准算例改造并进行对比实验，验证了所提算法的可行性与有效性。

Abstract: A scheduling model was established to minimize the maximum completion time, critical machine load, and total machine load for the flexible job shop scheduling problem, taking into account ma-chine pre maintenance. An improved genetic algorithm was proposed to solve the problem. Based on the characteristics of the problem, a dual layer encoding based on process and machine was de-signed, and three population initialization strategies were used to generate the initial population. In order to transform the solution into a feasible and effective scheduling scheme, an insertion de-coding method was designed that takes into account transportation time and machine pre mainte-nance. Adopting different individual update methods and introducing variable neighborhood search to improve the algorithm’s local search ability to avoid falling into local optima. Finally, the feasibility and effectiveness of the proposed algorithm were verified by modifying the benchmark calculation example and conducting comparative experiments.

1. 引言

柔性作业车间调度问题(Flexible Job-shop Scheduling Problem, FJSP)是经典作业车间调度问题的重要分支，相较于普通的车间调度，FJSP消除了机器的唯一性，更适合当前的生产环境 [1] 。FJSP自从被提出以来，研究人员提出了多种算法来求解FJSP问题的最优解，Calleja和Pastor提出了一种具有一些优先级调度规则的调度算法 [2] ，Li和Gao提出了一种混合禁忌搜索(Tabu Search, TS)与遗传算法的方法来对FJSP进行优化 [3] ，郑捷，潘大志设计了一种改进萤火虫算法 [4] ，李轲研究了柔性作业车间机器与AGV集成调度方法 [5] 。

以上算法都从不同角度对FJSP进行了一定的优化，在实际生产过程中，往往需要考虑很多环境因素，如机器故障，机器加工速度，新工件插入，运输时间等，Wang等对考虑预维护活动时间固定和不固定的两种FJSP进行了研究 [6] ，包哲人等以能耗、完工时间、生产成本和质量为目标，提出了一种改进的离散蝙蝠算法，Karimi等针对工件运输时间提出了一种基于模拟退火的局部搜索与帝国主义竞争算法相结合的自适应算法进行求解，张立果研究了工件插入的模糊FJSP [7] 。

综上所述，本文考虑机器速度以及机器预维护的情况，建立了最小化最大完工时间、关键机器负载以及机器总负载为目标的调度模型，并提出一种改进遗传算法进行求解。根据问题特点，设计了基于工序、机器的双层编码，并采用三种种群初始化策略来生成初始种群。

2. 问题描述及数学模型

2.1. 符号定义

本文所涉及的变量符号及其含义如表1所示。

Table 1. Variable symbol definition

表1. 变量符号定义

2.2. 问题描述

本文研究的问题描述为：车间内有n个工件以及m台机器，每个工件有固定的工序等待加工。每台机器有一系列已知的维护计划，当机器需要进行维护时，将无法执行加工操作。调度目标为最小化最大完工时间、关键机器负载以及机器总负载。假设如下：

1) 工件和机器在零时刻可用；

2) 同一机器单次只能加工一个工件；

3) 同一工件不能同时被多个机器加工；

4) 工序一经开始不能中断；

5) 工件工序之间存在顺序约束；

2.3. 模型建立

2.3.1. 优化目标

基于以上假设，建立数学模型如下：

$f_1=\min \left(\underset{1\le j\le n}{\max }\left(C_j\right)\right)$ (1)

$f_2=\min \left(\underset{1\le j\le m}{\max }{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\displaystyle \underset{h=1}{\overset{h_j}{\sum }}{p}_{ijh}}}{X}_{ijke}\right)$ (2)

$f_3=\min \left({\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{\displaystyle \underset{h=1}{\overset{h_j}{\sum }}{p}_{ijh}}}{X}_{ijke}}\right)$ (3)

式(1)、(2)、(3)为优化目标，分别表示最小化最大完工时间、关键机器负载以及机器总负载。

2.3.2. 约束条件

1) 一个工件的工序先后顺序约束。

$s_{ijh}+x_{ijh}\times p_{ijh}\le c_{jh}$ (4)

式中： $i=1,2,3,\cdots ,m$ ； $j=1,2,3,\cdots ,n$ ； $h=1,2,3,\cdots ,h_j$ 。

$c_{jh}\le s_{j\left(h+1\right)}$ (5)

式中： $j=1,2,3,\cdots ,n$ ； $h=1,2,3,\cdots ,h_j-1$ 。

2) 工件完工时间约束。

$c_{j{h}_j}\le C_{\max }$ (6)

式中： $j=1,2,3,\cdots ,n$ 。

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

$s_{jh}+p_{ijh}\le s_{kl}+L\left(1-y_{ijhkl}\right)$ (7)

式中： $j=1,2,3,\cdots ,n$ ； $k=1,2,3,\cdots ,n$ ； $h=1,2,3,\cdots ,h_j$ ； $l=1,2,3,\cdots ,h_k$ ； $i=1,2,3,\cdots ,m$ 。

$c_{jh}\le s_{j\left(h+1\right)}+L\left(1-y_{iklj\left(h=1\right)}\right)$ (8)

式中： $j=1,2,3,\cdots ,n$ ； $k=1,2,3,\cdots ,n$ ； $h=1,2,3,\cdots ,h_j-1$ ； $l=1,2,3,\cdots ,h_k$ ； $i=1,2,3,\cdots ,m$ 。

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

${\displaystyle \underset{i=1}{\overset{m_{jh}}{\sum }}{x}_{ijh}=1}$ (9)

式中： $j=1,2,3,\cdots ,n$ ； $h=1,2,3,\cdots ,h_j$ 。

5) 机器维护时间之间的关系。

$E{T}_{iq}\le s{t}_{iq}\le L{T}_{iq}$ (10)

$f{t}_{iq}\ge s{t}_{iq}+D{T}_{kq}$ (11)

3. 改进遗传算法求解FJSP

遗传算法是一种优秀的全局并行求优搜索算法，但其局部搜索能较差，往往会陷入局部最优解。针对这一问题本章将具有全局搜索能力的遗传算法与具有局部搜索能力的变邻域搜索算法进行优势组合，同时结合改进的基于Pareto多目标优化方法，设计一种基于Pareto多目标混合算法。算法步骤如下图1：

Figure 1. Algorithm flow chart

图1. 算法流程图

3.1. 编码与解码

本文采用工序排序(Operation Sequence, OS)和机器分配(Machine Assign, MA)双层编方式对解进行编码。OS编码层由工件序号组成，假设OS编码中某个位置编码值为2，且2在OS中第三次出现，则表示工件2的第三道工序。MA层编码由工件可用机器的索引组成，并按照工件顺序依次编码 [8] 。以图2为例，上层OS编码表示的加工顺序为O₂₁-O₁₁-O₁₂-O₃₁-O₃₂-O₂₂；下层表示的是选择加工的机器在可选机器集中的序号，例如工序O₁₁可以在机器M₁和M₂上加工，染色体上的1表示选择可选机器集中的第一个，也就是M₁进行加工。采用这种方式进行下层染色体的编码，可以在编码时避免某些情况产生的“非法染色体”出现导致的求解失误。

Figure 2. Encoding example

图2. 编码示例

针对问题的特点，前文提到的编码方式不包含设备维护活动的信息，因此我们在解码过程中考虑了设备维护的安排。本文在考虑运输时间的基础上引入了贪婪机制，将工件插入到机器的空闲时段内进行加工，以提高机器的利用率，并进而提高生产效率和降低能源消耗。

3.2. 适应度计算

在多目标柔性作业车间调度问题的优化过程中，适应值分配(fitness assignment)是一个关键问题。对于单目标问题，解的适应度函数与目标函数是一致的，可以方便地对解进行排序比较。然而，在多目标优化中，多个目标之间存在相互冲突的情况，简单的排序评估无法有效衡量解的优劣，因此需要综合考虑多个目标 [9] 。为了解决这个问题，本文采用了一种快速非支配排序方法来对种群P进行分类，将其划分为互不相交且具有支配关系的子群体 $P_1\prec P_2\prec \cdots \prec P_r$ 。其中，S_p表示受个体p支配的集合，n_p表示支配个体p的个体数。具体执行步骤如下：

1) 创建两个空集合F和S，F集合用来存放非支配个体，S集合存放每个个体所支配个体的集合。

2) 初始化n_p为0，初始化S_p为空集合，前者表示p被支配的个体数，后者用来存放p所支配的个体。

3) 对种群中P中的个体进行比较，如果p支配q，则将q添加到S_p集合，n_q随之增加1，反之，若q支配p，则将n_p加1。

4) 对种群P中每个个体p进行判断，如果n_p = 0，则将p加入到F中，否则加入到S中。

5) 重复步骤3和4，直到种群P中所有个体处理完毕。

3.3. 交叉原则

交叉操作在模拟生物进化过程中起到关键作用，它是通过两个染色体进行交配和重组产生新染色体的过程。在遗传算法中，交叉操作是一项核心技术。常用的交叉方法包括GPPX、PBX、SPX、MPX、POX、LOX等 [10] 。本文以Brandimarte所提出的10个案例中的Mk10案例进行测试，以最大完工时间最小为目标函数，最大进化次数为200。分别选用以下不同的交叉算子进行测试10次，测试结果如表2所示：

Table 2. Calculation results of different crossover methods in the Mk10 case

表2. 不同交叉方法在Mk10案例计算结果

根据所采用的编码的特点，本文使用两种不同的交叉操作。首先是基于工序编码的POX交叉操作。POX交叉首先从父代P₁中选择一个或多个序号，并将它们放置在子代C₁相同的位置。然后按照顺序将父代P₂中未被选择的序号依次填补到子代C₁中，以满足特定条件。同样地，基于父代P₂中被选中的序号生成子代C₂，交叉过程如图3所示。第二种交叉操作是基于机器编码的MPX交叉操作MPX交叉操作的过程如下 [11] ：首先随机生成一个与染色体长度相等的由0和1组成的集合R，然后按照R中的1的位置顺序从P₁和P₂中选出相应的工序，并交换它们的机器分配。P₁和P₂中的其他机器保留在子代中，从而产生子代C₁和C₂，交叉过程如图3所示。

Figure 3. Schematic diagram of POX intersection

图3. POX交叉示意图

Figure 4. MPX cross schematic diagram

图4. MPX交叉示意图

3.4. 种群多样性保持策略

多目标优化算法在进化过程中经常会收敛至单个解，因此应尽可能得到一组分布均匀的非劣解集。本文主要采用两种方法来保证种群多样性，动态交叉概率以及拥挤距离 [12] 。动态交叉是指在选择交叉个体时，一部分是两个个体通过锦标赛选择得到，另一部分来自记忆库和锦标赛选择。拥挤距离计算方法如下：

1) 初始化集合个体中每个个体的拥挤距离为0。

2) 对于每个目标函数维度，首先根据该维度对个体集合进行排序。

3) 对排序后的个体集合，去除最大和最小个体，计算其余个体在当前维度的拥挤距离，设当前维度为k，个体P_i的拥挤距离计算方法如下：

$D\left(P_i\right)=D\left(P_i\right)+\frac{k\left(P_{i+1}-P_{i-1}\right)}{k^{\max }-k^{\min }}$ (12)

4) 归一化处理所有个体的拥挤距离，除以集合的规模，确保拥挤距离在合理的范围内。

3.5. 精英保留策略

目前，多目标遗传算法迭代过程中精英个体的保留方式主要有两种，一种是将新旧种群合并进而选择个体，另一种方法是将算法进化过程中搜索到的非劣解保存到外部记忆库。在进化过程中合理的利用非劣解可以加快算法的收敛速度。本文采用第二种方法。对每一次产生的新种群进行评价排序，然后对外部记忆库进行更新。在每次更新过程中，进行如下操作来处理新解和记忆库中的解 [13] ：

1) 针对新解，检查是否有记忆库中的某个解支配它。如果有，则丢弃该新解。

2) 如果新解支配了记忆库中的某个解，则用新解替换掉记忆库中被支配的解。

3) 如果新解与记忆库中的解互相之间没有支配关系，即它们是非支配的，则将新解加入记忆库。

4. 算法测试与结果分析

4.1. 对比实验

为了验证算法的性能，采用一些数据集进行测试，采用的基准算例包括8 × 8、10 × 10及15 × 10三个测试算例。运行参数为：种群规模P = 200，GS比例为0.5，LS比例为0.3，RS比例为0.2。种群的最大迭代次数G为200，变异概率P_m = 0.02。结果对比如下所示。

在8 × 8问题中，涉及到8台机器和8个工件，总共涉及27道工序。平均而言，每道工序有多台机器可供选择加工，实验数据如表3所示。

Table 3. 8 × 8 Experimental data

表3. 8 × 8实验数据

在10 × 10问题中，涉及到10台机器和10个工件，共涉及30道工序。每道工序都有10台机器可供选择加工，实验数据如表4所示。

Table 4. 10 × 10 Experimental data

表4. 10 × 10实验数据

在15 × 10问题中，涉及到15台机器和10个工件，总共涉及56道工序。每道工序都有10台机器可供选择加工，实验数据如表5所示。

Table 5. 12 × 10 Experimental data

表5. 12 × 10实验数据

由以上结果可知，本文改进遗传算法在算法稳定性，搜索能力上均有较好的表现。

4.2. 结集分布性评价

解集的分布性是评价多目标优化算法的重要指标，通常用分布度D与变化率R来表示。为验证本文算法的解集分布性，用本文算法对Dpdata实例进行求解，并与Kacem的求解结果进行对比 [13] 。在Dpdata实例中，有18个问题，这些问题涉及工件数量从10到20，机器数量从5到10的不同组合。每组问题中，工序数在5到25之间变化。程序会连续运行20次。平均结果如表6所示。

$D={\displaystyle \underset{i=1}{\overset{P}{\sum }}\frac{\left|d-\bar{d}\right|}{P}}$ (13)

$R={\displaystyle \underset{i=1}{\overset{N}{\sum }}\frac{\left|D_i-\bar{D}\right|}{N}}$ (14)

式中：d表示Pareto非支配解集中相邻两个个体之间的欧几里得距离， $\bar{d}$ 代表d的平均值， $D_i$ 为每次求得的分布度D， $\bar{D}$ 代表 $D_i$ 的平均值，P表示非支配解集中解的个数，N为运行次数。

Table 6. Comparison of algorithm distribution

表6. 算法分布性对比

由上述结果可知，本文算法相对于Kacem具有更好的分布性以及稳定性。

5. 结语

本文针对传统的柔性作业车间调度问题引入了运输时间和机器预维护这两种实际因素，并在优化完工周期的基础上，进一步考虑了能源消耗目标。研究工作主要集中在考虑运输时间与机器预维护的柔性作业车间绿色调度问题。首先，建立了一个调度模型，旨在优化最小化最大完工时间、关键机器负载以及机器总负载。随后，设计了一种基于Pareto排序的多目标遗传算法以解决该问题。在该多目标遗传算法中，采用了多种方法来生成能够平衡加工时间和能耗的初始种群。此外，构建了带有预维护动态调整策略和考虑运输时间的贪婪插入解码方法，并与最早预维护策略以及最晚预维护策略进行了对比，以验证所提出的预维护计划安排策略的有效性。针对不同的解情况，设计了不同的个体更新方式。最后，通过与AL + CGA、POS + SA算法在不同规模的测试算例下进行对比实验，验证了本文设计的多目标遗传算法的有效性。需要指出的是，本文所研究的问题模型尚不完善，与实际生产情况存在一定差距，尚未考虑到机器故障和紧急订单等情况。这些方面将在后续的研究中得到进一步完善，以使模型更贴近实际情况。

基金项目

浙江省2023年度“尖兵”“领雁”研发攻关计划(2022C01SA111123)，国家自然科学基金资助项目(51475434)。