An O(N log (1/ɛ)) Algorithm for the Two-resource Allocation Problem with a Non-differentiable Convex Objective Function

Abstract

This paper considers a job consisting of N totally ordered tasks. There is a budget for each of the two non-substitutable resources needed for the tasks. The processing time of each task is inversely proportional to the amount of resource allocated. We determine how to distribute the resources to the tasks so that the completion time of the job is minimized. A search procedure is presented that solves the problem with a worst case performance O(N log (1/ɛ)), where ɛ is a given accuracy.

Keywords:

• Convex Resource Allocation
• Multiple Non-Substitutable Resources
• Search Algorithms