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

**Series:** 1998-05, Preprints

- MSC:
- 90C10 Integer programming
- 90C25 Convex programming

**Abstract:**

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$.

**Keywords:**

multiprocessor scheduling, on-line, worst-case performance