Tight Approximation for Resource Constrained Scheduling and Bin Packing

Srivastav, Anand and Stangier, Peter (1994) Tight Approximation for Resource Constrained Scheduling and Bin Packing.
Published In: Algorithms ESA '94 : Second Annual European Symposium Utrecht, The Netherlands, September 26 - 28, 1994 Proceedings, Lecture notes in computer science. 855 Springer 1994, pp. 307-318.


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.

Download: [img] Postscript - Preprinted Version
Download (262kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr95-212
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:19
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/212