An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
Abstract
The flowshop group scheduling problem (FGSP) has become a hot research problem owing to its practical applications in modern industry in recent years. The FGSP can be regarded as a combination of two coupled sub-problems. One is the group scheduling sub-problem with sequence-dependent setup times. The other is the job scheduling sub-problem within each group. A mixed integer linear programming model is built for the FGSP with the makespan criterion. Based on the problem-specific knowledge, i.e., the sequence-dependent group setup times are greater than the processing time of jobs, and the number of machines is small, the group scheduling sub-problem is approximated into an asymmetric traveling salesman problem (ATSP). Then, a matheuristic algorithm (MA) is proposed by integrating a branch-and-cut algorithm and an iterated greedy (IG) algorithm, where the branch-and-cut algorithm is used to generate the optimal Hamiltonian circuit for sub-group sequences of a group sequence obtained by the IG. On 405 test instances, the proposed MA performs significantly better than several state-of-the-art algorithms in the literature.
Details
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 597-610 |
Seitenumfang | 14 |
Fachzeitschrift | European journal of operational research |
Jahrgang | 310 |
Ausgabenummer | 2 |
Publikationsstatus | Veröffentlicht - 16 Okt. 2023 |
Peer-Review-Status | Ja |
Externe IDs
Mendeley | 6417ca90-8783-3c8c-9beb-c0b8b3e447a7 |
---|---|
ORCID | /0000-0003-0753-0517/work/144671667 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Asymmetric traveling salesman, Branch-and-cut, Iterated greedy, Matheuristic, Scheduling