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

**Series:** 2000-01, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**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

**This paper was published in:**

Information Processing Letters, Vol. 79, 2001, 291 - 296.