Integrated Planning and Scheduling

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.