Présentation

• Nous voulons affecter n tâches de durées variées à m machines indentiques (par exemple, des processeurs qui travaillent en parallèle), de façon à minimiser le délai qui sépare le lancement de la première tâche, de la fin de l'exécution de la dernière tâche. Nous supposons que ces tâches sont indépendantes: aucune n'a besoin d'attendre des résultats provenant d'une autre tâche.
• Ce problème est NP-complet; nous nous intéressons à plusieurs algorithmes donnant une solution approchée. La qualité d'un algorithme est résumée par la borne supérieure K du rapport T_algo/T_min entre la durée requise lorsque l'on déroule cet algorithme, et la durée minimale que l'on pourrait espérer.
• Le premier algorithme consiste à numéroter les tâches, puis à associer chaque tâche au premier processeur disponible. Nous montrons qu'avec cet algorithme, K=2.
• Le deuxième algorithme se base sur la remarque suivante: la borne précédente est approchée (mais jamais atteinte) en plaçant une tâche longue après de nombreuses tâches courtes. Il est donc intéressant de trier les tâches par ordre décroissant de durée. Nous montrons qu'avec ce nouvel algorithme, la borne devient K=4/3.
• Dans une dernière partie, nous mettons en oeuvre en Caml les idées précédentes.