Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
Lower Bounds and Semi On-line Multiprocessor Scheduling
Authors: T.C. Edwin Cheng, Hans Kellerer, Vladimir Kotov
– 0.18 Mb
Abstract
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,
E-mail:
Hans Kellerer,
Institut fur Statistik und Operations Research,
Universitat Graz,
Universitatsstrabe 15, A-8010 Graz, Austria,
E-mail:
Vladimir Kotov,
Belarusian State University,
Faculty of Applied Mathematics and Computer Science,
Belarusian State University,
Skarina ave.4, Minsk, 220050, Belarus
E-mail:
T.C. Edwin Cheng,
Department of Management,
The Hong Kong Polytecnic University,
Kowloon, Hong Kong,
E-mail:
Hans Kellerer,
Institut fur Statistik und Operations Research,
Universitat Graz,
Universitatsstrabe 15, A-8010 Graz, Austria,
E-mail:
Vladimir Kotov,
Belarusian State University,
Faculty of Applied Mathematics and Computer Science,
Belarusian State University,
Skarina ave.4, Minsk, 220050, Belarus
E-mail:
Fulltext
– 0.18 Mb
Contents
- Polynomial time algorithm for solving cyclic games
- Gray Code for Cayley Permutations
- Quasi-stability of a vector trajectorial problem with non-linear partial criteria
- Finite fields and cryptology
- Mobile Communications World: Security Implementations Aspects - A State of the Art
- Combined Randomized-Local Hough Transform versus UpWrite Transform in stamp detection
- Lower Bounds and Semi On-line Multiprocessor Scheduling
