Effective Redundant Constraints for Online Scheduling

Lise Getoor, Greger Ottosson, Markus Fromherz, Björn Carlson

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.