Constraint Guided Scheduling: A Short History of Scheduling Research at CMU

Abstract

This paper describes the historical evolution of the isis/opis/cortes family of knowledge-based scheduling systems developed at Carnegie Mellon University. At the core of the isis/opis/cortes family is an approach to automatic scheduling that provides a framework for incorporating the full range of real-world constraints. Given the conflicting nature of the domain's constraints, the problem differs from typical constraint satisfaction problems. One cannot rely solely on propagation techniques to arrive at an acceptable solution, since no feasible solution may exist. Rather, constraints must be selectively relaxed in which case the problem solving strategy becomes one of finding a solution that best satisfies the constraints. Secondly, constraints on the available capacity of resources forces a scheduling system to divert its attention opportunistically between a job-centered perspective and a resource-centered perspective.