History

Please fill in your query. A complete syntax description you will find on the General Help page.
Extending Graham’s result on scheduling to other heuristics. (English)
Oper. Res. Lett. 29, No.4, 149-153 (2001).
Summary: 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\over 3}-1/3k$ for the competitive ratios under the $C_{\max}$ norm applies to all algorithms of this class.