Linear-time filtering algorithms for the disjunctive constraint and a quadratic filtering algorithm for the cumulative not-first not-last
Authors: | Fahimi, Hamed; Ouellet, Yanick; Quimper, 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 | Size | Format | ||
---|---|---|---|---|
TimeLineProject.pdf | 378.1 kB | Adobe PDF | ![]() View/Open |
All documents in CorpusUL are protected by Copyright Act of Canada.