TY - JOUR
T1 - A machine learning approach for flow shop scheduling problems with alternative resources, sequence-dependent setup times, and blocking
AU - Benda, Frank
AU - Braune, Roland
AU - Dörner, Karl Franz
AU - Hartl, Richard
N1 - Publisher Copyright:
© 2019, The Author(s).
PY - 2019/12
Y1 - 2019/12
N2 - In proposing a machine learning approach for a flow shop scheduling problem with alternative resources, sequence-dependent setup times, and blocking, this paper seeks to generate a tree-based priority rule in terms of a well-performing decision tree (DT) for dispatching jobs. Furthermore, generating a generic DT and RF that yields competitive results for instance scenarios that structurally differ from the training instances was another goal of our research. The proposed DT relies on high quality solutions, obtained using a constraint programming (CP) formulation. Novel aspects include a unified representation of job sequencing and machine assignment decisions, as well as the generation of random forests (RF) to counteract overfitting behaviour. To show the performance of the proposed approaches, different instance scenarios for two objectives (makespan and total tardiness minimisation) were implemented, based on randomised problem data. The background of this approach is a real-world physical system of an industrial partner that represents a typical shop floor for many production processes, such as furniture and window construction. The results of a comparison of the DT and RF approach with two priority dispatching rules, the original CP solutions and tight lower bounds retrieved from a strengthened mixed-integer programming (MIP) formulation show that the proposed machine learning approach performs well in most instance sets for the makespan objective and in all sets for the total tardiness objective.
AB - In proposing a machine learning approach for a flow shop scheduling problem with alternative resources, sequence-dependent setup times, and blocking, this paper seeks to generate a tree-based priority rule in terms of a well-performing decision tree (DT) for dispatching jobs. Furthermore, generating a generic DT and RF that yields competitive results for instance scenarios that structurally differ from the training instances was another goal of our research. The proposed DT relies on high quality solutions, obtained using a constraint programming (CP) formulation. Novel aspects include a unified representation of job sequencing and machine assignment decisions, as well as the generation of random forests (RF) to counteract overfitting behaviour. To show the performance of the proposed approaches, different instance scenarios for two objectives (makespan and total tardiness minimisation) were implemented, based on randomised problem data. The background of this approach is a real-world physical system of an industrial partner that represents a typical shop floor for many production processes, such as furniture and window construction. The results of a comparison of the DT and RF approach with two priority dispatching rules, the original CP solutions and tight lower bounds retrieved from a strengthened mixed-integer programming (MIP) formulation show that the proposed machine learning approach performs well in most instance sets for the makespan objective and in all sets for the total tardiness objective.
KW - Constraint programming
KW - DISPATCHING RULES
KW - Decision trees
KW - Flow shop scheduling
KW - Machine learning
KW - Random forests
UR - http://www.scopus.com/inward/record.url?scp=85075372519&partnerID=8YFLogxK
U2 - 10.1007/s00291-019-00567-8
DO - 10.1007/s00291-019-00567-8
M3 - Article
VL - 41
SP - 871
EP - 893
JO - OR Spectrum: quantitative approaches in management
JF - OR Spectrum: quantitative approaches in management
SN - 0171-6468
IS - 4
M1 - 47
ER -