文献类型：期刊文献

英文题名：An improved max-min ant system with multi-stage acceleration and elite refinement for non-permutation flow-shop scheduling problem

作者：Wang, Yuwan[1];Yu, Zhenhua[1];Wang, Huazhong[1];Jiang, Qingchao[1];Zhong, Weimin[1]

机构：[1]East China Univ Sci & Technol, Key Lab Smart Mfg Energy Chem Proc, Minist Educ, Shanghai 200237, Peoples R China

年份：2026

卷号：331

外文期刊名：EXPERT SYSTEMS WITH APPLICATIONS

收录：;EI(收录号：20262621019000);WOS:【SCI-EXPANDED(收录号:WOS:001813745500001)】；

基金：This work was supported in part by the National Natural Science Foundation of China under Grants U25A20468 and 62322309, and in part by the Shanghai Explorer Program under Grant 24TS1411700.

语种：英文

外文关键词：Makespan minimization; Max-min ant system; Neighborhood search; Non-permutation flow-shop scheduling

摘要：The Non-Permutation Flow-shop Scheduling Problem (NPFSP) allows variable job sequences across machines, offering greater potential for schedule optimization. However, the expanded solution space poses a significant challenge, as existing algorithms often struggle with low efficiency and premature convergence. To mitigate these issues, this study proposes an Improved Max-Min Ant System with Elite Refinement (IMMAS-ER) to minimize the makespan. The first stage integrates the Max-Min Ant System with heuristic initialization and an insertion operator to identify high-quality permutation solutions for building an elite set. The second stage implements a double-machine job-pair swap operator and a greedy decoding mechanism to transform these solutions into superior non-permutation schedules. To reduce computational overhead, the first stage combines Taillard's technique with lower-bound pruning, and the second stage employs a tailored tri-level acceleration strategy that spans different phases of the schedule evaluation. Ablation studies confirm their efficiency: the first stage reduces execution time by 18.18% on average compared to the standard Taillard's method alone, while the tri-level architecture cuts the refinement baseline time by 90.66% without sacrificing solution quality. Extensive experiments on 40 benchmark instances demonstrate that the permutation solutions generated by the first stage achieve lower makespans than those of competing NPFSP algorithms in 30 instances. Through the refinement stage, IMMAS-ER consistently improves all permutation solutions and extends this advantage to 36 instances. These results verify the effectiveness of the designed two-stage framework and its acceleration strategies.