扩展帝国竞争算法求解分布式不相关并行机车间调度问题

摘 要：针对考虑加工约束的分布式不相关并行机车间调度问题，以总运输成本、工厂间并行机齐停评价函数和工件种类平均切换次数均衡评价函数为优化目标，提出一种扩展帝国竞争算法进行求解。该算法在原始帝国竞争算法的基础上，增加了适于工厂分配的初始化工厂-工件序列群；根据传统帝国竞争算法容易陷入局部最优的缺点，将较劣序列同化分为了外部同化机制和内部同化机制，采用局部和全局相结合的搜索方式实现扩展帝国竞争算法的智能搜索行为；采用部分匹配交叉和单点变异更新工厂-工件序列群，保证工厂-工件序列的多样性。最后设计3个不同规模12个算例，通过仿真实验验证所提算法的有效性，同时对比相关领域研究成果验证了该算法在求解分布式多目标不相关并行机调度问题方面的优越性。

关键词：扩展帝国竞争算法；分布式不相关并行机车间调度问题；总运输成本；工厂间并行机齐停评价函数；工厂间工件种类平均切换次数均衡评价函数

中图分类号：TP181 文献标志码：A 文章编号：1001-3695（2024）09-027-2758-08

doi：10.19734/j.issn.1001-3695.2023.12.0619

Extended empire competition algorithm for distributed unrelated

parallel machine workshop scheduling problem

Li Lishan1，Tao Yifei1，He Yi2，Zhou Guocheng1，Wang Jingjie1

（1.Faculty of Mechanical & Electrical，Kunming University of Science & Technology，Kunming 650504，China;2.Honghe Cigarette Factory of Hongyun Honghe Tobacco（Group）Co.，Ltd.，Honghe Yunnan 652399，China）

Abstract：Aiming at the distributed unrelated parallel machine scheduling problem with machining constraints，this paper proposed an extended empire competition algorithm to solve the problem，which took the total transportation cost，evaluation function for simultaneous shutdown of parallel machines among factories and equilibrium evaluation function for average switching frequency of workpiece types among factories as optimization objectives.Based on the original empire competition algorithm，this algorithm added an initial factory-workpiece sequence group suitable for factory assignment.According to the shortcoming of the traditional empire competition algorithm that it was easy to fall into the local optimum，this paper divided the inferior sequence assimilation into external assimilation mechanism and the internal assimilation mechanism.The extended empire competition algorithm combined local and global search methods to realize the intelligent search behavior.This paper used the partial matching crossover and single point mutation to update the factory-workpiece sequence group and ensure the diversity of the factory-workpiece sequence.Finally，this paper designed three different scales of 12 examples and verified the effectiveness of the proposed algorithm through simulation experiments.At the same time，this paper verified the advantages of the proposed algorithm in solving the distributed multi-objective unrelated parallel machine scheduling problem by comparing the research results in related fields.

Key words：extended empire competition algorithm;distributed unrelated machine parallel workshop scheduling;total transportation cost;evaluation function for simultaneous shutdown of parallel machines among factories;equilibrium evaluation function for average switching frequency of workpiece types among factories

0 引言

随着经济全球化进程的加速推进，制造业作为国民经济的重要支柱，已经从大规模、大批量的集中式制造转变为小规模、小批量的分布式制造，相应的生产调度问题也从单一工厂的调度问题扩展为多个工厂的分布式调度问题［1，2］。分布式并行机调度问题（distributed parallel machine scheduling problem，DPMSP）是为了企业能快速响应市场需求、提高企业竞争力，由传统单一工厂的并行机调度问题（parallel machine scheduling problem，PMSP）［3，4］扩展为在多个工厂环境下的分布式并行机调度问题，已经广泛应用到了多个行业，如烟草、钢铁等，因此研究DPMSP具有重要的理论意义和实际应用价值。

近年来，DPMSP的研究取得了一些进展。文献［5，6］以最小化作业提前/拖期及总完成时间之和为优化目标，提出一种混合整数规划模型，并设计了一种超启发式算法解决分布式并行机调度问题；文献［7］针对分布式并行机与装配调度问题，以最小化平均流程时间和延迟作业的数量为优化目标，提出一种新的泛化和元启发式算法，使用田口方法来校准和讨论元启发式参数，实验结果证明了所提算法在解决中规模问题的有效性；文献［8］考虑了在不同并行生产线上的几种产品的同时批量加工和调度问题，以最小化与序相关的设置和生产成本为优化目标，通过结合局部搜索元策略阈值接受和模拟退火，结合对偶再优化解决了该问题；文献［9］针对设备维修导致的生产延迟问题，提出一种辅助校正的优化方法，建立了联合生产和预防性维修调度问题的数学模型和仿真模型；文献［10］研究了分布式制造环境下的装配柔性作业车间生产与配送两阶段联合调度问题，结合实际的生产情况，考虑供应链下生产与配送过程所产生的库存成本，以最小化生产和配送的总成本为联合调度优化目标，提出一种改进鲸鱼算法进行求解；文献［11］针对分布式两阶段装配流水车间调度问题，以最小化总延迟时间为优化目标，提出一种帝国竞争-协作算法，并给出一种新型帝国竞争策略来提高算法的搜索效率，通过实验验证了所提算法在解决含不相关并行机的分布式车间调度问题方面的有效性；文献［12］提出了一种混合帝国主义竞争算法来解决分布式并行机调度问题，以最小化总延迟为优化目标，将所有帝国分为最强帝国、最弱帝国和其他帝国三种类型，不同帝国使用不同搜索算子，有效解决了所研究的问题；文献［13］研究了异构生产网络中具有最大完工时间最小化的分布式不相关并行机调度问题，并直接将其简化为扩展机器分配问题，提出一种新的带有记忆的帝国主义竞争算法进行求解；文献［14］提出一种求解异构工厂分布式并行机调度问题的新型帝国竞争算法，以最小化最大完成时间作为优化目标，将问题简化为工厂分配子问题进行求解。综上所述，目前已有部分文献对分布式不相关并行机车间调度问题或含有不相关并行机的分布式车间调度问题进行了研究，特别是近年来部分学者采用帝国竞争算法解决分布式不相关并行机车间调度问题，并取得了一定的研究成果。本文基于现有研究成果，考虑到实际工况下的加工约束，以及运输成本、并行机齐停、工件种类切换次数等优化目标，针对分布式不相关并行机车间调度问题展开研究。

帝国竞争算法（imperial competition algorithm，ICA）是受古代帝国和殖民地的启发于2007年提出的一种智能优化算法，与粒子群优化、蚁群等算法一样，都属于基于群体的随机优化搜索算法。因其具有较强的局部搜索能力和较快的收敛速度，ICA已广泛应用于生产调度、路径规划［15］、旅行商问题［16］、函数优化［17］、电网控制和电能分配问题［18］等。

本文针对分布式不相关并行机车间调度问题（distributed unrelated parallel machines scheduling problem，DUPMSP），提出一种扩展帝国竞争算法（extended empire competition algorithm，EICA），以总运输成本、工厂间并行机齐停评价函数和工件种类平均切换次数均衡评价函数为优化目标。该算法在初始阶段增加适合工厂分配的初始化工厂-工件序列群，将较劣序列同化分为较劣序列外部同化和内部同化，并且采用部分匹配交叉和单点变异以更新工厂-工件序列，有效解决ICA容易陷入局部最优的情况，最后通过Pareto非支配排序得到最优解集。

1 问题描述

分布式不相关并行机车间调度问题（DUPMSP）描述如下：假设i个工件（i=1，2，…，n）分配给位于不同地区和地理环境的f个工厂（f=1，2，…，F）进行加工。工厂f内有mf台不相关并行机Mf 1，…，Mfmf，总共N=∑Ff=1mf台并行机，每台并行机加工同一工件的加工时间不同，并行机的加工时间包含并行机调整时间，并行机加工时间服从均匀分布，一些工件只能在特定工厂的特定并行机上加工。图1为分布式不相关并行机车间调度模型示意图。

2.7 工厂-工件序列更新

通过快速非支配排序，选择第一阶层的工厂-工件序列作为父代工厂-工件序列。如果第一阶层工厂-工件序列的数量没有达到初始工厂-工件序列的数量，随机从第二和三阶层中选择一定数量的工厂-工件序列组成初始工厂-工件序列的数量，通过部分匹配交叉和单点变异操作对工厂-工件序列进行更新，保证工厂-工件序列多样性。

部分匹配交叉的操作步骤如下：

a）选择交叉区域。以一定的概率选择两个工厂-工件序列作为父代，在父代序列中随机选择一个交叉区域，如图8步骤a）所示。工厂-工件序列1：［9 3 6 4 10 2 5 7 1 8］和工厂-工件序列2：［3 7 9 5 10 4 8 6 1 2］，随机选择两个交叉点1、2确定交叉区域，两个工厂-工件序列被选中的区域位置相同，图中灰色部分为交叉区域。

b）交换被选中序列。交换两父代被选中的区域，生成两个新的工厂-工件序列，如图8步骤b）所示。交换被选中的序列后生成［9 3 9 5 10 4 8 7 1 8］和［3 7 6 4 10 2 5 6 1 2］。

c）元素冲突检测。根据交换的两个序列建立映射关系，以图8中步骤c）的8-5-4-2为例，可以看到交换被选中序列后得到的结果中工厂-工件序列［9 3 9 5 10 4 8 7 1 8］存在两个重复序号8，这时通过映射关系将选中区域之外的一个8转变为2，依此类推到无冲突为止。其他重复元素按照这种映射关系进行映射，确保新生成的工厂-工件序列中无元素冲突。

d）生成新序列。通过元素冲突检测，生成两个新工厂-工件序列。

单点变异与较劣序列革命类似，其操作步骤如下：

a）选择变异点。在部分匹配交叉之后，按一定的概率将新生成的工厂-工件序列中的某个元素随机转变为此序列中的其他元素。如图9中步骤a）所示，一个工厂-工件序列［6 3 9 5 10 4 8 7 1 2］，随机选择一个元素8作为变异点，变异为元素3。

b）元素冲突检测，变异后变异点的元素不变，与变异点发生冲突的其他位置的元素转变为变异前变异点的元素。如图9中步骤b）所示，变异后的序列［6 3 9 5 10 4 3 7 1 2］进行元素冲突检测，图中变异前变异点位置元素为8，变异后变异点元素为3，元素3在序列中有两个，则元素8替换与变异点元素3冲突的另一个3。

c）生成新序列。生成一个新的工厂-工件序列。

3 计算实验

为了验证EICA在求解分布式不相关并行机车间调度多目标问题的有效性，进行了分布式车间小规模、中规模和大规模的仿真实验。所有测试算例均通过Plant Simulation软件建立仿真模型，用Simtalk编写优化算法程序。分布式不相关并行机车间仿真模型如图10所示。

通过大量仿真实验得到相关参数设置为：工厂-工件序列即版图规模为50，并行机-工件序列即国家数量为100，成为帝国的概率a=0.5，工厂-工件序列更新中交叉概率为0.95，变异概率为0.05。

3.1 评价指标

参照文献［19］对算法性能评价指标的选取，将Pareto非支配解的个数NS（单位：个）、反世代距离IGD、解间距SP作为评价算法性能的指标。

3.2 测试算例与对比算法

本文选用分布式工厂的小规模、中规模和大规模共12个算例分别测试所提算法的有效性，表2描述了算例的基本信息，每个工件的加工时间和运输成本均服从均匀分布，其中工件数n=50，60，70，80的4个算例属于小规模算例，n=90，100，110，120的4个算例属于中规模算例，n=140，160，180，200的4个算例属于大规模算例。

本文选择以下两种对比算法：张清勇等人［14］针对异构工厂分布式并行机调度问题提出新型帝国竞争算法（ICA），原文通过大量实验表明新型ICA具有较强的搜索优势和较好的稳定性；轩华等人［20］针对含不相关并行机的分布式流水车间调度问题提出混合离散人工蜂群算法（HDABC），原文通过大量实验表明HDABC具有较强的搜索优势和较好的收敛性。因此本文选择新型ICA和HDABC两种算法作为对比算法。

3.3 实验结果与比较

根据算例信息表对JNQeIrsz3FblXXC19qX14w==每组算例独立运行20次取平均值，实验结果如表3所示。根据不同规模问题的实验结果绘制出IGD和SP箱线图，如图11、12所示。表4是运行每个算例得出的非支配解集按照文献［18］的层次分析法（analytic hierarchy process，AHP）决策出最优解，最后多次运行每个算例取平均值。其中目标函数F1单位为元，F2单位为s，F3单位为次，根据实际工况对目标函数F2、F3进行四舍五入取整。

通过不同规模的仿真实验结果得出以下结论：首先，对于小规模算例中的4个算例，除算例4中HDABC的非支配解个数比EICA的多外，EICA得出的Pareto非支配解个数比其他两种对比算法都多，说明EICA在解决小规模分布式不相关并行机车间调度问题时能搜索到更多的前沿解，可以提供更多的调度方案。EICA的IGD平均值为12.86，均低于其他两种算法的IGD平均值，说明在解决小规模分布式不相关并行机车间调度多目标问题时EICA的收敛性较好。但EICA的SP平均值为42.57，相比两种算法的SP平均值较大，说明EICA在解决小规模问题时解的分布均衡性较差。其次，在解决中规模的4个算例时，除算例6外EICA得出的非支配解个数都比新型ICA的多，说明EICA在解决中规模问题时与新型ICA相比，可以搜索到更多前沿解，但与HDABC相比有所不足。EICA的IGD平均值为5.75，比其他两种算法都低，由此可知，在解决中规模分布式不相关并行机车间调度多目标问题时EICA的收敛性较好，但EICA的SP平均值为35.11，说明在解决中规模问题时相比其他两种算法解的分布均衡性有所不足；最后，在大规模算例中，EICA得出的Pareto非支配解的个数NS都比其他两种算法多，EICA的IGD平均值为17.51、SP平均值为18.96，都低于其他两种算法的平均值，说明EICA在解决大规模问题时在解的个数、综合性能和解的均衡性方面都具有一定的优势。

根据表4可知，与新型ICA相比，除算例7、8、11三个算例的优化结果呈互不支配外，EICA在其他算例上的优化结果完全支配其优化结果。由此可知，EICA在解决分布式不相关并行机车间调度的多目标问题时优于新型ICA。与HDABC相比，EICA在算例4、6、8三个算例的优化结果与HDABC所求结果互不支配，在其余算例的优化结果均优于HDABC的优化结果。

由于上述优化结果有较多的互不支配状态，无法直观反映算法的好坏，结合图11、12和表3、4，从整体上直观分析所提算法的有效性和优越性。

从整体上分析可以得出以下结论：首先，从Pareto非支配解的个数NS角度分析，EICA非支配解的个数相较于新型ICA提升9%，相较于HDABC基本持平，说明EICA可以得到较多的非支配解。在此基础上根据表4可以看出，58%的算例得出的最优解中三个目标函数值相较其他两种算法得出的值更低，说明更加接近真实的Pareto非支配解。因此，EICA不仅在非支配解的个数上表现出其优越性，而且得出最优解的质量也高于其他两种算法。其次，依据表3和图11可以得出EICA的IGD平均值相比其他两种算法平均低了64%。因此，EICA相比新型ICA和HDABC有着更好的收敛性。最后，依据表3和图12可以得出EICA的SP均值相比新型ICA高了32%，相比HDABC的SP值高了0.9%，说明EICA在解决中小规模问题时，解的分布均衡性方面相对不足。综合分析以上几个因素可以得出EICA解集的质量较优且算法收敛性较好。

综上所述，EICA在求解分布式不相关并行机车间调度多目标问题时，得到解的个数较多、算法收敛性较好，特别在求解较大规模问题时表现出较好的综合性能，能够保证最优解的个数和解的质量，为分布式不相关并行机车间调度提供更多的调度方案以供选择。

下面给出算例12的调度甘特图，如图13所示。

4 结束语

针对分布式不相关并行机车间调度的多目标问题，提出一种扩展帝国竞争算法。该算法在传统帝国竞争算法的基础上增加适用于工厂分配的初始化工厂-工件序列群；并生成适用于并行机分配的并行机-工件序列群；将选出的较劣并行机-工件序列同化分为与选出的较优序列进行外部同化和较劣序列自身进行内部同化两种；最后工厂-工件序列新采用部分匹配交叉和单点变异进行更新。以总运输成本、工厂间并行机齐停评价函数和工件种类平均切换次数均衡评价函数为优化目标，设计不同规模的算例对算法性能进行测试，验证了所提算法的有效性，并与新型ICA、HDABC进行对比，扩展帝国竞争算法在Pareto非支配解的搜寻能力上具有一定的优势。

分布式车间调度是目前车间优化调度研究的焦点，在实际分布式不相关并行机车间调度问题中，约束条件更加复杂，工件多以批量生产的方式进行加工。因此，在未来的研究中，将对扩展帝国竞争算法作进一步的改进，并使用扩展帝国竞争算法求解以总运输成本、工厂间并行机齐停评价函数及工厂间工件种类平均切换次数均衡为优化目标的分布式不相关并行机车间分批调度问题。

参考文献：

［1］Marandi F，Ghomi F S.Network configuration multi-factory scheduling with batch delivery：a learning-oriented simulated annealing approach［J］.Computers & Industrial Engineering，2019，132：239-310.

［2］王思涵，李新宇，高亮，等.分布式车间调度研究综述［J］.华中科技大学学报：自然科学版，2022，50（6）：1-10.（Wang Sihan，Li Xinyu，Gao Liang，et al.A review of distributed workshop scheduling research［J］.Journal of Huazhong University of Science and Technology：Natural Science Edition，2022，50（6）：1-10.）

［3］Maryam E，Parviz D，Mohamad S，et al.A new approach based on the learning effect for sequence-dependent parallel machine scheduling problem under uncertainty［J］.Discrete Dynamics in Nature and Society，2022，2022：article ID 2648936.

［4］Mecler D，Abu-Marrul V，Martinelli R，et al.Iterated greedy algorithms for a complex parallel machine scheduling problem［J］.European Journal of Operational Research，2022，300（2）：545-560.

［5］Behnamian J，Asgari H.A hyper-heuristic for distributed parallel machine scheduling with machine-dependent processing and sequence-dependent setup times［J］.RAIRO-Operations Research，2022，56（6）：4129-4143.

［6］Behnamian J，Ghomi F S.Multi-objective multi-factory scheduling［J］.RAIRO-Operations Research，2021，55：1447-1467.

［7］Ikhlasul A，Budi S.Solving multi-objective modified distributed parallel machine and assembly scheduling problem（MDPMASP）with eligibility constraints using metaheuristics［J］.Production Manufacturing Research，2022，10（1）：198-225.

［8］Herbert M.Simultaneous lotsizing and scheduling on parallel machines［J］.European Journal of Operational Research，2002，139（2）：277-292.

［9］叶飞，李梓晴，赖李媛君.分布式车间生产维修联合调度仿真优化方法［J］.系统仿真学报，2022，34（4）：688-699.（Ye Fei，Li Ziqing，Lai Liyuanjun.Optimization method for distributed workshop production and maintenance joint scheduling simulation［J］.Journal of System Simulation，2022，34（4）：688-699.）

［10］唐红涛，沈毅，张伟，等.改进鲸鱼算法求解分布式装配柔性作业车间生产与配送联合调度问题［J］.计算机应用研究，2023，40（7）：1982-1990.（Tang Hongtao，Shen Yi，Zhang Wei，et al.Improved whale algorithm for solving the joint scheduling problem of production and distribution in distributed flexible assembly workshops［J］.Application Research of Computers，2023，40（7）：1982-1990.）

［11］Zheng Youlian，Yuan Yue，Zheng Qiaoxian，et al.A hybrid imperialist competitive algorithm for the distributed unrelated parallel machines scheduling problem［J］.Symmetry，2022，14（2）：204.

［12］陈雅玲，雷德明.求解分布式两阶段装配流水车间调度的帝国竞争-协作算法［J］.控制理论与应用，2021，38（12）：1957-1967.（Chen Yaling，Lei Deming.Empire competition collaboration algorithm for solving distributed two stage assembly flow shop scheduling［J］.Control Theory and Applications，2021，38（12）：1957-1967.）

［13］Lei Deming，Yuan Yue，Cai Jingcao，et al.An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling［J］.International Journal of Production Research，2020，58（2）：597-614.

［14］张清勇，王皓冉，雷德明.求解分布式并行机调度的新型帝国竞争算法［J］.华中科技大学学报：自然科学版，2019，47（8）：86-91.（Zhang Qingyong，Wang Haoran，Lei Deming.A novel imperial competition algorithm for solving distributed parallel machine scheduling［J］.Journal of Huazhong University of Science and Technology：Natural Science Edition，2019，47（8）：86-91.）

［15］Babak R，Gadelha F G，Rasul E，et al.Combining genetic local search into a multi-population imperialist competitive algorithm for the capaci-tated vehicle routing problem［J］.Applied Soft Computing，2023，142：110309.

［16］徐伟华，张根瑞，魏传祥，等.基于自适应继承策略的帝国竞争算法求解旅行商问题［J］.计算机应用研究，2021，38（11）：3349-3353.（X1ARblVoPHx+zJghmE8uwmg==u Weihua，Zhang Genrui，Wei Chuanxiang，et al.Empire competition algorithm based on adaptive inheritance strategy for solving traveling salesman problem［J］.Application Research of Computers，2021，38（11）：3349-3353.）

［17］Charadi S，Chakir E H，Redouane A，et al.A novel hybrid imperialist competitive algorithm-particle swarm optimization metaheuristic optimization algorithm for cost-effective energy management in Multi-Source residential microgrids［J］.Energies，2023，16（19）：6896.

［18］徐宜刚，陈勇，王宸，等.改进NSGA-Ⅲ求解高维多目标绿色柔性作业车间调度问题［J/OL］.系统仿真学报.（2023-09-18）.https：//kns.cnki.net/kcms/detail/11.3092.V.20230915.1327.007.html.（Xu Yigang，Chen Yong，Wang Chen，et al.Improving NSGA-Ⅲ for high-dimensional multi-objective green flexible job shop scheduling problem［J/OL］.Journal of System Simulation.（2023-09-18）.https：//kns.cnki.net/kcms/detail/11.3092.V.20230915.1327.007.html.）

［19］荀洪凯，陶翼飞，张源，等.多目标启发式狼群算法求解不相关并行机分批调度问题［J］.信息与控制，2023，52（1）：93-103.（Xun Hongkai，Tao Yifei，Zhang Yuan，et al.Multi objective heuristic wolf swarm algorithm for solving batch scheduling problems on unrelated parallel machines［J］.Information and Control，2023，52（1）：93-103.）

［20］轩华，李文婷，李冰.混合离散人工蜂群算法求解含不相关并行机的分布式柔性流水线调度［J］.控制与决策，2023，38（3）：779-789.（Xuan Hua，Li Wenting，Li Bing.Hybrid discrete artificial bee colony algorithm for distributed flexible pipeline scheduling with unrelated parallel machines［J］.Control and Decision Making，2023，38（3）：779-789.）

收稿日期：2023-12-20

修回日期：2024-02-29

基金项目：云南省重点研发计划（工业领域）资助项目（2018BA086）

作者简介：李立山（1994—），男，甘肃会宁人，硕士研究生，主要研究方向为复杂生产系统建模与优化调度；陶翼飞（1983—），男（通信作者），陕西西安人，讲师，硕导，博士，主要研究方向为复杂系统建模、调度与智能算法等（676379098@qq.com）；何毅（1976—），男，云南个旧人，工程师，主要研究方向为企业信息化建设；周国诚（1997—），男，山东安丘人，硕士研究生，主要研究方向为物流系统仿真建模与优化调度；王镜捷（1998—），男，云南昆明人，硕士研究生，主要研究方向为复杂生产系统建模与优化调度.