LIP6 2008/002

• Rapports de recherche
  Performance dans le pire des cas de l'algortihme de Garey-Johnson
• C. Hanen, Y. Zinder
• 33 pages - 20/11/2008- document en - http://www.lip6.fr/lip6/reports/2008/lip6-2008-001.pdf - 226 Ko
• Contact : Claire.Hanen (at) nulllip6.fr
• Équipe : RO
L'algorithme de Garey et Johnson permet de construire un ordonnancement de latence minimal pour un problème d'ordonnancement de tâches unitaires et dépendantes sur deux machines identiques, en présence de dates de disponibilité et de dates d'échéances. Cet article traite de la généralisation de cet algorithme au cas de m machines identiques, et analyse sa performance dans le pire des cas. Contrairement aux autres algorithmes connus pour la recherche de la latence minimale, le ratio de performance pour un nombre pair de machine est différent du ratio pour un nombre impair de machines. Nous montrons également que cette borne est atteinte.
• Mots clés : ordonnancement, machines parallèles, tâches unitaires, contraintes de précédence, latence, retard, dates de disponibilité, dates d'échéance
• Directeur de la publication : Thierry.Lanfroy (at) nulllip6.fr