New Publication in "European Journal of Operational Research"

We are pleased to announce a new publication with the participation of our chair in the "European Journal of Operational Research" entitled "An Asymmetric Traveling Salesman Problem Based Matheuristic Algorithm for Flowshop Group Scheduling Problem". Together with colleagues Xuan He, Qan-Ke Pan (both Shanghai University) and Liang Gao (Huazhong University of Science & Technology, Wuhan), Janis Neufeld presents an innovative matheuristic for the group scheduling problem. By combining a mathematical model and an iterated greedy metaheuristic, as well as integrating problem-specific knowledge, even large instances of this complex problem can be solved efficiently.

The publication can be accessed free of charge until June 12, 2023 via the following link:
https://authors.elsevier.com/c/1gywx1LnJ6pHSV

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.