改进遗传蜂群算法求解分布式柔性作业车间调度问题

李佳路，*王 雷，王静云

改进遗传蜂群算法求解分布式柔性作业车间调度问题

李佳路，*王 雷，王静云

（安徽工程大学机械工程学院，安徽，芜湖 241000）

针对分布式柔性作业车间调度问题，提出一种改进遗传蜂群算法求解方案。算法采用基于机器编码的编码方案，根据编码特点和分布式柔性作业车间的特点，设计了一种基于编码相似度的交叉操作，可以避免在交叉过程中产生非法解，提高算法的运行效率，并通过在不同的交叉操作后，以不同概率进行两种变异操作的方式改进了雇佣蜂时期的搜索操作，改善了算法的迭代速度；采用排序选择策略替代原来跟随蜂时期的选择策略；改进侦查蜂的蜜源抛弃机制，通过对比已获得的全局最优解，对达到搜索上限的蜜源进行部分抛弃，防止破坏优质解再次陷入随机搜索。最后，通过对比不同算法对实例求解，验证本文算法的有效性。

分布式调度；柔性作业车间；人工蜂群算法；遗传算法

在经济全球化的背景下，传统制造业受到了极大地冲击，并且随着企业规模的扩大，企业生产制造模式逐渐由单工厂生产转变为多工厂生产，以提高竞争力[1]。分布式车间调度既需要考虑每个车间内的工序调度还需要考虑多个车间的协作生产，是比单车间调度更加复杂的NP-hard问题，在这种多工厂生产模式下的调度问题也受到更多的学者关注与研究[2]。分布式柔性作业车间调度问题作为柔性作业车间调度问题的延伸，其中每一个工厂都可以看作是一个独立的柔性作业车间，多个工厂可以根据实际的加工能力和资源配置协作完成一批加工任务，生产调度更加灵活，也更加符合当前的生产模式[3]。

目前，分布式车间调度研究大部分集中在各类分布式流水车间调度[4-7]，而分布式柔性作业车间调度问题研究则相对较少。Felix T.S. Chan等[8]和L.De Giovanni等[9]采用遗传算法对分布式柔性作业车间调度问题进行了研究；杨江波等[10]根据车间实际生产过程，将生产调度过程划分为生产计划层、车间调度层和零件规划层，提出一种基于目标级联法和遗传算法的分级调度模型；Chang H C等[11]提出了一种混合遗传算法，该算法采用了一种新的编码机制和一些有效的交叉和变异算子提高搜索效率；Bilel Marzouki等[12]提出了一种化学反应优化的元启发式算法来解决分布式柔性作业车间调度问题；Lu P H等[13]设计了一种具有一维到三维解码方案的遗传算法求解分布式柔性作业车间调度问题；吴锐等[14]根据问题特性设计了基于关键路径思想的局部搜索算子；Meng L L等[15]为解决最大完工时间最小的分布式柔性作业车间调度问题，提出了四个基于不同建模思想的混合整数线性规划(MILP)模型和一个基于区间决策变量和区域过滤算法的约束规划(CP)模型。

综上，分布式柔性作业车间调度问题是近年发展起来的更加符合生产实际的问题，但目前对其求解方法偏少，且已有研究大部分都采用遗传算法求解，遗传算法存在收敛慢和容易陷入局部最优的缺点，在求解大规模问题时不具有优势；分布式柔性作业车间调度问题求解更为复杂，现有研究少有针对问题特点设计相应编码和进化操作，导致编码量大且易在进化迭代时产生非法解，降低算法效率。人工蜂群算法（Artificial bee colony algorithm, ABC）于2005年由Karaboga[16]提出，是模拟自然界蜂群采蜜的行为的一种群体智能优化算法，具有结构简单、参数较少、易于实现等特点，广泛的应用于生产调度领域[17-19]。因此，本研究利用人工蜂群算法求解分布式柔性作业车间调度问题，并改进算法的进化搜索机制，提高其对分布式柔性作业车间调度问题的求解性能。

1 分布式柔性作业车间调度问题

1.1 符号定义

在对分布式柔性作业车间调度问题进行描述前，先对本文所涉及相关符号说明如下：

表1 符号定义

1.2 问题描述

分布式柔性作业车间调度问题是多工厂调度问题，每个子工厂都可作为一个柔性作业车间对整个加工任务中的部分工件进行加工，因此分布式柔性作业车间调度问题包含3个子问题：1）为待加工工件分配加工工厂；2）为每道工序分配加工机器；3）对每个工厂进行工序调度。

1.3 建立问题模型

更快捷地完成生产任务是提升企业效益的有效途径，因此本文以最小化最大完工时间为生产调度的优化目标，并以此建立调度优化模型：

（1） （2） （3） （4） （5） （6） （7）

其中，式（1）是目标函数，表示最大完工时间是所有工厂完工的最大值；式（2）表示工厂的完工时间是工厂内加工的最后一道工序的结束时间；式（3）限制一个工件只能分配到一个工厂内加工；式（4）为工序约束，表示同一工件的工序必须按照顺序加工；式（5）为机器约束，保证同一机器同一时间只能加工一道工序；式（6）表示一道工序只能选择一个机器进行加工；式（7）表示工序开始后不能中断。

2 改进遗传蜂群算法求解分布式柔性作业车间调度问题

2.1 改进遗传蜂群算法流程

在标准的人工蜂群算法中，包括3种类型的蜜蜂：雇佣蜂、跟随蜂和侦查蜂，蜜源代表问题的可行解，蜜源质量为可行解的适应度，其中每个蜜源对应一个雇佣蜂，跟随蜂数量与雇佣蜂数量相等，侦查蜂由蜜源搜索达到限制条件的雇佣蜂生成[20]。但标准人工蜂群算法只能对连续型问题进行求解，无法对车间调度类等离散型问题进行求解。故我们根据遗传算法中染色体交叉变异的方法，对人工蜂群算法做离散化改进，使其适用于求解分布式柔性作业车间调度问题，并通过设计多种蜜源初始化策略、改进雇佣蜂交叉变异的搜索策略、跟随蜂的选择策略和侦查蜂的蜜源抛弃策略以提高算法求解性能。提改进遗传蜂群算法整体流程如图1所示。

图1 改进遗传蜂群算法整体流程图

2.2 编码和解码

目前现有求解分布式柔性作业车间调度问题的相关文献，在对问题编码大多都采用基于工序的编码、基于机器的编码和选择的工厂编码的三层编码方式[3,13-14]，在实际的分布式柔性作业车间调度问题中，加工规模都比较大，采用这种编码方式往往面临两个问题：一是编码量大，二是在交叉变异时极易产生非法解，影响算法的求解效率。因此，本文设计一种基于机器编码的编码方案，并根据编码特点设计相应的交叉变异操作，可以保证在不需要修补或重建的情况下，产生的新解为可行解，提高算法运行效率。

图2 编码示意

此基于机器的编码仅为待加工工件分配加工厂和为工序选择加工机器，并没有产生调度方案，需要对其进行解码来获得调度方案。对上述编码方案进行解码，根据分布式柔性作业车间调度问题的特性，解码主要包括两个部分，首先对可行解编码进行以加工工厂为单位的分解，然后分别对子码进行解码。以图2示例编码为例，具体解码过程如下：

1）编码分解；根据编码首列的加工工厂代码，对编码进行分解，将主体编码分解为以加工工厂为单位的子码，同时也将对应加工时间矩阵进行相应的分解，如图3所示。

图3 编码分解示意图

2）分别对子码进行解码；按本文编码方式，并未给出不同工件工序的加工顺序，根据本文编码方式设计一种基于剩余加工时间最长的MWKR法则和最早进入最先加工的FCFS法则解码方案，提高调度方案质量。具体操作为：对同一工厂所有工件的每一道工序进行调度，对于所有工件的同一道工序，若不同的工件都在不同的机器上加工，先判断对应机器上的加工空闲是否能将该道工序插入，若能，则插入；否则安排到之前机器加工的最后一道工序字后。若有工件在同一机器上加工，先对机器空闲进行判断，将可以进行插入的工序插入；若都可以插入但又不能同时插入时，将加工时间长的工序优先插入，以缩短机器空闲时间，提高加工效率；若不发生插入，则以MWKR法则优先安排剩余加工时间最长的工件进行加工，否则以FCFS法则进行调度。

通过采用上述解码方案对图2的编码进行解码，得到调度甘特图如图4所示。

图4 调度甘特图

2.3 蜂群初始化

在启发式算法中，初始种群的质量对算法收敛速度和求解结果有很大影响，一个高质量的初始种群在算法求解中非常关键。本设计的种群初始化方法，在为工件选择加工工厂时采用均衡原则，即加工机器多的工厂被选择的概率大，以均衡各个工厂的负载。确定工件的加工工厂后，每个工厂中工件的工序选择加工机器时按照以下策略生成：

1）随机选择加工机器，占初始种群的70%；

2）优先选择加工任务少的机器，当存在多选时，在同级别内进行随机选择，占初始种群的20%；

3）按局部处理时间最小规则选择，占初始种群的10%。

2.4 雇佣蜂搜索操作

由本文编码方式和分布式柔性作业车间调度问题特性可知，在两个父代发生交叉时，若交叉位置处两个工件处于不同的加工工厂，由于不同工厂中进行工序加工的可行机器和能力不同，此时交叉的意义不大，且极易产生非法解。因此本文根据编码特点，设计一种交叉操作，可以避免非法解的产生；并且根据分布式柔性作业车间的特点设计了变异操作。

在交叉操作之前，首先引入编码相似度，的计算方法如下：对比编码中每个工件加工工厂代码，若两个编码中同一工件的加工工厂相同，则为1，不同为0，对其求和即为。

交叉操作为随机多点交叉，交叉父代之一为当前蜜源，另一个父代在其他蜜源中随机选取2个蜜源，以70%的概率选择相似度高的蜜源作为交叉父代；以30%的概率，选择另一个蜜源作为交叉父代。交叉的具体操作为：首先对比两个父代第一件工件的加工工厂代码，若加工工厂相同，则产生随机位置，将两个父代第一个工件的子代码片段进行互换；若加工工厂不同，第一个工件子代码则不发生交叉操作。后续工件子代码交叉操作以此类推；对两个子代进行贪婪选择，较优的作为交叉后的新蜜源。

变异操作设置两种形式：

1）工序加工机器变异：随机产生编码矩阵位置（不包括加工工厂代码列），在当前位置随机选择一个可选机器进行替换。此种变异方式产生新蜜源与原蜜源差异较小。

2）工件加工工厂变异：选择当前蜜源下的随机一个工件进行加工工厂替换变异，即将当前工件所在加工工厂变换为另一个不同的可选工厂，由于工件在不同工厂中可用加工机器不同，当发生工厂变异时，需要重新选择加工机器。此种变异方式变异范围更大，邻域搜索范围更大。

由于选择交叉父代相似度的大小影响交叉时邻域搜索范围，在交叉产生的新蜜源不优于原蜜源时，根据交叉父代的相似度大小，采用不同的变异操作。

雇佣蜂搜索操作具体流程如图5所示，具体步骤如下：

图5 雇佣蜂搜索操作流程

步骤1：取当前位置蜜源作为交叉父代之一；

步骤2：随机选取两个不同于蜜源的蜜源1和2，并分别计算相似度1和2；

步骤3：判断所选两蜜源相似度1和2是否相等，不相等转步骤6；

步骤4：随机选取两蜜源之一作为父代与蜜源X进行交叉，选择生成两个子代适度值大的作为新蜜源，若优于，转步骤11；

现有的小区治理结构中存在着业主自治、居民自治和政府管理三种形式，但这些治理形式的边界如何确定，不同物业类型的小区治理结构又有着何种差异，是困扰当前小区内部治理的关键性难题。

步骤5：随机采用加工工厂变异或加工机器变异方式产生新蜜源，若优于，转步骤11；若不优于，转步骤12；

步骤6：产生随机值，若0.7，进行步骤7；否则转步骤9；

步骤7：选择两蜜源中相似度大的蜜源作为父代与蜜源进行交叉，选择生成两个子代适度值大的作为新蜜源，若优于，转步骤11；

步骤8：产生随机数，若<0.2，对蜜源进行加工工厂变异；否则进行加工机器变异，并产生新蜜源，若优于，转步骤11；若不优于，转步骤12；

步骤9：选择两蜜源中相似度小的蜜源作为父代与蜜源进行交叉，选择生成两个子代适度值大的作为新蜜源，若优于，转步骤11；

步骤10：产生随机数，若0.2，对蜜源进行加工工厂变异；否则进行加工机器变异，并产生新蜜源，若优于，转步骤11；若不优于，转步骤12；

步骤11：用新蜜源代替当前蜜源，雇佣蜂结束对当前蜜源搜索；

步骤12：当前蜜源保持不变，蜜源搜索限制加1，雇佣蜂结束对当前蜜源搜索。

2.5 跟随蜂搜索操作

式中为雇佣蜂个数，(t)为自适应参数，为当前迭代次数，max为最大迭代次数。通过该选择策略，在迭代初期，(t)较小，可以有效保持种群多样性；随迭代次数增加，(t)可以防止由于种群竞争减弱而出现搜寻停滞的趋势。在确定跟随的雇佣蜂后，将两个个体进行交叉并进行贪婪选择，若蜜源未更新，则蜜源搜索限制。

2.6 侦查蜂搜索操作

基本人工蜂群算法中，若蜜源搜索限制达到上限，则雇佣蜂放弃该蜜源，转化为侦查蜂进行随机搜索，产生一个新蜜源，通过该操作使算法在一定程度上跳出局部最优，但由于算法收敛性，若该解恰好为全局最优解，抛弃该解会导致算法重新搜索最优解，降低搜索效率。故本文提出以下改进方法：

1）记录当前全局最优蜜源；

2）搜索所有蜜源搜索次数达到上限的蜜源；

3）如果f=f，则保留当前蜜源，清零蜜源搜索限制；若存在多个，则随机抛弃其中的70%蜜源，随机生成新蜜源，清零蜜源搜索限制。

4）如果f<f，随机生成新蜜源，清零蜜源搜索限制。

在保留了可能的全局最优解的同时，也保证了算法后期具有一定能力可以跳出局部最优。

3 实例验证

为测试GABC算法在求解分布式柔性作业车间调度问题的有效性，以10个工件在2个柔性工厂的调度模型实例进行验证，其加工时间如表2所示。通过遗传算法（GA）作为对比算法验证本文的改进遗传蜂群算法（GABC）的求解性能；并将标准人工蜂群算法的雇佣蜂和跟随蜂搜索公式替换为交叉变异操作，命名为DABC，以其作为对比，验证GABC在进行局部搜索时的有效性。

算法通过MATLAB2019a编译，运行环境为Windows10 64位操作系统，Core i7-6700H 2.60Ghz CPU，12G RAM。

遗传算法基本参数设置：最大迭代次数Max=500，个体数目N=100，交叉概率=0.9，变异概率=0.3。

人工蜂群算法参数设置：最大迭代次数Max=500，蜜源数量N=100，雇佣蜂和跟随蜂数量都为=100，蜜源搜索次数上限=300。

表2 10个工件在2个工厂的加工时间表

三种算法分别运行30次，实验结果如表3所示，某次运行得到的迭代曲线如图6所示；改进人工蜂群算法得到的调度结果如图7所示，横坐标表示加工时间，纵坐标表示工厂的加工机器，图中小方块表示各个工件的工序，其中数字如、“3-1”表示第3个工件的第1道工序。

表3 测试结果

图6 迭代曲线

图7 10个工件在2个工厂调度甘特图

由表3数据和图6可以看出，通过对比GA和DABC算法，两种算法收敛速度相近，但DABC求得的最优值明显优于GA，证明人工蜂群算法在求解分布式柔性作业车间调度问题的优势。对比DABC算法，本设计的GABC算法求解最优值的平均值优于DABC算法，说明GABC算法求解得最优解比较稳定；GABC算法在迭代速度上占较大优势，证明所设计的局部搜索操作的高效性。

4 结论

针对分布式柔性车间调度问题的特性，结合遗传算法，改进了人工蜂群算法的局部搜索阶段，设计了一种基于机器编码的交叉变异操作，改进了侦查蜂抛弃蜜源的规则。通过仿真实验和其他算法进行对比，验证了本文的改进遗传蜂群算法在保证算法求解精度的同时，能够很好地缩短算法迭代次数，提高算法的求解效率，并且能有效地避免陷入局部最优。本研究针对最小化最大完工时间的分布式柔性作业车间调度问题，接下来将继续深入研究更加符合生产实际的多种加工约束和多优化目标的调度问题求解。

[1] 雷德明,苏斌.基于多班教学优化的多目标分布式混合流水车间调度[J].控制与决策,2021,36(2):303-313.

[2] 王凌, 邓瑾,王圣尧.分布式车间调度优化算法研究综述[J].控制与决策,2016,31(1):1-11.

[3] 吴秀丽,刘夏晶.差分进化算法求解分布式柔性作业车间调度问题[J].计算机集成制造系统,2019,25(10):2539-2558.

[4] Bargaoui H, Belkahla D O, GhediraK. A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion[J]. Computers & Industrial Engineering,2017,111(C):239-250.

[5] 杨晓林,胡蓉,钱斌,等.增强分布估计算法求解低碳分布式流水线调度[J].控制理论与应用,2019,36(5):803-815.

[6] 张清勇,孙泽轩,雷德明.分布式两阶段混合流水车间调度[J]华中科技大学学报:自然科学版,2020,48(4):127-132.

[7] Li M,Su B,Lei D M. A novel imperialist competitive algorithm for fuzzy distributed assembly flow shop scheduling[J]. Journal of Intelligent & Fuzzy Systems,2021,40(3):4545-4561.

[8] Chan FTS. Chung SH, Chan PLY. An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems with Applications,2005,29(2):364-371.

[9] Giovanni L D,Pezzella F. An Improved Genetic Algorithm for the Distributed and Flexible Job-shop Scheduling problem[J]. European Journal of Operational Research,2010,200(2):395-408.

[10] 杨江波,陈友玲,曹楠.面向柔性作业分布式车间的分层调度模型研究[J].计算机工程与应用,2014,50(23):239-244.

[11] Chang H C, Liu TK. Optimization of distributed manufacturing flexible job shop scheduling by using hybrid genetic algorithms[J]. Journal of Intelligent Manufacturing,2017,28(8):1973-1986.

[12] Marzouki B, Driss O B, Ghedira K. Solving Distributed and Flexible Job shop Scheduling Problem using a Chemical Reaction Optimization metaheuristic[J]. Procedia Computer Science,2018,126:1424-1433.

[13] Lu P H,Wu M C,Tan H,et al. A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems[J]. Journal of Intelligent Manufacturing,2018,29(1):19-34.

[14] 吴锐,郭顺生,李益兵,等.改进人工蜂群算法求解分布式柔性作业车间调度问题[J] .控制与决策,2019,34

(12):2527-2536.

[15] Meng L L,Zhang C Y, Ren Y P,et al. Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem[J].Computers & Industrial Engineering,2020,142:106347.

[16] Karaboga D.An idea based on honey bee swarm for numerical optimization[D]. Kayseri : Ereiyes University,2005.

[17] 易天,雷德明.基于人工蜂群算法的生产调度研究进展[J].河北工业大学学报,2020,49(4): 24-32.

[18] 陈少,吉卫喜,仇永涛,等.改进人工蜂群算法求解柔性作业车间调度问题[J].组合机床与自动化加工技术,2018(5):161-164.

[19] Zadeh M S, Katebi Y, Doniavi A. A heuristic model for dynamic flexible job shop scheduling problem considering variable processing times[J]. International Journal of Production Research,2019,57(9-10):3020-3035.

[20] 李益兵,黄炜星,吴锐.基于改进人工蜂群算法的多目标绿色柔性作业车间调度研究[J]. 中国机械工程,2020,31(11):1344-1350,1385.

AN IMPROVED GENETIC BEE COLONY ALGORITHM FOR DISTRIBUTED FLEXIBLE JOB SHOP SCHEDULING PROBLEM

LI Jia-lu,*WANG Lei, WANG Jing-yun

（School of Mechanical Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China）

An improved genetic bee colony algorithm was proposed to solve the distributed flexible job-shop scheduling problem. The algorithm adopts A coding scheme based on machine coding was adopt, and according to the characteristics of the encoding characteristics and distributed flexible job shop, crossover operation based on the similarity was designed, which could avoid illegal solutions in the process of cross and improve the efficiency of the algorithm, and through different crossover operation, the search operation in the employ bees was improved, the iteration speed of the algorithm was also improved. The sequencing selection strategy was adopted to replace the original strategy of following bees. The nectar source abandonment mechanism of scout bees was improved. By comparing the obtained global optimal solution, the nectar sources that reached the search upper limit were partially abandoned to prevent the destruction of high-quality solution from being trapped in random search again. Finally, the effectiveness of the proposed algorithm was verified by comparing different algorithms to solve examples.

distributed scheduling; flexible job shop; artificial bee colony algorithm; genetic algorithm

10.3669/j.issn.1674-8085.2021.06.014

1674-8085（2021）06-0074-08

TH165

A

2021-05-24；

2021-07-19

安徽省自然科学基金项目(1708085ME129)，安徽工程大学“中青年拔尖人才”项目

李佳路(1996-)，男，河北唐山人，硕士生，主要从事生产调度和智能优化算法研究(E-mail:986155622@qq.com)；

*王 雷(1982-)，男，安徽亳州人，教授，博士，主要从事智能车间调度及智能优化算法机器人路径规划与控制等研究(E-mail:wangdalei2000@126.com)；

王静云(1997-)，男，安徽铜陵人，硕士生，主要从事生产调度和智能优化算法研究(E-mail:937102540@qq.com).