  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.
