Summary: We study the off and on-line versions 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 in the case when all tasks have unit processing time the problem cannot be approximated within a factor of \(m^{\frac{1}{2}-\varepsilon}\), neither for some \(\varepsilon>0\), unless PN = NP; nor for any \(\varepsilon>0\), unless NP = ZPP. For this special case we give a simple algorithm based on the classical first-fit technique. We analyze the algorithm for both tasks arrive over time and tasks arrive over list on-line scheduling versions, and show that its competitive ratio is bounded by \(2 \sqrt{m}\) and \(2 \sqrt{m}+1\), respectively. Here we also use some preliminary results on (vertex) coloring of \(k\)-tuple graphs. For the case of arbitrary processing times, we show that any algorithm which uses the first-fit technique cannot be better than \(m\) competitive. Then, by using our split-round technique, we give a \(3 \sqrt{m}\)-approximation algorithm for the off-line version of the problem. Finally, we adapt the algorithm to the on-line case, in the paradigm of tasks arriving over time in which the existence of a task is unknown until its release date, and show that its competitive ratio is bounded by \(6\sqrt{m}\). Due to the conducted experimental results, we conclude that our algorithms can perform well in practice.
For the entire collection see [Zbl 1007.00050].