Effective redundant constraints for online scheduling

The use of heuristics as a means to improve constraint solverperformance has been researched widely. However, most
work has been on problem-independent heuristics (e.g., vari-
able and value ordering), and has focused on offline prob-
lems (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 fo-
cus on the use of domain-specific redundant constraints to ef-
fectively 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 con-
straints, which can be applied to a large class of job shop
scheduling problems.