求解多目标柔性作业车间调度问题的两阶段混合Pareto蚁群算法
Two？？Stage Hybrid Pareto Ant Colony Algorithm for Multi？？Objective Flexible Job Shop Scheduling

针对多目标柔性作业车间调度问题(FJSP)分解得到的作业分派、排序子问题仍是多目标优化问题的情况,提出了一种求解该问题的分层Pareto优化框架,并采用该框架构建了两阶段混合Pareto蚁群算法的求解算法,其中两个Pareto蚁群系统分别求解多目标作业分派、排序问题。结合GT算法、排产规则评估和过滤第一阶段的分派方案,将具有较好评估全局解的分派方案作为分派阶段的精英档案,并输入给排序蚁群系统获取其非支配调度解,进而获取问题全局非支配解。子问题算法混合了各目标相关的邻域搜索策略,与Pareto蚁群算法结合,以期提高解的质量。通过求解带有平均工件加权延迟时间指标的多个FJSP基准算例,验证了算法的有效性。计算结果表明,该分层Pareto优化框架对原问题进行分层分解,有利于降低原问题的复杂性,相比多数文献,算法能够获得各基准算例Pareto非支配解,从而为分解求解复杂多目标调度优化问题提供了一种途径。
Multi？？objective flexible job shop scheduling can be divided into two sub？？problems, namely job assignment and sorting, which are often multi？？objective optimization problems. Aiming at this situation, this paper presents a layered Pareto optimization frame for multi？？objective flexible job shop problem and proposes a two？？stage hybrid Pareto ant colony algorithm for multi？？objective operation assignment (OA) and operation sequencing (OS) sub？？problems. Embedding multiple scheduling rules in GT algorithm is used to evaluate and filter the assignment solutions. The global optimal non？？dominated front of the original problem is obtained by scheduling optimization as the elite archive of assignments. Each Pareto ant colony algorithm is combined with the neighborhood search strategies related to different objectives. The co？？evolutionary can obtain high？？quality solutions to multi？？objective FJSP. Finally, by solving four benchmark instances considering minimizing the mean weighted tardiness time, the effectiveness of the method is testified. The simulation results show that the layered Pareto optimization frame helps to reduce complexity of the problem, and compared with other literatures, the proposed algorithm can obtain the Pareto non？？dominant solutions of each instance, providing a new way for solving complex multi？？objective scheduling problems