An approximation algorithm for problem P, S1 vertical stroke S_i=1 vertical stroke sum C_i

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 done by a single server. The objective is to minimize the sum of the completion times in the case of unit setup times and arbitrary processing times. For this strongly NP-hard problem, we give an approximation algorithm with an absolute error bounded by the product of the number of short jobs (with processing times less than m-1) and m-2. (orig.)Available from TIB Hannover: RR 4487(2000,1) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman