Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method
This provides efficient scheduling solutions for industrial applications facing increased stochasticity, though it is an incremental improvement over existing methods.
The paper tackled the NP-hard Job Shop Scheduling Problem by proposing JSP-DNN, a deep learning method integrated with Lagrangian duality, which produced high-quality approximations on JSPLIB benchmark instances at negligible computational costs.
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. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.