98-05
Semi On-line algorithm for Multiprocessor Scheduling Problem
by Girlich, E.; Kotov, V.; Kovalev, M.
Preprint series: 98-05, Preprints
- MSC:
- 90C10 Integer programming
- 90C25 Convex programming
Abstract: Multiprocessor 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