Szczegóły publikacji
Opis bibliograficzny
Swap Method to improve $N$-NEH+ algorithm / Radosław PUKA, Iwona SKALNA, Bartosz ŁAMASZ // W: ICECET 2022 [Dokument elektroniczny] : international conference on Electrical, Computer and Energy Technologies : 20 - 22 July, 2022, Prague, Czech Republic : [proceedings]. — Wersja do Windows. — Dane tekstowe. — Piscataway : IEEE, cop. 2022. — Dod. ISBN: 978-1-6654-7088-9. — e-ISBN: 978-1-6654-7087-2. — S. [1–6]. — Wymagania systemowe: Adobe Reader. — Bibliogr. s. 5–6, Abstr. — Publikacja dostępna online od: 2022-09-09
Autorzy (3)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 142681 |
|---|---|
| Data dodania do BaDAP | 2022-10-04 |
| Tekst źródłowy | URL |
| DOI | 10.1109/ICECET55527.2022.9872559 |
| Rok publikacji | 2022 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Wydawca | Institute of Electrical and Electronics Engineers (IEEE) |
Abstract
The NEH heuristic is commonly regarded as the best constructive heuristic for solving the permutation flow-shop scheduling problem (PFSP) with the makespan criterion. Since its appearance in 1983, many attempts have been made to improve it. One of the best NEH improvements are the N-NEH and N NEH + construction heuristics that use the N-list technique in the insertion phase of the NEH algorithm. The performance of N-NEH and N-NEH + is however greatly affected by the order of jobs in the input sequence. Therefore, in this paper, we propose the Swap Method (SM) that is a deterministic method for reordering jobs in the input sequence. The SM method swaps jobs by using one of the two proposed swapping strategies, and the modified sequence of jobs is used as the input sequence by N-NEH and N-NEH +. The extensive numerical experiments on the standard Taillard’s and VRF benchmarks show that the proposed Swap Method significantly improves the results (ARPD) of the N-NEH and N-NEH + heuristics while maintaining their deterministic nature and asymptotic time complexity. In some cases, the improvement in results is as high as 1/3.
