The allocation problem discussed here is as follows. The processing time of a task is a linear function t-ax-by of amounts x, y of resources allocated to it, where t, a, b are positive constants. Given the amounts X and Y of available resources, we wish to allocate them among n independent tasks so as to minimize the maximal completion time. We solve this problem in linear time.
['Nimrod Megiddo', 'Tetsuo Ichimori']
A Two-Resource Allocation Problem Solvable in Linear Time