Lower Bounds and Semi On-line Multiprocessor Scheduling

Lower Bounds and Semi On-line Multiprocessor Scheduling

We are given a set of identical machines and a sequence of jobs from which we know the sum of the job weights in advance. The jobs have to be assigned on-line to one of the machines and the objective is to minimize the makespan. An algorithm with performance ratio 1.6 and a lower bound of 1.5 is pre...

Full description

Bibliographic Details
Main Authors: T.C. Edwin Cheng, Hans Kellerer, Vladimir Kotov
Format: Article
Language:English
Published: Vladimir Andrunachievici Institute of Mathematics and Computer Science 2003-10-01
Series:Computer Science Journal of Moldova
Online Access:http://www.math.md/files/csjm/v11-n2/v11-n2-(pp209-228).pdf

Similar Items

Similar Items