Article ID: | iaor200953675 |
Country: | United States |
Volume: | 20 |
Issue: | 1 |
Start Page Number: | 143 |
End Page Number: | 153 |
Publication Date: | Jan 2008 |
Journal: | INFORMS Journal On Computing |
Authors: | Mercier Luc, Hentenryck Pascal van |
The introduction of edge–finding techniques was a significant development in constraint–based scheduling. Today, edge finders are still the state of the art in the disjunctive case and a technique of interest in cumulative scheduling. This paper reconsiders edge–finding algorithms for cumulative scheduling and shows that Nuijten's edge finder, and its derivatives, are incomplete because they use an invalid dominance rule. We then present a correct cumulative edge finder running in time