Problem Decomposition and Multi-shot ASP Solving for Job-shop Schedul...

Scheduling methods are important for effective production and logistics management, where tasks needto be allocated and performed by limited resources. In particular, the Job-shop Scheduling Problem (JSP)is a well-known and challenging combinatorial optimization problem in which tasks sharing a machineare to be arranged in sequence such that encompassing jobs can be completed as early as possible. Giventhat already moderately sized JSP instances can turn out as highly combinatorial, so that neither optimalschedules nor the runtime to termination of complete optimization methods is known, efficient approachesto approximate good-quality schedules are of interest. In this paper, we propose problem decomposition intotime windows whose operations can be successively scheduled and optimized by means of multi-shot ASPsolving. From a computational perspective, decomposition aims to split highly complex scheduling tasksinto better manageable subproblems with a balanced number of operations, so that good-quality or evenoptimal partial solutions can be reliably found in a small fraction of runtime. Regarding the feasibility andquality of solutions, problem decomposition must respect the precedence of operations within their jobs, andpartial schedules optimized by time windows should yield better global solutions than obtainable in similarruntime on the full problem. We devise and investigate a variety of decomposition strategies in terms ofthe number and size of time windows as well as heuristics for choosing their operations. Moreover, weincorporate time window overlapping and compression techniques into the iterative scheduling process inorder to counteract limitations of window-wise optimization restricted to partial schedules. Our experimentson JSP benchmark sets of several sizes show that successive optimization by multi-shot ASP solving leadsto substantially better schedules within the runtime limit than global optimization on the full problem, wherethe gap increases with the number of operations to schedule.