Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Techniques d’ordonnancement d’atelier et de fournées basées sur la programmatio

Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes Arnaud Malapert Le 9 septembre 2011 à l’École Nationale Supérieure des Techniques Industrielles et des Mines de Nantes Directeur de thèse : Narendra Jussien, Professeur, École des Mines de Nantes Co-encadrant : Louis-Martin Rousseau, Professeur, École Polytechnique de Montréal Responsables scientiﬁques : Christelle Guéret, Maître-assistante, École des Mines de Nantes André Langevin, Professeur, Polytechnique de Montréal Plan 1 Introduction 2 Ordonnancement d’atelier 3 Ordonnancement d’une machine à traitement par fournées 4 Implémentation dans le solveur de contraintes choco 5 Conclusion et perspectives 2 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Plan 1 Introduction 2 Ordonnancement d’atelier 3 Ordonnancement d’une machine à traitement par fournées 4 Implémentation dans le solveur de contraintes choco 5 Conclusion et perspectives 3 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Programmation par contraintes Problème de satisfaction de contraintes (CSP) Un ensemble ﬁni de variables ; Une fonction associe à chaque variable son domaine ﬁni, l’ensemble discret de valeurs auxquelles elle peut être instanciée ; Un ensemble ﬁni de contraintes. ▶Une contrainte est une relation logique établie entre diﬀérentes variables. ▶Elle restreint les valeurs que ses variables peuvent prendre simultanément. Terminologie Une instanciation assigne une valeur de son domaine à une variable. Une aﬀectation est l’ensemble des domaines courants de toutes les variables. Une aﬀectation est dite consistante si elle ne viole aucune contrainte. Une solution est une aﬀectation totale et consistante. Optimisation sous contraintes : COP = CSP + fonction objectif f f est souvent modélisée par une variable. 4 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Problèmes d’ordonnancement Déﬁnition Organiser un ensemble de tâches soumises à certaines contraintes, et dont l’exécution nécessite des ressources : déterminer leurs dates de démarrage et d’achèvement ; leur attribuer des ressources ; de telle sorte que les contraintes soient respectées. Des problèmes très variés Tâches interruptibles, durées ﬁxes . . . Ressources renouvelables, consommables . . . Contraintes temporelles, fenêtres de temps . . . Critères d’optimalité liés au temps, aux ressources, à d’autres coûts . . . Problèmes traités Optimisation de critères réguliers pour des problèmes d’atelier et de fournées. 5 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Tâche ou activité Déﬁnitions Une tâche Ti est une entité élémentaire de travail localisée dans le temps par une date de début si et une date de ﬁn ei. Sa réalisation est caractérisée par une durée positive pi. Une tâche Ti peut être : ▶interruptible ⇒si + pi ≤ei ; ▶non interruptible ⇒si + pi = ei. Fenêtre de temps d’une tâche Ti : [esti, lcti]. Partie obligatoire d’une tâche non interruptible Ti : [lsti, ecti]. pi esti ecti pi lsti lcti 6 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Contraintes temporelles Contrainte de précédence Une contrainte de précédence entre deux tâches Ti et Tj est représentable par une unique inégalité de potentiel. Déﬁnition : Ti ⪯Tj ⇔ sj −ei ≥0 (Ti précède Tj). Contrainte de disjonction Une contrainte de disjonction entre deux tâches Ti et Tj est satisfaite si les tâches s’exécutent dans des fenêtres de temps disjointes. Déﬁnition : Ti ≃Tj ⇔ (Ti ⪯Tj) ∨(Tj ⪯Ti). Arbitrage : déterminer l’ordre relatif entre les deux tâches. Réiﬁcation : une variable booléenne représente l’arbitrage. 7 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Contraintes de partage de ressource Déﬁnitions 1. Une ressource est un moyen technique ou humain requis pour la réalisation d’une tâche et disponible en quantité limitée. 2. Une ressource disjonctive ne peut exécuter qu’une seule tâche à la fois. Contrainte globale Utiliser l’information sémantique issue de raisonnements sur des sous-pbs. Augmenter l’eﬃcacité du ﬁltrage ou réduire les temps de calcul. 8 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un CSP Déclaration d’un CSP disjunctive (T1, T2, T3) T1 ∈[2, 9] T2 ∈[3, 9] T3 ∈[0, 10] Processus de résolution T1 T2 T3 9 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un CSP Not ﬁrst/not last Déterminer si une tâche Ti peut être ordonnancée avant/après un sous- ensemble de tâches Ω: 1. estimer la date de ﬁn au plus tôt ou de début au plus tard des tâches de Ω; 2. ajuster la fenêtre de temps de la tâche Ti en fonction. Processus de résolution T1 T2 T3 9 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un CSP Not ﬁrst/not last Déterminer si une tâche Ti peut être ordonnancée avant/après un sous- ensemble de tâches Ω: 1. estimer la date de ﬁn au plus tôt ou de début au plus tard des tâches de Ω; 2. ajuster la fenêtre de temps de la tâche Ti en fonction. Processus de résolution T1 T2 T3 9 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un CSP Propagation de contraintes La consistance locale ne peut plus réaliser aucune inférence. Le point ﬁxe est atteint. Processus de résolution T1 T2 T3 9 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un CSP Algorithme backtrack avec standard labelling Sélection de variable : déterminer l’ordre suivant lequel on va les instancier. Sélection de valeur : déterminer la prochaine valeur du domaine à tester. Backtrack : Remettre en cause la dernière décision. Processus de résolution T1 T2 T3 s2 = 4 9 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un CSP Algorithme backtrack avec standard labelling Sélection de variable : déterminer l’ordre suivant lequel on va les instancier. Sélection de valeur : déterminer la prochaine valeur du domaine à tester. Backtrack : Remettre en cause la dernière décision. Processus de résolution T1 T2 T3 s2 = 4 s2 ̸= 4 9 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ Introduction Résolution d’un COP Procédures d’optimisation : résolution d’une série de CSPs. bottom-up incrémente la borne inférieure lb lorsque le CSP où obj = lb est insatisﬁable jusqu’à ce qu’une solution optimale soit trouvée. top-down résout le CSP où obj < ub jusqu’à ce que le sous-problème devienne insatisﬁable. variantes dichotomiques, incomplètes . . . 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 4 2 10 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ GP04-01 - Cmax=1281 0 100 200 300 400 500 600 700 800 900 1 000 1 100 1 200 1 300 Time M_0 M_1 M_2 M_3 Resources T_3_0 T_3_1 T_3_2 T_2_2 T_2_3 T_1_1 T_1_2 T_1_3 T_0_0 T_0_3 Ordonnancement d’atelier Plan 1 Introduction 2 Ordonnancement d’atelier 3 Ordonnancement d’une machine à traitement par fournées 4 Implémentation dans le solveur de contraintes choco 5 Conclusion et perspectives 11 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ GP04-01 - Cmax=1281 0 100 200 300 400 500 600 700 800 900 1 000 1 100 1 200 1 300 Time M_0 M_1 M_2 M_3 Resources T_3_0 T_3_1 T_3_2 T_2_2 T_2_3 T_1_1 T_1_2 T_1_3 T_0_0 T_0_3 Ordonnancement d’atelier Déﬁnition des problèmes de base Structure d’un atelier Une pièce doit être usinée ou assemblée sur diﬀérentes machines. Les tâches sont regroupées en n lots constitués chacun de m tâches à exécuter sur m machines distinctes. Chaque machine ne peut exécuter qu’une tâche à la fois. Séquencement des lots ﬂow-shop : l’ordre est ﬁxé et commun à tous les lots. job-shop : l’ordre est ﬁxé, mais propre à chaque lot. open-shop : le séquencement des tâches des lots n’est pas imposé. Minimisation du délai total (Cmax). O//Cmax, J//Cmax et F//Cmax sont NP-diﬃciles pour m ≥3. Sous-ensembles dominants pour d’autres critères réguliers. Calcul des chemins critiques et des goulots d’étranglement. 12 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la programmation par contraintes ▲ GP04-01 - Cmax=1281 0 100 200 300 400 500 600 700 800 900 1 000 1 100 1 200 1 300 Time M_0 M_1 M_2 M_3 Resources T_3_0 T_3_1 T_3_2 T_2_2 T_2_3 T_1_1 T_1_2 T_1_3 T_0_0 T_0_3 Ordonnancement d’atelier Ordonnancement optimal d’un open-shop GP04-01 - Cmax=1281 0 100 200 300 400 500 600 700 800 900 1 000 1 100 1 200 1 300 Time M_0 M_1 M_2 M_3 Resources T_3_0 T_3_1 T_3_2 T_2_2 T_2_3 T_1_1 T_1_2 T_1_3 T_0_0 T_0_3 13 / 51 Techniques d’ordonnancement d’atelier et de fournées basées sur la uploads/Voyage/ techniques-de-ordonnancement-d-x27-atelier.pdf