Actions for Computing the Envelope for Stepwise Constant Resource Allocations

Email RIS file
Bookmark
Report an Issue

Computing the Envelope for Stepwise Constant Resource Allocations

Author
Clancy, Daniel
Published
[2001].
Physical Description
1 electronic document
Additional Creators
Muscettola, Nicola
Online Version

Availability

I Want It
I Want It

Finding items...

Restrictions on Access
Unclassified, Unlimited, Publicly available.
Free-to-read Unrestricted online access
Summary
Estimating tight resource level 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 noises equal to the events and edges equal to the necessary predecessor links between events. The incremental solution of 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. The staged algorithm has the same computational complexity of solving a maximum flow problem on the entire flow network. This makes this method computationally feasible for use in the inner loop of search-based scheduling algorithms.
Other Subject(s)
Collection
NASA Technical Reports Server (NTRS) Collection.
Note
Document ID: 20020052599.
Terms of Use and Reproduction
No Copyright.
View MARC record | catkey: 15423908