一句话：提出面向作业车间调度的多种时间窗口分解策略与 multi-shot ASP 求解方法，在紧时限内显著提升调度质量。
作业车间调度问题（JSP）是经典且困难的组合优化问题，需为共享同一机器的任务排序，使整体作业尽早完成。本文研究将问题分解为时间窗口，并借助 multi-shot ASP 逐步调度与优化，目标是将复杂调度任务拆成操作数量较均衡、更易处理的子问题，从而在较短时间内稳定找到优质甚至最优的部分解。作者设计并比较多种分解策略，涵盖时间窗口数量、大小及选择操作启发式，并引入窗口重叠与压缩技术以缓解窗口内局部调度带来的优化限制。在不同 JSP 基准集上的实验表明，在严格运行时限下，multi-shot ASP 的连续优化显著优于对完整问题的 single-shot 优化；将高效启发式初始解分解为时间窗口还能进一步提升解质量。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{ElKholanyGS25,
title = {Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling},
author = {Mohammed M. S. El-Kholany and Martin Gebser and Konstantin Schekotihin},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 3},
year = {2025},
doi = {10.46298/lmcs-21(3:16)2025}
}