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 de ordonnancement d x27 atelier

Techniques d ? ordonnancement d ? atelier et de fournées basées sur la programmation par contraintes Arnaud Malapert Le septembre à 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 n ques Christelle Guéret Ma? tre-assistante École des Mines de Nantes André Langevin Professeur Polytechnique de Montréal Plan Introduction Ordonnancement d ? atelier Ordonnancement d ? une machine à traitement par fournées Implémentation dans le solveur de contraintes choco Conclusion et perspectives Techniques d ? ordonnancement d ? atelier et de fournées basées sur la programmation par contraintes Introduction Plan Introduction Ordonnancement d ? atelier Ordonnancement d ? une machine à traitement par fournées Implémentation dans le solveur de contraintes choco Conclusion et perspectives 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 n ni de variables Une fonction associe à chaque variable son domaine n ni l ? ensemble discret de valeurs auxquelles elle peut être instanciée Un ensemble n ni de contraintes Une contrainte est une relation logique établie entre di n é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 n ectation est l ? ensemble des domaines courants de toutes les variables Une a n ectation est dite consistante si elle ne viole aucune contrainte Une solution est une a n ectation totale et consistante Optimisation sous contraintes COP CSP fonction objectif f f est souvent modélisée par une variable Techniques d ? ordonnancement d ? atelier et de fournées basées sur la programmation par contraintes Introduction Problèmes d ? ordonnancement Dé n 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 n 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 Techniques d ? ordonnancement d ? atelier et de fournées basées sur la programmation par contraintes Introduction T? che ou activité Dé n 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 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 esti pi ecti lsti