Seuil d'approximation pour le modèle UET-UCT en présence d'une infinité de processeurs

摘要

We propose a new approach for the proof of classical scheduling problem with communication delay. We study the problem of minimizing the makespan for the multiprocessor scheduling problem in the presence of a communication delay. We consider the problem in which all the tasks, in the precedence graph admit an unit execution time and the multiprocessor system is constituted by an unrestricted number of processors. The communication delays between two adjacency tasks i and j which are executed on two different processors is equal to one unit oj time (UET-UCT model). In such a context, we prove that there is no heuristic with performance guarantee smaller than 7/6 (resp. 9/8) for the minimization of the length of the schedule (resp. the sum of the completion time).%Nous proposons une nouvelle approche pour la démonstration de la NP-complêtude pour l'un des problèmes central de l'ordonnancement avec délais de communication. Nous nous intéressons au problème où toutes les tâches du graphe de précédence ont une durée unitaire et où le système multiprocesseur est constitué d'un nombre non borné de processeurs. Le délai de communication pour transférer les données entre une tâche prédécesseur i et une tâche successeur j exécutée sur des processeurs différents dure une unité de temps (modèle UET-UCT). Dans ce cadre, nous allons redémontrer qu 'il n 'existe pas d'algorithme avec une garantie de performance inférieure à 7/6 (resp. 9/8) pour le cas de la minimisation de la longueur de l'ordonnancement (resp. de la somme des temps de complétude).