Extending Graham's result on scheduling to other heuristics

This paper considers the off-line scheduling problem where a list of jobs must be scheduled on k-parallel processors. The heuristic of Graham is relaxed to create a class of algorithms which includes many well-known algorithms such as best fit, first fit, random fit and greedy. We show that Graham's upper bound of 4/3 – 1/3k for the competitive ratios under the Cmax norm applies to all algorithms of this class.