An Ontology for Constructing Scheduling Systems

The Robotics Institute
Carnegie Mellon University
Pittsburgh, PA 15213, USA

Abstract

In this paper, we consider the use of ontologies as a basis for structuring and simplifying the process of constructing domain-specific problem-solving tools. We focus specifically on the task of scheduling. Though there is commonality in scheduling system requirements and design at several levels across application domains, different scheduling environments invariably present different challenges (e.g., different dominating constraints, different objectives, different domain structure, different sources of uncertainty, etc.), and hence we can expect high-performance application systems to require customized solutions. Unfortunately, the time and cost associated with such domain-specific system development at present is typically quite large.

Our work toward overcoming this application construction bottleneck has led to the development of OZONE, a toolkit for configuring constraint-based scheduling systems. A central component of OZONE is its scheduling ontology, which defines a reusable and extensible base of concepts for describing and representing scheduling problems, domains and constraints. The OZONE ontology provides a framework for analyzing the information requirements of a given target domain, and a structural foundation for constructing an appropriate domain model. Through direct association of software component capabilities with concepts in the ontology, the ontology promotes rapid configuration of executable systems and allows concentration of modeling effort on those idiosyncratic aspects of the target domain. The OZONE ontology and toolkit represent a synthesis of extensive prior work in developing constraint-based scheduling models for a range of applications in manufacturing, space and transportation logistics.

We first motivate the use of ontologies as model building tools, establishing linkages to recent concepts in software engineering and proposing an extended view of ontologies that includes capability descriptions. We then describe our perspective on the structure of planning and scheduling domain models and summarize major components of current OZONE scheduling ontology. *

* The work described in this paper was sponsored in part by the Advanced Research Projects Agency and Rome Laboratory, Air Force Material Command, USAF, under grant numbers F30602-90-C-0119 and F30602-95-1-0018 and the CMU Robotics Institute. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Advanced Research Projects Agency and Rome Laboratory or the U.S. Government.