Effective Redundant Constraints for Online Scheduling

Lise Getoor, Greger Ottosson, Markus P.J. Fromherz, and Björn Carlson

Abstract

The use of heuristics as a means to improve constraint solver performance has been researched widely. However, most work has been on problem-independent heuristics (e.g., variable and value ordering), and has focused on offline problems (e.g., one-shot constraint satisfaction). In this paper, we present an online scheduling problem for which we are developing a real-time scheduling algorithm. While we can and do use generic heuristics in the scheduler, here we focus on the combination of an anytime algorithm and redundant constraints to effectively approximate optimal offline solutions. We present a taxonomy of redundant domain constraints, and examine their impact on the effectiveness of the scheduler. This taxonomy should be of general use to practitioners in other scheduling domains, and help guide the search for domain-specific scheduling heuristics.

For postscript file, send mail to fromherz parc com.

Back to the top.