Effective Redundant Constraints for Online Scheduling

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 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.