Parametric LPT-bound on parallel machine scheduling with nonsimultaneous machine available time

0.00 Avg rating—0 Votes

Article ID:	iaor20003425
Country:	Singapore
Volume:	15
Issue:	1
Start Page Number:	29
End Page Number:	36
Publication Date:	May 1998
Journal:	Asia-Pacific Journal of Operational Research
Authors:	Yong H.E.
Keywords:	heuristics

Abstract:

This paper addresses the problem of scheduling n independent jobs on m identical machines in order to minimize the makespan. The jobs are available at time zero, while some machines may not be. Lee analyzed the worst case performance ratio of the LPT algorithm. The author generalizes his result and give a tight parametric bound which shows that LPT scheduling is asymptotically optimal.

Reviews

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