IMI/Publicaţii/CSJM/Ediţii/CSJM v.11, n.2 (32), 2003/

Lower Bounds and Semi On-line Multiprocessor Scheduling

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


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.

T.C. Edwin Cheng, Hans Kellerer, Vladimir Kotov,
T.C. Edwin Cheng,
Department of Management,
The Hong Kong Polytecnic University,
Kowloon, Hong Kong,
Hans Kellerer,
Institut fur Statistik und Operations Research,
Universitat Graz,
Universitatsstrabe 15, A-8010 Graz, Austria,
Vladimir Kotov,
Belarusian State University,
Faculty of Applied Mathematics and Computer Science,
Belarusian State University,
Skarina ave.4, Minsk, 220050, Belarus


Adobe PDF document0.18 Mb