Iterated Greedy Algorithm with Problem-specific Knowledge for Multi-objective No-wait Flowshop Scheduling Problem

doi:10.3901/JME.2025.04.344

Abstract

Abstract: The no-waiting flowshop scheduling problem(NWFSP) has a wide range of applications in the manufacturing industry. It is very necessary to develop efficient algorithms for solving NWFSP. Most of the existing literature only considers optimizing one production scheduling objective, but multiple objectives in actual production scenarios often need to be optimized simultaneously. Therefore, we focus on optimizing both the makespan and total flow time simultaneously, and propose an iterated greedy algorithm with problem-specific knowledge(KIG). First, the conflict relationship between the two objectives is verified by converting the total flow time objective in the mixed integer programming model into a constraint. Then, the problem-specific knowledge in each objective is analyzed and obtained. For the makepan objective, NWFSP is transformed into an asymmetric traveling salesman problem, and a dynamic programming algorithm is used to locally optimize the search solution. For the total flow time objective, a dominance criterion guided local search is used to deterministically optimize the partial sequence of the search solution. Finally, the conical scalar weighting method transforms the two optimization objectives into one optimization objective to perform local search efficiently. Extensive experimental results demonstrate the effectiveness of the KIG.

Key words: no-wait flowshop scheduling problem, multi-objective optimization, dynamic programming, domination criterion, iterated greedy

CLC Number:

TP301

HE Xuan, PAN Quanke, GAO Liang. Iterated Greedy Algorithm with Problem-specific Knowledge for Multi-objective No-wait Flowshop Scheduling Problem[J]. Journal of Mechanical Engineering, 2025, 61(4): 344-354.

References

[1] ALLAHVERDI A. A survey of scheduling problems with no-wait in process[J]. European Journal of Operational Research，2016，255(3):665-686.
[2] NAGANO M S，JUNQUEIRA V S V，ROSSI F L. An objective review and perspectives on the permutation flowshop scheduling with no-wait constraint and setup times[J]. IFAC Journal of Systems and Control，2024，29:100279.
[3] UTAMA D M，UMAMY S Z，AL-IMRON C N J R-O R. No-wait flow shop scheduling problem:A systematic literature review and bibliometric analysis[J]. RAIRO-Operations Research，2024，58(2):1281-1313.
[4] LIN S W，YING K C. Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics[J]. Omega，2016，64:115-125.
[5] LEE T E，LEE H Y，LEE S J. Scheduling a wet station for wafer cleaning with multiple job flows and multiple wafer-handling robots[J]. Recent Developments in Modelling and Analysis of Semiconductor Manufacturing，2007，45(3):487-507.
[6] PAN Quanke，FATIH TASGETIREN M，LIANG Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J]. Computers and Operations Research，2008，35(9):2807-2839.
[7] PAN Quanke，WANG Ling，QIAN Bin. A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems[J]. Computers and Operations Research，2009，36(8):2498-2511.
[8] ZHAO Fuqing，HE Xuan，WANG Ling. A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem[J]. IEEE Transactions on Cybernetics，2021，51(11):5291-5303.
[9] HE Xuan，PAN Quanke，GAO Liang，et al. A greedy cooperative co-evolution ary algorithm with problem-specific knowledge for multi-objective flowshop group scheduling problems[J]. IEEE Transactions on Evolutionary Computation，2021，27(3):430-444.
[10] HE Xuan，PAN Quanke，GAO Liang，et al. Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times[J]. Omega，2024，123:102997.
[11] GAREY M R，JOHNSON D S. Computers and intractability:A guide to the theory of NP completeness[M]. San Francisco:W. H. Freeman and Company，1979.
[12] 苏建涛，董绍华，朱诗敏. 多目标混合流水车间机器故障重调度问题研究[J]. 机械工程学报，2024，60(4):438-448. SU Jiantao，DONG Shaohua，ZHU Shimin. Research on machine fault rescheduling problem of multi objective hybrid flow shop based on intelligent manufacturing[J]. Journal of Mechanical Engineering，2024，60(4):438-448.
[13] 吴秀丽，闫晓燕. 基于改进Q学习的可重入混合流水车间绿色动态调度[J]. 机械工程学报，2023，59(13):246-259. WU Xiuli，YAN Xiaoyan. An improved Q learning algorithm to optimize green dynamic scheduling problem in a reentrant hybrid flow shop[J]. Journal of Mechanical Engineering，2023，59(13):246-259.
[14] 牟健慧，段培永，高亮，等. 基于混合遗传算法求解分布式流水车间逆调度问题[J]. 机械工程学报，2022，58(6):295-308. MU Jianhui，DUAN Peiyong，GAO Liang，et al. Hybrid genetic algorithm for distributed flow shop inverse scheduling problem[J]. Journal of Mechanical Engineering，2022，58(6):295-308.
[15] MUCHA M，SVIRIDENKO M. No-wait flowshop scheduling is as hard as asymmetric traveling salesman problem[J]. Mathematics of Operations Research，2016，41(1):247-254.
[16] NAWAZ M，ENSCORE E E，HAM I. A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J]. Omega，1983，11(1):91-95.
[17] YE H，LI W，MIAO E. An effective heuristic for no-wait flow shop production to minimize makespan[J]. Journal of Manufacturing Systems，2016，40:2-7.
[18] YE H，LI W，ABEDINI A. An improved heuristic for no-wait flow shop to minimize makespan[J]. Journal of Manufacturing Systems，2017，44:273-279.
[19] ZHAO Fuqing，HE Xuan，ZHANG Yi，et al. A jigsaw puzzle inspired algorithm for solving large-scale no-wait flow shop scheduling problems[J]. Applied Intelligence，2020，50(1):87-100.
[20] 郭伟飞，雷琦，宋豫川，等. 基于虚拟零部件的零等待约束复杂产品综合调度算法[J]. 机械工程学报，2020，56(4):246-257. GUO Weifei，LEI Qi，SONG Yuchuan，et al. Integrated scheduling algorithm of complex product with no-wait constraint based on virtual component[J]. Journal of Mechanical Engineering，2020，56(4):246-257.
[21] AVCI M. An effective iterated local search algorithm for the distributed no-wait flowshop scheduling problem[J]. Engineering Applications of Artificial Intelligence，2023，120:105921.
[22] 李浩然，高亮，李新宇. 基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J].机械工程学报，2023，59(2):291-306. LI Haoran，GAO Liang，LI Xinyu. Discrete artificial bee colony algorithm for multi-objective distributed heterogeneous no-wait flowshop scheduling problem[J]. Journal of Mechanical Engineering，2023，59(2):291-306.
[23] ZHANG Ziqi，XU Yanxuan，QIAN Bin，et al. An enhanced estimation of distribution algorithm with problem-specific knowledge for distributed no-wait flowshop group scheduling problems[J]. Swarm and Evolutionary Computation，2024，87:101559.
[24] 魏鑫，张泽群，唐敦兵，等. 面向节能的导弹结构件混线生产作业车间多目标调度研究[J]. 机械工程学报，2018，54(9):45-54. WEI Xin，ZHANG Zequn，TANG Dunbing，et al. Energy-saving oriented multi-objective shop floor scheduling for mixed-line production of missile components[J]. Journal of Mechanical Engineering，2018，54(9):45-54.
[25] DU Songlin，ZHOU Wenju，FEI Minrui，et al. Bi-objective scheduling for energy-efficient distributed assembly blocking flow shop[J]. CIRP Annals，2024，73(1):357-360.
[26] ABELEDO H，FUKASAWA R，PESSOA A，et al. The time dependent traveling salesman problem:Polyhedra and algorithm[J]. Mathematical Programming Computation，2013，5(1):27-55.
[27] FISCHETTI M，TOTH P. A polyhedral approach to the asymmetric traveling salesman problem[J]. Management Science，1997，43(11):1520-1536.
[28] CHUNG C S，FLYNN J，KIRCA O. A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems[J]. International Journal of Production Economics，2002，79(3):185-196.
[29] DING J Y，SONG S，ZHANG R，et al. A novel block-shifting simulated annealing algorithm for the no-wait flowshop scheduling problem[C]//Proceedings of the IEEE Congress on Evolutionary Computation(CEC)，May 25-28，2015，Sendai，Japan，NewYork:IEEE，2015:2768-2774.
[30] TAILLARD E. Benchmarks for basic scheduling problems[J]. European Journal of Operational Research，1993，64(2):278-285.
[31] DEB K，PRATAP A，AGARWAL S，et al. A fast and elitist multiobjective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation，2002，6(2):182-197.
[32] WANG Jingjing，WANG Ling. A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop[J]. IEEE Transactions on Systems，Man，and Cybernetics:Systems，2020，50(5):1805-1819.