Lower Bounds and Semi On-line Multiprocessor Scheduling

oleh: T.C. Edwin Cheng, Hans Kellerer, Vladimir Kotov

Format: Article
Diterbitkan: Vladimir Andrunachievici Institute of Mathematics and Computer Science 2003-10-01

Deskripsi

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 presented. This improves recent results by Azar and Regev who published an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance.