基于离散人工蜂群算法的分布式装配置换流水车间调度问题

摘  要：文章针对分布式装配置换流水车间调度问题，提出一种离散人工蜂群算法，以最小化最大完工时间。首先，提出一种基于随机产品与工件顺序的初始解生成方法。然后，设计一种基于关键路径的种群个体领域搜索策略，并结合锦标赛选择与新型精英保留策略，以达到加速种群收敛的目的。最后，通过变换陷入局部陷阱的种群个体，实现挖掘与探索能力的平衡。研究中基于1 710个算例，进行了大量的计算实验，计算结果验证了所提算法的优越性。

关键词：流水车间;调度;人工蜂群算法;最大完工时间

中图分类号：TP301.1      文献标识码：A文章编号：2096-4706（2021）24-0124-06

Abstract： For the distributed assembly permutation flow shop scheduling problem， a discrete artificial bee colony algorithm is proposed to minimize the makespan. Firstly， an initial solution generation method based on random product order and workpiece order is proposed. Secondly， an population individual neighborhood search strategy based on the critical path is designed， and tournament selection and novel elite retention strategy are employed to accelerate population convergence. Finally， the balance of exploitation and exploration capability is achieved by transforming the population individuals caught in local traps. A large number of computational experiments based on 1710 instances are carried out. The results verify the superiority of the proposed algorithm.

Keywords： flow shop; scheduling; artificial bee colony algorithm; makespan

0  引  言

裝配置换流水车间调度问题（Assembly Permutation Flow Shop Scheduling Problem， APFSSP）广泛存在于消防车生产[1]、电脑装配[2]、电路板生产[3]和塑料生产[4]等制造系统，以及分布式数据系统[5]、多页发票打印系统[6]等服务系统中。APFSSP假定只有一个生产中心或工厂，所有工序都在同一个工厂完成。然而，市场竞争的加剧迫使很多企业选择采用具有多个生产中心的分布式生产模式[7]。分布式生产能够让企业获得产品质量很高、生产成本较低、管理风险较小的竞争优势[8]。因此，分布式APFSSP即分布式装配置换流水车间调度问题（Distributed Assembly Permutation Flow Shop Scheduling Problem， DAPFSSP）受到众多学者与企业的广泛关注。

2013年，Hatami等[9]首次提出了以最小化最大完工时间为目标的DAPFSSP。2016年，Lin和Zhang[10]提出了嵌入多种新颖启发式的混合生物地理学优化算法;Wang等[11]提出了基于分布矩估计的文化基因算法。2017年，Lin等[12]提出了回溯搜索超启发式方法。2019年，Pan等[13]提出了多种有效的启发式算法;Ferone等[14]提出了一种偏随机迭代局部搜索元启发式算法。2020年，Zhang等[15]提出了融合改进社会蛛网优化和元-拉马克学习与单纯性搜索的文化基因算法。2021年，Zhang等[16]提出了一种基于矩阵—立方的分布矩估计算法。此外，2015年，Hatami等[17]提出了具有序列相关准备时间的DAPFSSP。2021年，Song等[18]提出了采用遗传编程超启发式算法求解该问题。2017年，Gonzalez-Neira等[19]提出了加工时间具有随机性的DAPFSSP。2018年，Zhang等[20]提出了具有柔性装配车间与准备时间的DAPFSSP。2018年，Sang等[21]提出了采用离散入侵杂草算法求解该问题。这些研究的重点集中于提出高效的算法来求解DAPFSSP。高效的调度算法能够显著提升生产过程的效率，因此，设计高效的调度算法具有重要意义[22]。

DAPFSSP是一种比APFSSP更复杂的NP难问题[9]，很难用精确算法来求解。人工蜂群算法[23]（Artificial Bee Colony， ABC）是一种基于种群的进化元启发式算法。该算法模拟了蜜蜂在自然界中的智能觅食行为，由雇佣蜂、跟随蜂、侦察蜂三个角色组成。雇佣蜂负责搜寻可行解和近邻解;跟随蜂通过与雇佣蜂交换信息获得新的可行解，然后通过适应度值决定是否接受新的解，加快搜索收敛速度;如果可行解在迭代次数限制内没有更新，雇佣蜂将会变成侦察蜂，搜寻新的可行解。由于本身具有高效的搜索性能，离散型ABC即离散人工蜂群算法（Discrete Artificial Bee Colony， DABC）经常用于求解诸多生产调度问题。

首先，提出一种结构化启发式方法，以生成具有较高质量的初始种群。其次，提出一种基于关键路径的种群个体领域搜索策略，以提高个体的局部搜索能力;最后，通过变换陷入局部陷阱的种群个体，提升种群个体的全局搜索能力，以实现种群在进化过程中挖掘与探索能力的平衡。通过大量的计算实例，验证了DABC求解DAPFSSP的有效性和优越性。

1  分布式装配置换流水车间调度问题

DAPFSSP包括生产和装配两个阶段。在生产阶段，n个工件{J1，J2，…，Jn}分配给F个工厂，每个工件只能分配给一个工厂。每个工厂有m台机器{M1，M2，…，MM}。任一工件Ji的m道工序{Mi，1，Mi，2，…，Mi，m}依次在任一工厂的m台机器上加工，加工时间用ti，j表示。每台机器同一时刻只允许加工一个工件，每个工件同一时刻只允许在一台机器上加工。在装配阶段，生产阶段完工的工件在装配机器MA组最终装成H个产品{P1，P2，…，PH}。产品Ph由Nh个工件组装而成，装配时间用th表示。每个工件只属于一个产品，任一产品只有在全部所需工件在生产阶段加工完成后才能开始组装，装配机器一次只能装配一个产品。

2  DABC算法求解DAPFSSP

2.1  编码与解码

DAPFSSP包含决定工件的工厂分配、各工厂的工件加工顺序、产品的装配顺序三个子问题。工厂的工件加工顺序可以唯一确定工件分配和产品的装配顺序。因此，采用基于工厂的工件加工顺序编码表示调度解。各加工厂按照所确定的工件顺序进行加工，各产品所有部件实行先加工完成先装配解码，可以唯一确定整个调度方案。

以文献[9]中的算例I_16_2_2_2_3为例，产品P1由工件{2，4，5，6，7，8，9，10，14，16}构成，产品P2由工件{1，3，11，12，13，15}构成。图1为该算例的一个调度方案所对应的甘特图，调度解为{[1，13，11，5，4，14，16，2，8]，[12，15，3，7，6，9，10]}，即工厂1的工件加工顺序为[1，13，11，5，4，14，16，2，8]，工厂2的工件加工顺序为[12，15，3，7，6，9，10]。

2.2  种群初始化

初始种群虽然可以通过随机化方法产生，但是通过启发式方法可能会获得更好的搜索性能。在生产阶段，属于同一产品的工件在各工厂的加工时间尽可能接近，可以减少装配阶段的等待时间[11]。因此，以各产品所属部件为一个整体在各工厂进行分配，可以保证所生成的整个种群具有较高质量。初始解或个体的生成过程为：

Step1：从当前产品集中随机选出一个产品。

Step2：从所选产品隶属的工件集中随机选出一个工件分配给其中一个工厂，使此工厂在原有的基础上生产该工件所需的完工时间最短。

Step3：从剩余的工件集中随机选择一个工件进行分配，直至分配完毕，进入下一步。

Step4：从剩余的产品集中随机选出一个产品。如果产品分配完毕，则生产过程结束;否则，返回执行Step2。

反复执行初始解生成过程，就可以得到一个初始种群。

2.3  雇佣蜂阶段

在雇佣蜂阶段，雇佣蜂或种群个体在它的领域内搜索新的可行解。雇佣蜂的搜索效率决定了整个算法的搜索性能。在调度问题中，调度方案的关键路径决定了整个调度方案的最大完工时间。只要关键路径上的工序不变，整个调度方案的最大完工时间就不会发生变化[24]。因此，设计一种基于关键路径的领域搜索策略。关键路径上工序的所属工件称作关键工件，所有关键工件构成的集合称作关键工件集。将与某工件的加工时间存在重合的工件称作该工件的时间相关工件，某工件的所有时间相关工件称作该工件的时间相关工件集。选择某一关键工件作为交换工件，选择该关键工件的时间相关工件作为被交换工件，执行位置交换，得到新的调度解。

领域搜索策略为：

Step1：确定调度解中的关键工件集。

Step2：从关键工件集中随机选出一个工件作为交换工件。

Step3：确定交换工件的时间相关工件集。

Step4：从时间相关工件集中随机选出一个工件作为被交换工件。

Step5：将交换工件与被交换工件互换位置，得到新的调度解。

Step6：如果新的调度解的最大完工时间小于原来的最大完工时间，则新的调度解代替原来的调度解，结束搜索;否则，从剩余的时间相关工件集中随机选出一个工件作为被交换工件，如果原来的调度解的时间相关工件集为空集，结束搜索;否则，返回执行step3。

由图1可知，该调度方案的关键工件集为{1，13，11，5，4，14，16，2，8}，工件2的时间相关工件集为{16，6，9，10，8}。交换工件9和2可得到新的調度解{[1，13，11，5，4，14，16，2，8]，[12，15，3，7，6，9，10]}。

2.4  跟随蜂阶段

在跟随蜂阶段，锦标赛选择可以改善算法的效率，同时还可以避免陷入局部最优解。从种群中随机选择λ个个体，比较个体适应度值。选择适应度最小的一个个体，执行领域搜索策略，得到一个调度解。执行锦标赛选择φ次，得到φ个个体。再与原种群的所有个体进行比较，选择最大完工时间最小的ρ个个体组成新的种群。种群进化速度的决定因素是最坏的个体，而不是最好的个体，而这种基于贪婪的种群更新方法可以有效保证种群的全局质量。

2.5  侦察蜂阶段

在侦察蜂阶段，如果某个体的最大完工时间在累计执行η次领域搜索策略后没有减小，则舍弃该个体，按照初始解生成过程生成一个新的调度解，代替原来的解，成为新的种群个体。这种个体替换方式实现种群个体在全域范围的搜索能力。

2.6  算法描述

DABC求解DAPFSSP的具體过程为：

Step1：按照初始解的产生过程，生成具有ρ个个体的初始种群。

Step2：让种群中的每个个体执行一次领域搜索策略，生成一个新的种群。

Step3：应用锦标赛选择挑选φ个个体，各执行一次领域搜索策略，生成φ个个体。与原种群中的ρ个个体做比较，选择最大完工时间较短的前ρ个个体，构成一个新的种群。

Step4：如果个体的最大完工时间在累计执行η次领域搜索策略后未得到优化，则舍弃掉该解，按照初始解产生过程生成一个新解来代替该解。

Step5：如果满足终止条件，求解结束，输出最优调度;否则，返回执行Step2。

3  实验结果与分析

为了验证DABC算法求解DAPFSSP的有效性，对文献[9]中的两组基准算例进行仿真计算。两组基准算例由不同的工件数量、机器数量、工厂数量和产品数量构成。第一组算例包含900个小尺度算例，工件数量n={8，12，16，20，24}，机器数量m={2，3，4，5}，工厂数量F={2，3，4}，产品数量H={2，3，4};第二组算例包含810个大算例，工件数量n={100，200，500}，机器数量m={2，3，4，5}，工厂数量F={4，6，8}，产品数量H={30，40，50}。为了比较各种算法的有效性和效率，实验结果通常采用平均相对百分比偏差（ARPD）作为比较指标[25]，计算过程为：

其中，Cbest表示每个算例的已知最优解，Ci表示每个实例在第次试验中所获得的最优结果，R表示执行计算的次数。ARPD越小表示算法的性能越好，ARPD的值小于零表示最优解得到了优化。

3.1  参数设置

所选参数的合适与否对启发式算法求解的质量、计算效率等性能具有重要影响。因此，采用田口试验方法确定影响DABC求解DAPFSSP的四个关键参数，包括种群个体数量ρ、参与锦标赛选择的种群个体数量φ、种群个体最大允许领域搜索次数η、最大迭代次数κ。每个参数选择4个不同的水平，参数值组合如表1所示。

参数正交阵列L16（44）的选择基于参数的数量和因子水平。选择实例I_24_5_3_2_2进行仿真试验。每个参数组合独立运行20次，计算平均最大完工时间（AM）。φ=ρ×10%，参数正交阵列和AM计算结果如表2所示。计算各参数的平均AM值，并对各因素的因子水平进行显著性检验。各参数的平均AM值和显著性水平如表3所示，各参数不同取值下AM值的变化趋势如图2所示。

由图2和表3可知，种群个体数量ρ是4个影响因素中影响最明显的，选择较大的ρ可以得到更优的AM值。然而，选择较大的ρ意味着需要更大的计算成本（即更多的计算时间）。在最大迭代次数κ达到200次时，AM值存在逐渐减少的变化趋势。λ和η在选择较小的因子水平时可以得到更小的AM值。因此，选择ρ=100、λ=5、η=2、κ=100作为DABC的参数值。

3.2  计算结果与分析

基于两组算例，对比已知的12种启发式算法，分析DABC求解DAPDSSP的性能。针对每个算例，独立运行5次，计算平均ARPD值。对于900个小尺度算例，其计算结果按照工厂数量F与工件数量n的组合分组，每组F×n表示60个算例的ARPD平均值。12种参与对比的启发式算法的计算结果直接取自文献[9]。如表4所示，DABC在所有算法结果里取得了最优的结果。在15组算例分组中，有8组的平均ARPD值小于0。计算结果显示，87个小尺度算例取得了更小的最大完工时间。

对于810个大尺度算例，计算结果分别按照工厂数量F、产品数量H、工件数量n进行分组，每组表示270个大尺度算例的ARPD平均值。12种参与对比的启发式算法的计算结果直接取自文献[9]。如表5所示，DABC在所有算法中取得了最好的计算结果。在9组算例分组中，所有分组的平均ARPD值小于0。计算结果显示，114个小尺度算例取得了更小的最大完工时间。

4  结  论

本文针对以最大完工时间最小化为目标的分布式装配置换流水车间调度问题，提出了一种离散人工蜂群算法。通过大量调度问题标准算例进行实验研究，结果表明该算法具有较好的搜索性能和效果。本文只讨论了单目标分布式装配调度问题，未来将进一步探索使用人工蜂群算法解决更加复杂的多目标或多约束的分布式装配调度问题。

参考文献：

[1] LEE C Y，CHENG T C E，LIN B M T. Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem [J].Management Science，1993，39（5）：616-625.

[2] POTTS C N，SEVASTJANOV S V，STRUSEVICH V A，et al. The Two-Stage Assembly Scheduling Problem：Complexity and Approximation [J].Operations Research，1995，43（2）：346-355.

[3] CHENG T C E，WANG G. Scheduling the fabrication and assembly of components in a two-machine flowshop [J].IIE Transactions，1999，31（2）：135-143.

[4] ALI A，HARUN A. The two stage assembly flowshop scheduling problem to minimize total tardiness [J].Journal of Intelligent Manufacturing，2015，26（2）：225-237.

[5] ALI A，AL-ANZI F S. The two-stage assembly scheduling problem to minimize total completion time with setup times [J].Computers and Operations Research，2009，36（10）：2740-2747.

[6] ZANG Y，ZHOU Z L，LIU J Y. The production scheduling problem in a multi-page invoice printing system [J].Computers and Operations Research，2010，37（10）：1814-1821.

[7] BEHNAMIAN J，GHOMI S M T F. A survey of multi-factory scheduling [J].Journal of Intelligent Manufacturing，2016，27（1）：231-249.

[8] NADERI B，RUIZ R. The distributed permutation flowshop scheduling problem [J].Computers and Operations Research，2010，37（4）：754-768.

[9] HATAMIS，Ruiz R，ANDRES-ROMANO C. The Distributed Assembly Permutation Flowshop Scheduling Problem [J].International Journal of Production Research，2013，51（17）：5292-5308.

[10] LIN J，ZHANG S. An effective hybrid biogeography-based optimization algorithm for the distributed assembly permutation flow-shop scheduling problem [J].Computers & Industrial Engineering，2016，97：128-136.

[11] WANG S Y，WANG L. An Estimation of Distribution Algorithm-Based Memetic Algorithm for the Distributed Assembly Permutation Flow-Shop Scheduling Problem [J].IEEE Transactions on Systems， Man， and Cybernetics： Systems，2016，46（1）：139-149.

[12] LIN J，WANG Z J，LI X. A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem [J]. Swarm and Evolutionary Computation，2017，36：124-135.

[13] PAN Q K，GAO L，LI X Y，et al. Effective constructive heuristics and meta-heuristics for the distributed assembly permutation flowshop scheduling problem [J].Applied Soft Computing，2019，81：105492.

[14] FERONE D，HATAMI S，GONZ?LEZ‐NEIRA EM，et al. A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem [J]. International Transactions in Operational Research，2020，27（3）：1368-1391.

[15] ZHANG G H，XING K Y，Zhang G Y，et al. Memetic algorithm with meta-Lamarckian learning and simplex search for distributed flexible assembly permutation flowshop scheduling problem [J].IEEE Access，2020，8：96115-96128.

[16] ZHANG Z Q，QIAN B，HU R，et al. A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem [J].Swarm and Evolutionary Computation，2021，60：100785.

[17] HATAMI S，RUIZ R，ANDRES-ROMANO C. Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times [J].International Journal of Production Economics，2015，169：76-88.

[18] SONG H B，LIN J . A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times [J].Swarm and Evolutionary Computation，2021，60：100807.

[19] GONZALEZ-NEIRA E M，FERONE D，HATAMI S，et al. A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times [J].Simulation Modelling Practice and Theory，2017，79：23-36.

[20] ZHANG G H，XING K Y，CAO F. Scheduling distributed flowshops with flexible assembly and set-up time to minimize makespan [J].International Journal of Production Research，2018，56（9-10）：3226-3244.

[21] SANG H Y，PAN Q K，LI J Q，et al. Effective invasive weed optimization algorithms for distributed assembly permutation flowshop problem with total flowtime criterion [J]. Swarm and Evolutionary Computation，2019，44：64-73.

[22] LI D N，Li M，Meng X W，et al. A Hyperheuristic Approach for Intercell Scheduling With Single Processing Machines and Batch Processing Machines [J].IEEE Transactions on Systems， Man， and Cybernetics： Systems，2015，45（2）：315-325.

[23] OZTURK C，GORKEMLI B，KARABOGA D，et al. A comprehensive survey： artificial bee colony （ABC） algorithm and applications [J].Artificial Intelligence Review： An International Science and Engineering Journal，2014，42：21-57.

[24] LIU Z M. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem [J].Computers & Industrial Engineering，2012，62（4）：917-926.

[25] RUIZ R，MAROTO C，ALCARAZ J. Two new robust genetic algorithms for the flowshop scheduling problem [J].Omega，2006，34（5）：461-476.

作者簡介：段秀山（1995—），男，汉族，重庆彭水人，硕士研究生在读，研究方向：智能制造。