Abstract
This paper addresses the mixed no-idle flowshop scheduling problem with flowtime minimization. In a mixed no-idle environment, machines are set in series and some machines do not allow idleness and require continuous processing. We approached a variant of this problem that analyses the total flowtime minimization criterion. As this is a new problem, novel high-performance heuristics and metaheuristics were presented. In order to assess the proposed algorithms, we evaluated well-known heuristics and metaheuristics from similar scheduling problems. Furthermore, we developed a speed-up procedure to increase the efficiency of the proposed methods. The presented algorithms were exhaustively tested in a well-known large benchmark with 1750 problem instances. Our results indicate that the novel heuristics and metaheuristics are computationally efficient and obtain high-quality solutions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Baker KR (1974) Introduction to sequencing and scheduling. Wiley, New Jersey
Baptiste P, Hguny LK (1997) A branch and bound algorithm for the F/no- idle/Cmax. Proceedings of the international conference on industrial engineering and production management, IEPM 97:429–438
Baraz D, Mosheiov G (2008) A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time. Eur J Op Res 184(2):810–813
Chen J, Wang L, Zp Peng (2019) A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling. Swarm and Evolutionary Computation 50:100557 https://doi.org/10.1016/j.swevo.2019.100557, https://www.sciencedirect.com/science/article/pii/S2210650219302652
Cheng CY, Lin SW, Pourhejazy P, Ying KC, Lin YZ (2021) No-Idle Flowshop Scheduling for Energy-Efficient Production: An Improved Optimization Framework. Mathematics 9(12), https://doi.org/10.3390/math9121335, https://www.mdpi.com/2227-7390/9/12/1335
Cura T (2015) An evolutionary algorithm for the permutation flowshop scheduling problem with total tardiness criterion. Int J Op Res 22(3):366–384
Deng G, Gu X (2012) A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion. Computers Op Res 39(9):2152–2160. https://doi.org/10.1016/jcor201110024
Dong X, Huang H, Chen P (2008) An improved NEH-based heuristic for the permutation flowshop problem. Computers Op Res 35(12):3962–3968. https://doi.org/10.1016/j.cor200705005
Dudek RA, Teuton OF (1964) Development of M-stage decision rule for scheduling N jobs through M machines. Op Res 12(3):471–497. https://doi.org/10.1287/opre.12.3.471
Fernandez-Viagas V, Framinan JM (2014) On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers Op Res 45:60–67. https://doi.org/10.1016/jcor201312012
Fernandez-Viagas V, Framinan JM (2015) A new set of high-performing heuristics to minimise flowtime in permutation flowshops. Computers Op Res 53:68–80. https://doi.org/10.1016/jcor201408004
Fernandez-Viagas V, Leisten R, Framinan JM (2016) A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime. Expert Syst Appl 61:290–301. https://doi.org/10.1016/j.eswa.2016.05.040
Fernandez-Viagas V, Ruiz R, Framinan JM (2017) A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation. European Journal of Operational Research 257(3):707–721 https://doi.org/10.1016/j.ejor.2016.09.055, http://www.sciencedirect.com/science/article/pii/S0377221716308074
Fernandez-Viagas V, Valente JMS, Framinan JM (2018) Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness. Expert Systems with Applications 94:58–69 https://doi.org/10.1016/j.eswa.2017.10.050, http://www.sciencedirect.com/science/article/pii/S0957417417307327
Framinan JM, Leisten R (2003) An efficient constructive heuristic for flowtime minimisation in permutation flow shops. Omega 31(4):311–317. https://doi.org/10.1016/S0305048303000471
Framinan JM, Leisten R (2008) Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm. Int J Prod Res 46(22):6479–6498
Framinan JM, Gupta JND, Leisten R (2004) A review and classification of heuristics for permutation flow-shop scheduling with Makespan objective. J Op Res Soc 55(12):1243–1255
Framinan JM, Leisten R, Ruiz-Usano R (2005) Comparison of heuristics for flowtime minimisation in permutation flowshops. Computers & Operations Research 32(5):1237–1254 https://doi.org/10.1016/J.COR.2003.11.002, https://www.sciencedirect.com/science/article/pii/S0305054803003198?via%3Dihub
Garey MR, Johnson DS (1979) Computers and intractability. A Series of Books in the Mathematical Sciences, A guide to the theory of NP-completeness
Graham RL, Lawler EL, Lenstra JK, Kan A (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discr Math 5:287–326. https://doi.org/10.1016/S016750600870356X
Gupta JND, Stafford EF (2006) Flowshop scheduling research after five decades. European Journal of Operational Research 169(3):699–711 https://doi.org/10.1016/j.ejor.2005.02.001, http://www.sciencedirect.com/science/article/pii/S0377221705001372
Johnson SM (1954) Optimal two-and three-stage production schedules with setup times included. Naval Res Log(NRL) 1(1):61–68
Kalczynski PJ, Kamburowski J (2005) A Heuristic for Minimizing the Makespan in No-idle Permutation Flow Shops. Comput Ind Eng 49(1):146–154. https://doi.org/10.1016/j.cie.2005.05.002
Kalczynski PJ, Kamburowski J (2007) On no-wait and no-idle flow shops with makespan criterion. Eur J Op Res 178(3):677–685
Kalczynski PJ, Kamburowski J (2007) On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega 35(1):53–60. https://doi.org/10.1016/jomega200503003
Kalczynski PJ, Kamburowski J (2008) An improved NEH heuristic to minimize makespan in permutation flow shops. Computers Op Res 35(9):3001–3008. https://doi.org/10.1016/jcor200701020
Kalczynski PJ, Kamburowski J (2009) An empirical analysis of the optimality rate of flow shop heuristics. Eur J Op Res 198(1):93–101. https://doi.org/10.1016/jejor200808021
Kalczynski PJ, Kamburowski J (2011) On recent modifications and extensions of the neh heuristic for flow shop sequencing. Foundations Comput Decision Sci 36:18–33
Kamburowski J (2004) More on three-machine no-idle flow shops. Computers Indus Eng 46(3):461–466
Karabulut K (2016) A hybrid iterated greedy algorithm for total tardiness minimization in permutation flowshops. Computers & Industrial Engineering 98:300–307 https://doi.org/10.1016/j.cie.2016.06.012, http://www.sciencedirect.com/science/article/pii/S0360835216302078
Krajewski LJ, King BE, Ritzman LP, Wong DS, Kanban MRP (1987) Shaping the manufacturing environment. Manage Sci 33(1):39–57. https://doi.org/10.1287/mnsc.33.1.39
Li X, Wang Q, Wu C (2009) Efficient composite heuristics for total flowtime minimization in permutation flow shops. Omega 37(1):155–164 https://doi.org/10.1016/j.omega.2006.11.003, http://www.sciencedirect.com/science/article/pii/S0305048306001484
Liu J, Reeves CR (2001) Constructive and composite heuristic solutions to the P sum Ci scheduling problem. Eur J Op Res 132(2):439–452. https://doi.org/10.1016/S0377221700001375
Liu WL, Gong YJ, Chen WN, Liu Z, Wang H, Zhang J (2020) Coordinated charging scheduling of electric vehicles: a mixed-variable differential evolution approach. IEEE Trans Intell Transp Syst 21(12):5094–5109. https://doi.org/10.1109/TITS.2019.2948596
Low C, Yeh JY, Huang KI (2004) A robust simulated annealing heuristic for flow shop scheduling problems. Int J Adv Manuf Technol 23:762–767
Nagano MS, Moccellin JV (2002) A high quality solution constructive heuristic for flow shop sequencing. J Op Res Soc 53(12):1374–1379. https://doi.org/10.1057/palgrave.jors.2601466
Nagano MS, Rossi FL, Tomazella CP (2017) A new efficient heuristic method for minimizing the total tardiness in a no-idle permutation flow shop. Prod Eng 11(4):523–529. https://doi.org/10.1007/s11740-017-0747-2
Nagano MS, Rossi FL, Martarelli NJ (2018) High-performing heuristics to minimize flowtime in no-idle permutation flowshop. Eng Optim 65:1–14. https://doi.org/10.1080/0305215X.2018.1444163
Nagano MS, Rossi FL, Martarelli NJ (2019) High-performing heuristics to minimize flowtime in no-idle permutation flowshop. Eng Optim 51(2):185–198. https://doi.org/10.1080/0305215X.2018.1444163
Narain L, Bagga PC (2005) Flowshop/no-idle scheduling to minimise the mean flowtime. ANZIAM J 47(2):265–275. https://doi.org/10.1017/S1446181100010026
Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11(1):91–95. https://doi.org/10.1016/0305048383900889
Pan QK, Ruiz R (2013) A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers Op Res 40(1):117–128. https://doi.org/10.1016/jcor201205018
Pan QK, Ruiz R (2014) An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega 44:41–50. https://doi.org/10.1016/jomega201310002
Pan QK, Wang L (2008) A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems. Eur J Indus Eng 2(3):279–297. https://doi.org/10.1504/EJIE2008017687
Pan QK, Wang L (2008) No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm. Int J Adv Manuf Technol 39(7):796–807. https://doi.org/10.1007/s0017000712520
Rad SF, Ruiz R, Boroojerdian N (2009) New high performing heuristics for minimizing makespan in permutation flowshops. Omega 37(2):331–345. https://doi.org/10.1016/j.omega200702002
Rajendran C, Ziegler H (1997) An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs. Eur J Op Res 103(1):129–138. https://doi.org/10.1016/S0377-2217(96)00273-1
Ribas I, Companys R, Tort-Martorell X (2010) Comparing three-step heuristics for the permutation flow shop problem. Computers Op Res 37(12):2062–2070. https://doi.org/10.1016/jcor201002006
Ronconi DP (2004) A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics 87(1):39–48 https://doi.org/10.1016/S0925-5273(03)00065-3, http://www.sciencedirect.com/science/article/pii/S0925527303000653
Rossi FL, Nagano MS (2019) Heuristics for the mixed no-idle flowshop with sequence-dependent setup times. J Op Res Soc 25:1–27. https://doi.org/10.1080/01605682.2019.1671149
Rossi FL, Nagano MS (2019) Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion. Expert Systems with Applications 125:40–54 https://doi.org/10.1016/j.eswa.2019.01.057, http://www.sciencedirect.com/science/article/pii/S0957417419300624
Rossi FL, Nagano MS (2020) Heuristics and metaheuristics for the mixed no-idle flowshop with sequence-dependent setup times and total tardiness minimisation. Swarm and Evolutionary Computation 55:100689 https://doi.org/10.1016/j.swevo.2020.100689, http://www.sciencedirect.com/science/article/pii/S221065021930608X
Rossi FL, Nagano MS (2021) Heuristics and iterated greedy algorithms for the distributed mixed no-idle flowshop with sequence-dependent setup times. Computers & Industrial Engineering 157:107337 https://doi.org/10.1016/j.cie.2021.107337, https://www.sciencedirect.com/science/article/pii/S0360835221002412
Rossi FL, Nagano MS, Neto RFT (2016) Evaluation of high performance constructive heuristics for the flow shop with makespan minimization. Int J Adv Manuf Technol 87(1):125–136. https://doi.org/10.1007/s00170-016-8484-9
Ruiz R, Vallada E, Fernández-Martínez C (2009) Scheduling in flowshops with no-idle machines. In: Chakraborty UK (ed) Computational intelligence in flow shop and job shop scheduling, springer. Springer Berlin Heidelberg, Berlin
Saadani NEH, Guinet A, Moalla M (2003) Three stage no-idle flow-shops. Computers Indus Eng 44(3):425–434
Saadani NEH, Guinet A, Moalla M (2005) A travelling salesman approach to solve the F/no-idle/Cmax problem. Eur J Op Res 161(1):11–20. https://doi.org/10.1016/jejor200308030
Shao W, Pi D, Shao Z (2017) Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion. Appl Soft Comput 54:164–182. https://doi.org/10.1016/j.asoc.2017.01.017
Shen J, Wang L, Sy Wang (2015) A bi-population EDA for solving the no-idle permutation flow-shop scheduling problem with the total tardiness criterion. Knowledge-Based Syst 74:167–175
Storer RH, Wu SD, Vaccari R (1992) New search spaces for sequencing problems with application to job shop scheduling. Manage Sci 38(10):1495–1509. https://doi.org/10.1287/mnsc.38.10.1495
Tasgetiren M, Öztop H, Gao L, Pan QK, Li X (2019) A Variable Iterated Local Search Algorithm for Energy-Efficient No-idle Flowshop Scheduling Problem. Procedia Manufacturing 39:1185–1193 https://doi.org/10.1016/j.promfg.2020.01.351, https://www.sciencedirect.com/science/article/pii/S2351978920304182
Tasgetiren MF, Pan QK, Suganthan PN, Buyukdagli O (2013) A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Computers and Operations Research 40(7):1729–1743 https://doi.org/10.1016/jcor201301005, http://www.sciencedirect.com/science/article/pii/S0305054813000130
Tasgetiren MF, Pan QK, Suganthan PN, Oner A (2013) A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Appl Math Modell 37(10):6758–6779
Valente JMS, Alves RAFS (2005) Filtered and recovering beam search algorithms for the early/tardy scheduling problem with no idle time. Computers & Industrial Engineering 48(2):363–375 https://doi.org/10.1016/j.cie.2005.01.020, http://www.sciencedirect.com/science/article/pii/S0360835205000215
Valente JMS, Alves RAFS (2008) Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Computers & Operations Research 35(7):2388–2405 https://doi.org/10.1016/j.cor.2006.11.004, http://www.sciencedirect.com/science/article/pii/S0305054806002966
Vallada E, Ruiz R (2010) Genetic algorithms with path relinking for the minimum tardiness permutation flowshop problem. Omega 38(1):57–67https://doi.org/10.1016/j.omega.2009.04.002, http://www.sciencedirect.com/science/article/pii/S0305048309000322
Zhao F, Zhang L, Zhang Y, Ma W, Zhang C, Song H (2020) A hybrid discrete water wave optimization algorithm for the no-idle flowshop scheduling problem with total tardiness criterion. Expert Systems with Applications 146:113166 https://doi.org/10.1016/j.eswa.2019.113166, https://www.sciencedirect.com/science/article/pii/S0957417419308838
Zhao F, Zhao L, Wang L, Song H (2020) An ensemble discrete differential evolution for the distributed blocking flowshop scheduling with minimizing makespan criterion. Expert Systems with Applications 160:113678 https://doi.org/10.1016/j.eswa.2020.113678, http://www.sciencedirect.com/science/article/pii/S0957417420305029
Zhou S, Xing L, Zheng X, Du N, Wang L, Zhang Q (2021) A self-adaptive differential evolution algorithm for scheduling a single batch-processing machine with arbitrary job sizes and release times. IEEE Trans Cybern 51(3):1430–1442. https://doi.org/10.1109/TCYB.2019.2939219
Zhou Y, Chen H, Zhou G (2014) Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem. Neurocomputing 137:285–292 https://doi.org/10.1016/jneucom201305063, http://www.sciencedirect.com/science/article/pii/S0925231214002604
Acknowledgements
We thank the Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) - Brazil (Grant Number 306075/2017-2, 312585/2021-7 and 430137/2018-4) for supporting this work.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Rossi, F.L., Nagano, M.S. Beam search-based heuristics for the mixed no-idle flowshop with total flowtime criterion. OR Spectrum 44, 1311–1346 (2022). https://doi.org/10.1007/s00291-022-00678-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-022-00678-9