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...
| Main Authors: | , , |
|---|---|
| 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 |