Logo PTI Logo FedCSIS

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

Annals of Computer Science and Information Systems, Volume 35

New measures of algorithms quality for permutation flow-shop scheduling problem

, ,

DOI: http://dx.doi.org/10.15439/2023F7072

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 1107–1111 ()

Full text

Abstract. The permutation flow-shop scheduling problem (PFSP) is an important problem in production industry. The problem has been a subject of many research and various algorithms to solve PFSP have been developed over the years. The newly developed algorithms are usually tested on Taillard and VRF benchmarks and their results are compared using various measures that assess the size of error made by an algorithm and the computation time. In this paper, we propose two new measures to assess the quality of results of algorithms for solving PFSP with the makespan criterion. The first ARD.NEH measure gives similar results as the well known ARPD measure but is robust to updates of the best known solutions of benchmark problems. The second ARID measure is an interval based measure and is able to assess whether the good quality of algorithm results stems from a good behavior this algorithm for a few instances or from a good behavior for most instances. The computational experiments confirm the usefulness of the proposed quality measures.

References

  1. X. Dong, H. Huang, and P. Chen. An improved NEH-based heuristic for the permutation flowshop problem. Computers & Operations Research, 35(12):3962–3968, 2008. Part Special Issue: Telecommunications Network Engineering.
  2. 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.
  3. 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.
  4. M.R. Garey and D.S. Johnson. Computers and intractability, volume 174. W.H. Freeman, San Francisco, 1979.
  5. J. Gmys. Exactly solving hard permutation flowshop scheduling problems on peta-scale gpu-accelerated supercomputers. INFORMS Journal on Computing, 34(5):2502–2522, 2022.
  6. 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.
  7. J.Gmys, M. Mezmaz, N Melab, and D. Tuyttens. A computationally efficient branch-and-bound algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 284(3):814–833, 2020.
  8. 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.
  9. 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.
  10. Bashir Naderi and Rubén Ruiz. The distributed permutation flowshop scheduling problem. Computers & Operations Research, 37:754–768, 04 2010.
  11. 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.
  12. R. Puka, J. Duda, A. Stawowy, and I. Skalna. N-NEH+ algorithm for solving permutation flow shop problem. Computers & Operations Research, 132:105296, 2021.
  13. R. Puka, I. Skalna, J. Duda, and A. Stawowy. vN-neh+ algorithm with modified n-list technique to solve the permutation flow shop problem with makespan criterion, 2022, http://dx.doi.org/10.2139/ssrn.4239708.
  14. Radosław Puka, Iwona Skalna, and Bartosz Łamasz. Swap method to improve n-neh+ algorithm. In 2022 International Conference on Electrical, Computer and Energy Technologies (ICECET), pages 1–6, 2022.
  15. Radosław Puka, Bartosz Łamasz, and Iwona Skalna. Improving n-neh+ algorithm by using starting point method. In 2022 17th Conference on Computer Science and Intelligence Systems (FedCSIS), pages 357–361, 2022.
  16. S.F. Rad, R. Ruiz, and N. Boroojerdian. New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2):331–345, 2009.
  17. 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.
  18. R. Ruiz and C. Maroto. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2):479–494, 2005.
  19. E. Taillard. Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Operational Research, 47(1):65–74, 1990.
  20. E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993. Project Management anf Scheduling.
  21. 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.
  22. Kuo-Ching Ying and Shih-Wei Lin. A high-performing constructive heuristic for minimizing makespan in permutation flowshops. Journal of Industrial and Production Engineering, 30(6):355–362, 2013.