We study the on-line version of the well known problem of scheduling a set of $n$ independent multiprocessor tasks with prespecified processor allocations on a set of identical processors in order to minimize the makespan. Recently, it has been proven that even in the off-line case with unit processing time tasks no polynomial time approximation algorithm can be found with approximation factor $m^{{1}/{2}-\eps}$ for any $\eps >0$, unless \NP=\ZPP. We first study simple approximation and on-line algorithms based on the classical first-fit technique. Then, by using a split-round technique, we give a $3 \sqrt{m}$-approximation algorithm for the off-line version of the problem. Finally, we adapt this algorithm to the on-line case, in the paradigm of tasks arriving over time, and show that its competitive ratio is bounded by $(6\sqrt{m}+1)$. Due to the conducted experimental results, which also analyzed here, we conclude that our algorithms can also perform well in practice.
Scheduling of Independent Dedicated Multiprocessor Tasks
Caramia M;
2002
Abstract
We study the on-line version of the well known problem of scheduling a set of $n$ independent multiprocessor tasks with prespecified processor allocations on a set of identical processors in order to minimize the makespan. Recently, it has been proven that even in the off-line case with unit processing time tasks no polynomial time approximation algorithm can be found with approximation factor $m^{{1}/{2}-\eps}$ for any $\eps >0$, unless \NP=\ZPP. We first study simple approximation and on-line algorithms based on the classical first-fit technique. Then, by using a split-round technique, we give a $3 \sqrt{m}$-approximation algorithm for the off-line version of the problem. Finally, we adapt this algorithm to the on-line case, in the paradigm of tasks arriving over time, and show that its competitive ratio is bounded by $(6\sqrt{m}+1)$. Due to the conducted experimental results, which also analyzed here, we conclude that our algorithms can also perform well in practice.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
