Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion
Since its creation by Nawaz, Enscore, and Ham in 1983, NEH remains the best heuristic method to solve flowshop scheduling problems. In the large body of literature dealing with the application of this heuristic, it can be clearly noted that results differ from one paper to another. In this paper, tw...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-04-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/5/112 |
| _version_ | 1797569249999323136 |
|---|---|
| author | Christophe Sauvey Nathalie Sauer |
| author_facet | Christophe Sauvey Nathalie Sauer |
| author_sort | Christophe Sauvey |
| collection | DOAJ |
| description | Since its creation by Nawaz, Enscore, and Ham in 1983, NEH remains the best heuristic method to solve flowshop scheduling problems. In the large body of literature dealing with the application of this heuristic, it can be clearly noted that results differ from one paper to another. In this paper, two methods are proposed to improve the original NEH, based on the two points in the method where choices must be made, in case of equivalence between two job orders or partial sequences. When an equality occurs in a sorting method, two results are equivalent, but can lead to different final results. In order to propose the first improvement to NEH, the factorial basis decomposition method is introduced, which makes a number computationally correspond to a permutation. This method is very helpful for the first improvement, and allows testing of all the sequencing possibilities for problems counting up to 50 jobs. The second improvement is located where NEH keeps the best partial sequence. Similarly, a list of equivalent partial sequences is kept, rather than only one, to provide the global method a chance of better performance. The results obtained with the successive use of the two methods of improvement present an average improvement of 19% over the already effective results of the original NEH method. |
| first_indexed | 2024-03-10T20:09:16Z |
| format | Article |
| id | doaj.art-2f0a83f9c95946e7916a8e6be16c7460 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T20:09:16Z |
| publishDate | 2020-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-2f0a83f9c95946e7916a8e6be16c74602023-11-19T23:03:49ZengMDPI AGAlgorithms1999-48932020-04-0113511210.3390/a13050112Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan CriterionChristophe Sauvey0Nathalie Sauer1Université de Lorraine, LGIPM, F-57000 Metz, FranceUniversité de Lorraine, LGIPM, F-57000 Metz, FranceSince its creation by Nawaz, Enscore, and Ham in 1983, NEH remains the best heuristic method to solve flowshop scheduling problems. In the large body of literature dealing with the application of this heuristic, it can be clearly noted that results differ from one paper to another. In this paper, two methods are proposed to improve the original NEH, based on the two points in the method where choices must be made, in case of equivalence between two job orders or partial sequences. When an equality occurs in a sorting method, two results are equivalent, but can lead to different final results. In order to propose the first improvement to NEH, the factorial basis decomposition method is introduced, which makes a number computationally correspond to a permutation. This method is very helpful for the first improvement, and allows testing of all the sequencing possibilities for problems counting up to 50 jobs. The second improvement is located where NEH keeps the best partial sequence. Similarly, a list of equivalent partial sequences is kept, rather than only one, to provide the global method a chance of better performance. The results obtained with the successive use of the two methods of improvement present an average improvement of 19% over the already effective results of the original NEH method.https://www.mdpi.com/1999-4893/13/5/112NEHflowshopschedulingheuristicmethodsfactorial basis decomposition |
| spellingShingle | Christophe Sauvey Nathalie Sauer Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion Algorithms NEH flowshop scheduling heuristic methods factorial basis decomposition |
| title | Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion |
| title_full | Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion |
| title_fullStr | Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion |
| title_full_unstemmed | Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion |
| title_short | Two NEH Heuristic Improvements for Flowshop Scheduling Problem with Makespan Criterion |
| title_sort | two neh heuristic improvements for flowshop scheduling problem with makespan criterion |
| topic | NEH flowshop scheduling heuristic methods factorial basis decomposition |
| url | https://www.mdpi.com/1999-4893/13/5/112 |
| work_keys_str_mv | AT christophesauvey twonehheuristicimprovementsforflowshopschedulingproblemwithmakespancriterion AT nathaliesauer twonehheuristicimprovementsforflowshopschedulingproblemwithmakespancriterion |