/Integrated Planning and Scheduling

Integrated Planning and Scheduling

Portrait of Integrated Planning and Scheduling
Head: Stephen Smith
Contact: Stephen Smith
Associated Lab: Intelligent Coordination and Logistics Laboratory
Last Project Publication Year: 2001

Goal-oriented activity in complex domains typically requires a combination of planning and scheduling. Military planners must select courses of actions that achieve strategic objectives, while making the most of available assets. A manufacturing facility must develop process plans for ordered parts that can be integrated cost-effectively with current production operations. Space observatories must allocate viewing instruments to maximize scientific return under a large and diverse set of causal restrictions and dependencies. Though conceptually decomposable, planning and scheduling processes in such domains can be and often are highly interdependent. Different planning options for achieving a given objective can make quite different demands on system resources; correspondingly, current resource commitments and availability will impact the feasibility or desirability of various planning options. The dynamics of the operating environment complicate matters further, requiring efficient response to continual unexpected changes to system objectives and resource availability.

Despite their inter-dependency in most domains, effective integration of planning and scheduling processes remains a difficult problem. In manufacturing organizations, this problem has been characterized as the “wall between engineering and manufacturing”. Similar sorts of barriers can be found in other large-scale enterprises. The crux of the problem is lack of communication. Plans are developed with no visibility of resource availability and operational status and, likewise, schedules are developed and managed without knowledge of objectives and dependencies. Without such information exchange, planning and scheduling processes are each forced to proceed in an uninformed and inherently inefficient manner. In the simplest case, the result is an iterative waterfall model of integration, where planning and scheduling are performed in sequential lockstep fashion, and any problem encountered during scheduling simply triggers the generation of a new plan. Unfortunately, the iterative waterfall approach to integration is quite common in many application domains, leading to artificially inflated lead times and costs in manufacturing environments, more protracted and more resource wasteful military campaigns, missed opportunities at scientific observatories, and so on.

In collaboration with the researchers at SRI, we are investigating the development of techniques for tighter integration of planning and scheduling processes. Starting from pre-existing planning and scheduling technologies (SRI’s CHIP HTN Planner and CMU’s ACS scheduler), we have developed a joint planner/scheduler for air operations planning. Through experimentation with the planner/scheduler, we have demonstrated that increased exchange of information between planner and scheduler, and greater flexibility to interleave planning and scheduling decisions can yield performance gains along three dimensions: (1) more streamlined (and more computationally efficient) solution generation and repair, (2) better quality plans and schedules, and (3) greater stability in the solutions generated over time. One effective coordination strategy that we have developed is based on the idea of approximating the resource intensity of different planning options, and then incrementally exchanging and exploiting information about likely resource shortfalls and excess capacity to settle on options that best utilize available resources. One thread of our current work is investigating expanded strategies for coordinating planner/scheduler interaction. Another thread is extending capabilities of the ACS (Air Campaign Scheduler) component and transitioning this tool into an Advanced Technology Demonstration within AFRL’s Effects-Based Operations program.

Displaying 2 Publications
Integrating Planning and Scheduling through Adaptation of Resource Intensity Estimates
Karen Myers, Stephen Smith, David W. Hildum, Peter Jarvis and R. de Lacaze

Conference Paper, Proceedings 5th European Conference on Planning, September, 2001
Integrating Planning and Scheduling through Intensity Adaptation
Karen Myers, Stephen Smith, David W. Hildum, Peter Jarvis and R. de Lacaze

Workshop Paper, Proceedings of the IJCAI-01 Workshop on Planning with Resources, July, 2001

Current RI People

Past Project People

  • David W Hildum
  • Karen Myers
  • Peter Jarvis