An Efficient Algorithm for a Class of Two-Resource Allocation Problems

We propose an efficient algorithm for the two resource allocation problem defined on a series-parallel graph, where nodes represent tasks, and arcs represent precedence relationships. The completion time of each task is inversely proportional to the amount of resource allocated, and the objective is to minimize the length of the longest path on the graph. Our algorithm is derived based on a formal analysis of the primal and Lagrangian dual optimal solutions. The resulting search process always ends up with one of three exclusive cases. For the first two cases, a closed form solution exists. For the third case, a bisectional search is used. The computational complexity of the algorithm is thus bounded fromabove by O(Nlog(1/ɛ)), where N is the total number of tasks, and ∈ is any given accuracy.