Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics

Dynamic problem structure analysis as a basis for constraint-directed scheduling heuristics

0.00 Avg rating0 Votes
Article ID: iaor2002204
Country: United States
Volume: 117
Issue: 1
Start Page Number: 31
End Page Number: 81
Publication Date: Feb 2000
Journal: Artificial Intelligence
Authors: ,
Keywords: artificial intelligence
Abstract:

While the exploitation of problem structure by heuristic search techniques has a long history in AI, many of the advances in constraint-directed scheduling technology in the 1990s have resulted from the creation of powerful propagation techniques. In this paper, we return to the hypothesis that understanding of problem structure plays a critical role in successful heuristic search even in the presence of powerful propagators. In particular, we examine three heuristic commitment techniques and show that the two techniques based on dynamic problem structure analysis achieve superior performance across all experiments. More interestingly, we demonstrate that the heuristic commitment technique that exploits dynamic resource-level non-uniformities achieves superior overall performance when those non-uniformities are present in the problem instances.

Reviews

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