|
|
_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.
|
|
|
|
|
|
## Proposed solution
|
|
|
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](uploads/sched_exponential.lp): 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](uploads/sched_incremental.lp): 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](uploads/main.py) script in Python.
|
|
|
|
|
|
## Experimental evaluation
|
|
|
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.
|
|
|
|
|
|
## Usage
|
|
|
To run the tests, first install [Clingo](https://potassco.org/clingo/) via [Conda](https://anaconda.org/potassco/clingo).
|
|
|
|
|
|
Then, to run for example [instance 5](uploads/experiments/Day1/instance5.lp) 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. |
|
|
\ No newline at end of file |