UET-UCT scheduling on 2 processors with constrained communications

C. PICOULEAU

IBP-Litp 1996/13: Rapport de Recherche Litp / Litp research reports
11 pages - Mars/March 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: UET-UCT scheduling on 2 processors with constrained communications

Résumé : Nous nous intéressons au problème d'ordonnancement d'un graphe de tâches UET-UCT sur 2 processeurs. Au problème classique, nous ajoutons des contraintes limitant le nombre de communications par unité de temps. Nous montrons des résultats de NP-complétude pour des graphes arbitraires et concevons un algorithme linéaire pour les arborescences.

Abstract : We are interested in the problem of scheduling a UET-UCT task graph on 2 identical processors To the classical problem are added constraints limiting the number of communications per unit of time. We prove NP-completeness results for arbitrary precedence graphs and polynomial algorithms for trees

Publications internes Litp 1996 / Litp research reports 1996