Le filtrage des bornes pour les contraintes cumulative et multi-inter-distance
|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|
|Open Access Date:||20 April 2018|
|Collection:||Thèses et mémoires|
All documents in CorpusUL are protected by Copyright Act of Canada.