The worst-case analysis of the Garey–Johnson algorithm

The worst-case analysis of the Garey–Johnson algorithm

0.00 Avg rating0 Votes
Article ID: iaor200971279
Country: United Kingdom
Volume: 12
Issue: 4
Start Page Number: 389
End Page Number: 400
Publication Date: Aug 2009
Journal: Journal of Scheduling
Authors: ,
Abstract:

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 generalization 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.

Reviews

Required fields are marked *. Your email address will not be published.