ODO Constraint Directed Scheduling ShellEnterprise Integration Laboratory
University of Toronto
4 Taddle Creek Rd., Toronto, Ontario M5S 3G9
Tel: +1-416-978-6823 Fax: +1-416-971-2479 Email: firstname.lastname@example.org
Updated: 18 February 2002
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:
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:
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.