AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Linear-Time Filtering Algorithms for the Disjunctive Constraint
Hamed Fahimi, Claude-Guy Quimper

Last modified: 2014-06-21

Abstract


We present three new filtering algorithms for the Disjunctive constraint that all have a linear running time complexity in the number of tasks. The first algorithm filters the tasks according to the rules of the time tabling. The second algorithm performs an overload check that could also be used for the Cumulative constraint. The third algorithm enforces the rules of detectable precedences. The two last algorithms use a new data structure that we introduce and that we call the time line. This data structure provides many constant time operations that were previously implemented in logarithmic time by the Theta-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.

Keywords


Constraint Programming; Scheduling; Global Constraint; Disjunctive

Full Text: PDF