Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method

• URL: http://arxiv.org/abs/2110.06365v1
• Date: Tue, 12 Oct 2021 21:15:19 GMT
• Title: Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method
• Authors: James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck
• Abstract summary: The Jobs shop Scheduling Problem (JSP) is a canonical optimization problem that is routinely solved for a variety of industrial purposes. The problem is NP-hard and computationally challenging even for medium-sized instances. This paper explores a deep learning approach to deliver efficient and accurate approximations to the problem.
• Score: 44.4747903763245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. Computational results show that JSP-DNN can produce JSP approximations of high quality at negligible computational costs.

Related papers

• Developing an Algorithm Selector for Green Configuration in Scheduling Problems [0.8151943266391491]
  Job Shop Scheduling Problem (JSP) is central to operations research. Job Shop Scheduling Problem (JSP) is central to operations research.
  arXiv  Detail & Related papers  (2024-09-13T08:58:24Z)
• Learning to Solve Job Shop Scheduling under Uncertainty [1.3002317221601185]
  Job-Shop Scheduling Problem (JSSP) is a optimization problem where tasks need to be scheduled on machines in order to minimize criteria such as makespan or delay. This paper introduces a new approach that leverages Deep Reinforcement Learning (DRL) techniques to search for robust solutions.
  arXiv  Detail & Related papers  (2024-03-04T08:38:55Z)
• Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problem [8.398387430247201]
  Job-shop scheduling problem (JSP) is a mathematical optimization problem widely used in industries like manufacturing. In this paper, we propose a new approach, named residual scheduling, to solving/FJSP. Our approach even reaches zero gap for 49 among 50 instances whose job numbers are more than 150 on 20 machines.
  arXiv  Detail & Related papers  (2023-09-27T09:33:56Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  We propose a multi-head ensemble multi-task learning (MEMTL) approach with a shared backbone and multiple prediction heads (PHs) MEMTL outperforms benchmark methods in both the inference accuracy and mean square error without requiring additional training data.
  arXiv  Detail & Related papers  (2023-09-02T11:01:16Z)
• Flexible Job Shop Scheduling via Dual Attention Network Based Reinforcement Learning [73.19312285906891]
  In flexible job shop scheduling problem (FJSP), operations can be processed on multiple machines, leading to intricate relationships between operations and machines. Recent works have employed deep reinforcement learning (DRL) to learn priority dispatching rules (PDRs) for solving FJSP. This paper presents a novel end-to-end learning framework that weds the merits of self-attention models for deep feature extraction and DRL for scalable decision-making.
  arXiv  Detail & Related papers  (2023-05-09T01:35:48Z)
• A Reinforcement Learning Approach for Scheduling Problems With Improved Generalization Through Order Swapping [0.0]
  JSSP falls into the category of NP-hard COP, in which solving the problem through exhaustive search becomes unfeasible. In recent years, the research towards using DRL to solve COP has gained interest and has shown promising results in terms of solution quality and computational efficiency. In particular, we employ the PPO algorithm that adopts the policy-gradient paradigm that is found to perform well in the constrained dispatching of jobs.
  arXiv  Detail & Related papers  (2023-02-27T16:45:04Z)
• Two-Stage Learning For the Flexible Job Shop Scheduling Problem [18.06058556156014]
  This paper investigates the potential of using a deep learning framework to generate fast and accurate approximations for the Flexible Job-shop Scheduling Problem. In particular, this paper proposes a two-stage learning framework that explicitly models the hierarchical nature of FJSP decisions. Results show that 2SL-FJSP can generate high-quality solutions in milliseconds, outperforming a state-of-the-art reinforcement learning approach.
  arXiv  Detail & Related papers  (2023-01-23T20:23:35Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  We introduce a trainable neural model that learns to map problem instances to a piece-wise linear value function. $nu$-SDDP can significantly reduce problem solving cost without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-12-01T22:55:23Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.