Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm (Q806667)

The well-known, NP-complete problem of scheduling a set of n independent jobs nonpreemptively on m identical parallel processors to minimize the maximum finish time is considered. Let \(\omega_ 0\) be the finish time of an optimal schedule and \(\omega\) the finish time of a schedule found by the Longest Processing Time (LPT-)heuristic. We will improve the Graham-bound for the LPT-heuristic \((\omega /\omega_ 0\leq 4/3-1/3m)\), which is tight in general, by considering only jobs with similar processing times.