Zurück zu den Preprints des Jahres 1998


Semi On-line algorithm for Multiprocessor Scheduling Problem

by Girlich, E., Kotov, V., Kovalev, M..

Series: 1998-05, Preprints

90C10 Integer programming
90C25 Convex programming

tiprocessor 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/ \sqrt{2}$ for $m \ge 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$.

multiprocessor scheduling, on-line, worst-case performance