A best-compromise bicriteria scheduling algorithm for malleable tasks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

A best-compromise bicriteria scheduling algorithm for malleable tasks

Pierre-François Dutot
Denis Trystram

Résumé

We consider in this paper the problem of scheduling a set of inde- pendent parallel tasks (jobs) with respect to two criteria, namely, the makespan (time of the last finishing job) and the minsum (average completion time). There exist several algorithms with a good performance guaranty for one of these criteria. We are interested here in studying the optimization of both criteria simultaneously. The numerical values are given for the moldable task model, where the execution time of a task depends on the number of processors alloted to it. The main result of this paper is to derive explicitly a family of algorithms guaranteed for both the minsum and the makespan. The performance guaranty of these algorithms is better than the best algorithms known so far. The Guaranty curve of the family is the set of all points (x; y) such that there is an algorithm with guarantees x on makespan and y on the min-sum. When the ratio on the minsum increases, the curve tends to the best ratio known for the makespan for moldable tasks (3/2). One extremal point of the curves is a (3;6)-approximation algorithm. Finally a randomized version is given, which improves this results to (3;4.08).
Fichier principal
Vignette du fichier
dt_wea05.pdf (148.98 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00001080 , version 1 (01-02-2006)

Identifiants

  • HAL Id : inria-00001080 , version 1

Citer

Pierre-François Dutot, Denis Trystram. A best-compromise bicriteria scheduling algorithm for malleable tasks. Workshop on Efficient Algorithms, May 2005, Santorini Island, Greece. ⟨inria-00001080⟩
181 Consultations
102 Téléchargements

Partager

Gmail Facebook X LinkedIn More