Scheduling divisible loads with return messages on heterogeneous master-worker platforms

In this paper, we consider the problem of scheduling independent tasks, or divisible loads, onto an heterogeneous star platform, with both heterogeneous computing and communication resources. We consider the case where the workers, after processing the tasks, send back some results to the master processor. This corresponds to a more general framework than the one used in many divisible load papers, where only forward communications are taken into account. To the best of our knowledge, this paper constitutes the first attempt to derive optimality results under this general framework (forward and backward communications, heterogeneous processing and communication resources). We prove that it is possible to derive the optimal solution both for LIFO and FIFO distribution schemes. Nevertheless, the complexity of the general problem remains open: we also prove in the paper that the optimal distribution scheme may be neither LIFO nor FIFO.Nous nous intéressons ici au problème de l'ordonnancement de tâches divisibles sur une plate-forme de calcul hétérogène en étoile. L'hétérogénéité concerne les ressources de calcul comme les liens de communication. Nous considérons le cas où les esclaves, après avoir effectué des tâches, doivent envoyer les résultats obtenus au processeur maître. Ceci correspond à un schéma plus général que celui utilisé dans l'essentiel de la littérature sur les tâches divisibles, où seules les communications du maître vers les esclaves sont prises en compte.A notre connaissance, ceci est la première tentative pour obtenir des résultats d'optimalité pour ce problème général (communications dans les deux sens,hétérogénéité pour les puissances de calcul et de communication). Nous montrons qu'il est possible de concevoir des solutions optimales pour les schémas de communication FIFO et LIFO. Cependant, la complexité du problème reste ouverte : nous montrons également que le schéma de communication optimal peut n'être ni LIFO ni FIFO