Many important practical problems require efficient allocation of resources to competing goal activities over time in the presence of complex state-dependent constraints. Synchronizing the on-board activities of a space mission, coordinating the movement of personnel and supplies to support disaster relief efforts, and managing the flow of materials through an automated manufacturing facility are all examples of this type of problem. Such problems are typically categorized as scheduling problems, where resources must be allocated so as to optimize overall performance objectives (e.g., maximizing scientific return of space missions, initiating relief efforts as soon as possible, maximizing product throughput). At the same time, since the executability of a given goal activity in such problems also depends on conditions of the predicted world state other than resource availability (e.g., spacecraft vibration level, the locations of transport or material handling vehicles), solution feasibility can only be guaranteed by dynamically generating and synchronizing the auxiliary activities necessary to bring about and preserve enabling state conditions. In short, solutions to these problems must integrate resource allocation and plan synthesis capabilities.
For the past several years we have been conducting research aimed at extending the applicability of constraint-based scheduling frameworks and heuristics to problems requiring integrated planning and scheduling capabilities. Our initial work focused on basic infra-structure requirements for integrating planning and scheduling, resulting in development of the HSTS planning and scheduling architecture. HSTS synthesizes the descriptive strengths of contemporary temporal planning frameworks with the resource modeling concepts exploited by scheduling frameworks, and advocates an integrated view of planning and scheduling as a constraint posting process. Funded by NASA, HSTS has been applied principally to space-based observatory management problems, including short-term observation scheduling for the Hubble Space Telescope and, more recently, the Small Wave Sub-Millimeter Astronomy Satellite mission scheduling problem.
Recognizing the advantage of constraint-posting frameworks as an infra-structure for integrated planning and scheduling, one principal thrust of our current work is development of Constraint Posting Scheduling Procedures, which construct schedules not by assigning start times to activities but by instead imposing sequencing constraints between those activities competing for the same resources. We have recently developed a family of constraint-posting procedures, generically referred to as PCP (Precedence Constraint Posting). These procedures have shown outstanding scheduling performance in comparison to state of the art techniques in both Artificial Intelligence and Operations Research, as well as an ability to handle more complex types of constraints. We have also applied constraint-posting scheduling concepts to the problem of managing parallel experimentation in an automated chemistry workstation resident in the CMU Chemistry Department, where our solution has almost doubled the workstation's throughput.