Speeding Up the Resource Envelope Computation for Activities with Linear Resource Impact

Previous work on Linear Resource Temporal Networks (LRTNs) has shown how to construct tight bounds for re-source availability as a function of time. The previous al-gorithm is pseudo-polynomial; in particular, the complexity has two components involving h, where h is the length of the scheduling horizon. However, h may be exponential in the number of activities, making this approach of limited use for practical problems. In this paper we build upon the previous results to prove a Persistence Theorem showing that the set of activity pieces that maximizes the availability increases monotonically over time. This provides a polynomial bound on the number of slope changes and leads to an algorithm that eliminates one of the h factors in the complexity of the previous algorithm. We also make progress on the other h component, which arose from the need to chop activities into unit pieces, by chopping only to the extent needed to satisfy an alignment condition between producers and consumers. A “worst case ” example shows that may still result in chopping to units, but that is an improvement over the previous method, which required chopping to units in all cases