We consider the following resource constrained scheduling problem. We are given m identical processors, s resources R-1, ..., R-s with upper bounds b(1), ..., b(s), n independent jobs T-1, ..., T-n of unit length, where each job T-j has a start time r(j) is an element of N, requires one processor and an amount R-i(j) is an element of {0, 1} of resource R-i, i = 1, ..., s. The optimization problem is to schedule the jobs at discrete times in N subject to the processor, resource and start-time constraints so that the latest scheduling time is minimum. Multidimensional bin packing is a special case of this problem. Resource constrained scheduling can be relaxed in a natural way when one allows the scheduling of fraction of jobs. Let C-opt (resp. C) be the minimum schedule size for the integral (resp. fractional scheduling). While the computation of C-opt is a NP-hard problem, C can be computed by linear programming in polynomial time. In case of zero start times Rock and Schmidt (1983) showed for the integral problem a polynomial-time approximation within (m/2)C-opt and de la Vega and Lueker (1981), improving a classical result of Garey et al. (1976), gave for every is an element of > 0 a linear time algorithm with an asymptotic approximation guarantee of (s + epsilon)C-opt. The main contributions of this paper include the first polynomial-time algorithm approximating C-opt for every epsilon is an element of(0, 1) within a factor of 1 + epsilon for instances with b(i) = Omega(epsilon(-2)log(Cs)) for all i and m = Omega(epsilon(-2) logC), and a proof that the achieved approximation under the given conditions is best possible, unless P = NP. Furthermore, in some cases we give for every fixed alpha > 1 a parallel 2 alpha-factor approximation algorithm.
