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

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung



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.


Seiten (von - bis)597-610
FachzeitschriftEuropean journal of operational research
PublikationsstatusVeröffentlicht - 16 Okt. 2023

Externe IDs

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



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