An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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
Original language | English |
---|---|
Pages (from-to) | 597-610 |
Number of pages | 14 |
Journal | European journal of operational research |
Volume | 310 |
Issue number | 2 |
Publication status | Published - 16 Oct 2023 |
Peer-reviewed | Yes |
External IDs
Mendeley | 6417ca90-8783-3c8c-9beb-c0b8b3e447a7 |
---|---|
ORCID | /0000-0003-0753-0517/work/144671667 |
Keywords
ASJC Scopus subject areas
Keywords
- Asymmetric traveling salesman, Branch-and-cut, Iterated greedy, Matheuristic, Scheduling