LIP6 2001/016

• Rapports de recherche «Minimiser la durée d'un ordonnancement pour un graphe biparti sur un processeur avec un délai entier et des tâches de durée unitaire»
• A. Munier-Kordon
• 14 pages - 11/06/2001 - document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.016.pdf 172 Ko
• Contact Alix.Munier (at) nulllip6.fr
• Ancien Thème : SYSDEF
Nous considèrons un ensemble de tâches de durée unitaire et un graphe de delais de précédence biparti avec une valeur du delai d: tout arc (i,j) de ce graphe signifie que j doit être exécutée au moins d unités de temps après l'exécution de i. Le problème est alors de déterminer un ordonnancement des tâches sur un processeur de durée minimale. Dans un premier temps, nous montrons que le problème de décision associé est NP-complet. Puis, nous développons un algorithme polynomial non trivial dans le cas ou le degré de toutes les tâches de l'un des deux ensembles du graphe biparti est 2. Finalement, nous développons un algorithme approché de ratio de performance 3/2.