Ordonnancement cumulatif avec
calendriers et heuressupplémentaires
Samuel Cloutier
Claude-Guy Quimper1

Introduction• Dans quel ordre accomplir des tâches ne pouvant pas toutes être faites enmême temps?

• Problème d’ordonnancement• Utile pour : Réfection de navires, plani cation de production manufacturière,
plani cation des tâches d’un robot à deux bras…

fifi2

Plan
• Le problème d’ordonnancement cumulatif• Programmation par contraintes• Les calendriers et les heures supplémentaires• Contrainte Calendar• Contrainte CumulativeOvertime• Résultats

3Ordonnancement cumulatif!!!

Capacitéde ressource

11Tâches

3221211111111

consommationde ressource

56111111113Durée

344t

La programmation par contraintes• Type de programmation déclarative• On dicte des variables, des contraintes, une fonction objectif• Un solveur général résout le problème pour nous

Exécution

5

Fonctionnement d’un solveur
La recherche

Contrainte: y < x
x=1

y=1
dom(x) = {1}dom(y) = {1}dom(x) = {1}dom(y) = {1,2,3}y=2

dom(x) = {1}dom(y) = {2}dom(x) = {1,2}dom(y) = {1,2,3}

y=3

y=1

dom(x) = {1}dom(y) = {3}dom(x) = {2}dom(y) = {1}6x=2
dom(x) = {2}dom(y) = {1,2,3}

Fonctionnement d’un solveur
La recherche - le ltrage• Il est possible de couper des branches sans solutions• Exemple simpliste:x ∈ {1,3}y ∈ {1,2}z ∈ {1,2}x≠yx≠zy≠z• Après avoir branché sur x = 1, on peut détecter directement un con it• Une contrainte globale AllDi erent aurait ltré la valeur 1 sans branchement• Un domaine ltré est dit cohérent (avec divers niveaux de cohérences)
flfi

fffi

fi

7

Fonctionnement d’un solveur
La recherche - les heuristiques de recherche• L’ordre dans lequel l’arbre est exploré a un impact important• Si l’on fait toujours les bons choix, le ltrage est presque obsolète• Dans un contexte d’optimisation, une heuristique trouvant rapidement dessolutions de qualité aidera le Branch-and-Bound• Les heuristiques dépendent grandement du problème• Il n’y a pas de garantie• Le ltrage évite de visiter des branches sans intérêt, les (bons) heuristiques
tentent de nous faire explorer des branches prometteuses.
fifi

8Calendriers et temps supplémentaire• Chaque temps ne permet pas toujours de faire progresser une tâche (parexemple, les ns de semaine)• Le temps supplémentaire est possible pour terminer des tâches plus tôt• Chaque tâche possèdera un calendrier•dénote une heure de travail régulière,
une heure de travail supplémentaire

ZZZ

une heure de fermeture et• Exemple de journée 8-16 avec plage de 4 heures supplémentaires:
ZZZ

ZZZ

ZZZ

ZZZ

ZZZ

ZZZ

ZZZ

ZZZ

9fiZZZ

ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire• Les durées (nouvelle variable) ne sont pas xes et dépendent du contexte• L’utilisation de temps supplémentaire (nouvelle variable) a un coût additionnel• Règles à respecter:• Une tâche ne peut commencer ou se terminer à une heure non travaillée• Le temps travaillé dans la période d’exécution d’une tâche doit être sadurée de travail• On ne peut travailler plus d’heures supplémentaires qu’il y en a dans lapériode d’exécution d’une tâchefi10

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)

Tâche 1, en travaillant 0 heure supplémentaire

0ZZZ

12ZZZ

345ZZZ

67ff

118ZZZ

910 11 12 13ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(1,7,1)

Tâche 1, en travaillant 1 heure supplémentaire

0ZZZ

12

ZZZ

3

45ZZZ

67

ff

128

ZZZ

910 11 12 13
ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(1,7,1)(1,6,2)Tâche 1, en travaillant 2 heuressupplémentaires

0ZZZ

12ZZZ

345ZZZ

67ff

138ZZZ

910 11 12 13ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(3,7,1)(1,7,1)(1,6,2)Tâche 1, en travaillant 1 heure supplémentaire

0ZZZ

12ZZZ

345ZZZ

67ff

148

ZZZ

910 11 12 13ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(3,7,1)(1,7,1)(3,5,2)(1,6,2)Tâche 1, en travaillant 2 heuressupplémentaires

0ZZZ

12ZZZ

345ZZZ

67ff

158ZZZ

910 11 12 13
ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(3,7,1)(1,7,1)(3,5,2)(1,6,2)(4,9,0)Tâche 1, en travaillant 0 heure supplémentaire

0ZZZ

12ZZZ

345ZZZ

67ff168ZZZ

910 11 12 13
ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(3,7,1)(4,6,1)(1,7,1)(3,5,2)(1,6,2)(4,9,0)Tâche 1, en travaillant 1 heure
supplémentaire

0ZZZ

12

ZZZ

3

4

5

ZZZ

67ff

178

ZZZ

910 11 12 13ZZZ

ZZZ

ZZZ

Calendriers et temps supplémentaire
Exemple d’e etValeurs possibles (T, D, S):• Tâche de durée de travail 4(1,9,0)(3,7,1)(4,6,1)(1,7,1)(3,5,2)(6,7,1)(1,6,2)(4,9,0)Tâche 1, en travaillant 1 heure supplémentaire

0ZZZ

12ZZZ

345ZZZ

67ff

18

8ZZZ

910 11 12 13ZZZZZZZZZ

Nos contributions
Contrainte Calendar• Permet de ltrer jusqu’à cohérence de bornes les variables de temps dedébut, durées et surtemps selon les calendriers.
Valeurs possibles (T, D, S):(1,9,0)(3,7,1)(4,6,1)(1,7,1)(3,5,2)(6,7,1)

T : Temps de début(1,6,2)(4,9,0)

D : Durée réelle
S : Surtemps travaillé• Avec la tâche (durée de travail 4) et le calendrier précédent,dom(T) = {0..8}, dom(D) = {4..8}, dom(S) = {0..4} sont ltrés à:
dom(T) = {1..6}

dom(D) = {5..7}

dom(S) = {1..2}
fifi19Structures clefs pour le filtrage• On veut faire le ltrage rapidement• On précalcule quatre vecteurs qui permettront plusieurs calculs en tempsconstantA-10ZZZ

0102ZZZ

031415ZZZ

16720fi

228ZZZ

39334410 11 12 13ZZZZZZZZZStructures clefs pour le filtrage• On veut faire le ltrage rapidement• On précalcule quatre vecteurs qui permettront plusieurs calculs en temps
constant

B0ZZZ

12ZZZ

31445ZZZ

76721fi

9128ZZZ

910 11 12 13ZZZ

ZZZ

ZZZ

Fonctions utilitaires
Compter le temps régulier dans un intervalle

A-1000111224791233342-(-1)=3B0 [ 1ZZZ2ZZZ

3145ZZZ

67228 ) 9ZZZ

10 11 12 13ZZZ

ZZZ

ZZZ

Fonctions utilitaires
Plus grand temps régulier qui n’est pas après un temps donné

A-10ZZZ

0102ZZZ

3011122B

14791245ZZZ

67238ZZZ

39334

10 11 12 13ZZZ

ZZZ

ZZZ

Fonctions utilitaires
Plus grand temps régulier qui n’est pas après un temps donné

A-10ZZZ

0102ZZZ

3011122B

14791245ZZZ

67248ZZZ

3933410 11 12 13ZZZZZZZZZFonctions utilitaires
Trouver la plus petite n d’intervalle possédant une quantité
donnée d’heures régulières
N=3A

-1

000

1

1122791233343+0=3B

ZZZ

1 [ 23ZZZ

445ZZZ6725fi

018ZZZ

910 ) 11 12 13ZZZZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

0ZZZ

1ZZZ

2 [ 3ZZZ

dom(S) = {0..1}

dom(D) = {3..6}

456ZZZ

2678910 11 12 13
ZZZ

ZZZ

Exemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}dom(D) = {3..6}

1. Ajouter la durée de travail

0ZZZ

1ZZZ

2 [ 3ZZZ45)6ZZZ

2778910 11 12 13ZZZZZZ

Exemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

2. Ajuster à la durée minimale

0ZZZ1ZZZ

2 [ 3ZZZ45)6 )7ZZZ

288910 11 12 13ZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

3. Véri er que l’on a su samment de temps régulier
OK0ZZZ2 [ 31ZZZ

ZZZ

456ZZZ)7ffifi298910 11 12 13ZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

4. Corriger la queue de surtemps non travaillée

0ZZZ

1ZZZ

2 [ 3ZZZ

456ZZZOops)7308)9

10 11 12 13ZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

5. Véri er le maximum de D, le minimum de SOopset les têtes/queues non travaillées
OK0ZZZ

1ZZZ

2 [ 3ZZZ

456ZZZfi3178)910 11 12 13ZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

0ZZZ

1ZZZ

2ZZZ

3 [ 4dom(S) = {0..1}dom(D) = {3..6}

56ZZZ

32

78910 11 12 13ZZZZZZ

Exemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

1. Ajouter la durée de travail

0ZZZ

1ZZZ

2ZZZ

3 [ 456ZZZ)7338910 11 12 13ZZZZZZ

Exemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

2. Ajuster à la durée minimale

0ZZZ

1ZZZ

2ZZZ

3 [ 456ZZZ)7348)910 11 12 13ZZZZZZ

Exemple de filtrageBorne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

3. Véri er que l’on a su samment de temps régulier
OK0ZZZ

12ZZZ

ZZZ

3 [ 456ZZZ

ffi

fi

3578)910 11 12 13ZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {0..8}

dom(S) = {0..1}

dom(D) = {3..6}

4. Corriger la queue de surtemps non travailléeOK0ZZZ

1ZZZ

2ZZZ

3 [ 456ZZZ

3678)910 11 12 13ZZZZZZExemple de filtrage
Borne inférieure du temps de début, tâche de durée de travail 2dom(T) = {4..8}{0..8}

dom(S) = {0..1}

dom(D) = {3..6}

5. Véri er le maximum de D, le minimum de S

OK
OKet les têtes/queues non travaillées

0ZZZ

1ZZZ

2ZZZ

3 [ 45fiOK6ZZZ

3778OK)910 11 12 13ZZZ

ZZZ

Filtrage de la Cumulative par Time-Tabling• Pour certaines contraintes, ltrer autant que possible est trop lent.
• On applique donc une cohérence plus faible

Tâche 1123456738fi

08910 11 12 13

Profil de Time-Tabling

Tâche 10123456739

89

10 11 12 13

Profil de Time-Tabling

Tâche 10123456740

8910 11 12 13

Profil de Time-Tabling

Tâche 1012

345674189

10 11 12 13

Profil de Time-Tabling

Tâche 10123456742

8

9

10 11 12 13

Profil de Time-Tabling

Tâche 1012345674389

10 11 12 13

Profil de Time-Tabling

Tâche 1012345674489

10 11 12 13

Profil de Time-Tabling
Tâche 1Tâche 1

012345645

789

10 11 12 13

Filtrage avec Time-Tabling
Tâche 30

123456746

89

10 11 12 13

Filtrage avec Time-Tabling!!!
Tâche 30

123456747

8

9

10 11 12 13

Filtrage avec Time-Tabling
Filtrage du plus petit temps de début
Tâche 30123456748

8

910 11 12 13Nos contributions

Contrainte CumulativeOvertime• Introduit directement l’impact des calendriers dans le ltrage Time-Tabling
Sanscalendrier

Tâche 1dom(D) = {4..7}

Tâche 1dom(S) = {0..1}

Tâche 1

12

ZZZ

3

ZZZ

45

6

7

89

ZZZ

49
fi

ZZZ

dom(T) = {1..5}

Tâche 1Avec
calendrier0

Durée de travail de 4

10 11 12 13
ZZZ

ZZZ

Nos contributions

Contrainte CumulativeOvertime
Durée de travail de 3dom(T) = {1..9}dom(D) = {4..5}
dom(S) = {0..1}
Sans calendrier

0ZZZ

12ZZZ

3ZZZ

4dom(T) = {7..9}!!!

Avec calendrier

56750

8ZZZ

910 11 12 13ZZZZZZ

Résultats
Amélioration des temps de résolution
Minimisation des coûts de surtemps

600

Temps de résolution du modèle
CumulativeOvertime (s)Temps de résolution du modèle
Calendar (s)Minimisation des coûts de surtemps

45030015000150300

45060060045030015000150300

450

Temps de résolution du modèle Calendar (s)Temps de résolution du modèle Décomposition(s)51600

Résultats
Amélioration des solutions
Minimisation des coûts de surtemps

Minimisation des coûts de surtemps
400 000

Meilleure solution du modèle
CumulativeOvertime

Meilleure solution du modèle
Calendar

400 000

300 000

200 000

100 000

00

100 000

200 000

300 000

400 000

Meilleure solution du modèle Décomposition

300 000

200 000

100 000

00

100 000

200 000

300 000

Meilleure solution du modèle Calendar

52

400 000

Conclusion• Implémentation de contraintes gérant les calendriers et le temps
supplémentaire dans les problèmes d’ordonnancement• Amélioration des performances des modèles associés

53