基于改进遗传算法的柔性作业车间调度研究*

金 秋 王清岩 原博文

（天津科技大学经济与管理学院，天津 300457）

柔性作业车间调度问题（FJSP）是柔性制造系统中的一项关键调度问题，有效的生产调度对于提高工业生产效率和资源利用率具有重要意义。在FJSP 中，每个作业都可以在不同的机器上完成，并且每个作业在每台机器上的加工时间可能存在差异。此外，每个作业的工序顺序也可能不同，使得FJSP 成为一个复杂的NP-Hard 问题[1]。

在解决FJSP 问题时，Brucker P 和Schlie R 提出了一种多项式图算法[2]，然而该算法在处理多工件、多机床、大规模和多约束调度问题时效果不佳。因此，研究人员开始尝试采用启发式优化算法来解决这些问题。

粒子群算法[3]、遗传算法[4]、贪婪算法[5]和蚁群算法[6]等是常见的启发式算法，在学术研究中被广泛应用。相较于其他算法，遗传算法具有过程简单、搜索能力快和鲁棒性好等优点。因此，在解决柔性作业车间调度问题时，遗传算法被广泛采用[7-10]。然而，传统的遗传算法存在收敛速度慢和容易陷入局部最优等问题。因此，近年来国内外研究人员对传统的遗传算法进行了改进，以克服其不足之处。王佳怡等[11]构建了一个多目标混合整数线性规划模型，设计了一种改进的遗传算法，引入了基于多父代的交叉算子和多种变异算子，并结合了精英保留和轮盘赌选择策略。姜一啸等[12]提出了一种低碳调度模型，采用改进的带精英策略的非支配遗传算法（NSGA-II）来优化该模型。唐艺军等[13]提出了一种改进的混合遗传算法，结合了模拟退火算法和莱维飞行扰动策略，以提高算法性能。赵慧娟等[14]提出了一种方法，考虑不同情境下目标权重系数的变化，并采用改进的遗传算法来优化完工时间、能耗和质量的权衡模型。Chen R 等[15]提出了一种自学习遗传算法（SLGA），其中采用遗传算法（GA）作为基本优化方法，并基于强化学习（RL）对其关键参数进行智能调整。

根据国内外学者们对FJSP 的相关研究现状，存在以下几个问题：（1）使用的优化算法的寻优能力一般，主要是算法的反应时间太长，容易进入局部最优解，并且关键参数无法进行有效的动态调整，导致求解效率和质量无法满足生产要求；（2）优化的目标过于单一，优化目标往往只考虑了最大完工时间，没有反映车间的实际生产情况。

为此，本文建立以最大完工时间和能耗为目标的数学模型，提出了一种改进算法。该算法针对无法动态调整参数的问题，对交叉变异算子进行了非均匀改进，并引入了基于邻域的变异算子，以提高算法的搜索能力和稳定性。

1 问题描述及数学模型

1.1 问题描述

FJSP 是对经典JSP 的扩展，用于描述N个待加工工件在M台机器上进行加工。每个工件由S道工序组成，FJSP 问题的主要参数见表1。

1.2 柔性作业车间调度模型

对于FJSP，每个作业由一系列优先级受限的操作组成，这些操作的加工时间在不同分配的机器之间是不同的。本文旨在建立一个多目标柔性作业车间调度模型，目标函数是将归一化的最大完工时间和能耗加权最小化，见式（7），并给出一些约束条件。

约束条件：

对目标函数的处理、加权：

最小化最大完工时间用式（1）表示；通过式（2）可以实现最小化加工能耗；式（3）描述了同一工件工序的先后约束关系；任一工序的完工时间均需满足式（4）的约束；式（5）表示工序的加工时间大于零；式（6）表示所有工件在0 时刻开始加工。式（7）为目标函数，其中 φ为权重系数，0＜ φ＜1。

2 改进遗传算法

2.1 改进遗传算法流程

改进后算法流程图如图1 所示，具体步骤如下。

图1 改进后的遗传算法流程图

步骤一：设置相关参数，随机生成一组初始种群。

步骤二：编码与解码。

步骤三：采用轮盘赌策略，选择优秀个体。

步骤四：计算种群个体适应度值。

步骤五：对选中父代进行均匀交叉操作，改变个体的编码，再经过非均匀交叉率筛选。

步骤六：对工件编码进行邻域搜索变异操作，对机器编码采用单点变异，再经过非均匀变异率，以此提高算法的搜索能力和稳定性。

步骤七：判断是否满足终止条件，如果达到最大迭代次数或达到停止条件时，终止迭代过程，否则返回步骤四。

步骤八：输出结果。

2.2 编码与解码

FJSP 的染色体由操作顺序部分和机器分配部分组成，这种编码方式可简化解码过程，降低成本。图2 展示表2 中的一个FJSP 实例的编码示例，它表示优化问题的解决方案，其中操作的机器分配用粗体表示。染色体的长度是操作次数的两倍，在该实例中共有8 个操作，因此染色体的长度为16。扫描操作顺序时，工件层按照从左到右的顺序，第一个“l”是指在机器M3上处理的作业J1的第一个操作，对应机器分配部分的“3”；第二个“1”表示将在机器M2上处理的工件1 的第二个操作，对应机器分配部分中的“2”。根据上述说明，机器M1的操作顺序为O41→O21→O32，机器M2为O31→O42→O12，机器M3为O11→O22。求解的操作顺序和机器分配可以解释为：{(O11,M3),(O41,M1),(O31,M2),(O21,M1),(O42,M2),(O32,M1),(O12,M2),(O22,M3)}。

图2 表1 染色体的编码图

表2 一个4×3 的部分FJSP 实例

2.3 适应度函数

适应度函数是评估个体质量、筛选方案和确定群体中优秀个体的方法。通常，适应度函数通过计算个体的适应度来实现，该适应度基于目标函数值的倒数。在遗传算法中，适应度函数起着重要作用，能够量化个体的适应程度，并作为选择和进化的依据。通过适应度函数的评估，遗传算法能够优化搜索过程，保留和发展群体中更优秀的个体。适应度函数为

式中：fit(f(x)) 为适应度值；Cmax为最大完工时间；E为机器加工的总负荷；φ为权重系数。

2.4 选择操作

为了使遗传算法在迭代早期朝着更好、更有优势的方向发展，选择操作用于从群体中选出优秀的个体。常用的基于适应度值进行选择的方法是轮盘赌选择法。该方法根据个体的适应度值来确定选择概率，适应度值越高的个体被选中的概率也越高，这样可以确保优秀的个体在群体中得到更多被选择的机会，记为Pa。

Pa的计算公式为

式中：fa为群体中每个个体的适应度值；F为种群的总适应度。

2.5 交叉操作

本文采用了均匀交叉方式来生成新个体。具体实现是随机选择两个个体的基因位，并以相等的概率交换这些基因位，从而产生两个新的个体。这种交叉方式的目的是增加遗传算法的多样性，提高全局搜索的效果。为解决这个问题，引入了非均匀交叉概率Pc：

式中：Pc0表示初始交叉率；gen表示当前迭代次数；MAXGEN表示总的迭代次数；γ为(0,1)的常数。

在遗传算法中，交叉操作采用了多种不同的方式，包括均匀交叉、多点交叉、局部均匀交叉、顺序交叉和周期交叉等方法。这些方法提供了多样的策略，用于在遗传算法的进化过程中实现基因的交换和组合。本文采用了均匀交叉方式，其具体实现是随机选择两个个体的基因位，并以相等的概率交换这些基因位，从而生成两个新的个体。均匀交叉是一种常见的遗传算法交叉操作方式，能够帮助算法更好地搜索解空间，增强全局搜索能力。均匀交叉的示例图如图3 所示。

图3 染色体工序编码交叉示例图

被选择进行交叉操作的基因位在图3 和图4 中为阴影部分，而每一个基因位被选择的概率都是随机的，不是确定的。

图4 染色体机器编码交叉示例图

2.6 变异操作

传统遗传算法领域，常见的做法是使用固定的变异概率进行操作。然而，这种方式可能使算法陷入局部最优解，从而无法找到更优的解决方案。为了解决这个问题，可以引入非均匀变异率Pm，使得遗传算法在搜索空间中进行更全面的探索。

通常情况下，初始阶段的变异率较高，以便快速地探索解空间。随着迭代次数的增加，变异率逐渐降低，以便更精确地搜索最优解。具体的非均匀变异率可以根据式（11）来计算。

式中：Pm0为初始变异率。这个函数的意义是，随着迭代次数的增加，变异率会随之缓慢降低，ρ的范围在(0,1)，作用是控制变异率的下降速度，ρ的值接近1 时，变异率的下降速度会比较缓慢；ρ的值接近0 时，变异率的下降速度会比较快。运用非均匀变异使得变异率随着迭代次数的增加逐渐降低，以达到更好的优化效果。本文提出了一种改进的工件编码变异方法，旨在提高子代适应度并朝着更优的方向进化，同时保持种群多样性。该方法利用基于邻域搜索的变异算子来进行工件编码的变异。在机器编码中，采用了单点变异法来替换机器的选择操作。具体的操作示意如图5 和图6 所示。

图5 工序层基于邻域操作的变异操作

图6 机器编码单点变异操作

变邻域变异操作具体步骤如下：

（1）选出一定数量的不同位置，代表不同工件的基因。这些位置可以是随机选择或者使用其他策略进行选择。

（2）对于这些位置进行全排列，生成当前邻域中的所有解。对这些位置进行全排列，可以得到邻域解的不同组合。

（3）计算每个邻域解的适应度，根据具体问题使用适应度函数进行评估。

（4）具有最佳适应度的邻域解被选择为当前解。根据适应度的评估结果，选择适应度最高的邻域解作为当前解。

通过以上步骤，可以实现变邻域操作，增加搜索空间和多样性，从而提高算法的收敛性和搜索能力。

3 仿真结果与分析

为了评估本文提出的改进非均匀交叉和非均匀变异的遗传算法的性能，选取基准算例kacem01 和kacem03 进行测试[16]。其中，kacem01 算例表示4个工件对应5 台加工机器，而kacem03 算例表示10 个工件对应10 台加工设备。使用Matlab R2023a作为具体的数据仿真软件，并将仿真结果同传统遗传算法进行比较。本文相关参数设置为：最大迭代次数MAXGEN=300，选择率Ps=0.8，初始交叉率Pc=0.8，初始变异率Pm=0.03。

4×5 和10×10 算例的迭代过程如图7 和图8 所示，可以看出，本文提出的改进遗传算法所得到的最优解均低于平均值，证明该改进算法在寻找最优解方面具有更强的能力。

图7 4×5 迭代过程图

图8 10×10 迭代过程图

对比图9 和图10 可以看出改进后遗传算法与传统遗传算法之间的差异。目标函数用于衡量解的优劣，如果目标函数是最小化的，适应度越低表示解越好。这是因为适应度是根据目标函数的值来计算的，而目标函数越小越好。因此，适应度越低表示解越接近最优解。通过观察图9 和图10 可以发现，改进后的遗传算法在最优适应度方面表现更低。

图9 4×5 改进后的遗传算法与改进前遗传算法的对比图

图10 10×10 改进后遗传算法与改进前遗传算法的对比图

本文基于改进的遗传算法所求得的调度结果如图11 和图12 所示。在遗传算法等优化算法中，通常会使用适应度来评估个体的优劣，并根据适应度来进行选择、交叉和变异等操作，以搜索最优解。由图11 和图12 可以看出，改进后的遗传算法在获取解的质量上有明显的提升，在4×5 的经典算例中最优适应度从6.5 优化到4，10×10 的算例中则从6优化到3，证明了改进后算法的优越性。

图11 4×5 改进后遗传算法调度结果甘特图

图12 10×10 改进后遗传算法调度结果甘特图

4 结语

本文提出了一个柔性作业车间调度问题模型，目标函数为最小化最大完工时间和最小化总能耗。为了有效解决该问题，引入了改进的遗传算法方法。

通过引入非均匀改进，能够根据问题的特点和种群的演化阶段动态调整交叉率和变异率，改进的遗传算法可以提高算法的全局搜索的能力。并且在变异操作中，对工件编码使用邻域变异，对机器编码使用单点变异，以增加解空间的探索能力和多样性。

通过这种改进的遗传算法，期望能够找到更好的解决方案，并优化算法的性能。该算法能够在较短的时间内收敛到较优的解，从而提高问题的求解效率。

为了验证改进遗传算法的效果，进行了改进遗传算法和传统遗传算法的对比实验，选取经典算例kacem。实验结果表明，改进后的算法的最优适应度明显低于传统遗传算法。

然而，本研究还存在一些局限性，只考虑了完工时间和能耗这两个目标，而实际生产中可能还存在其他重要目标。此外，本研究仅针对静态调度问题，对于动态调度问题仍需进一步研究。