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

Authors: Martel, Vincent
Advisor: Quimper, Claude-Guy
Abstract: Constraint programming is a technology originating from artificial intelligence that explores a search space to solve combinatorial problems. It uses filtering algorithms to filter the search space and speedup the search of a solution. This master thesis covers an application of this method in scheduling. The goal is to integrate a convex cost function to the Disjunctive constraint that governs the execution order of tasks unable to overlap each other on a time line. In this context, the cost is treated as a delay (tardiness) computed from a due date specified for each task. The contribution translates in a new constraint named DisjunctiveTardiness that brings a stronger relation between the order in a schedule and the sum of tardinesses. Consistency of the constraint is achieved by a filtering algorithm. The algorithm builds a weighted network flow from the allowed time window of the tasks and their due date. The solution is implemented in a solver. The experimental results show that the new algorithm applies stronger filtering, but its time complexity is too high to recommend it in practice. To conclude, several potential upgrades are proposed to reduce the execution time.
Document Type: Mémoire de maîtrise
Issue Date: 2019
Open Access Date: 22 October 2019
Permalink: http://hdl.handle.net/20.500.11794/37036
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
Description SizeFormat 
35551.pdf1.04 MBAdobe PDFThumbnail
View/Open
All documents in CorpusUL are protected by Copyright Act of Canada.