Bounding the Resource Availability of Activities with Linear Resource Impact

摘要

We introduce the Linear Resource Temporal Network (LRTN), which consists of activities that consume or produce a resource, subject to absolute and relative metric temporal constraints; production and consumption is restricted to linear functions of activity duration. We show how to construct tight bounds for resource availability as a function of time in LRTNs; for a broad class of problems, the complexity is polynomial time in the time horizon h and the number of activities n. Our approach extends a maximum flow formulation previously used to construct tight bounds for networks of events with instantaneous resource impact. We construct the bounds in two parts: we make direct use of maximum flows to find local maxima of the upper bound (and symmetrically local minima of the lower bound), and we solve a related linear programming problem to find local minima of the upper bound (and symmetrically local maxima of the lower bound).