Authors: Giulia Francescutto, Konstantin Schekotihin, Mohammed M. S. El-Kholany
We consider a variant of the job-shop scheduling problem, in which:
- the operations of the job are partially ordered
- there are multiple resources that have to be used to execute the operations
- each resource is able to execute multiple operations
The goal is to find a feasible schedule that minimizes the total tardiness of a schedule.
We address the problem using Answer Set Programming with Difference Logic and Multi-shot solving. Difference Logic allows one to express time requirements in a compact way; we use multi-shot solving to implement two search strategies to find a tight bound for the tardiness.
The two search approaches can be summarized as follows:
- exponential approach: multi-shot solving is exploited to perform an exponential search to find the tightest bound for the tardiness. Then, the total tardiness is optimized within the bound found.
- incremental approach: the bound for the tardiness is incrementally extended by a fixed value, and at each step, a solver checks if the solution lies within the bound considered.
The search is controlled by a main script in Python.
We also propose a basic ASP encoding with Difference Logic, where the bound is not computed with multi-shot solving, but is computed in advance as simple sum of all the job operations processing times.
Experiments are conducted on a set of instances describing different daily routines occurring in the Failure Analysis Lab of Infineon Technologies, Austria. Ten operational days have been extracted from the historical data, and the resulting instances have been split into sub instances of increasing size to perform the tests.
To run for example instance 5 of Day 1, type:
python main.py exp need.lp sched_exponential.lp experiments/Day1/instance5.lp
for the exponential version, and
python main.py inc need.lp sched_incremental.lp experiments/Day1/instance5.lp
for the incremental one.
To test the single-shot version, type:
clingo-dl scheduling.lp need.lp experiments/Day1/instance5_bound.lp experiments/Day1/instance5.lp