Proceedings of the 17th Conference on Computer Science and Intelligence Systems

DOI: http://dx.doi.org/10.15439/2022F103

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)

Full text

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.

References

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.