Volltext-Downloads (blau) und Frontdoor-Views (grau)

An algorithm selection approach for the flexible job shop scheduling problem : choosing constraint programming solvers through machine learning

  • Constraint programming solvers are known to perform remarkably well for most scheduling problems. However, when comparing the performance of different available solvers, there is usually no clear winner over all relevant problem instances. This gives rise to the question of how to select a promising solver when knowing the concrete instance to be solved. In this article, we aim to provide first insights into this question for the flexible job shop scheduling problem. We investigate relative performance differences among five constraint programming solvers on problem instances taken from the literature as well as randomly generated problem instances. These solvers include commercial and non-commercial software and represent the state-of-the-art as identified in the relevant literature. We find that two solvers, the IBM ILOG CPLEX CP Optimizer and Google’s OR-Tools, outperform alternative solvers. These two solvers show complementary strengths regarding their ability to determine provably optimal solutions within practically reasonable time limits and their ability to quickly determine high quality feasible solutions across different test instances. Hence, we leverage the resulting performance complementarity by proposing algorithm selection approaches that predict the best solver for a given problem instance based on instance features or parameters. The approaches are based on two machine learning techniques, decision trees and deep neural networks, in various variants. In a computational study, we analyze the performance of the resulting algorithm selection models and show that our approaches outperform the use of a single solver and should thus be considered as a relevant tool by decision makers in practice.

Export metadata

Additional Services

Search Google Scholar


Document Type:Article
Author:Daivd Müller, Marcus G. Müller, Dominik Kress, Erwin PeschORCiD
Center:Center for Advanced Studies in Management (CASiM)
Parent Title (English):European journal of operational research : EJOR
Issue:3 (November 2022)
Date of Publication (online):2022/01/31
First Page:874
Last Page:891
Content Focus:Academic Audience
Peer Reviewed:Yes
Rankings:AJG Ranking / 4
VHB Ranking / A
SJR Ranking / Q1
Licence (German):License LogoUrheberrechtlich geschützt