Abstract | 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). |