Tight approximations for resource constrained scheduling and bin packing

AbstractWe consider the following resource constrained scheduling problem. We are given m identical processors, s resources R1, …, Rs with upper bounds b1, …, bs, n independent jobs T1, …, Tn of unit length, where each job Tj has a start time rj ϵ N, requires one processor and an amount Ri(j) ϵ {0, 1} of resource Ri, 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 Copt (resp. C) be the minimum schedule size for the integral (resp. fractional scheduling). While the computation of Copt is a NP-hard problem, C can be computed by linear programming in polynomial time. In case of zero start times Röck and Schmidt (1983) showed for the integral problem a polynomial-time approximation within ((m2)Copt and de la Vega and Lueker (1981), improving a classical result of Garey et al. (1976), gave for every ε > 0 a linear time algorithm with an asymptotic approximation guarantee of (s + ε)Copt. The main contributions of this paper include the first polynomial-time algorithm approximating Copt for every ε ϵ (0, 1) within a factor of 1 + ε for instances with bi = Ω(ε−2log(Cs)) for all i and m = Ω(ε−2log C), 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 α > 1 a parallel 2α-factor approximation algorithm