Le filtrage des bornes pour les contraintes cumulative et multi-inter-distance

Authors: Ouellet, Pierre
Advisor: Quimper, Claude-Guy
Abstract: This thesis discusses how to solve scheduling problems using constraint programming. We study global constraints and particularly the Cumulative constraint. We survey its main filtering rules and their state-of-the-art filtering algorithms. We explain the Vilím’s Edge-Finder and its cumulative tree.We introduce a more efficient and more general algorithm that enforces the filtering rules from the energetic reasoning. We study the special case where all tasks have identical processing times. To efficiently model such problems, we introduce the Multi-Inter-Distance constraint. The scheduling algorithm by López-Ortiz and Quimper is adapted to produce a filtering algorithm enforcing bounds consistency. The constraint Multi-Inter-Distance is proved efficient to solve the runway scheduling problem on the benchmark by Artiouchine and Baptiste.
Document Type: Mémoire de maîtrise
Issue Date: 2014
Open Access Date: 20 April 2018
Permalink: http://hdl.handle.net/20.500.11794/25000
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
30388.pdf1.6 MBAdobe PDFView/Open
All documents in CorpusUL are protected by Copyright Act of Canada.