We consider a semi on-line version of the multiprocessor scheduling problem on three processors, where the total size of the tasks is known in advance. We prove a lower bound 1 +(sqrt(129)−9)/6 > 1.3929 on the competitive ratio of any algorithm and propose a simple algorithm with competitive ratio equal to 1.5. The performance is improved to 1 + 8/19 < 1.4211 by a preprocessing strategy. The latter algorithm is only 2% away from the lower bound.
Semi on-line scheduling on three processors with known sum of the tasks
ANGELELLI, Enrico;SPERANZA, Maria Grazia;
2007-01-01
Abstract
We consider a semi on-line version of the multiprocessor scheduling problem on three processors, where the total size of the tasks is known in advance. We prove a lower bound 1 +(sqrt(129)−9)/6 > 1.3929 on the competitive ratio of any algorithm and propose a simple algorithm with competitive ratio equal to 1.5. The performance is improved to 1 + 8/19 < 1.4211 by a preprocessing strategy. The latter algorithm is only 2% away from the lower bound.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
3PJS-published.pdf
gestori archivio
Tipologia:
Full Text
Licenza:
DRM non definito
Dimensione
273.99 kB
Formato
Adobe PDF
|
273.99 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
