OADymPPaC

Outils pour l'Analyse Dynamique et la mise au Point de
Programmes avec Contraintes


Bibliothèque d'exemples,
Exemples classiques

Openshop

Description du Problème :

General scheduling shop problem: A set of n Jobs consisting each of m Tasks must be scheduled on a set of m Machines.

Openshop problem: n=m, and operations for a given Job are sequenced as wanted but only one a time (no overlap of the tasks).
The openshop problem is NP hard as soon as min(n,m) >= 3
No solution known: (6,6)

Intérêt : le problème d'école avec des instances difficiles sinon non résolues.

Sources :
Parameters and variables:
N number of jobs, index I
M number of machines, index J
XIJ starting time of Job I on Machine J  (there are N*M variables XIJ)
Makespan: total duration of the whole work (to minimize)


Data: p(I,J,DIJ): task IJ: duration DIJ of job I on machine J
Example of data for (2,2):

p(1, 1, 5).
p(1, 2, 10).
p(2, 1, 7).
p(2, 2, 8).

upper_bound(30) %max domain size

nbMachines(2).
nbJobs(2).
Two codes by Alex Tessier code-1 GNU-Prolog(without labeling) code-2 GNU-Prolog(with labeling)
Data 22data.pl, 33data.pl, 44data.pl, 66data.pl (partial trace)

Codeine Traces:

Model 1 : (by default code-1, without labeling)
Model 2 :