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

Extended empire competition algorithm for distributed unrelated parallel machine workshop scheduling problem

作　　者：李立山 陶翼飞[1] 何毅[2] 周国诚 王镜捷 Li Lishan;Tao Yifei;He Yi;Zhou Guocheng;Wang Jingjie(Faculty of Mechanical&Electrical,Kunming University of Science&Technology,Kunming 650504,China;Honghe Cigarette Factory of Hongyun Honghe Tobacco(Group)Co.,Ltd.,Honghe Yunnan 652399,China)

机构地区：[1]昆明理工大学机电工程学院,昆明650504 [2]红云红河烟草(集团)有限责任公司红河卷烟厂,云南红河652399

出　　处：《计算机应用研究》2024年第9期2758-2765,共8页Application Research of Computers

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

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

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

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]