Find in Library
Search millions of books, articles, and more
Indexed Open Access Databases
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.