This paper is devoted to some heuristics for the problem P ‖ Cmax. This problem is known to be NP-complete. Graham's list scheduling method is generalized in the following way: First a nonincreasing processing time order of the tasks is determined. Then the next two steps are iterated: 1: Find the best possible allocation of the next k tasks. 2: Assign only the next task accordingly to this schedule. We prove that this algorithm improves the theoretical efficiency of Graham's algorithm, and we also give some numerical results.
