超启发式人工蜂群算法求解多场景鲁棒分布式置换流水车间调度问题  

Hyper-heuristic artificial bee colony algorithm for the multi-scenario-based robust distributed permutation flow-shop scheduling problem

作　　者：连戈 朱荣 钱斌[1,2] 吴绍云 胡蓉[1,2] LIAN Ge;ZHU Rong;QIAN Bin;WU Shao-yun;HU Rong(School of Information Engineering and Automation,Kunming University of Science and Technology,Kunming Yunnan 650500,China;Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming Yunnan 650500,China;City College,Kunming University of Science and Technology,Kunming Yunnan 650051,China;Tipping Paper Mill of Yuxi,Yuxi Yunnan 653100,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,云南昆明650500 [2]昆明理工大学、云南省人工智能重点实验室,云南昆明650500 [3]昆明理工大学城市学院,云南昆明650051 [4]云南玉溪水松纸厂,云南玉溪653100

出　　处：《控制理论与应用》2023年第4期713-723,共11页Control Theory & Applications

基　　金：国家自然科学基金项目(62173169,61963022);云南省基础研究重点项目(202201AS070030)资助。

摘　　要：本文考虑现实中广泛存在的加工时间不确定的分布式置换流水车间调度问题(DPFSP),研究如何建立问题模型和设计求解算法,方可确保算法最终获得的解在多个典型DPFSP场景下,均具有能满足客户期望的较小优化目标值(即makespan值).在问题建模方面,首先,采用场景法构建多个不同典型场景以组成场景集(每个场景对应1个具有不同加工时间的DPFSP),并设定合适的makespan值作为场景阈值,用于在评价问题解时从场景集中动态筛选出“坏”场景子集;其次,在常规优化目标makespan的基础上,结合“坏”场景子集概念提出可实现鲁棒调度的新型优化目标,用于引导算法每代加强对当前“坏”场景子集中每个DPFSP场景对应解空间的搜索;然后,结合所提的新型优化目标,建立基于多场景的鲁棒DPFSP(MSRDPFSP).在算法设计方面,提出一种超启发式人工蜂群算法(HHABC)对MSRDPFSP进行求解.HHABC分为高、低两层结构,其中低层设计6种启发式操作(HO),高层采用人工蜂群算法控制和选择低层HOs来不断生成新的混合启发式算法,从而实现在不同场景对应解空间中的较深入搜索.在不同规模测试问题上的仿真实验与算法对比,验证了HHABC的有效性.This paper considers the widely existing distributed permutation flow shop scheduling problem(DPFSP)with uncertain processing time,and studies how to establish the problem model and design the solution algorithm,so as to ensure that the final solution obtained by the algorithm has a smaller optimization target value(i.e.makespan value)that can meet customer expectation in multiple typical scenarios of DPFSP.In terms of problem modeling,firstly,the scenario method is used to construct multiple different typical scenarios to form a scenario set in which each scenario corresponds to a DPFSP with different processing time,and the appropriate makespan value is selected as the scenario threshold to dynamically filter out the bad scenario subset from the scenario set when evaluating the problem’s solution;secondly,based on the conventional optimization objective(i.e.,makespan)and combined with the concept of“bad”scene subset,a new optimization objective that can realize robust scheduling is proposed to guide each generation of the algorithm to strengthen the search in the corresponding solution space of each DPFSP’s scenario in the current“bad”scenario set;thirdly,combined with the proposed new optimization objective,a multi-scenario-based robust DPFSP(MSRDPFSP)is established.In terms of algorithm design,a hyper-heuristic artificial bee colony algorithm(HHABC)is proposed to solve the MSRDPFSP.The HHABC is divided into a high-level and low-level structure.The low level is designed with six heuristic operations(HO),and the high level utilizes the artificial bee colony algorithm to control and select low-level HOs to continuously generate new hybrid heuristic algorithms,which are used to realize in-depth search in the corresponding solution spaces of different scenarios.Simulation experiments and algorithm comparisons on the test problems with different scales verify the effectiveness of HHABC.

关 键 词：分布式置换流水车间调度问题 多场景 鲁棒调度 人工蜂群算法 超启发式算法 

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