Universität zu Köln

Srivastav, Anand and Stangier, Peter (1994). Tight Approximation for Resource Constrained Scheduling and Bin Packing. Springer. ["eprint_fieldopt_monograph_type_preprint" not defined].

Preview

PDF zpr95-212.pdf Download (343kB) | Preview

Abstract

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.

Item Type:	Preprints, Working Papers or Reports (["eprint_fieldopt_monograph_type_preprint" not defined])
Creators:	Creators Email ORCID ORCID Put Code Srivastav, Anand UNSPECIFIED UNSPECIFIED UNSPECIFIED Stangier, Peter UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-547032
Series Name:	Lecture notes in computer science
Volume:	855
Page Range:	pp. 307-318
Date:	1994
Publisher:	Springer
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54703