A Multi-Decompositional Approach to Integration of Planning and Scheduling — An Applied Perspective

Contents

This paper proposes a multi-decompositional approach to integrating planning and scheduling. In many practical domains, planning and scheduling problems are tightly intertwined: the right decomposition for a given goal cannot be determined without considering scheduling. Commonly used approaches suffer from limited lookahead. The key steps of the proposed approach are: (a) perform and store multiple decompositions for each goal or activity that require decomposition and then (b) identify the best selections among the combined set of alternative decompositions. To accomplish the latter - selection and scheduling within the space of multiple alternative decompositions -- we propose a novel extension of Constraint-Directed Heuristic Search. Several applications of the approach to practical large-scale systems in domains such as logistics and transportation are described.