The worst case analysis of the Garey-Johnson algorithm

Performance dans le pire des cas de l'algortihme de Garey-Johnson

Claire Hanen (1) , Yakov Zinder

1 RO - Recherche Opérationnelle

The Garey-Johnson algorithm is a well known polynomial-time algorithm constructing an optimal schedule for the maximum lateness problem with unit execution time tasks, two parallel identical processors, precedence constraints and release times. The paper is concerned with the worst-case analysis of a generalisation of the Garey-Johnson algorithm to the case of arbitrary number of processors. In contrast to other algorithms for the maximum lateness problem, the tight performance guarantee for the even number of processors differs from the tight performance guarantee for the odd number of processors.

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.

Keywords: scheduling; parallel machines; UET tasks; precedence constraints; maximum lateness; release times; due dates

Keywords: ordonnancement; machines parallèles; tâches unitaires; contraintes de précédence; latence; retard; dates de disponibilité; dates d'échéance

Domains: Computer Science [cs]

Claire Hanen, Yakov Zinder. The worst case analysis of the Garey-Johnson algorithm. [Research Report] lip6.2008.002, LIP6. 2008. ⟨hal-02545977⟩