A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs

In this paper, we consider the problem of allocating a large number of independent, equal-sized tasks to a heterogeneous processor farm. The master processor and the p slaves have different computation and communication capabilities. We assume communication-computation overlap for each slave (and for the master), but the communication medium is exclusive: the master can only communicate with a single slave at each time-step. We give a polynomial-time algorithm to solve the following scheduling problem: given a time-bound T, what is the maximal number of tasks that can be processed by the master and the p slaves within T time-units?.Nous nous intéressons à l'ordonnancement des tâches indépendantes sur une plateforme maitre-esclave hétérogène, modélisée par un graphe fork. Le maitre et les p esclaves ont des vitesses de calcul différentes D e même , les liens de communication entre le maître et chaque esclave ont des capacités différentes. Le modèle autorise le recouvrement calcul-communication sur chaque processeur, mais on suppose que toutes les communications s'effectuent en mode 1-port : à tout instant, le maître ne peut envoyer qu'un seul message ( à un esclave donné).Nous présentons un algorithme polynomial pour résoudre le problème d'ordonnancement correspondant : étant donnée une borne temporelle T, maximiser le nombre total de tâches qui peuvent être effectuées par le maître et les p esclaves en temps T