Semi on-line algorithm for multiprocessor scheduling problem with a given total processing time

Mutiprocessor scheduling problem is one of the basic NP-complete problem. There are a lot of efficient heuristics for this problem but no heuristic for the on-line problem can have a worst-case performance lower than 1+1/#sq root#2 for m #>=# 4 and becames 1.837 for m large enough. In this paper we investigate a semi on-line version of multiprocessor scheduling problem when the total processing time of jobs is known in advance. For this version we propose a heuristic and investigate its worst-case performance which is 5/3. (orig.)SIGLEAvailable from TIB Hannover: RR 4487(1998,5) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman