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