多目标混合进化算法求解加工时间可控的开放车间调度问题  

Multi-objective hybrid evolutionary algorithm for solving open-shop scheduling problem with controllable processing time

作　　者：陈揆能 袁小芳[2] CHEN Kuineng;YUAN Xiaofang(Hunan Engineering Research Center of Control Technology and Equipment of Special Robot in Complex Environment(Hunan Vocational Institute of Technology),Xiangtan Hunan 411104,China;College of Electrical and Information Engineering,Hunan University,Changsha Hunan 410082,China)

机构地区：[1]复杂环境特种机器人控制技术与装备湖南省工程研究中心(湖南理工职业技术学院),湖南湘潭411104 [2]湖南大学电气与信息工程学院,长沙410082

出　　处：《计算机应用》2022年第8期2617-2627,共11页journal of Computer Applications

基　　金：湖南省自然科学基金资助项目(2019JJ40036)。

摘　　要：开放车间调度问题属于典型的NP-hard问题。目前的相关研究大多假设工序在机器上具有固定的加工时间。然而,在大多数现实生产场景中,机床的加工时间可以通过调节加工功率加以控制。同时优化完工时间和总能耗两个冲突目标对高效、节能的开放车间生产具有重要意义。为此,研究了可控加工时间的多目标开放车间调度问题(MOOSPCPT),以最小化完工时间和总额外能耗为目标构建了混合整数规划模型,并提出一种多目标混合进化算法(MOHEA)用于求解MOOSPCPT。在MOHEA中提出多个策略:(1)改进生物地理学优化算法中的迁移策略和变异策略用于全局搜索,有效地提高了种群的多样性;(2)基于关键路径设计一种自调整变邻域搜索策略,增强了算法的局部搜索能力;(3)设计了一种加工时间重置算子,从而显著提升了算法的搜索效率。仿真实验结果表明:所提出的策略有效地提升了算法性能;相较于NSGA-Ⅱ(Non-dominated Sorting Genetic AlgorithmⅡ)、NSGA-Ⅲ(Non-dominated Sorting Genetic Algorithm Ⅲ)和SPEA2(Strength Pareto Evolutionary Algorithm 2),MOHEA能够更有效地解决MOOSPCPT。The open-shop scheduling problem is a typical NP-hard problem.Most of the existing research assumes that the processing time of a procedure is fixed.However,in real-world production scenarios,the processing time can be controlled by adjusting the processing power.At the same time,optimizing the two conflicting objectives of completion time and energy consumption is significant for the high-efficiency and energy-saving open-shop production.Therefore,the Multi-objective Open-shop Scheduling Problem with Controllable Processing Time(MOOSPCPT)was studied,a mixed-integer programming model was constructed with the objectives of minimizing makespan and total extra energy consumption,and a Multi-objective Hybrid Evolutionary Algorithm(MOHEA)was proposed to solve MOOSPCPT.Several strategies were developed in the MOHEA:(1)the migration strategy and mutation strategy in the biogeographic-based optimization algorithm were improved for global search,which facilitated the diversity of the population effectively;(2)a self-adjusting variable neighborhood search strategy was designed based on the critical path,which enhanced the local search performance of the algorithm;(3)a processing time resetting operator was designed,which improved the search efficiency of the algorithm significantly.Simulation results show that the proposed strategies are effective in improving algorithm performance;MOHEA solves MOOSPCPT more effectively compared with Non-dominated Sorting Genetic AlgorithmⅡ(NSGA-Ⅱ),Non-dominated Sorting Genetic AlgorithmⅢ(NSGA-Ⅲ)and Strength Pareto Evolutionary Algorithm 2(SPEA2).

关 键 词：开放车间调度问题 加工时间可控 完工时间 总额外能耗 多目标混合进化算法 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]