Article ID: | iaor19997 |
Country: | United States |
Volume: | 10 |
Issue: | 1 |
Start Page Number: | 114 |
End Page Number: | 120 |
Publication Date: | Dec 1998 |
Journal: | INFORMS Journal On Computing |
Authors: | Armstrong R., Gu S., Lei L. |
Keywords: | programming: multiple criteria, graphs |
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 from above by