AAAI Conference 1997 Conference Paper
Effective Redundant Constraints for Online Scheduling
- Lise Getoor
- Markus Fromherz
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-tune scheduling algorithm. While we can and do use generic heuristics in the scheduler, here we focus on the use of domain-specific 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. We also describe several techniques for generating redundant constraints, which can be applied to a large class of job shop scheduling problems.