Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling
- URL: http://arxiv.org/abs/2205.07537v1
- Date: Mon, 16 May 2022 09:33:00 GMT
- Title: Problem Decomposition and Multi-shot ASP Solving for Job-shop Scheduling
- Authors: Mohammed M. S. El-Kholany, Martin Gebser and Konstantin Schekotihin
- Abstract summary: Job-shop Scheduling Problem (JSP) is a well-known and challenging optimization problem.
We propose problem decomposition into time windows whose operations can be successively scheduled and optimized.
Our experiments on benchmark sets of several sizes show that successive optimization by multi-shot ASP solving leads to substantially better schedules within the runtime limit.
- Score: 5.070542698701157
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Job-shop Scheduling Problem (JSP) is a well-known and challenging
combinatorial optimization problem in which tasks sharing a machine are to be
arranged in a sequence such that encompassing jobs can be completed as early as
possible. In this paper, we propose problem decomposition into time windows
whose operations can be successively scheduled and optimized by means of
multi-shot Answer Set Programming (ASP) solving. Decomposition aims to split
highly complex scheduling tasks into better manageable sub-problems with a
balanced number of operations so that good quality or even optimal partial
solutions can be reliably found in a small fraction of runtime. Problem
decomposition must respect the precedence of operations within their jobs and
partial schedules optimized by time windows should yield better global
solutions than obtainable in similar runtime on the entire instance. We devise
and investigate a variety of decomposition strategies in terms of the number
and size of time windows as well as heuristics for choosing their operations.
Moreover, we incorporate time window overlapping and compression techniques
into the iterative scheduling process to counteract window-wise optimization
limitations restricted to partial schedules. Our experiments on JSP benchmark
sets of several sizes show that successive optimization by multi-shot ASP
solving leads to substantially better schedules within the runtime limit than
global optimization on the full problem, where the gap increases with the
number of operations to schedule. While the obtained solution quality still
remains behind a state-of-the-art Constraint Programming system, our multi-shot
solving approach comes closer the larger the instance size, demonstrating good
scalability by problem decomposition.
Related papers
- Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks.
A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form.
This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method.
A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
arXiv Detail & Related papers (2023-12-28T23:15:18Z) - An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling
Problems Based on Constraint Programming [5.070542698701157]
This paper proposes a novel end-to-end approach to solving scheduling problems by means of CP and Reinforcement Learning (RL)
Our approach leverages existing CP solvers to train an agent learning a Priority Dispatching Rule (PDR) that generalizes well to large instances, even from separate datasets.
arXiv Detail & Related papers (2023-06-09T08:24:56Z) - Let the Flows Tell: Solving Graph Combinatorial Optimization Problems
with GFlowNets [86.43523688236077]
Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms.
GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially.
In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
arXiv Detail & Related papers (2023-05-26T15:13:09Z) - Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep
Learning Method [44.4747903763245]
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.
arXiv Detail & Related papers (2021-10-12T21:15:19Z) - Generalized Conflict-directed Search for Optimal Ordering Problems [18.231677739397973]
We present GCDO, a branch-and-bound ordering method that generates an optimal total order of events.
Due to its ability to reason over generalized conflicts, GCDO is much more efficient in finding high-quality total orders than the previous conflict-directed approach CDITO.
arXiv Detail & Related papers (2021-03-31T18:46:48Z) - 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) - Solving a Multi-resource Partial-ordering Flexible Variant of the
Job-shop Scheduling Problem with Hybrid ASP [0.4511923587827302]
We consider a Multi-resource Partial-ordering Flexible Job-shop Scheduling (MPF-JSS) problem.
The resources are flexible and can perform one or more operations depending on their properties.
Experiments conducted on a set of instances extracted from a medium-sized semiconductor fault analysis lab indicate that our approach can find schedules for 87 out of 91 considered real-world instances.
arXiv Detail & Related papers (2021-01-25T15:21:32Z) - 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) - Jump Operator Planning: Goal-Conditioned Policy Ensembles and Zero-Shot
Transfer [71.44215606325005]
We propose a novel framework called Jump-Operator Dynamic Programming for quickly computing solutions within a super-exponential space of sequential sub-goal tasks.
This approach involves controlling over an ensemble of reusable goal-conditioned polices functioning as temporally extended actions.
We then identify classes of objective functions on this subspace whose solutions are invariant to the grounding, resulting in optimal zero-shot transfer.
arXiv Detail & Related papers (2020-07-06T05:13:20Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination.
We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
arXiv Detail & Related papers (2020-05-27T01:10:41Z)
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.