Reconfigurable architectures for mixed-initiative planning and scheduling
Stephen F. Smith, Marcel Becker · 1998
This thesis addresses the problem of building software applications for planning and scheduling systems. Most planning and scheduling problems are NP-complete even for simplified formulations. The practical utilization of planning and scheduling systems as decision support tools requires not only dealing with this computational complexity in a reasonable way but also considering the uncertainties associated with executing plans and schedules in a real environment. Given the complexity of the problem, implementing applications capable of generating high quality solutions for these problems is a time consuming activity. Although each application domain has its own challenges and idiosyncrasies, a certain level of similarities can be identified across related problems. The development time would clearly be reduced if good implementations of these common functionality could be adapted to be used in new applications. Despite all the software reuse effort, few applications explore these commonalities. Most of the currently implemented systems and solutions are too problem specific, or too complex to provide any reuse opportunity. Motivated by recent efforts from the software reuse community and from the knowledge acquisition community, I designed and implemented a modeling framework based on an ontological model—the OZONE modeling framework. The ontology defines a domain specific terminology that can be used as a language for describing planning and scheduling models. By associating capabilities or functionalities to the concepts in the ontology, a functional model can be obtained. If this functionality is supported by an actual implementation, executable models can be easily generated. The development framework proposed is composed of this planning and scheduling ontology, the implementation of the capabilities described by the ontology as an object-oriented class library, and a software tool that implements the mechanisms needed to generate executable software applications from model descriptions. The applicability and validation of the solution approach is obtained by applying this framework to build scheduling applications in three different domains: two problems in the area of transportation and logistics—strategic deployment, and aeromedical evacuation; and one problem in the area of resource constrained project scheduling.