Improving N-NEH+ algorithm by using Starting Point method
Radosław Puka, Bartosz Łamasz, Iwona Skalna
Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 357–361 (2022)
Abstract. 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.
- 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.
- 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.
- M.R. Garey and D.S. Johnson. Computers and intractability, volume 174. W.H. Freeman, San Francisco, 1979.
- 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.
- P.J. Kalczynski and J. Kamburowski. On the NEH heuristic for minimizing the makespan in permutation flow shops. Omega, 35(1):53–60, 2007.
- 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.
- 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.
- 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.
- 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.
- R. Puka, J. Duda, A. Stawowy, and I. Skalna. N-neh+ algorithm for solving permutation flow shop problems. Computers & Operations Research, 132:105296, 2021.
- S.F. Rad, R. Ruiz, and N. Boroojerdian. New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2):331–345, 2009.
- 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.
- R. Ruiz and C. Maroto. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2):479–494, 2005.
- E. Taillard. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1):65–74, 1990.
- E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993. Project Management anf Scheduling.
- 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.