Semi On-line algorithm for Multiprocessor Scheduling Problem

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


Preprint series: 98-05, Preprints

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

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster