Item – Theses Canada

​
OCLC number
1132126822
Link(s) to full text
LAC copy
Author
Moisan, Thierry,
Title
Minimisation des perturbations et parallélisation pour la planification et l'ordonnancement
Degree
Philosophiæ doctor (Ph. D.) -- Université Laval, 2016
Publisher
Québec : Université Laval, [2016]
Description
1 ressource en ligne (xix, 157 pages) :illustrations en partie en couleur, fichier PDF (2,54 Mo)
Notes
Titre de l'écran-titre (visionné le 4 mars 2016).
Bibliographie : pages 145-157.
Abstract
Nous étudions dans cette thèse deux approches réduisant le temps de traitement nécessaire pour résoudre des problèmes de planification et d'ordonnancement dans un contexte de programmation par contraintes. Nous avons expérimenté avec plusieurs milliers de processeurs afin de résoudre le problème de planification et d'ordonnancement des opérations de rabotage du bois d'oeuvre. Ces problèmes sont d'une grande importance pour les entreprises, car ils permettent de mieux gérer leur production et d'économiser des coûts reliés à leurs opérations. La première approche consiste à effectuer une parallélisation de l'algorithme de résolution du problème. Nous proposons une nouvelle technique de parallélisation (nommée PDS) des stratégies de recherche atteignant quatre buts : le respect de l'ordre de visite des noeuds de l'arbre de recherche tel que défini par l'algorithme séquentiel, l'équilibre de la charge de travail entre les processeurs, la robustesse aux défaillances matérielles et l'absence de communications entre les processeurs durant le traitement. Nous appliquons cette technique pour paralléliser la stratégie de recherche Limited Discrepancy-based Search (LDS) pour ainsi obtenir Parallel Limited Discrepancy-Based Search (PLDS). Par la suite, nous démontrons qu'il est possible de généraliser cette technique en l'appliquant à deux autres stratégies de recherche : Depth-Bounded discrepancy Search (DDS) et Depth-First Search (DFS). Nous obtenons, respectivement, les stratégies Parallel Discrepancy-based Search (PDDS) et Parallel Depth-First Search (PDFS). Les algorithmes parallèles ainsi obtenus créent un partage intrinsèque de la charge de travail : la différence de charge de travail entre les processeurs est bornée lorsqu'une branche de l'arbre de recherche est coupée. En utilisant des jeux de données de partenaires industriels, nous avons pu améliorer les meilleures solutions connues. Avec la deuxième approche, nous avons élaboré une méthode pour minimiser les changements effectués à un plan de production existant lorsque de nouvelles informations, telles que des commandes additionnelles, sont prises en compte. Replanifier entièrement les activités de production peut mener à l'obtention d'un plan de production très différent qui mène à des coûts additionnels et des pertes de temps pour les entreprises. Nous étudions les perturbations causéees par la replanification à l'aide de trois métriques de distances entre deux plans de production : la distance de Hamming, la distance d'édition et la distance de Damerau-Levenshtein. Nous proposons trois modèles mathématiques permettant de minimiser ces perturbations en incluant chacune de ces métriques comme fonction objectif au moment de la replanification. Nous appliquons cette approche au problème de planification et ordonnancement des opérations de finition du bois d'oeuvre et nous démontrons que cette approche est plus rapide qu'une replanification à l'aide du modèle d'origine.
Other link(s)
Accès via CorpusUL
Subject
Production scheduling.
Computer scheduling.
Constraint programming (Computer science)
Woodwork.
Ordonnancement (Gestion)
Ordonnancement (Informatique)
Programmation par contraintes.
Travail du bois.
Ordonnancement (Gestion)
Ordonnancement (Informatique)
Programmation par contraintes
Travail du bois