Uniform machine scheduling of unit-time jobs subject to resource constraints

AbstractThe problem of scheduling a set of unit-time jobs on m uniform machines is studied. Some jobs may require a unit of an additional single resource during their execution. The resource is renewable but the total resource consumption is limited by the same value at each time instant. The objective is to find a feasible schedule minimizing the maximum job completion time. We show that an approach suggested in the literature to solve this problem is incorrect. Then we present an O(m log m) algorithm for the problem with no machine idle times and a linear-time algorithm for the problem with identical machines