# Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling

arXiv: https://arxiv.org/abs/2205.07537 · HTML: https://mlsanity.com/paper/2205.07537/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 70 references that are in the map.
- First posted on arXiv 16 May 2022.

## Builds on (most cited first, 9 of 9)

- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [ASP-Core-2 Input Language Format](https://mlsanity.com/paper/1911.04326/) (2019)
- [A Reinforcement Learning Environment For Job-Shop Scheduling](https://mlsanity.com/paper/2104.03760/) (2021)
- [Clingo goes Linear Constraints over Reals and Integers](https://mlsanity.com/paper/1707.04053/) (2017)
- [Answer Set Solving with Bounded Treewidth Revisited](https://mlsanity.com/paper/1702.02890/) (2017)
- [An ASP-based Solution to the Chemotherapy Treatment Scheduling problem](https://mlsanity.com/paper/2108.02637/) (2021)
- [On the Foundations of Grounding in Answer Set Programming](https://mlsanity.com/paper/2108.04769/) (2021)
- [Boosting Binary Optimization via Binary Classification: A Case Study of Job Shop Scheduling](https://mlsanity.com/paper/1808.10813/) (2018)
- [Solving a Multi-resource Partial-ordering Flexible Variant of the Job-shop Scheduling Problem with Hybrid ASP](https://mlsanity.com/paper/2101.10162/) (2021)

## Built on by (most cited first, 3 of 3)

- [Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling](https://mlsanity.com/paper/2305.11969/) (2023)
- [Hybrid ASP-based multi-objective scheduling of semiconductor manufacturing processes (Extended version)](https://mlsanity.com/paper/2307.14799/) (2023)
- [Learning to Solve and Optimize by Evolving Code](https://mlsanity.com/paper/2605.31049/) (2026)

## Abstract (arXiv)

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 investigate problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving. From a computational perspective, decomposition aims to split highly complex scheduling tasks into better manageable subproblems with a balanced number of operations such that good-quality or even optimal partial solutions can be reliably found in a small fraction of runtime. 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 optimization limitations due to the restriction to window-wise partial schedules. Our experiments on different JSP benchmark sets show that successive optimization by multi-shot ASP solving leads to substantially better schedules within tight runtime limits than single-shot optimization on the full problem. In particular, we find that decomposing initial solutions obtained with proficient heuristic methods into time windows leads to improved solution quality.