Intégration d'une fonction de coût à la contrainte Disjunctive utilisée en ordonnancement

Auteur(s): Martel, Vincent
Direction de recherche: Quimper, Claude-Guy
Résumé: La programmation par contraintes est une technique accélérant la recherche de solutions pour des problèmes d’optimisation combinatoire. Ce mémoire porte sur l’application de cette technique en ordonnancement. Le but est d’intégrer une fonction de coût convexe à la contrainte Disjunctive qui régit l’ordre d’exécution d’un ensemble de tâches ne pouvant pas se chevaucher dans le temps. Dans ce contexte, le coût est perçu comme un retard déterminé par une échéance préférable indiquée pour chaque tâche. La contribution se traduit en l’introduction de la contrainte DisjunctiveTardiness qui tisse de nouveaux liens entre l’ordre d’exécution des tâches et la somme des retards engendrés. La cohérence de la contrainte est assurée par un algorithme de filtrage. L’algorithme raisonne à partir de la construction d’un réseau de flot pondéré basé sur la fenêtre d’exécution des tâches et leur échéance préférable. Il est implémenté dans un solveur et comparé à une alternative compétitive. Tel qu’observé, le nouvel algorithme amène un filtrage tangible, mais sa complexité trop élevée empêche d’aboutir à un nouvel état de l’art en pratique. En revanche, plusieurs pistes de solution pour réduire le temps d’exécution sont proposées.
Type de document: Mémoire de maîtrise
Date de publication: 2019
Date de la mise en libre accès: 22 octobre 2019
Lien permanent: http://hdl.handle.net/20.500.11794/37036
Université décernant le diplôme: Université Laval
Collection :Thèses et mémoires

Fichier(s) :
Description TailleFormat 
35551.pdf1.04 MBAdobe PDFMiniature
Télécharger
Tous les documents dans CorpusUL sont protégés par la Loi sur le droit d'auteur du Canada.