187
Views
8
CrossRef citations to date
0
Altmetric
Original Article

Heuristics for the mixed no-idle flowshop with sequence-dependent setup times

&
Pages 417-443 | Received 12 Feb 2018, Accepted 12 Sep 2019, Published online: 18 Dec 2019

References

  • Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, 246(2), 345–378. doi:10.1016/j.ejor.2015.04.004
  • Allahverdi, A., Gupta, J. N. D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, 27(2), 219–239. doi:10.1016/S0305-0483(98)00042-5
  • Allahverdi, A., Ng, C. T., Cheng, T. C. E., & Kovalyov, M. Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187(3), 985–1032. doi:10.1016/j.ejor.2006.06.060
  • Allahverdi, A., & Soroush, H. (2008). The significance of reducing setup times/setup costs. European Journal of Operational Research, 187(3), 978–984. doi:10.1016/j.ejor.2006.09.010
  • Bagga, P. C. (2003). Minimizing total elapsed time subject to zero total idle time of machines in n×3 flowshop problem. Indian Journal of Pure Applied Mathematics, 34(2), 219–228.
  • Baptiste, P., & Hguny, L. K. (1997). A branch and bound algorithm for the F|no−idle|Cmax. In Proceedings of the international conference on industrial engineering and production management (IEPM97), Lyon, France, 429–438.
  • Baraz, D., & Mosheiov, G. (2008). A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time. European Journal of Operational Research, 184(2), 810–813. doi:10.1016/j.ejor.2006.11.025
  • Benavides, A. J., & Ritt, M. (2016). Two simple and effective heuristics for minimizing the makespan in non-permutation flow shops. Computers & Operations Research, 66, 160–169. doi:10.1016/j.cor.2015.08.001
  • Benkalai, I., Rebaine, D., Gagné, C., & Baptiste, P. (2016). The migrating birds optimization metaheuristic for the permutation flow shop with sequence dependent setup times. IFAC-PapersOnLine, 49(12), 408–413. doi:10.1016/j.ifacol.2016.07.640
  • Benkalai, I., Rebaine, D., Gagné, C., & Baptiste, P. (2017). Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times. International Journal of Production Research, 55(20), 6145–6157. doi:10.1080/00207543.2017.1327732
  • Corwin, B. D., & Esogbue, A. O. (1974). Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach. Naval Research Logistics Quarterly, 21(3), 515–524. doi:10.1002/nav.3800210311
  • Das, S. R., Gupta, J. N. D., & Khumawala, B. M. (1995). A savings index heuristic algorithm for flowshop scheduling with sequence dependent set-up times. The Journal of the Operational Research Society, 46(11), 1365–1373. doi:10.2307/2584570
  • Deng, G., & Gu, X. (2012). A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion. Computers & Operations Research, 39(9), 2152–2160. doi:10.1016/j.cor.2011.10.024
  • Dong, X., Huang, H., & Chen, P. (2008). An improved NEH-based heuristic for the permutation flowshop problem. Computers & Operations Research, 35(12), 3962–3968. doi:10.1016/j.cor.2007.05.005
  • Fernandez-Viagas, V., & Framinan, J. M. (2014). On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers & Operations Research, 45, 60–67. doi:10.1016/j.cor.2013.12.012
  • Fernandez-Viagas, V., & Framinan, J. M. (2015). A new set of high-performing heuristics to minimise flowtime in permutation flowshops. Computers & Operations Research, 53, 68–80. doi:10.1016/j.cor.2014.08.004
  • Fernandez-Viagas, V., & Framinan, J. M. (2017). A beam-search-based constructive heuristic for the PFSP to minimise total flowtime. Computers & Operations Research, 81, 167–177. doi:10.1016/j.cor.2016.12.020
  • Fernandez-Viagas, V., Leisten, R., & Framinan, J. M. (2016). A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime. Expert Systems with Applications, 61, 290–301. doi:10.1016/j.eswa.2016.05.040
  • Fernandez-Viagas, V., Ruiz, R., & Framinan, J. M. (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. doi:10.1016/j.ejor.2016.09.055
  • Framinan, J. M., & Leisten, R. (2003). An efficient constructive heuristic for flowtime minimisation in permutation flow shops. Omega, 31(4), 311–317. doi:10.1016/S0305-0483(03)00047-1
  • Framinan, J. M., & Leisten, R. (2008). Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm. International Journal of Production Research, 46(22), 6479–6498. doi:10.1080/00207540701418960
  • Framinan, J. M., Leisten, R., & Ruiz-Usano, R. (2002). Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation. European Journal of Operational Research, 141(3), 559–569. doi:10.1016/S0377-2217(01)00278-8
  • Gajpal, Y., Rajendran, C., & Ziegler, H. (2006). An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs. The International Journal of Advanced Manufacturing Technology, 30(5/6), 416–424. doi:10.1007/s00170-005-0093-y
  • Goncharov, Y., & Sevastyanov, S. (2009). The flow shop problem with no-idle constraints: A review and approximation. European Journal of Operational Research, 196(2), 450–456. doi:10.1016/j.ejor.2008.03.039
  • Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 287–326. doi:10.1016/S0167-5060(08)70356-X.
  • Gupta, J. N. D. (1972). Heuristic algorithms for multistage flowshop scheduling problem. A I I E Transactions, 4()1, 11–18. doi:10.1080/05695557208974823
  • Gupta, J. N. D., & Darrow, W. P. (1986). The two-machine sequence dependent flowshop scheduling problem. European Journal of Operational Research, 24(3), 439–446. doi:10.1016/0377-2217(86)90037-8
  • Huang, J. D., Liu, J. J., Chen, Q. X., & Mao, N. (2017). Minimizing makespan in a two-stage flow shop with parallel batch-processing machines and re-entrant jobs. Engineering Optimization, 49(6), 1010–1023. doi:10.1080/0305215X.2016.1231307
  • Ince, Y., Karabulut, K., Tasgetiren, M. F., & Pan, Q-K. (2016). A discrete artificial bee colony algorithm for the permutation flowshop scheduling problem with sequence-dependent setup times. In 2016 IEEE congress on Evolutionary computation (CEC) (pp. 3401–3408).
  • Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68. doi:10.1002/nav.3800010110
  • Kalczynski, P. J., & Kamburowski, J. (2005). A heuristic for minimizing the makespan in no-idle permutation flow shops. Computers & Industrial Engineering, 49(1), 146–154. doi:10.1016/j.cie.2005.05.002
  • Kalczynski, P. J., & Kamburowski, J. (2007). On no-wait and no-idle flow shops with makespan criterion. European Journal of Operational Research, 178(3), 677–685. doi:10.1016/j.ejor.2006.01.036
  • Kalczynski, P. J., & Kamburowski, J. (2009). An empirical analysis of the optimality rate of flow shop heuristics. European Journal of Operational Research, 198(1), 93–101. doi:10.1016/j.ejor.2008.08.021
  • Kamburowski, J. (2004). More on three-machine no-idle flow shops. Computers & Industrial Engineering, 46(3), 461–466. doi:10.1016/j.cie.2004.01.008
  • Kendall, G., Bai, R., Błazewicz, J., De Causmaecker, P., Gendreau, M., John, R., … Yee, A. (2016). Good laboratory practice for optimization research. Journal of the Operational Research Society, 67(4), 676–689. doi:10.1057/jors.2015.77
  • Laha, D., & Sarin, S. C. (2009). A heuristic to minimize total flow time in permutation flow shop. Omega, 37(3), 734–739. doi:10.1016/j.omega.2008.05.002
  • Liu, J., & Reeves, C. R. (2001). Constructive and composite heuristic solutions to the P//∑Ci scheduling problem. European Journal of Operational Research, 132()2, 439–452. doi:10.1016/S0377-2217(00)00137-5
  • Liu, W., Jin, Y., & Price, M. (2017). A new improved NEH heuristic for permutation flowshop scheduling problems. International Journal of Production Economics, 193, 21–30. doi:10.1016/j.ijpe.2017.06.026
  • Mirabi, M. (2011). Ant colony optimization technique for the sequence-dependent flowshop scheduling problem. The International Journal of Advanced Manufacturing Technology, 55(1–4), 317–326. doi:10.1007/s00170-010-3037-0
  • Mirabi, M. (2014). A novel hybrid genetic algorithm to solve the sequence-dependent permutation flow-shop scheduling problem. The International Journal of Advanced Manufacturing Technology, 71(1–4), 429–437. doi:10.1007/s00170-013-5489-5
  • Nagano, M. S., & Moccellin, J. A V. (2002). A high quality solution constructive heuristic for flow shop sequencing. Journal of the Operational Research Society, 53(12), 1374–1379. doi:10.1057/palgrave.jors.2601466
  • Nagano, M. S., Rossi, F. L., & Martarelli, N. J. (2018). High-performing heuristics to minimize flowtime in no-idle permutation flowshop. Engineering Optimization, 51(2), 185–198. doi:10.1080/0305215X.2018.1444163
  • Nagano, M. S., Rossi, F. L., & Tomazella, C. P. (2017). A new efficient heuristic method for minimizing the total tardiness in a no-idle permutation flow shop. Production Engineering, 11(4/5), 523–529. doi:10.1007/s11740-017-0747-2
  • Narain, L., & Bagga, P. (2005). Flowshop/no-idle scheduling to minimize total elapsed time. Journal of Global Optimization, 33(3), 349–367. doi:10.1007/s10898-004-1848-y
  • Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91–95. doi:10.1016/0305-0483(83)90088-9
  • Pagnozzi, F., & Stützle, T. (2017). Speeding up local search for the insert neighborhood in the weighted tardiness permutation flowshop problem. Optimization Letters, 11(7), 1283–1292. doi:10.1007/s11590-016-1086-5
  • Pan, Q.-K., & Ruiz, R. (2012). Local search methods for the flowshop scheduling problem with flowtime minimization. European Journal of Operational Research, 222(1), 31–43. doi:10.1016/j.ejor.2012.04.034
  • Pan, Q.-K., & Ruiz, R. (2013). A comprehensive review and evaluation of permutation flowshop heuristics to minimize flowtime. Computers & Operations Research, 40(1), 117–128. doi:10.1016/j.cor.2012.05.018
  • Pan, Q.-K., & Ruiz, R. (2014). An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega, 44 (Supplement C), 41–50. doi:10.1016/j.omega.2013.10.002
  • Pan, Q.-K., & Wang, L. (2008). No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm. The International Journal of Advanced Manufacturing Technology, 39(7/8), 796–807. doi:10.1007/s00170-007-1252-0
  • Pan, Q.-K., & Wang, L. (2008). A novel differential evolution algorithm for no-idle permutation flow-shop scheduling problems. European J. Of Industrial Engineering, 2(3), 279–297. doi:10.1504/EJIE.2008.017687
  • Pan, Q.-K., & Wang, L. (2012). Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega, 40(2), 218–229. doi:10.1016/j.omega.2011.06.002
  • Pessoa, L. S., & Andrade, C. E. (2018). Heuristics for a flowshop scheduling problem with stepwise job objective function. European Journal of Operational Research, 266(3), 950–962. doi:10.1016/j.ejor.2017.10.045
  • Pinedo, M. L. (2016). Scheduling: Theory, algorithms, and systems. Springer.
  • Rad, S. F., Ruiz, R., & Boroojerdian, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2), 331–345. doi:10.1016/j.omega.2007.02.002
  • Ribas, I., Companys, R., & Tort-Martorell, X. (2010). Comparing three-step heuristics for the permutation flow shop problem. Computers & Operations Research, 37(12), 2062–2070. doi:10.1016/j.cor.2010.02.006
  • Ribas, I., Companys, R., & Tort-Martorell, X. (2017). Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Systems with Applications, 74, 41–54. doi:10.1016/j.eswa.2017.01.006
  • Ríos-Mercado, R. Z., & Bard, J. F. (1998a). Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. Computers & Operations Research, 25(5), 351–366. doi:10.1016/S0305-0548(97)00079-8
  • Ríos-Mercado, R. Z., & Bard, J. F. (1998). Heuristics for the flow line problem with setup costs. European Journal of Operational Research, 110(1), 76–98. doi:10.1016/S0377-2217(97)00213-0
  • Ríos-Mercado, R. Z., & Bard, J. F. (1999a). A branch-and-bound algorithm for permutation flow shops with sequence-dependent setup times. IIE Transactions, 31(8), 721–731. doi:10.1080/07408179908969871
  • Ríos-Mercado, R. Z., & Bard, J. F. (1999). An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup times. Journal of Heuristics, 5(1), 53–70. doi:10.1023/A:100969102
  • Ríos-Mercado, R. Z., & Bard, J. F. (2003). The flow shop scheduling polyhedron with setup times. Journal of Combinatorial Optimization, 7(3), 291–318. doi:10.1023/A:1027372722187
  • Rossi, F. L., & Nagano, M. S. (2019). Heuristics for the mixed no-idle flowshop with sequence-dependent setup times and total flowtime criterion. Expert Systems with Applications, 125, 40–54. doi:10.1016/j.eswa.2019.01.057
  • Rossi, F. L., Nagano, M. S., & Neto, R. F. T. (2016). Evaluation of high performance constructive heuristics for the flow shop with makespan minimization. The International Journal of Advanced Manufacturing Technology, 87(1–4), 125–136. doi:10.1007/s00170-016-8484-9
  • Rossi, F. L., Nagano, M. S., & Sagawa, J. K. (2017). An effective constructive heuristic for permutation flow shop scheduling problem with total flow time criterion. The International Journal of Advanced Manufacturing Technology, 90(1–4), 93–107. doi:10.1007/s00170-016-9347-0
  • Ruiz, R., Maroto, C., & Alcaraz, J. (2005). Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics. European Journal of Operational Research, 165(1), 34–54. doi:10.1016/j.ejor.2004.01.022
  • Ruiz, R., Maroto, C., & Alcaraz, J. (2006). Two new robust genetic algorithms for the flowshop scheduling problem. Omega, 34(5), 461–476. doi:10.1016/j.omega.2004.12.006
  • Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–2049. doi:10.1016/j.ejor.2005.12.009
  • Ruiz, R., & Stützle, T. (2008). An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 187(3), 1143–1159. doi:10.1016/j.ejor.2006.07.029
  • Ruiz, R., Vallada, E., & Fernández-Martínez, C. (2009). Scheduling in flowshops with no-idle machines. In U. K. Chakraborty (ed.), Computational intelligence in flow shop and job shop scheduling. Studies in Computational Intelligence. (pp. 21–51). Berlin, Heidelberg: Springer.
  • Saadani, N. E. H., Guinet, A., & Moalla, M. (2003). Three stage no-idle flow-shops. Computers & Industrial Engineering, 44(3), 425–434. doi:10.1016/S0360-8352(02)00217-6
  • Saadani, N. E. H., Guinet, A., & Moalla, M. (2005). A travelling salesman approach to solve the F|no−idle|Cmax problem. European Journal of Operational Research, 161(1), 11–20. doi:10.1016/j.ejor.2003.08.030
  • 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. Applied Soft Computing, 54, 164–182. doi:10.1016/j.asoc.2017.01.017
  • Sheibani, K. (2010). A fuzzy greedy heuristic for permutation flow-shop scheduling. Journal of the Operational Research Society, 61(5), 813–818. doi:10.1057/jors.2008.194
  • Simons, J. V. Jr, (1992). Heuristics in flow shop scheduling with sequence dependent setup times. Omega, 20(2), 215–225. doi:10.1016/0305-0483(92)90075-I
  • Sioud, A., & Gagné, C. (2018). Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times. European Journal of Operational Research, 264(1), 66–73. doi:10.1016/j.ejor.2017.06.027
  • Srikar, B. N., & Ghosh, S. (1986). A MILP model for the n-job, m-stage flowshop with sequence dependent set-up times. International Journal of Production Research, 24(6), 1459–1474. doi:10.1080/00207548608919815
  • Stafford, E. F., Jr., & Tseng, F. T. (1990). On the Srikar-Ghosh MILP model for the iV × M SDST flowshop problem. International Journal of Production Research, 28(10), 1817–1830. doi:10.1080/00207549008942836
  • Stafford, E. F., Jr., & Tseng, F. T. (2002). Two models for a family of flowshop sequencing problems. European Journal of Operational Research, 142(2), 282–293. doi:10.1016/S0377-2217(01)00320-4
  • Stützle, T. (1997). An ant approach to the flow shop problem. In Proceedings of the 6th European Congress on Intelligent Techniques & Soft Computing (EUFIT 98) (pp. 1560–1564). Aachen, Germany: Verlag.
  • Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1), 65–74. doi:10.1016/0377-2217(90)90090-X
  • Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278–285. doi:10.1016/0377-2217(93)90182-M
  • Tasgetiren, M. F., Liang, Y.-C., Sevkli, M., & Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930–1947. doi:10.1016/j.ejor.2005.12.024
  • Tasgetiren, M. F., Pan, Q.-K., Suganthan, P. N., & Buyukdagli, O. (2013). A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Computers & Operations Research, 40(7), 1729–1743. doi:10.1016/j.cor.2013.01.005
  • Tasgetiren, M. F., Pan, Q.-K., Suganthan, P. N., & Oner, A. (2013). A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Applied Mathematical Modelling, 37(10/11), 6758–6779. doi:10.1016/j.apm.2013.02.011
  • Tseng, F. T., Gupta, J. N. D., & Stafford, E. F. Jr, (2006). A penalty-based heuristic algorithm for the permutation flowshop scheduling problem with sequence-dependent set-up times. Journal of the Operational Research Society, 57(5), 541–551. doi:10.1057/palgrave.jors.2602020
  • Tseng, F. T., & Stafford, E. F. Jr, (2001). Two MILP models for the N × M SDST flowshop sequencing problem. International Journal of Production Research, 39(8), 1777–1809. doi:10.1080/00207540010029433
  • Uskup, E., & Smith, S. B. (1975). A branch-and-bound algorithm for two-stage production-sequencing problems. Operations Research, 23(1), 118–136. doi:10.1287/opre.23.1.118
  • Vachajitpan, P. (1982). Job sequencing with continuous machine operation. Computers & Industrial Engineering, 6(3), 255–259. doi:10.1016/0360-8352(82)90004-3
  • Vanchipura, R., & Sridharan, R. (2013). Development and analysis of constructive heuristic algorithms for flow shop scheduling problems with sequence-dependent setup times. The International Journal of Advanced Manufacturing Technology, 67(5–8), 1337–1353. doi:10.1007/s00170-012-4571-8
  • Vanchipura, R., Sridharan, R., & Babu, A. S. (2014). Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time. Journal of Manufacturing Systems, 33(1), 65–75. doi:10.1016/j.jmsy.2013.07.003
  • Wang, Y., Dong, X., Chen, P., & Lin, Y. (2014). Iterated local search algorithms for the sequence-dependent setup times flow shop scheduling problem minimizing makespan. In Z. Wen & T. Li (eds.), Foundations of intelligent systems. Advances in Intelligent Systems and Computing. (vol. 277, pp. 329–338). Berlin, Heidelberg: Springer.
  • Woollam, C. R. (1986). Flowshop with no idle machine time allowed. Computers & Industrial Engineering, 10()1, 69–76. doi:10.1016/0360-8352(86)90028-8
  • Zhou, Y., Chen, H., & Zhou, G. (2014). Invasive weed optimization algorithm for optimization no-idle flow shop scheduling problem. Neurocomputing, 137, 285–292. doi:10.1016/j.neucom.2013.05.063

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.