Incremental maximum flows for fast envelope computation
Nicola Muscettola · 2004
Resource envelopes provide the tightest exact bounds on the resource consumption and production caused by all possible instantiations of a temporally flexible plan. We present a new algorithm that computes an envelope in O(Maxflow(n, m, U)) where n, m and U measure the size of the flexible plan. This is an O(n) improvement on the best envelope algorithm known so far and makes envelopes more amenable to practical use in scheduling algorithms. The reduction in complexity depends on the fact that when the algorithm computes the constant segment i of the envelope it makes full reuse of the maximum flow that was computed in order to obtain segment i-1. Resource Envelopes The execution of plans greatly benefits from temporal