New idle time-based tie-breaking rules in heuristics for the permutation flowshop scheduling problems

Baskar, 2016, Revisiting the NEH algorithm-the power of job insertion technique for optimizing the makespan in permutation flow shop scheduling, Int. J. Ind. Eng. Comput., 7, 353 Baskar, 2012, Effects of dummy machines on makespan in a few classical heuristics using Taillard benchmark problems, Int. J. Mater. Prod. Technol., 45, 145, 10.1504/IJMPT.2012.051349 Baskar, 2013, Optimization of makespan in flow shop scheduling problems using combinational NEH family of heuristics-an analysis, Int. J. Appl. Eng. Res., 8, 1205 Baskar, 2015, Analysis of job insertion technique for different initial sequences in permutation flow shop scheduling problems, Int. J. Enter. Netw.Manag., 6, 153 Benavides, A. J. (2018). A New Tiebreaker in the NEH heuristic for the Permutation Flow Shop Scheduling Problem (No. 440). EasyChair. Birgin, 2020, A filtered beam search method for the m-machine permutation flowshop scheduling problem minimizing the earliness and tardiness penalties and the waiting time of the jobs, Comput. Oper. Res., 114, 104824, 10.1016/j.cor.2019.104824 Campbell, 1970, A heuristic algorithm for the n job, m machine sequencing problem, Manage. Sci., 16, B-630, 10.1287/mnsc.16.10.B630 Chen, S., Pan, Q. K., Hu, X., & Tasgetiren, M. F. (2020, July). NEH-Based heuristics for the distributed blocking flowshop with makespan criterion. In 2020 39th Chinese Control Conference (CCC) (pp. 1710-1715). IEEE. Dannenbring, 1977, An evaluation of flow shop sequencing heuristics, Manage. Sci., 23, 1174, 10.1287/mnsc.23.11.1174 Dong, 2008, An improved NEH-based heuristic for the permutation flowshop problem, Comput. Oper. Res., 35, 3962, 10.1016/j.cor.2007.05.005 Fernandez-Viagas, 2014, On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem, Comput. Oper. Res., 45, 60, 10.1016/j.cor.2013.12.012 Fernandez-Viagas, 2015, NEH-based heuristics for the permutation flowshop scheduling problem to minimise total tardiness, Comput. Oper. Res., 60, 27, 10.1016/j.cor.2015.02.002 Fernandez-Viagas, 2019, A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective, Comput. Oper. Res., 112, 104767, 10.1016/j.cor.2019.104767 Fernandez-Viagas, 2017, A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation, Eur. J. Oper. Res., 257, 707, 10.1016/j.ejor.2016.09.055 Framinan, 2003, Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem, Int. J. Prod. Res., 41, 121, 10.1080/00207540210161650 Fernandez-Viagas, 2020, Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling, Eur. J. Oper. Res., 282, 858, 10.1016/j.ejor.2019.10.017 Gao, 2007, 3348 Gupta, 1979, 363 Hamzadayı, 2020, An effective benders decomposition algorithm for solving the distributed permutation flowshop scheduling problem, Comput. Oper. Res., 123, 105006, 10.1016/j.cor.2020.105006 Hundal, 1988, An extension of Palmer's heuristic for the flow shop scheduling problem, Int. J. Prod. Res., 26, 1119, 10.1080/00207548808947922 Jin, 2007, An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems, Iie Trans., 39, 229, 10.1080/07408170600735553 Johnson, 1954, Optimal two-and three-stage production schedules with setup times included, Naval Res. Logis. Quart., 1, 61, 10.1002/nav.3800010110 Kalczynski, 2007, On the NEH heuristic for minimizing the makespan in permutation flow shops, Omega, 35, 53, 10.1016/j.omega.2005.03.003 Kalczynski, 2008, An improved NEH heuristic to minimize makespan in permutation flow shops, Comput. Oper. Res., 35, 3001, 10.1016/j.cor.2007.01.020 Kalczynski, 2009, An empirical analysis of the optimality rate of flow shop heuristics, Eur. J. Oper. Res., 198, 93, 10.1016/j.ejor.2008.08.021 Koulamas, 1998, A new constructive heuristic for the flowshop scheduling problem, Eur. J. Oper. Res., 105, 66, 10.1016/S0377-2217(97)00027-1 Krajewski, 1987, Kanban, MRP, and shaping the manufacturing environment, Manage. Sci., 33, 39, 10.1287/mnsc.33.1.39 Kurniawati, 2017, Computational study of N-Job M-machine flow shop scheduling problems: SPT, EDD, NEH, NEH-EDD, and modified-NEH algorithms, J. Adv. Manuf. Syst., 16, 375, 10.1142/S0219686717500226 Liou, 2020, Dominance conditions determination based on machine idle times for the permutation flowshop scheduling problem, Comput. Oper. Res., 122, 104964, 10.1016/j.cor.2020.104964 Liu, G., Song, S., Wu, C., 2012. Two techniques to improve the NEH algorithm for flowshop scheduling problems. In: Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence, pp. 41–48. Liu, 2017, A new improved NEH heuristic for permutation flowshop scheduling problems, Int. J. Prod. Econ., 193, 21, 10.1016/j.ijpe.2017.06.026 Maassen, 2019, 1 Nagano, 2002, A high quality solution constructive heuristic for flow shop sequencing, J. Oper. Res. Soc., 53, 1374, 10.1057/palgrave.jors.2601466 Nawaz, 1983, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, 91, 10.1016/0305-0483(83)90088-9 Palmer, 1965, Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum, J. Oper. Res. Soc., 16, 101, 10.1057/jors.1965.8 Pour, 2001, A new heuristic for the n-job, m-machine flow-shop problem, Prod. Plan. Control, 12, 648, 10.1080/09537280152582995 Rad, 2009, New high performing heuristics for minimizing makespan in permutation flowshops, Omega, 37, 331, 10.1016/j.omega.2007.02.002 Rajendran, 2017, Heuristic rules for tie-breaking in the implementation of the NEH heuristic for permutation flow-shop scheduling, Int. J. Oper. Res., 28, 87, 10.1504/IJOR.2017.080597 Riahi, 2019, Constraint guided accelerated search for mixed blocking permutation flowshop scheduling, Comput. Oper. Res., 102, 102, 10.1016/j.cor.2018.10.003 Riahi, 2020, A new iterated greedy algorithm for no-idle permutation flowshop scheduling with the total tardiness criterion, Comput. Oper. Res., 117, 104839, 10.1016/j.cor.2019.104839 Ribas, I., & Mateo, M. (2009, September). Improvement tools for NEH based heuristics on permutation and blocking flow shop scheduling problems. In IFIP International Conference on Advances in Production Management Systems (pp. 33-40). Springer, Berlin, Heidelberg. Rinnooy Kan, A. H. (1976). Machine scheduling problems: classification, complexity, and computations. PhD thesis, University of Amsterdam. Ruiz, 2005, A comprehensive review and evaluation of permutation flowshop heuristics, Eur. J. Oper. Res., 165, 479, 10.1016/j.ejor.2004.04.017 Sauvey, 2020, Two NEH heuristic improvements for flowshop scheduling problem with makespan criterion, Algorithms, 13, 112, 10.3390/a13050112 Suliman, 2000, A two-phase heuristic approach to the permutation flow-shop scheduling problem, Int. J. Prod. Econ., 64, 143, 10.1016/S0925-5273(99)00053-5 Taillard, 1990, Some efficient heuristic methods for the flow shop sequencing problem, Eur. J. Oper. Res., 47, 65, 10.1016/0377-2217(90)90090-X Taillard, 1993, Benchmarks for basic scheduling problems, Eur. J. Oper. Res., 64, 278, 10.1016/0377-2217(93)90182-M Tanaev, V., Gordon, W., & Shafransky, Y. M. (2012). Scheduling theory. Single-stage systems (Vol. 284). Springer Science & Business Media. Vakharia, 1990, Designing a cellular manufacturing system: a materials flow approach based on operation sequences, IIE Trans., 22, 84, 10.1080/07408179008964161 Vallada, 2015, New hard benchmark for flowshop scheduling problems minimising makespan, Eur. J. Oper. Res., 240, 666, 10.1016/j.ejor.2014.07.033 Vasiljevic, 2015, Handling ties in heuristics for the permutation flow shop scheduling problem, J. Manuf. Syst., 35, 1, 10.1016/j.jmsy.2014.11.011 Xiao-ping, L., Yue-xuan, W., & Cheng, W. (2004, June). Heuristic algorithms for large flowshop scheduling problems. In Fifth World Congress on Intelligent Control and Automation (IEEE Cat. No. 04EX788) (Vol. 4, pp. 2999-3003). IEEE. Ying, 2013, A high-performing constructive heuristic for minimizing makespan in permutation flowshops, J. Ind. Prod. Eng., 30, 355 Taillard, E., n.d. Summary of best known lower and upper bounds of Taillard's instances [WWW Document]. URL http://mistic.heig-vd.ch/taillard/ problemes.dir/ordonnancement.dir/flowshop. dir/best_lb_up.txt (accessed 5.22.15).