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.

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster