Input Sequence of Jobs on NEH Algorithm for Permutation Flowshop Scheduling Problem
DOI:
https://doi.org/10.24425/mper.2022.140874Abstract
One of the most popular heuristics used to solve the permutation flowshop scheduling problem (PFSP) is the NEH algorithm. The reasons for the NEH popularity are its simplicity, short calculation time, and good-quality approximations of the optimal solution for a wide range of PFSP instances. Since its development, many works have been published analysing various aspects of its performance and proposing its improvements. The NEH algorithm includes, however, one unspecified and unexamined feature that is related to the order of jobs with equal values of total processing time in an initial sequence. We examined this NEH aspect using all instances from Taillard’s and VRF benchmark sets. As presented in this paper, the sorting operation has a significant impact on the results obtained by the NEH algorithm. The reason for this is primarily the input sequence of jobs, but also the sorting algorithm itself. Following this observation, we have proposed two modifications of the original NEH algorithm dealing with sequencing of jobs with equal total processing time. Unfortunately, the simple procedures used did not always give better results than the classical NEH algorithm, which means that the problem of sequencing jobs with equal total processing time needs a smart approach and this is one of the promising directions for further research.References
Dong X., Huang H. and Chen P. (2008), An improved NEH-based heuristic for the permutation flowshop problem, Computers and Operations Research, Vol. 35, No. 12, pp. 3962–3968. DOI: 10.1016/j.cor.2007.05.005
Fernandez-Viagas V. and Framinan J.M. (2014), On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem, Computers and Operations Research, Vol. 45, pp. 60–67. DOI: 10.1016/j.cor.2013.12.012
Fernandez-Viagas V., Ruiz R. and Framinan, J.M. (2017), a new vision of approximate methods for the permutation flowshop to minimise makespan: Stateof-the-art and computational evaluation, European Journal of Operational Research, Vol. 257, No. 3, pp. 707–721. DOI: 10.1016/j.ejor.2016.09.055
Framinan J.M., Leisten R. and Rajendran C. (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, International Journal of Production Research, Vol. 41, No. 1, pp. 121–148. DOI: 10.1080/00207540210161650
Kalczynski P.J. and Kamburowski, J. (2007), On the NEH heuristic for minimizing the makespan in permutation flow shops, Omega, Vol. 35, No. 1, pp. 53-60. DOI: 10.1016/j.omega.2005.03.003
Kalczynski P.J. and Kamburowski J. (2008), An improved NEH heuristic to minimize makespan in permutation flow shops, Computers and Operations Research, Vol. 35, No. 9, pp. 3001–3008. DOI: 10.1016/j.cor.2007.01.020
Kalczynski P.J. and Kamburowski J. (2009), An empirical analysis of the optimality rate of flow shop heuristics, European Journal of Operational Research, Vol. 198, No. 1, pp. 93–101. DOI: 10.1016/j.ejor.2008.08.021
Liu W. Jin Y. and Price M. (2017), A new improved NEH heuristic for permutation flowshop scheduling problems, International Journal of Production Economics, Vol. 193, pp. 21–30. DOI: 10.1016/j.ijpe.2017.06.026
Nagano M.S. and Moccellin, J.V. (2002), A high quality solution constructive heuristic for flow shop sequencing, Journal of the Operational Research Society, Vol. 53, No. 12, pp. 1374–1379. DOI: 10.1016/j.scient.2012.10.034
Nawaz M., Enscore Jr E.E. and Ham I. (1983), A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, Vol. 11, No. 1, pp. 91–95. DOI: 10.1016/0305-0483(83)90088-9
Rad S. F., Ruiz R. and Boroojerdian N. (2009), New high performing heuristics for minimizing makespan in permutation flowshops, Omega, Vol. 37, No. 2, pp. 331–345. DOI: 10.1016/j.omega.2007.02.002
Rossi F.L., Nagano M.S. and 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, Vol. 87, pp. 125–136. DOI: 10.1007/s00170-016-8484-9
Ruiz R. and Maroto C. (2005), A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, Vol. 165, No. 2, pp. 479–494. DOI: 10.1016/j.ejor.2004.04.017
Semančo P. and Modrák V. (2012), A comparison of constructive heuristics with the objective of minimizing makespan in the flow-shop scheduling problem, Acta Polytechnica Hungarica, Vol. 9, No. 5, pp. 177–190.
Taillard E. (1990), Some efficient heuristic methods for the flow shop sequencing problem, European, Journal of Operational Research, Vol. 47, No. 1, pp. 65–74. DOI: 10.1016/0377-2217(90)90090-X
Taillard E. (1993), Benchmarks for basic scheduling problems, European Journal of Operational Research, Vol. 64, No. 2, pp. 278–285. DOI: 10.1016/0377-2217(93)90182-M
Vallada E., Ruiz R. and Framinan J.M. (2015), New hard benchmark for flowshop scheduling problems minimising makespan, European Journal of Operational Research, Vol. 240, No. 3, pp. 666-677. DOI: 10.1016/j.ejor.2014.07.033
Vasiljevic D. and Danilovic M. (2015), Handling ties in heuristics for the permutation flow shop scheduling problem, Journal of Manufacturing Systems, Vol. 35, pp. 1–9. DOI: 10.1016/j.jmsy.2014.11.011
Ying K.C. and Lin S.W. (2013), A high-performing constructive heuristic for minimizing makespan in permutation flowshops, Journal of Industrial and Production Engineering, Vol. 30, No. 6, pp. 355–362. DOI: 10.1080/21681015.2013.843597
