Portal de Periódicos da CAPES

N-NEH+ algorithm for solving permutation flow shop problems

2021; Elsevier BV; Volume: 132; Linguagem: Inglês

10.1016/j.cor.2021.105296

1873-765X

Radosław Puka, Jerzy Duda, A. Stawowy, Iwona Skalna,

Optimization and Packing Problems

Permutation flow shop scheduling problem with makespan criterion is known to be NP-hard if the number of machines is greater than two. The most known polynomial complexity algorithm for solving PFSP is the constructive NEH heuristic. In this paper we propose the N-NEH+ algorithm which extends the classical NEH heuristic and which is, to our best knowledge, the first deterministic constructive algorithm that can produce a family of solutions having equal quality. The main idea of the N-NEH+ algorithm is to use a list (called N-list) of N jobs to be candidates for partial sequencing. The results of the extensive numerical experiments confirm that the N-list technique performs well in improving the NEH heuristic. Moreover, the proposed approach can be easily adapted for a multi-core processing environment, which is very difficult with other constructive algorithms. Another advantage of the proposed technique is that it can be used to improve many other algorithms for solving permutation flow shop problems.