Input Sequence of Jobs on NEH Algorithm for Permutation Flowshop Scheduling Problem

• Autorzy: Radosław Puka , Jerzy Duda , Adam Stawowy
• Języki publikacji: EN

Abstrakty

EN

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. (original abstract)

Słowa kluczowe

EN

Optimalization; Task scheduling theory; Algorithms

PL

Optymalizacja; Teoria szeregowania zadań; Algorytmy

• Czasopismo: Management and Production Engineering Review
• Rocznik: 2022
• Tom: 13
• Numer: nr 1
• Strony: 32--43

Twórcy

autor

Radosław Puka

• AGH University of Science and Technology, Poland

autor

Jerzy Duda

• AGH University of Science and Technology, Poland

autor

Adam Stawowy

• AGH University of Science and Technology, Poland

Bibliografia

• Dong X., Huang H. and Chen P. (2008), An improved NEH-based heuristic for the permutation flow shop 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 in-sertion tie-breaking rules in heuristics for the per-mutation 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: State- of-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), Dif-ferent initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idletime or flowtime in the static permutation flowshop sequenc-ing 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. 5360. 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 sequenc-ing, 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 se-quencing 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 per-mutation flowshops, Journal of Industrial and Production Engineering, Vol. 30, No. 6, pp. 355-362. DOI: 10.1080/21681015.2013.843597

Identyfikatory

DOI

10.24425/mper.2022.140874