Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last

Authors: Fahimi, HamedOuellet, YanickQuimper, Claude-Guy
Abstract: We present new filtering algorithms for Disjunctive and Cumulative constraints, each of which improves the complexity of the state-of-theart algorithms by a factor of log n. We show how to perform TimeTabling and Detectable Precedences in linear time on the Disjunctive constraint. Furthermore, we present a linear-time Overload Checking for the Disjunctive and Cumulative constraints. Finally, we show how the rule of Not-first/Not-last can be enforced in quadratic time for the Cumulative constraint. These algorithms rely on the union find data structure, from which we take advantage to introduce a new data structure that we call it time line. This data structure provides constant time operations that were previously implemented in logarithmic time by the Θ-tree data structure. Experiments show that these new algorithms are competitive even for a small number of tasks and outperform existing algorithms as the number of tasks increases. We also show that the time line can be used to solve specific scheduling problems.
Document Type: Article de recherche
Issue Date: 11 April 2018
Open Access Date: 11 April 2019
Document version: AM
Permalink: http://hdl.handle.net/20.500.11794/21641
This document was published in: Constraints (2018)
https://doi.org/10.1007/s10601-018-9282-9
Kluwer
Alternative version: 10.1007/s10601-018-9282-9
Collection:Articles publiés dans des revues avec comité de lecture

Files in this item:
Description SizeFormat 
TimeLineProject.pdf
378.1 kBAdobe PDF    Request a copy
All documents in CorpusUL are protected by Copyright Act of Canada.