A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion
The No-wait Flowshop Scheduling Problem (NWFSP) has always been a research hotspot because of its importance in various industries. This paper uses a matheuristic approach that combines exact and heuristic algorithms to solve it with the objective to minimize the makespan. Firstly, according to the...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-04-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/14/5/913 |
| _version_ | 1797495132988112896 |
|---|---|
| author | Yu Gao Ziyue Wang Liang Gao Xinyu Li |
| author_facet | Yu Gao Ziyue Wang Liang Gao Xinyu Li |
| author_sort | Yu Gao |
| collection | DOAJ |
| description | The No-wait Flowshop Scheduling Problem (NWFSP) has always been a research hotspot because of its importance in various industries. This paper uses a matheuristic approach that combines exact and heuristic algorithms to solve it with the objective to minimize the makespan. Firstly, according to the symmetry characteristics in NWFSP, a local search method is designed, where the first job and the last job in the symmetrical position remain unchanged, and then, a three-level neighborhood division method and the corresponding rapid evaluation method at each level are given. The two proposed heuristic algorithms are built on them, which can effectively avoid al-ready searched areas, so as to quickly obtain the local optimal solutions, and even directly obtain the optimal solutions for small-scale instances. Secondly, using the equivalence of this problem and the Asymmetric Traveling Salesman Problem (ATSP), an exact method for solving NWFSP is constructed. Importing the results of the heuristics into the model, the efficiency of the Mil-ler-Tucker-Zemlin (MTZ) model for solving small-scale NWFSP can be improved. Thirdly, the matheuristic algorithm is used to test 141 instances of the Tailard and Reeves benchmarks, and each optimal solution can be obtained within 134 s, which verifies the stability and effectiveness of the algorithm. |
| first_indexed | 2024-03-10T01:44:05Z |
| format | Article |
| id | doaj.art-3ed6a1b5a25944559382d4e033f4e294 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T01:44:05Z |
| publishDate | 2022-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-3ed6a1b5a25944559382d4e033f4e2942023-11-23T13:18:08ZengMDPI AGSymmetry2073-89942022-04-0114591310.3390/sym14050913A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan CriterionYu Gao0Ziyue Wang1Liang Gao2Xinyu Li3School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaSchool of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaSchool of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaSchool of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, ChinaThe No-wait Flowshop Scheduling Problem (NWFSP) has always been a research hotspot because of its importance in various industries. This paper uses a matheuristic approach that combines exact and heuristic algorithms to solve it with the objective to minimize the makespan. Firstly, according to the symmetry characteristics in NWFSP, a local search method is designed, where the first job and the last job in the symmetrical position remain unchanged, and then, a three-level neighborhood division method and the corresponding rapid evaluation method at each level are given. The two proposed heuristic algorithms are built on them, which can effectively avoid al-ready searched areas, so as to quickly obtain the local optimal solutions, and even directly obtain the optimal solutions for small-scale instances. Secondly, using the equivalence of this problem and the Asymmetric Traveling Salesman Problem (ATSP), an exact method for solving NWFSP is constructed. Importing the results of the heuristics into the model, the efficiency of the Mil-ler-Tucker-Zemlin (MTZ) model for solving small-scale NWFSP can be improved. Thirdly, the matheuristic algorithm is used to test 141 instances of the Tailard and Reeves benchmarks, and each optimal solution can be obtained within 134 s, which verifies the stability and effectiveness of the algorithm.https://www.mdpi.com/2073-8994/14/5/913heuristicmatheuristicneighborhood searchno-wait |
| spellingShingle | Yu Gao Ziyue Wang Liang Gao Xinyu Li A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion Symmetry heuristic matheuristic neighborhood search no-wait |
| title | A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion |
| title_full | A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion |
| title_fullStr | A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion |
| title_full_unstemmed | A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion |
| title_short | A Matheuristic Approach for the No-Wait Flowshop Scheduling Problem with Makespan Criterion |
| title_sort | matheuristic approach for the no wait flowshop scheduling problem with makespan criterion |
| topic | heuristic matheuristic neighborhood search no-wait |
| url | https://www.mdpi.com/2073-8994/14/5/913 |
| work_keys_str_mv | AT yugao amatheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT ziyuewang amatheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT lianggao amatheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT xinyuli amatheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT yugao matheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT ziyuewang matheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT lianggao matheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion AT xinyuli matheuristicapproachforthenowaitflowshopschedulingproblemwithmakespancriterion |