A variation of Graham’s LPT-algorithm

0.00 Avg rating—0 Votes

Article ID:	iaor19931348
Country:	Belgium
Volume:	31
Start Page Number:	63
End Page Number:	68
Publication Date:	Nov 1991
Journal:	Belgian Journal of Operations Research, Statistics and Computer Science
Authors:	Hassler Hannes, Woeginger Gerhard J.
Keywords:	Graham's LPT algorithm

Abstract:

The authors consider the problem of scheduling a set of n jobs nonpreemptively on m identical machines. The goal is to minimize C*, the maximum completion time over all jobs. This problem is known to be NP-complete. We present a class of new approximation algorithms that have low running time O(nlogm) and guarantee the worst case performance of Graham’s famous LPT-algorithm.

Reviews

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