A completable approach to integrating planning and scheduling

Extended Abstract The need to integrate planning and scheduling becomes more apparent as more complex real–world problems are addressed by researchers in planning and scheduling. Consider the problem of manufacturing a particular part from a block of raw material. Solving this problem involves determining some sequence of operations to be performed on the block to achieve the desired features, as well as actually selecting the machines and the tools to carry out the operations. Planning research has concentrated on the problem of determining an ordered sequence of actions to achieve the goal, while scheduling research has concentrated on the problem of assigning tasks or operations to resources to meet some performance criterion. Realistically, however, the planning problem cannot be treated independently of the scheduling problem. The value of decisions such as which operation to use to achieve a specific part feature, or the order in which to perform a set of operations, depends not only on a priori information such as process capabilities but also on runtime information such as machine availability. The classical approach of first doing planning and then scheduling may result in overcommitted plans which needlessly constrain the scheduler in its search for task–to–resource assignments. Early scheduling research showed that flexible machine selection and operation sequence process routing improves performance. 1 More recently, reactive methods have been developed for incorporating runtime information in scheduling decisions to facilitate scheduling in dynamic domains [Ow88, Prosser89, Zweben90]. The completable approach to integrating planning and scheduling grew out of our previous work on completable planning [Gervasio90a, Gervasio90b, Gervasio91]. A completable planner consists of aclassical (deliberative) element augmented with the ability to defer achievable goals to a reactive element. A goal is achievable if the reactive element is guaranteed to find a plan to achieve the goal. 2 This integration permits a system to adapt to unpredictable situations and utilize runtime information in its planning while retaining the goal–directedness afforded by projection. In contrast to other integrated approaches—which compile projection into reactive rules [Drummond90, Kaelbling88, Mitchell90, Schoppers87] or defer planning until certain information is available [Firby87, Olawsky90]—our approach maintains a distinction between deliberative and reactive goals and defers only achievable goals. Completable planning was designed for domains in which the expected situations and effects of actions could be characterizedfairly well but imperfectly. Process planning is just such a domain. Given a part to manufacture, process planning involves determining a set of operations (tasks) to achieve the part and the assignment of these tasks to a set of machines (resources). For a particular feature, there are often many alternative operations, and for each operation, many alternative machines. Resources generally behave as expected—i.e. they are usually available and succeed in processing a task as expected. However, they are also subject to some unpredictable events, such as sudden unavailability due to breakdown or preemption, which may in turn render particular operations unexecutable or less desirable. By deferring goals until execution time, a completable system can use runtime information to complete and correct its imperfect a priori information about a domain. The use of runtime information to provide additional constraints is particularly important in scheduling, where underconstrained problems are the norm and the focus is on finding a good solution. 3 A system which utilizes all the available information in making its decisions is thus likely to do better than one which relies only on a priori information. The completable approach to planning and scheduling permits the deliberative element to defer goals involving operator choice and operator ordering. 4 A completable system defers the decision of which operation to use to service a particular task if there are multiple methods for achieving the task and the a priori information does not enable the system to isolate one. If different methods are applicable in different situations, the deferred goal is considered achievable if the situations corresponding to the different conditions sufficiently covers the space of possible situations. In the case of multiple applicable actions, the question is more one of optimality than achievability, and while the completable approach does not directly solve the problem of finding an optimal solution, it may facilitate the search for one through the utilization of additional runtime information. A completable system defers ordering decisions if a priori planning yields no ordering constraints between the tasks—i.e. each task neither establishes nor denies the preconditions of the other tasks. In this case, the additional constraints provided by runtime information may be useful in determining preferred orderings. Because of the achievability criterion, the choice of deferred goals is highly dependent on the available a priori information and the kinds of information the system knows it is capable of obtaining during execution. Deferred operator choices and ordering decisions are addressed during execution by conditionals and dispatchers. The form of a conditional is {COND c 1 → a 1 ; …; c n → a n }, where each c i is a set of conditions and a i , an applicable action. To execute a conditional, a system evaluates the different condition–action rules to determine an appropriate action. In the case of multiple conditions being satisfied, the system uses some given performance metric to evaluate the proposed actions and choose the best candidate. A dispatcher may be viewed as a repeat loop over a conditional on the unordered set of tasks, with the set of tasks becoming smaller with every loop, and the exit condition being that all the tasks are serviced. While a completable system may employ the same heuristics as a reactive system for choosing between multiple applicable alternatives, its a priori planning will generally result in a smaller space of alternatives to be searched by the reactive element, and its achievability proofs guarantee that a completion will be found. The performance of a completable system in a simple job– shop scheduling domain was compared to that of a classical (purely deliberative) system and a purely reactive system. The basic problem was to determine a plan/schedule which successfully serviced a given set of tasks in the least time possible. Uncertainty entered the system via the possibility of sudden resource unavailability (e.g. breakdown, preemption) during execution. Plans/schedules were evaluated on two aspects: ability to successfully service a set of tasks, and when successful, the cost incurred in servicing the tasks. The results supported our hypotheses: 1) completable plans equal or outperform classical plans, 2) the performance improvement of completable plans over classical plans is increases as uncertainty increases, 3) completable plans are more successful than reactive plans, and 4) the success rate of reactive plans is decreased by greater task interactions. 5 The completable approach achieves a well–founded integration of planning and scheduling based on the achievability criterion, which enables a completable system to gain the benefits of reactivity without losing the benefits provided by apriori planning. However, other scheduling concerns, such as deadlines, resource utilization, and resource contention, remain to be addressed in the completable approach. Further experimentation is also needed to more exhaustively test the approach and to develop a framework for understanding the various factors which influence the relative merits of the different approaches.