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

• Autorzy: Puka Radosław , Duda Jerzy , Stawowy Adam

Identyfikatory

DOI

10.24425/mper.2022.140874

• 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.

Słowa kluczowe

EN

job; activity scheduling; scheduling; optimization; permutation flowshop scheduling problem; NEH algorithm; input sequence

• Wydawca: Production Engineering Committee of the Polish Academy of Sciences ; Polish Association for Production Management
• Czasopismo: Management and Production Engineering Review
• Rocznik: 2022
• Tom: Vol. 13, No. 1
• Strony: 32--43
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Puka Radosław

• AGH University of Science and Technology, Faculty of Management, Poland

autor

Duda Jerzy

• AGH University of Science and Technology, Faculty of Management, Poland

autor

Stawowy Adam

• AGH University of Science and Technology, Faculty of Management, 30-067 Kraków, ul. Gramatyka 10

Bibliografia

• 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

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)