The exact LPT-bound for maximizing the minimum completion time

The exact LPT-bound for maximizing the minimum completion time

0.00 Avg rating—0 Votes
Article ID: iaor1993990
Country: Netherlands
Volume: 11
Issue: 5
Start Page Number: 281
End Page Number: 287
Publication Date: Jun 1992
Journal: Operations Research Letters
Authors: , ,
Abstract:

The authors consider the problem of assigning a set of jobs to a system of m identical processors in order to maximize the earliest processor completion time. It was known that the LPT-heuristic gives an approximation of worst case ratio at most equ1. In this note the authors show that the exact worst case ratio of LPT is equ2.

Reviews

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