For the basic problem of non‐preemptively scheduling n independent jobs on m identical parallel machines so that the minimum (or earliest) machine completion time is maximized, we compare the performance relationship between two well‐known longest‐first heuristics–the LPT‐ (longest processing time) and the RLPT‐heuristic (restricted LPT). We provide insights into the solution structure of these two sequencing heuristics and prove that the minimum completion time of the LPT‐schedule is at least as long as the minimum completion time of the RLPT‐schedule. Furthermore, we show that the minimum completion time of the RLPT‐heuristic always remains within a factor of 1/m of the optimal minimum completion time. The paper finishes with a comprehensive experimental study of the probabilistic behavior of RLPT‐schedules compared to LPT‐schedules in the two‐machine case.
