| 引用本文: | 连戈,朱荣,钱斌,吴绍云,胡蓉.超启发式人工蜂群算法求解多场景鲁棒分布式置换流水车间调度问题[J].控制理论与应用,2023,40(4):713~723.[点击复制] |
| LIAN Ge,ZHU Rong,QIAN Bin,WU Shao-yu,HU Rong.Hyper-heuristic artificial bee colony algorithm for the multi-scenario-based robust distributed permutation flow-shop scheduling problem[J].Control Theory and Technology,2023,40(4):713~723.[点击复制] |
|
| 超启发式人工蜂群算法求解多场景鲁棒分布式置换流水车间调度问题 |
| Hyper-heuristic artificial bee colony algorithm for the multi-scenario-based robust distributed permutation flow-shop scheduling problem |
| 摘要点击 1325 全文点击 451 投稿时间：2021-10-26 修订日期：2023-03-12 |
| 查看全文 查看/发表评论 下载PDF阅读器 |
| DOI编号 10.7641/CTA.2022.11026 |
| 2023,40(4):713-723 |
| 中文关键词 分布式置换流水车间调度问题 多场景 鲁棒调度 人工蜂群算法 超启发式算法 |
| 英文关键词 distributed permutation flow-shop scheduling problem multi-scenario robust scheduling artificial bee colony algorithm hyper-heuristic algorithm |
| 基金项目 国家自然科学基金项目(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. |
|
|
|
|
|