Deterministic constructive vN-NEH plus algorithm to solve permutation flow shop scheduling problem with makespan criterion

doi:10.1016/j.cor.2023.106473

2024-02-01

PRE

DOI：10.1016/j.cor.2023.106473

原文链接

原文求助

摘要

En 中文

Scheduling jobs in a permutation flow shop (PFS) environment is one of the most studied problems in scheduling theory and practice. In this paper, we propose a new efficient algorithm to solve the permutation flow shop scheduling problem (PFSP) with the makespan criterion. The proposed algorithm, referred to as vN-NEH+, extends the Nawaz-Enscore-Ham (NEH) heuristic by employing the variable-length list (vN-list) of candidate jobs. Extensive numerical experiments on the standard set of benchmarks show that the proposed vN-NEH+ algorithm is one of the most efficient NEH-based deterministic constructive algorithms in terms of trade-off between solution quality and computing time. Moreover, in contrary to existing scheduling methods, vN-NEH+ produces in a single run a set of good quality solutions that can serve as an initial population in population-based metaheuristics for solving PFSPs. Another advantage of vN-NEH+ is that it can work in parallel mode, which is difficult or even impossible with other NEH-based heuristics. In addition to vN-NEH+, we propose a new ART.NEH (Average Relative Time over NEH) indicator to assess the running time of PFSP algorithms. The main advantage of ART.NEH is its hardware/software and instance size independence, which allows an objective and reliable comparison of computational effort of PFSP algorithms. In addition, the idea behind ART.NEH can be easily adopted to reliably assess time complexity of algorithms for solving various other computational problems.

Keyword:

PFSP

Makespan

NEH-based heuristics

vN-list

ART.NEH