Edge Finding for Cumulative Scheduling

Edge Finding for Cumulative Scheduling

0.00 Avg rating0 Votes
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: ,
Abstract:

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 O(n2k), where n is the number of tasks and k the number of different capacity requirements of the tasks. The new algorithm is organized in two phases and first uses dynamic programming to precompute the innermost maximization in the edge–finder specification. The paper also proposes the first extended edge–finding algorithms that run in time O(n2k), improving the running time of available algorithms. Finally, the paper discusses how to speed up the algorithm in practice and how the first phase can be used to improve algorithms based on energetic reasoning.

Reviews

Required fields are marked *. Your email address will not be published.