Neuer Beitrag im "European Journal of Operational Research"

Wir freuen uns über eine neue Veröffentlichung unter Beteiligung unseres Lehrstuhl in der Zeitschrift "European Journal of Operational Research" mit dem Titel "An Asymmetric Traveling Salesman Problem Based Matheuristic Algorithm for Flowshop Group Scheduling Problem". Gemeinsam mit den Kollegen Xuan He, Qan-Ke Pan (beide Shanghai University) sowie Liang Gao (Huazhong University of Science & Technology, Wuhan) stellt Janis Neufeld in dem Artikel eine innovative Matheuristic für das Group Scheduling Problem vor. Durch die geschickte Kombination eines mathematischen Modells und einer Iterated Greedy Metaheuristik sowie die Integration von problemspezifischen Wissen können selbst große Instanzen dieses komplexen Problems äußerst effizient gelöst werden.

Die Publikation kann unter folgender Internetadresse bis zum 12. Juni 2023 kostenlos abgerufen werden:
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.