Several algorithms developed for use in automated planning and scheduling of sets of interdependent activities employ aggregation techniques to increase the efficiency of searching for temporal assignments that are legal in the sense that they do not violate constraints. In the aggregate-search approach, one computes the aggregate state and resource requirements of a cluster of interdependent activities and searches for minimally conflicting temporal placements for the corresponding cluster of requirements. During the search, all activities that temporally constrain each other (for example, as in the requirement to complete activity A before starting activity B) are moved in unison. In computational tests based on a synthetic planning and scheduling problem and on problems from spacecraft and Rocky-7 Mars Rover operations, the aggregation-search algorithms were found to out-perform alternative algorithms that follow the "naïve" approach of searching for legal placements of the constituent activities individually.
This work was done by Steve Chien, Russell Knight, Gregg Rabideau, and Robert Sherwood of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp under the Materials category.
This software is available for commercial licensing. Please contact Don Hart of the California Institute of Technology at (818) 393-3425. Refer to NPO-20660.
This Brief includes a Technical Support Package (TSP).
Aggregate-Search Approach for Planning and Scheduling
(reference NPO-20660) is currently available for download from the TSP library.
Don't have an account? Sign up here.