CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Apprendre la sensitivité d’un ordonnancement
en analysant le processus de recherche
Marc-André Ménard, Ph.D. student
marc-andre.menard.2@ulaval.ca
Claude-Guy Quimper, Professeur
Jonathan Gaudreault, Professeur1• Entreprise œuvrant dans le domaine aéronautique et militaire.
• Usinage de haute précision.
• Développe un logiciel Meta4.0 pour aider la production et la gestion
de l’entreprise.

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Machine à commande numérique

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Tourelle dans une machine CNC

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Usinage par extraction

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Plan de production

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

“What if”•En analysant la solution retourné par le solveur, nouspouvons avoir plusieurs questions.
Capacitéde laressource

Tâche 2Tâche 1Tâche 3Tâche 4

MakespanCONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Resource-Constrained Project Scheduling Problem (RCPSP)• Tâches• Temps d’exécution• Quantité de ressources requises• Temps de début• Précédences entre les tâches

Tâche 2CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Tâche 4

Resource-Constrained Project Scheduling Problem (RCPSP)• Ressources• Capacité

Capacitéde laressource

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Resource-Constrained Project Scheduling Problem (RCPSP)
Tâche 1

Tâche 3

Capacitéde laressource

Tâche 2Tâche 4Makespan• Minimiser le temps pour terminer toutes les tâches (Makespan) tout
en respectant les précédences et la capacité des ressources
CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Programmation par contraintes• C’est une technique de résolution de problèmes combinatoires.
• L’utilisateur décrit son problème en utilisant un langage informatique.
• Un solveur résout le problème.
• L’utilisateur n’a pas à dire comment résoudre le problème.

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

4.

qui retourne une solutionSolveur

1.

2.

L’utilisateur se sert descontraintes du solveur

pour construire
un modèle

3.
Modèlequi est soumis
au solveur

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Cataloguede contraintes

AlgorithmesModèle pour le problème RCPSPCONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Recherche dans un arbre

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Génération de clauses• Combiner un solveur de programmation par contraintes avec unsolveur SAT• Problème SAT:
• Permet de prendre avantage de la modélisation haut niveau, de lacompréhension de la structure du problème et la génération declauses des solveur SAT.

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Génération de clauses• Lorsqu’une contrainte filtre ou détecte un conflit, elle doit expliquer laraison à l’aide d’une clauseCONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Génération de clauses• Lorsqu’une contrainte filtre ou détecte un conflit, elle doit expliquer laraison à l’aide d’une clause

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Génération de clauses• Lorsqu’une contrainte filtre ou détecte un conflit, elle doit expliquer laraison à l’aide d’une clause

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Génération de clauses• Lorsqu’une contrainte filtre ou détecte un conflit, elle doit expliquer laraison à l’aide d’une clause

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Apprentissage de clauses• Après la détection d’un conflit, le solveur crée une clause à partir desclauses générées par les contraintes• Évite de faire les mêmes mauvais choix lors de l’exploration d’uneautre partie de l’arbre de recherche

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Apprentissage de clauses

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Apprentissage de clauses

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Apprentissage de clauses

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

“What if”•En analysant la solution retourné par le solveur, nous
pouvons avoir plusieurs questions.
Capacitéde laressource

Tâche 2Tâche 1

Tâche 3Tâche 4Makespan
CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Analyse de sensitivité• Étude de l’impact sur la solution de changer la valeur d’un paramètre
du problème• Peu de méthode existe pour l’analyse de sensitivité en programmation
par contraintes

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Question 1• Prédire l’impact sur le makespan d’augmenter/diminuer la capacité
d’une ressource
Makespan = 10

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Makespan = ?

Question 2• Prédire l’impact sur le makespan de finir une tâche plus tôt

Capacitéde laressource

Tâche 2Tâche 1Tâche 30
CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Tâche 4MakespanStratégie• Machine learning• Forêt aléatoire• S’entraîner sur les instances passées pour répondre aux questions del’instance courante• Features• Features par rapport à la solution• Features par rapport à la recherche• Features par rapport à l’instance du problème

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Génération du jeu de données – changer la capacité d’une ressource

MakespanMakespanC∆C∆ M2-50%3solveur

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

solveurMakespanfeaturessolveurGénération du jeu de données – changer la capacité d’une ressource

Makespan

Makespan
C∆C

∆ M

2-50%

32+50%-1

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Makespanfeatures

Génération du jeu de données – changer la capacité d’une ressource

Makespan

Makespan
C

∆C

∆ M

2-50%

32+50%-1

1+100%-3

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Makespanfeatures

Génération du jeu de données – changer la capacité d’une ressource

Makespan

MakespanC∆C∆ M

2-50%

32+50%-1

1+100%-3

1+300%-4

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

MakespanfeaturesGénération du jeu de données – terminer une tâche plus tôt• Pour chaque instance historique, nous trouvons une solution auproblème original• Pour chaque tâche qui n’a pas de successeur, nous forçons cette tâcheà terminer plus tôt

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Ratio d’utilisation de la ressource
Capacitéde laressource

Makespan
CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Ratio d’utilisation de la ressource
Capacitéde laressource

Makespan
CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Duration pour laquelle la ressource est utilisée à pleine capacité2
Capacitéde laressource

Tâche 2Tâche 1

Tâche 3Tâche 4

Makespan

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Duration pour lequel la ressource est utilisée à pleine capacité
Capacitéde laressource
Tâche 2Tâche 1

Tâche 3Tâche 4Makespan

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Nombre de tâches qui attend pour la disponibilité de la resource pourcommencer
Capacitéde laressource

Tâche 2Tâche 1

Tâche 3Tâche 4Makespan

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Nombre de tâches qui attend pour la disponibilité de la resource pourcommencer
Capacitéde laressource
Tâche 2Tâche 1

Tâche 3Tâche 4Makespan

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• La duration du temps d’attente des tâches qui attend pour ladisponibilité de la ressource pour commencer
Capacitéde laressource

Tâche 2Tâche 1

Tâche 323
CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Tâche 4MakespanFeatures par rapport à la solution• La duration du temps d’attente des tâches qui attend pour ladisponibilité de la ressource pour commencer
Capacitéde laressource

Tâche 3Tâche 2Tâche 1

Tâche 4Makespan

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la solution• Features pour prédire l’impact sur la solution de terminer une tâcheplus tôt• Nombre de tâches terminant avant la tâche qu’on veut devancer• MakespanCONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche• Récolter des informations sur les contraintes représentant lesressources (Cumulative)• Features pour chaque contrainte:• Nombre de fois que la contrainte a filtré le domaine de la variable• La quantité de filtrage

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche
Nombre de filtrage: 0Quantité de filtrage: 0Capacitéde laressourceTâche 2Tâche 1

Tâche 40Tâche 3CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche
Nombre de filtrage: 1
Quantité de filtrage: 3

Capacitéde laressource

Tâche 2Tâche 1Tâche 40Tâche 3CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche
Nombre de filtrage: 1
Quantité de filtrage: 3

Capacitéde laressource

Tâche 2Tâche 10Tâche 4CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0Tâche 3

Features par rapport à la recherche
Nombre de filtrage: 2Quantité de filtrage: 8Capacitéde laressourceTâche 2Tâche 1Tâche 30Tâche 4CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche
Cumulative…

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

faux

Features par rapport à la recherche• Features par rapport au filtrage de la valeur objective
Cumulative…

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche• Features par rapport au filtrage de la valeur objective
Cumulative…

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche• Features par rapport au filtrage de la valeur objective•: ensemble des bornes sur la fonction objectif qui a comme
explication la contrainte• La plus petit valeur:• La plus grande valeur:• La valeur moyenne:

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche• Features pour prédire l’impact de terminer une tâche plus tôt• Features par rapport au domaine de la variable de début de la tâche• Le nombre de fois que le domaine est filtré• Le nombre de valeurs filtrées du domaine

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche
Nombre de fois filtré: 0Nombre de valeurs filtrées: 0Capacitéde laressource

Tâche 2Tâche 10Tâche 4CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Tâche 3Features par rapport à la recherche
Nombre de fois filtré: 1
Nombre de valeurs filtrées: 3

Capacitéde laressource

Tâche 2Tâche 1Tâche 30Tâche 4

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à la recherche
Nombre de fois filtré: 2
Nombre de valeurs filtrées: 5

Capacitéde laressource

Tâche 2Tâche 1Tâche 30Tâche 4CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Features par rapport à l’instance du problème• Le nombre de tâches
• La capacité de la ressource• Features pour prédire l’impact d’augmenter ou diminuer la capacité
d’une ressource• La nouvelle capacité de la ressource• Le ratio d’augmentation/diminution de la capacité de la ressource• Features pour prédire l’impact sur la solution de terminer une tâcheplus tôt• La différence entre le temps de fin de la tâche et la nouvelle date d’échéanceCONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Benchmark• PSPLib [Kolisch et Sprecher, 1997]• Nombre de tâches: 30, 60, 90, 120• 4 ressources• Beaucoup de précédences entre les tâches

• Pack [Carlier et Néron, 2003]• Entre 17 et 32 tâches
• Entre 2 et 5 ressources• Moins de précédences entre les tâches que PSPLibCONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Résultats – changer la capacité de la ressource sur PSPLib• Prédire si oui ou non, il y a un impact sur le makespan de modifier lacapacité de la ressource

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Résultats – changer la capacité de la ressource sur PSPLib• Prédire si oui ou non, il y a un impact sur le makespan de modifier lacapacité de la ressource

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Résultats – changer la capacité de la ressource sur Pack
• Prédire si oui ou non, il y a un impact sur le makespan de modifier lacapacité de la ressource

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Résultats – changer la capacité de la ressource• Prédire la différence sur le makespan en modifiant la capacité de laressource

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Résultats – finir une tâche plus tôt sur PSPLib• Prédire si oui ou non, il y a un impact sur le makespan de finir unetâche plus tôt

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Résultats – finir une tâche plus tôt sur PSPLib• Prédire la différence sur le makespan de finir une tâche plus tôt

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Conclusion• Permet à une compagnie de rapidement vérfier quelles ressources
acheter pour améliorer la production• Permet d’expliquer pourquoi une solution n’est pas satisfiable• Exemple: Cette semaine, nous aurions besoin d’un outil de plus pour avoir cetteordonnancement• Permet à la compagnie de faire une meilleure analyse del’ordonnancement

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0

Travaux futurs• Appliquer cette méthode chez APN• Dans la réalité les problèmes sont différents• Adapter la méthode à la recherche locale à grand voisinage

CONSORTIUM DE RECHERCHE EN INGÉNIERIEDES SYSTÈMES INDUSTRIELS 4.0