Abstract. Computing tight resource-level bounds is a fundamental problem in the construction of flexible plans with resource utilization. In this paper we describe an efficient algorithm that builds a resource envelope, the tightest possible such bound. The algorithm is based on transforming the temporal network of resource consuming and producing events into a flow network with nodes equal to the events and edges equal to the necessary predecessor links between events. A staged maximum flow problem on the network is then used to compute the time of occurrence and the height of each step of the resource envelope profile. Each stage has the same computational complexity of solving a maximum flow problem on the entire flow network. This makes this method computationally feasible and promising for use in the inner loop of flexible-time scheduling algorithms. Retaining temporal flexibility in activity plans is important for dealing with execution uncertainty. For example, flexible plans allow explicit reasoning about the temporal uncontrollability of exogenous events [11] and the seamless incorporation of execution countermeasures. Fixed-time schedules (i.e., the assignment of a precise start and end time to all activities) are brittle and it is typically very difficult to exactly follow them during execution. For an example of the effect of fixed-time schedules in an intelligent execution situation, consider the "Skylab strike" [6] , when during the Skylab 4 mission, astronauts went on a sit-down strike after 45 days of trying to catch up with the exact demands of a fast paced schedule with no flexibility for them to adjust to the space environment. A major obstacle to using flexible schedules, however, remains the difficulty of computing the amount of resources needed across all of their possible executions. This problem is particularly difficult for multiple-capacity resources (such as electrical power) that can be both consumed and produced in any amount by concurrent activities. Techniques have been developed [5] [10] for giving conservative estimates of the resource levels needed by a flexible schedule, yielding both an upper bound and a lower bound profile on the resource level over time. In the context of a systematic search method to build flexible plans, resource-level bounds can be used at each search step as follows: a) as a backtracking test, i.e., to determine when the lower/upper bound interval is outside of the range of allowed resource levels at some time and therefore no fixed-time instantiations of the plan is resource-feasible; and b) as a search termination test, i.e., to determine when the lower/upper bound range is inside the range of allowed resource levels at all times and therefore all fixed-time instantiations of the plan are resource-feasible. Bound tightness is extremely important computationally since a tight bound can save a potentially exponential amount of search (through early backtracking and solution detection) when compared to a looser bound. In this paper, we discuss how to compute the resourcelevel envelope, i.e., the measure of maximum and minimum resource consumption at any
The concept of "envelope" has been introduced in REF , where the author deals with the scheduling of a temporal network with piecewise-constant resources.
Computing the envelope for stepwise-constant resource allocations
Proceedings of the 9th International Conference on the Principles and Practices of Constraint Programming
Computer Science