A two machine sequencing approximation algorithm for maximizing the number of early jobs

A two machine sequencing approximation algorithm for maximizing the number of early jobs

0.00 Avg rating—0 Votes
Article ID: iaor20043569
Country: China
Volume: 18A
Issue: 2
Start Page Number: 207
End Page Number: 212
Publication Date: Jun 2003
Journal: Applied Mathematics (A Journal of Chinese Universities)
Authors: ,
Abstract:

The problem of scheduling m parallel machines to maximise the number of early jobs is NP-hard when m ≥ 2. In this paper, an approximation algorithm is given for the problem with m ≥ 2 of which the absolute performance ratio is 0.75. A further, related problem is also studied. In this case the asymptotic performance ratio of the algorithm is 2/3.

Reviews

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