ODO Constraint Directed Scheduling Shell

Enterprise Integration Laboratory
University of Toronto
4 Taddle Creek Rd., Toronto, Ontario M5S 3G9
Tel: +1-416-978-6823 Fax: +1-416-971-2479 Email: msf@eil.utoronto.ca
Updated: 18 February 2002

Constraint-Directed Scheduling

EIL Theory

EIL Applications

EIL Other

Overview

Back in the olden days (early 1980's), it was recognised that the real goal of industrial scheduling is not simply meeting due dates, but rather satisfying the many complex and interacting constraints from disparate sources within the plant, and indeed within the enterprise as a whole [Fox, 1983, Fox, 1990]. In fact, this was one of the original reasons to believe that the scheduling was a prime (in fact the prime) application of constraint technologies.

Since then, many different constraint-based scheduling systems have been developed, and applied successfully to various application domains. However, to our knowledge, most research to date has reported either:

  • the performance of a particular system's approach on a particular domain, with little analysis of why this system's approach might be preferred over another;
  • a relatively limited comparison of a few different algorithms on a small number of simple and unrealistic academic benchmark job shop problems.

We have seen little attempt to develop a science of scheduling algorithms, based on how different components of scheduling algorithms, such as heuristics and propagators, interact and behave; not only on job shop problems but also on more realistic models of scheduling involving, for instance, alternate resources, inventory, multiple process plans, etc.

Thus while much of the field of empirical study of algorithms is relatively immature, empirical scheduling research may be especially so due to the widespread (and currently unmet) demand for scheduling solutions to real problems in industry and elsewhere. This demand has significant positive impact for research in terms of funding, sources of challenging problems, and opportunities to contribute beyond the academic world. However, the same demand can result in a retardation of progress of the progress of science due to the strong temptation to concentrate on delivering an acceptable solution method for a particular problem, rather than on developing an understanding of the relative merits of existing and novel techniques.

The goal of our work is to develop a deep understanding of heuristics and search techniques for a wide variety of scheduling problems as they exist in the real world. To this end we have developed ODO, a constraint based scheduling shell. ODO's four level architecture integrates problem acquisition, generative- and repair-based techniques, and schedule execution around a single constraint graph representation. By uniting constraint-directed search under a foundation of assertion and retraction of commitments (with propagation of the commitments to related problem variables) we are able to emulate a large portion of existing scheduling technology. Our motivation behind developing ODO has been to design a framework for constraint directed scheduling which:

  • allows rigorous experimental design, isolating all the components of algorithm except those being evaluated;
  • allows straightforward implementation of new work, allowing it to be easily integrated within other algorithm contexts;
  • easy to develop new components in existing framework.
  • orthogonal components can be isolated, experiment with new combinations of components.

A detailed description of the ODO can be found in: Beck, J.C., Davenport, A.J., Fox, M.S., (1998), "The ODO Project: Towards a Unified Basis for Constraint-Directed Scheduling", International Journal of Scheduling, Vol. 1, pp. 89-125.

ODO Documentation