Evaluating procedures in the NEH heuristic for the PFSP - SIST

Laurentys, C.; Nagano, M.

Abstract: The development and assessment of 48 heuristics for the sequence-independent setup time permutation flow shop problem (PFSP-SIST) are presented in this article. This contribution combines four tie-breaking solutions with twelve priority rules for the NEH heuristic fourth and first stage, respectively. Heuristics are evaluated on Ruiz and Allahverdi (2007) benchmark problem instances, that covers small, medium and large-size problems. The popular accelerations of Taillard were used in all tests, which were adapted to the sequence-independent setup time constraint. The aim is to reduce the longest job completion time, which is also referred to as makespan. Computation results show that using different tie-breaking strategies has a greater impact on performance than using different priority rules. The heuristics that presented the best results in relatively low computation time are those that use the FFs tie-breaking strategy procedure to the sequence-independent setup time problem.

How to cite this paper

 Laurentys, C & Nagano, M. (2024). Evaluating procedures in the NEH heuristic for the PFSP - SIST.Journal of Project Management, 9(1), 17-26.

References

Allahverdi, A., Ng, C. T., Cheng, T. E. & Kovalyov, M. Y. (2008). A Survey Of Scheduling Problems With Setup Times Or Costs. European Journal Of Operational Research, 187(3), 985-1032. https://doi.org/10.1016/j.ejor.2006.06.060.
Baker, K. R. (1974). Introduction To Scheduling And Sequencing. Nova York: Wiley.
Belabid, J., Aqil, S. & Karam, A. (2020). Solving Permutation Flow Shop Scheduling Problem with Sequence-Independent Setup Time. Journal of Applied Mathematics, 2020(1), Article ID 7132469. https://doi.org/10.1155/2020/7132469.
Dong, X., Huang, H. & Chen, P. (2008). An Improved NEH-Based Heuristic For The Permutation Flowshop Problem. Computers & Operations Research, 35(12), 3962-3968. https://doi.org/10.1016/j.cor.2007.05.005.
Fernandez-Viagas, V. & Framinan, J. M. (2014). On insertion tie-breaking rules in heuristics for the permutation flow-shop scheduling problem. Computers & Operations Research, 45(1), 60-67. https://doi.org/10.1016/j.cor.2013.12.012.
Fernandez-Viagas, V., Ruiz, R. & Framinan, J. M. (2017). 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. https://doi.org/10.1016/j.ejor.2016.09.055.
Graham, R. L., Lawler, E. L., Lenstra, J. K. & Kan, A. R. (1979). Optimization And Approximation In Deterministic Se-quencing And Scheduling: A Survey. Annals Of Discrete Mathematics, 5(1), 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X.
Johnson, S. M. (1954). Optimal Two- And Three-Stage Production Schedules With Setup Times Included. Naval Re-search Logistics Quarterly, 1(1), 61-68. https://doi.org/10.1002/nav.3800010110.
Kalczynski, P. J. & Kamburowski, J. (2008). An improved NEH heuristic to minimize makespan in permutation flow shops. Computers & Operations Research, 35(9), 3001-3008. https://doi.org/10.1016/j.cor.2007.01.020.
Liu, W., Jin, Y. & Price, M. (2016). A new Nawaz–Enscore–Ham-based heuristic for permutation flow-shop problems with bicriteria of makespan and machine idle time. Engineering Optimization, 48(10), 1808-1822. https://doi.org/10.1080/0305215X.2016.1141202.
Liu, W., Jin, Y. & Price, M. (2017). A new improved NEH heuristic for permutation flowshop scheduling problems. In-ternational Journal of Production Economics, 193(1), 21-30. https://doi.org/10.1016/j.ijpe.2017.06.026.
Maccarthy, B. L. & Liu, J. (1993). Addressing The Gap In Scheduling Research: A Review Of Optimization And Heuris-tic Methods In Production Scheduling. International Journal Of Production Research, 31(1), 59-79. https://doi.org/10.1080/00207549308956713.
Nawaz, M., Ensore Jr., E. & Ham, I. (1982). A Heuristic Algorithm for the m-Machine, n-Job Flow-shop Sequencing Problem. Omega, 11(1), 91-95. https://doi.org/10.1016/0305-0483(83)90088-9.
Reza Hejazi, S. & Saghafian, S. (2005). Flowshop-Scheduling Problems With Makespan Criterion: A Review. Interna-tional Journal Of Production Research, 43(14), 2895-2929. https://doi.org/10.1080/0020754050056417.
Ribas, I., Companys, R. & Tort-Martorell, X. (2010). Comparing three-step heuristics for the permutation flow shop problem. Computers & Operations Research, 37(12), 2062-2070. https://doi.org/10.1016/j.cor.2010.02.006.
Rossi, F. L. & Nagano, M. S. (2019). Heuristics for the mixed no-idle flowshop with sequence-dependent setup times. Expert Systems with Applications, 125(1), 40-54. https://doi.org/10.1016/j.eswa.2019.01.057.
Ruiz, R. & Allahverdi, A. (2007). Some effective heuristics for no-wait flowshops with setup times to minimize total completion time. Annals of Operations Research, 156(1), 143-171. RePEc:spr:annopr:v:156:y:2007:i:1:p:143-171:10.1007/s10479-007-0227-8.
Ruiz, R. & Maroto, C. (2005). A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research, 165(2), 479-494. https://doi.org/10.1016/j.ejor.2004.04.017.
Taillard, E. (1990). Some efficient heuristic methods for the flow shop sequencing problem. European Journal of Oper-ational Research, 47(1), 65-74. https://doi.org/10.1016/0377-2217(90)90090-X.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285. https://doi.org/10.1016/0377-2217(93)90182-M.
Watson, J. P., Barbulescu, R., Whitley, L. D. & Howe, A. E. (2002). Contrasting structured and random permutation flow-shop scheduling problems: search-space topology and algorithm performance. INFORMS Journal on Compu-ting, 14(2), 98-123. https://doi.org/10.1287/ijoc.14.2.98.120.
Wu, Q., Gao, Q., Liu, W. & Cheng, S. (2023). Improved NEH-based heuristic for the blocking flow-shop problem with bicriteria of the makespan and machine utilization. Engineering Optimization, 55(3), 399-415. https://doi.org/10.1080/0305215X.2021.2010727.
Zhang, J., Dao, S. D., Zhang, W., Goh, M., Yu, G., Jin, Y. & Liu, W.. (2023). A new job priority rule for the NEH-based heuristic to minimize makespan in permutation flowshops. Engineering Optimization. https://doi.org/10.1080/0305215X.2022.2085259.