research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Proceedings
Entered by:ichatz
TitlePoster Proceedings of the 4th WEA 2005
Bibtex cite IDRACTI-RU1-2005-24
Booktitle 4th International Workshop on Efficient and Experimental Algorithms (WEA)
Year published 2005
Publisher Ellinika Grammata and CTI Press
ISBN 960-442-034-8
We consider in this paper the problem of scheduling a set of independent 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 minsum. 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).
Chatzigiannakis, Ioannis
Nikoletseas, Sotiris
WEA05posters.pdf (main file)
Publication ID266