Topics
features
Publications
Issue Archive
Computing Bounds on Resource Levels for Flexible Plans
 Created: Tuesday, 01 September 2009
New algorithm entails less computation than previous algorithms.
A new algorithm efficiently computes the tightest exact bound on the levels of resources induced by a flexible activity plan (see figure). Tightness of bounds is extremely important for computations involved in planning because tight bounds can save potentially exponential amounts of search (through early backtracking and detection of solutions), relative to looser bounds.
The bound computed by the new algorithm, denoted the resourcelevel envelope, constitutes the measure of maximum and minimum consumption of resources at any time for all fixedtime schedules in the flexible plan. At each time, the envelope guarantees that there are two fixedtime instantiations — one that produces the minimum level and one that produces the maximum level. Therefore, the resourcelevel envelope is the tightest possible resourcelevel bound for a flexible plan because any tighter bound would exclude the contribution of at least one fixedtime schedule. If the resourcelevel envelope can be computed efficiently, one could substitute looser bounds that are currently used in the inner cores of constraintposting scheduling algorithms, with the potential for great improvements in performance.What is needed to reduce the cost of computation is an algorithm, the measure of complexity of which is no greater than a lowdegree polynomial in N (where N is the number of activities). The new algorithm satisfies this need. In this algorithm, the computation of resourcelevel envelopes is based on a novel combination of (1) the theory of shortest paths in the temporalconstraint network for the flexible plan and (2) the theory of maximum flows for a flow network derived from the temporal and resource constraints. The measure of asymptotic complexity of the algorithm is O(N·O(maxflow(N)), where O(x) denotes an amount of computing time or a number of arithmetic operations proportional to a number of the order of x and O(maxflow(N)) is the measure of complexity (and thus of cost) of a maximumflow algorithm applied to an auxiliary flow network of 2N nodes. The algorithm is believed to be efficient in practice; experimental analysis shows the practical cost of maxflow to be as low as O(N^{1.5}).
The algorithm could be enhanced following at least two approaches. In the first approach, incremental subalgorithms for the computation of the envelope could be developed. By use of temporal scanning of the events in the temporal network, it may be possible to significantly reduce the size of the networks on which it is necessary to run the maximumflow subalgorithm, thereby significantly reducing the time required for envelope calculation. In the second approach, the practical effectiveness of resource envelopes in the inner loops of search algorithms could be tested for multicapacity resource scheduling. This testing would include innerloop backtracking and termination tests and variable and valueordering heuristics that exploit the properties of resource envelopes more directly.
This work was done by Nicola Muscettola of Ames Research Center and David Rijsman of Mission Critical Technologies Inc. For further information contact the Technology Partnerships Division, Ames Research Center, (650) 6042954. ARC149481
White Papers

