LIP6 2008/002

• Reports
  Performance dans le pire des cas de l'algortihme de Garey-Johnson
• C. Hanen, Y. Zinder
• 33 pages - 11/20/2008- document en - http://www.lip6.fr/lip6/reports/2008/lip6-2008-001.pdf - 226 Ko
• Contact : Claire.Hanen (at) nulllip6.fr
• Team : RO
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.
• Keywords : scheduling, parallel machines, UET tasks, precedence constraints, maximum lateness, release times, due dates
• Publisher : Thierry.Lanfroy (at) nulllip6.fr