An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem

Research output: Contribution to journalResearch articleContributedpeer-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 languageEnglish
Pages (from-to)597-610
Number of pages14
JournalEuropean journal of operational research
Volume310
Issue number2
Publication statusPublished - 16 Oct 2023
Peer-reviewedYes

External IDs

Mendeley 6417ca90-8783-3c8c-9beb-c0b8b3e447a7
ORCID /0000-0003-0753-0517/work/144671667

Keywords

Keywords

  • Asymmetric traveling salesman, Branch-and-cut, Iterated greedy, Matheuristic, Scheduling