An approximation algorithm for problem $P,S1 | s_i = 1 | \sum C_i$

by Kravchenko, S.A.; Werner, F.:


Preprint series: 00-01, Preprints

The paper is published: Information Processing Letters, Vol. 79, 2001, 291 - 296.

90B35 Scheduling theory, See also {68M20}


Abstract: In this note we consider the problem of scheduling a set of jobs on m identical parallel machines. For each job, a setup has to be doen by a single server. The objective is to minimize the sum of the completion times. For this strongly NP-hard problem, we give an approximation algortihm with an absolute error bounded by the product of the number of short jobs (with processing times less than m - 1) and m - 2.

Keywords: scheduling, parallel amchines, single server, unit setup times, total completion time, approximation algorithm

The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.