A best-compromise bicriteria scheduling algorithm for malleable tasks

Pierre-François Dutot 1 Denis Trystram 1
1 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Abstract : 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).
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00001080
Contributor : Pierre-François Dutot <>
Submitted on : Wednesday, February 1, 2006 - 6:28:39 PM
Last modification on : Wednesday, March 13, 2019 - 2:58:27 PM
Long-term archiving on : Saturday, April 3, 2010 - 10:03:01 PM

Identifiers

  • HAL Id : inria-00001080, version 1

Collections

INRIA | IMAG | UGA

Citation

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⟩

Share

Metrics

Record views

318

Files downloads

132