Effective Redundant Constraints for Online Scheduling

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.

Authors

• Lise Getoor
• Markus Fromherz Björn Carlson

Keywords

No keywords are indexed for this paper.