Tight Approximation for Resource Constrained Scheduling and Bin Packing

We consider the following resource constrained scheduling problem. Given m identical processors, s resources with upper bounds, n independent tasks of unit length, where each task has a start time and requires one processor and a task-dependent amount of every resource. The optimization problem is to schedule all tasks at discrete times in N, minimizing the latest completion time Cmax subject to the processor, resource and start-time constraints. Multidimensional bin packing is a special case of this problem. The problem is NP-hard even under much simpler assumptions. In case of zero start times Röck and Schmidt (1983) showed an (m/2)-factor approximation algorithm and de la Vega and Lueker (1981), improving a classical result of Garey, Graham, Johnson and Yao (1976), gave for every epsilon > 0 a linear time algorithm with an asymptotic approximation guarantee of s +epsilon. The contribution of this paper is to break the O(m) resp. O(s) barrier, even in the case of zero start times, at least for problems where the number of processors and the resource bounds are in Omega(log |I|), |I| being the input size of the problem. The main results are constant factor approximation algorithms for such problems and the proof of the optimality of the achieved approximation under the hypothesis P not= NP