打开文本图片集

摘要：针对柔性作业车间调度问题，设计了改进文化基因算法进行求解。首先针对柔性作业车间调度问题的特征建立了数学模型，以最大完成时间为优化目标，然后设计了双层编码方式，将POX和JBX组合交叉算子引入到算法的种群交叉阶段，以确保子代的多样性。在局部搜索中使用基于N5和N7邻域结构的变邻域禁忌搜索，自适应调整禁忌搜索次数，以提高提高算法的搜索效率和质量。最后，与其他3种经典算法对比，通过在Mk算例集上的仿真实验验证了本算法的优化性能。

关键词：柔性作业车间调度；改进文化基因算法；变邻域搜索

1引言

车间调度是企业管理的重要组成部分。近年来，随着市场竞争日趋激烈，新的生产系统中，不仅有多种加工能力的生产单元，也有可选择加工设备的工艺。因此，柔性作业车间调度问题日益受到关注。柔性作业车间调度问题（Flexible Job-Shop Scheduling Problem，FJSP）在经典的作业车间调度问题基础上增加了机器选择过程。一般而言，在柔性作业车间中，大部分工件的大部分工序都有多台机器可以用于加工。柔性作业车间能够更好地满足多品种小批量的生产要求，进而帮助企业更快地对市场上的突发情况做出反应。

FJSP有众多目标，其中最常见的是最小化最大完工时间。本文的研究将关注点放在优化最大完工时间上。该问题是NP难问题，无法在有限时间内得到最优解。目前，对该问题已有一些研究。

在上世纪90年代， Brucker P和 Schlie R[1]首先提出和研究了FJSP，并假设所有加工设备加工某工件的同一工序所消耗的时间相同，建立了一种新的FJSP多项式模型。在此之后，更多的研究人员开始着手研究这一问题。虽然已有的基于析取图的精确算法被用来解决FJSP，但是对于20个工件，10台设备以上的调度问题，其处理效率较低的。于是，学者们把目光投向了各种各样的近似算法。在众多的研究和探索中，群智能算法是通过对自然界中生物和人类行为的一些特征进行模拟而开发出来的，如遗传算法[2-3]、粒子群优化算法[4]、蚁群优化算法[5-6]等。近几年，人们对 FJSP问题进行了更加深入的研究， Bagheri等[7]利用基于集成方法的人工免疫算法对其进行了求解，设计了多种种群初始化策略和变异算子。

其中，遗传算法是最经典的近似算法框架之一。文化基因算法基于遗传算法发展而来，其核心思想是将文化传承的概念引入进化过程中，具体流程如图1所示[8]。文化基因算法（ Memetic Algorithm， MA）是一种智能优化算法框架，兼具集中搜索和广泛搜索的能力。至少有两个主要模块：全局搜索和局部搜索模块。

文化基因算法由Moscato[9]于1989年首次提出。在文化基因算法中，个体间的竞争、协作、个体自我预备等行为交替进行。Luo等人[10]提出了一个特殊的分布式柔性作业车间调度问题，其中一个工件的不同工序可以在不同的工厂进行，并设计了一种有效的模因算法来实现以最小化工厂的完工时间、最大工作量和总能耗为目标的多目标优化。李瑞等人[11]设计了一种N6邻域结构的变体，并将其嵌入知识驱动的文化基因算法的变邻域搜索环节来求解分布式绿色柔性调度。

本文以FJSP为研究对象，主要工作内容如下：首先对所研究问题的意义和研究现状进行介绍。然后，给出了以最小化最大完工时间为目标的柔性作业车间调度问题的混合整数规划模型。接着，对文化基因算法进行改进，采用了特殊的编解码及初始化方法，设计了基于N5邻域结构和N7邻域结构的变邻域禁忌搜索方法。在国际著名的Mk算例集上进行一系列的仿真对比实验。最后总结并分析实验结果，指出未来的发展方向。

2柔性作业车间调度问题

2.1问题描述

柔性作业车间调度问题可以具体描述为[12]：在一个制造车间中，有N个待加工产品集合J={J1， J2， …， JN}，每个产品可以在多个可选加工单元上加工，加工设备M={M1，M2，…，Mm}，每个待加工的产品有若干个加工工序，且加工工序之间存在一定的顺序加工工艺约束 ，而每个工序的加工单元选择有一定范围，并且不同加工单元上的加工时间一般不相同。以最小化最大完工时间为优化目标，确定每台加工设备上每道工序的加工最优排列顺序与开工时间。柔性作业车间调度包含两个子问题，分别是待加工产品的加工设备分配子问题和各加工设备上的产品工序排序子问题。

此外，对加工过程的约束如下：

（1）同一工件的不同工序存在先后级约束关系，即必须前一道工序加工完成后，才能对后一道加工工序进行加工；

（2）一个加工单元在同一时间内仅能处理一道工序；

（3）在0时刻所有加工设备均可使用，所有加工产品均可被加工；

（4）一个加工产品的一道工序只能选择一个设备加工且仅加工一次；

（5）不同的加工产品之间没有先后优先级关系，不同加工产品的工序之间也没有先后优先级关系；

（6）忽略加工中断等特殊情况。

表1展示了一个简单的柔性作业车间调度问题的一个示例，该示例中包含了3个代加工工件（J1，J2，J3），加工设备数为4，其中J1包含3道工序，J2包含3道工序，J3包含2道工序。

其中，“-”表示相应工序不能在该加工设备上进行加工，表中的数字对应了每个工件每道工序在特定加工设备上加工所需要的时间。例如工件J1的第3道工序O1，3，在加工设备M1上的加工时间为4，但该工序不能在加工设备M3上进行加工。

2.2符号描述

索引号：

i：产品索引号，i∈{1， 2， …， N}；

j：工序索引号；

k：加工设备索引号；

r：加工顺序索引号；

变量：

Ji：第i个待加工产品；

Oi，j：产品i的第j道工序；

Mk：第k个加工设备；

N：产品总数；

pi：产品i中工序总数；

m：加工设备总数；

tk i，j：第k个加工设备对产品i中第j道工序所需的加工时间；

Si，j：加工产品i中第j道工序起始时间；

Ci，j：加工产品i中第j道工序的结束时间；

Ci：加工产品i的完工时间；

Cmax：全局最大完工时间；

Ek，r：第k个加工设备上加工顺序索引号为r的工件的开始加工时间；

qk：第k个加工设备加工的工序总数。

决策变量：

xk i，j：判断产品i的第j道工序是否在第k个加工设备进行加工，如果是该变量等于1，反之等于0；

zk，r i，j：判断产品i的第j道工序在第k个加工设备上的加工顺序索引号是否为r，如果是，等于1，反之等于0。

2.3模型建立

其中：式（1）表示以最小化最大完工时间为本调度问题的目标函数，即最小化所有工件加工完成时间的最大值；式（2）表示加工产品的最后一道工序的完工时间即为该加工产品的加工完成的时间；式（3）表示该工序的总加工完成时间；式（4）表示所有加工产品的所有工序是有一定的顺序工艺约束；式（5）表示对加工设备的约束，即在同一时间只能加工一道工序；式（6）表示某工序只能在一个加工设备加工；式（7）表示所有工序只能被加工设备加工一次；式（8）和（9）表示决策变量的取值范围。

相较于作业车间调度问题的数学模型，柔性作业车间调度问题模型的变化之处主要在于， xk i，j由确定值变为了决策变量。

3改进文化基因算法求解柔性作业车间调度问题

3.1算法基本流程

本文以遗传算法作为文化基因算法的主体框架，变邻域禁忌搜索算法作为改进文化基因的局部搜索框架，首先初始化种群，也就是对初始的文化进行一个传播输入，通过文化交流（交叉）得到新的文化（种群），然后对新文化进行文化传承（变邻域搜索），通过邻域结构产生新解，最后筛选中最优解组成新种群。其中，所提出的自适应变邻域禁忌搜索采用了不同的邻域结构，减少了无效的搜索，同时禁忌搜索迭代次数和禁忌表长度自适应变化，提高了算法的效率和性能。

改进文化基因算法流程如图2所示，以下是算法的详细步骤：

3.2编解码与种群初始化

该问题需要同时解决加工设备选择和每台加工设备上的工序加工序列两个子问题的编码。因此，本文设计了基于工序的和加工设备选择结合的双层编码方式。以表1示例为例，双层染色体编码如图3所示。

第一层染色体编码为工序编码，为OS，每一个染色体上的基因代表一个工序，如图所示的OS染色体表示工序的加工顺序为O1，1→O3，1→O2，1→O1，2→O1，3→O2，2→O2，3；加工设备选择MS按照顺序表示J1，J2，J3，例如MS染色体的前3位基因依次表示J1的O1，1，O1，2，O1，3工序的选择的加工设备为M2，M1，M4；MS染色体的前4、5、6位基因依次表示J2的O2，1，O2，2，O2，3工序的选择的加工设备为M2，M3，M4；MS染色体的前7、8位基因依次表示J2的O3，1，O3，2工序的选择的加工设备为M1，M3。

在解码时采取主动解码，将每道工序在不影响已安排工序的开工时间的前提下，尽量早开工。所有工序都被解码后，最后完工的工序的完工时间即为当前解的最大完工时间。该解码策略旨在尽可能提前每道工序的加工，达到缩短整体最大完工时间的目的。以表3-1数据位例介绍主动解码。具体如下：

假设针对该问题存在一个可行解的染色体工序序列OS为：2，1，1，3，1，3，2，2；加工设备选择MS为：2，1，3，2，2，3，1，3。主动解码通过将工序尽可能提前的策略，将其安排到最佳可行的地方，以此方式得到的甘特图如图4所示。

针对于工序选择OS和加工设备选择MS编码的种群初始化，为了提高初始解的分布随机性，采取随机初始化方法。

3.3交叉操作

交叉操作是指按照某种规律使染色体上的基因发生交叉互换，从而实现群体内个体间的信息交换。同时，为防止群体的过分单一，扩大群体的差异性，增大群体的干扰因子。本文针对于OS序列，设计了POX交叉[13]和JBX[14]交叉的组合策略；而针对MS序列，采用两点交叉法。具体步骤如下：

Step1 设置相关算法的交叉概率Cr；

Step2 若需要交叉，随机选择两个个体作为父本和母本；

Step3 对OS交叉随机采取POX交叉或JBX交叉，具体交叉操作如图5所示；

在POX交叉中，对于随机选择的两个亲本Parent1（P1）和Parent2（P2），将所有工件随机划分为2个集合。对于属于集合1的工件，如图3-7a中的工件3，将Parent1的相关基因直接复制到O1中的相同位置，将Parent2的相关基因直接复制到O2中的相同位置；对于剩下的位置，O1按顺序复制Parent2中集合2的工件基因，O2按顺序复制Parent1中集合2的工件基因。

在JBX交叉中，对于随机选择的两个亲本Parent1和Parent2，将所有工件随机划分为2个集合。对于属于集合1的工件，如图3-7b中的工件3，将Parent1的相关基因直接复制到O1中的相同位置；对于属于集合2的工件，如工件1和2，将Parent2的相关基因直接复制到O2中的相同位置；对于剩下的位置，O1按顺序复制Parent2中集合2的工件基因，O2按顺序复制Parent1中集合1的工件基因。

Step4 对MS交叉，随机选择两个位置，如图6所示，属于范围内的Parent1部分放到中，不属于范围内的Parent2部分放到O1中；属于范围内的Parent2部分放到中，不属于范围内的Parent1部分放到O2中；

Step5 更新父本；

重复上述Step1 – Step5过程。

3.4禁忌搜索

（1）邻域结构

禁忌搜索算法的优劣主要取决于邻域结构的设计，目前车间调度广泛采用基于关键路径的工序块邻域结构。 N5邻域结构和N7邻域分别由Nowicki和 Smutnicki[15]和张超勇等人[16]提出，是针对作业车间调度问题的高效邻域结构，也可以推广应用于柔性作业车间调度问题。N5邻域结构由N2邻域结构发展而来，删去了不必要的多工序联动部分，仅交换关键块首两相邻工序或关键块尾两相邻工序，这部分最有希望产生更优解。N5邻域解空间小，求解效率特别高，但不具有连通性、容易陷入局部最优。N5和N7邻域结构的基本动作如图7和图8所示。

其中，Ox→Oy→Ou→Ov是一个完整的关键块，N5邻域结构产生新解的方式是将工序Ox移动至工序Oy之后加工，或将工序Ov移动至工序Ou之前加工。N5邻域结构不会产生不可行解，因此不需要额外的约束条件保证邻域解可行。

N7邻域结构则有4种邻域动作：将一个关键块内工序移动至其块首之前，将一个关键块内工序移动至其块尾之后，将关键块首工序插入块内部，或将关键块尾工序插入块内部。N7邻域结构对一个关键块进行了十分充分的搜索，故求解效率相对较低，但连通性更好。

通过设计基于N5和N7邻域结构的变邻域搜索，不仅提高了求解效率，同时也有效的兼顾了邻域解空间的大小，增强算法的局部寻优能力。变邻域搜索的流程图如图9所示，具体步骤如下：

Step1：设置禁忌搜索的最大迭代次数iteration，将种群中的子代个体作为初始解输入，并设置当前的最优解，初始化禁忌表；

Step2：已达到预定的最大迭代次数iteration，则输出最优解，替代初始解融入返回到遗传算法种群；若不满足没有达到，则进行下一个步骤；

Step3：选定邻域结构。初始选的N5邻域结构。如上次选用的邻域结构已连续使用5次，则更换邻域结构（N5换成N7，或者N7换成N5），否则继续沿用上次的邻域结构；

Step4：对输入个体依次进行邻域搜索，生成新的个体；

Step5：处理邻域解集，如果是目前为止的全局最优解或不在禁忌列表中，则替换为当前最优解；反之，如果上述情况不存在时，当前解即选择禁忌列表中的最优解；

Step6：禁忌表更新，转至Step2。

（2）自适应禁忌搜索参数设置

为了提高对解空间的搜索，本算法会对每一个子代个体进行禁忌搜索，从而会导致耗费大量的计算时间。为了能够达到两者平衡，本算法设计了自适应的禁忌搜索次数，在迭代初期进行全局搜索时，禁忌搜索次数较少；而在后期陷入局部最优解时，禁忌搜索次数自适应增多。其自适应变化公式如下：

其中TSIteration表示禁忌搜索的搜索次数，TSGen表示初始设置的禁忌搜索搜索次数， gen表示种群当前的迭代次数。

4仿真实验及分析

4.1改进文化基因算法的实验设计

为了验证改进文化基因算法求解柔性作业车间调度问题的性能，使用Mk数据集[17]对算法求解FJSP的有效性进行测试。算法采用Java语言在VScode平台编程实现，使用基于2.6GHz的i7-9750H CPU的个人电脑运行程序，RAM为8G。通过预实验，确定的算法基本参数如表2所示。为了尽可能降低实验的偶然性对实验结果造成的影响，本仿真实验对改进文化基因算法重复独立运行10次。

4.2实验结果展示与对比

已经有大量算法使用Brandimarte（BRdata）的10个数据集进行实验验证，这里选取了一些有代表性的算法如下： Bozejko[18]等人提出的TS3算法，用TS3表示；邢立宁等人[19]提出的基于知识的蚁群算法，记作KBACO；Mohsen[20]提出的启发式算法，记作Heuristic；改进文化基因算法用IMA表示。将改进文化基因算法和这3种算法在Mk集上的最佳运行结果对比，如表3所示：

其中IMA.best代表文化基因算法的最优解，IMA.ave代表文化基因算法的平均解。从表3中可以看出，无论是IMA.best还是IMA.ave，都在绝大部分算例上达到了最优，且平均makespan均优于其他算法。分算例看，对于Mk05之前总工序数不超过100的小规模算例，其他部分算法一般也求得了最优解；但当问题规模逐渐增大，IMA.best和IMA.ave的优势逐渐显著。显示了改进文化基因算法求解效果更为出色且稳定。Mk09算例的迭代曲线如图10所示。

从图10可以看出，改进文化基因算法在迭代初期可以快速准确进行收敛，并且在长时间陷入局部最优解的时候跳出局部最优，不断搜索全局最优解。种群的平均解远大于最优解且不断波动，说明种类差距大、种群丰富度高，全局搜索能力较强。从实验结果可以看出，该方法在求解FJSP问题时可以得到较好的效果。

5结语

本文提出了一种基于改进文化基因算法的柔性作业车间调度问题的研究方法。首先构建了以最大完工时间最小化为目标的整数规划模型。然后，以标准文化基因算法作为框架，使用基于工件的双层编码方式。通过随机初始化得到初始种群，保证了初始解的离散性。其次，在算法交叉操作中引入了POX和JBX组合交叉算子，保证了子代的多样性和对优良性状的继承性。最后，在局部搜索中使用基于N5和N7邻域结构的变邻域禁忌搜索，设计了自适应的禁忌搜索次数，在保证求解效率的同时，有效改善了个体的质量。最后通过国际通用的Mk算例集进行仿真实验，验证了改进算法在柔性作业车间调度问题上的有效性。

本文提出的改进文化基因算法在实现过程中，发现该算法还有许多需要进行进一步完善的地方，所以还要针对其不足之处进行的修正。本文主要改进了经典文化基因算法的种群初始化方法、交叉算子、局部搜索策略。然而，在本文实验阶段发现虽然该改进算法可以进行快速收敛并求出最优解，但是在算法运行中，有个别情况陷入了局部最优解，此外该算法在求解大规模问题时效率较低。此外，还需考虑算法的复杂性、收敛性对算法性能的影响。

参考文献：

[1]P. Brucker， R. Schlie. Job-shop Scheduling with Multi-purpose Machines. Computing 45， 369-375. Computing， 1990， 45（4）： 369-375.

[2]H. Chen， J. Ihlow， C. Lehmann. A genetic algorithm for flexible job-shop scheduling. IEEE International Conference on Robotics & Automation IEEE， 1999， 35（10）： 3202-3212.

[3]I. Kacem， S. Hammadi， P. Borne. Approach by localization and multi objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems Man and Cybernetics Part C （Applications and Reviews）， 2002， 32（1）： 1-13.

[4]G. Zhang， X. Shao， P. Li， L. Gao. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering. 2009， 56（4）： 1309-1318.

[5]A. Rossi ， G. Dini . Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method. Robotics and Computer-Integrated Manufacturing. 2007， 23（5）： 503-516.

[6]王万良， 赵澄， 熊婧， 徐新黎. 基于改进蚁群算法的柔性作业车间调度问题的求解方法. 系统仿真学报， 2008（16）： 4326-4329.

[7]A. Bagheri， M. Zandieh， I. Mahdavi， M. Yazdani. An artificial immune algorithm for the flexible job-shop scheduling problem. Future Generation Computer Systems， 2010， 26（4）： 533-541.

[8]刘漫丹. 文化基因算法（Memetic Algorithm）研究进展. 自动化技术与应用， 2007（11）： 1-4+18.

[9]P. Moscato. On Evolution， Search， Optimization， Genetic Algorithms and Martial Arts - Towards Memetic Algorithms. Caltech Concurrent Computation Program， C3P Report， 826， 1989.

[10]Q. Luo， Q.W. Deng， G.L Gong， L.K Zhang， W.W. Han， K.X. Li. An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers. Expert Systems With Applications， 2020， 160： 1-15.

[11]李瑞， 王凌， 龚文引. 知识驱动的模因算法求解分布式绿色柔性调度. 华中科技大学学报（自然科学版）， 2022， 50（06）： 55-60.

[12]张国辉， 高亮， 李培根， 张超勇. 改进遗传算法求解柔性作业车间调度问题. 机械工程学报， 2009， 45（07）： 145-151.

[13]张超勇， 饶运清， 刘向军， 李培根. 基于POX交叉的遗传算法求解Job-Shop调度问题. 中国机械工程， 2004， 15（23）： 5.