TIGHT APPROXIMATIONS FOR RESOURCE CONSTRAINED SCHEDULING AND BIN PACKING

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 leng th, where each job T-j has a start time r(j) is an element of N, requi res one processor and an amount R-i(j) is an element of {0, 1} of reso urce R-i, i = 1, ..., s. The optimization problem is to schedule the j obs at discrete times in N subject to the processor, resource and star t-time constraints so that the latest scheduling time is minimum. Mult idimensional bin packing is a special case of this problem. Resource c onstrained 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 t he computation of C-opt is a NP-hard problem, C can be computed by lin ear programming in polynomial time. In case of zero start times Rock a nd Schmidt (1983) showed for the integral problem a polynomial-time ap proximation within (m/2)C-opt and de la Vega and Lueker (1981), improv ing a classical result of Garey et al. (1976), gave for every is an el ement 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 ev ery 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 = Omeg a(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-facto r approximation algorithm.