On-line scheduling of independent dedicated multiprocessor tasks. submitted

We study the offline and online versions of the well known problem of scheduling a set of n indepen-dent multiprocessor tasks with prespecified processor allocations on a set of identical processors in order to minimize the makespan. Recently, in [13], 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 1 2 −ε, neither for some ε> 0, un-less P = NP; nor for any ε> 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 online scheduling versions, and show that its competitive ratio is bounded by 2 √ m and 2 √ 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 √ m-approximation algorithm for the offline version of the problem. Finally, by using some ideas from [21], we adapt the algorithm to the online 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 √ m. Due to th