Track:
All Papers
Downloads:
Abstract:
Resource envelopes provide the tightest exact bounds on the resource consumption and production caused by all possible executions of a temporally flexible plan. We present a new class of algorithms 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 complexity bound for an envelope algorithm known so far and makes envelopes more amenable to practical use in scheduling. 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 used to obtain segment i-1.