Improving N-NEH+ algorithm by using Starting Point method

• Autorzy: Puka Radosław , Łamasz Bartosz , Skalna Iwona

Identyfikatory

DOI

10.15439/2022F103

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

The N-NEH+ algorithm is one of the most efficient construction algorithms for solving the permutation flow-shop problem with the makespan criterion. It extends the well-known NEH heuristic with the N-list technique. In this paper, we propose the Starting Point (SP) method that employs a new strategy for using the N-list technique. Extensive numerical experiments on the standard set of Taillard's and VRF benchmarks show that the SP method significantly improves the results of the N-NEH+ algorithm.

Słowa kluczowe

EN

computer science; sociology; benchmark testing; delays; statistics; standard; genetic algorithm

PL

informatyka; socjologia; testy porównawcze; opóźnienia; statystyka; standard; algorytm genetyczny

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 357--361
• Opis fizyczny: Bibliogr. 16 poz., tab., wz.

Twórcy

autor

Puka Radosław

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

autor

Łamasz Bartosz

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

autor

Skalna Iwona

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

Bibliografia

• 1. V. Fernandez-Viagas and J.M. Framinan. On insertion tie-breaking rules in heuristics for the permutation flowshop scheduling problem. Computers & Operations Research, 45:60–67, 2014.
• 2. V. Fernandez-Viagas, R. Ruiz, and J.M. Framinan. 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, 2017.
• 3. M.R. Garey and D.S. Johnson. Computers and intractability, volume 174. W.H. Freeman, San Francisco, 1979.
• 4. R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G.Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In P.L. Hammer, E.L. Johnson, and B.H. Korte, editors, Discrete Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287–326. Elsevier, 1979.
• 5. P.J. Kalczynski and J. Kamburowski. On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega, 35(1):53–60, 2007.
• 6. P.J. Kalczynski and J. Kamburowski. An improved NEH heuristic to minimize makespan in permutation flow shops. Computers & Operations Research, 35(9):3001–3008, 2008. Part Special Issue: Bio-inspired Methods in Combinatorial Optimization.
• 7. P.J. Kalczynski and J. Kamburowski. An empirical analysis of the optimality rate of flow shop heuristics. European Journal of Operational Research, 198(1):93–101, 2009.
• 8. M.S. Nagano and J.V. Moccellin. A high quality solution constructive heuristic for flow shop sequencing. Journal of the Operational Research Society, 53(12):1374–1379, 2002.
• 9. M. Nawaz, E.E. Enscore, and I. Ham. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1):91–95, 1983.
• 10. R. Puka, J. Duda, A. Stawowy, and I. Skalna. N-neh+ algorithm for solving permutation flow shop problems. Computers & Operations Research, 132:105296, 2021.
• 11. S.F. Rad, R. Ruiz, and N. Boroojerdian. New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2):331–345, 2009.
• 12. I. Ribas, R. Companys, and X. Tort-Martorell. Comparing three-step heuristics for the permutation flow shop problem. Computers & Operations Research, 37(12):2062–2070, 2010.
• 13. R. Ruiz and C. Maroto. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2):479–494, 2005.
• 14. E. Taillard. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1):65–74, 1990.
• 15. E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993. Project Management anf Scheduling.
• 16. E. Vallada, R. Ruiz, and J.M. Framinan. New hard benchmark for flowshop scheduling problems minimising makespan. European Journal of Operational Research, 240(3):666–677, 2015.

Uwagi

1. Short article

2. Track 6: 15th International Workshop on Computational Optimization

3. 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).