An efficient algorithm for a class of two-resource allocation problems

An efficient algorithm for a class of two-resource allocation problems

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: multiple criteria, graphs
Abstract:

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 O(N log(1/ϵ)), where N is the total number of tasks, and ϵ is any given accuracy.

Reviews

Required fields are marked *. Your email address will not be published.