Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method
Authors
- James KotarySyracuse University
- Ferdinando FiorettoSyracuse University
- Pascal Van HentenryckGeorgia Institute of Technology
DOI:
https://doi.org/10.1609/aaai.v36i7.20685Keywords:
Machine Learning (ML), Constraint Satisfaction And Optimization (CSO)Abstract
The Jobs Shop Scheduling problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization, to guarantee solution feasibility. The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library and is shown to produce JSP approximations of high quality at negligible computational costs.
Downloads
Published
2022-06-28
How to Cite
Kotary, J., Fioretto, F., & Hentenryck, P. V. (2022). Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method.Proceedings of the AAAI Conference on Artificial Intelligence,36(7), 7239-7246. https://doi.org/10.1609/aaai.v36i7.20685
Issue
Section
AAAI Technical Track on Machine Learning II
