Carnegie Mellon University
HSTS: Integrating Planning and Scheduling

Nicola Muscettola
tech. report CMU-RI-TR-93-05, Robotics Institute, Carnegie Mellon University, March, 1993

  • Adobe portable document format (pdf) (2MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

In the traditional approach to managing complex systems, planning and scheduling are two very distinct phases. However, in a wide variety of applications this strict separation is not possible or beneficial. During scheduling it is often necessary to make planning decisions (plan the setup of a machine); moreover planning decisions can benefit from scheduling information (choose a process plan depending on resource loads). HSTS (Heuristic Scheduling Testbed System) is a representation and problem solving framework that provides an integrated view of planning and scheduling. HSTS emphasizes the decomposition of a domain into state variables evolving over continuous time. This allows the description and manipulation of resources far more complex than it is possible in classical scheduling. The inclusion of time and resource capacity into the description of causal justifications allows a fine-grain integration of planning and scheduling and a better adaptation to problem and domain structure. HSTS puts special emphasis on leaving as much temporal flexibility as possible during the planning/scheduling process to generate better plan/schedules with less computation effort. Within the HSTS framework we have implemented several planning/scheduling systems. In the paper we describe an integrated planner and scheduler for short term scheduling of the Hubble Space Telescope. This system has demonstrated the ability to deal effectively with all of the important constraints of the domain. Experimental results show that executable schedules for Hubble can be built in a time compatible with operational needs. The paper also describes a methodology for job-shop scheduling problems. The methodology exploits the temporal flexibility provided by HSTS. Experimental results show that this approach is more effective than other intelligent scheduling techniques in the solution of scheduling problems with non-negotiable deadlines.

planning, scheduling, Hubble

Sponsor: NASA, DARPA
Grant ID: NASA #NCC 2-707, DAR #F30602-91-F-0016
Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Intelligent Coordination and Logistics Laboratory
Associated Project(s): HSTS Space Observatory Scheduler
Number of pages: 34

Text Reference
Nicola Muscettola, "HSTS: Integrating Planning and Scheduling," tech. report CMU-RI-TR-93-05, Robotics Institute, Carnegie Mellon University, March, 1993

BibTeX Reference
   author = "Nicola Muscettola",
   title = "HSTS: Integrating Planning and Scheduling",
   booktitle = "",
   institution = "Robotics Institute",
   month = "March",
   year = "1993",
   number= "CMU-RI-TR-93-05",
   address= "Pittsburgh, PA",