LPT Parallel-Machine Load Balance
Balance known job lengths across identical machines and measure greedy scheduling loss.
By Riano · Published · Updated · Report a correction
LPT Parallel-Machine Load Balance
When jobs of varying lengths arrive, deciding how to assign them to a fixed set of identical machines is a classic scheduling problem. The goal is to minimize the total time until all jobs are complete, known as the makespan.
Worked Example: Sorting and Assigning
Consider the "Tight two" instance on 2 machines. The jobs have processing times of 3, 3, 2, 2, and 2. We use the Longest Processing Time (LPT) rule, assigning the longest unassigned job to the currently least loaded machine.
| Job Index | Duration | M0 Load Before | M1 Load Before | Assigned Machine |
|---|---|---|---|---|
| 0 | 3 | 0 | 0 | M0 (tie break) |
| 1 | 3 | 3 | 0 | M1 |
| 2 | 2 | 3 | 3 | M0 (tie break) |
| 3 | 2 | 5 | 3 | M1 |
| 4 | 2 | 5 | 5 | M0 (tie break) |
The LPT algorithm completes in 7 units of time (M0 load is 7, M1 is 5). However, an optimal assignment can achieve a makespan of 6 by assigning jobs (3, 3) to M0 and (2, 2, 2) to M1.
Experiment: Comparing Schedules
Use the LPT Parallel-Machine Load Balance explorer to see how LPT performs compared to the optimal makespan across different scenarios.
- Set Jobs to "Tight two" and Machines to 2. The observed LPT makespan is 7, whereas the optimal is 6, giving an approximation ratio of exactly 7/6.
- Change Machines to 3. The makespan becomes 5 and matches the optimal, yielding a ratio of 1.0. The Graham bound (4/3 - 1/(3m)) strictly limits the worst-case error for LPT.
- Set Jobs to "Mixed" (lengths 7, 5, 4, 3, 2, 1) and Machines to 2. The LPT makespan is exactly 11, matching the optimal makespan.
Assumptions and Limitations
This module focuses strictly on offline, identical parallel machine scheduling without preemption. It assumes all job durations are known precisely in advance and that machines never fail. It uses an exact small-domain enumeration to find the true optimal makespan for comparison, which does not scale beyond a handful of jobs. LPT is an approximation algorithm; although it is extremely fast and effective, it is not an exact solver.
References
The 4/3 - 1/(3m) bound for Longest Processing Time scheduling on identical machines was famously proven by Ronald Graham. The original list scheduling and optimal partitioning are distinct concepts not to be confused with general interval scheduling.
- Advanced Algorithms (Cambridge) covers Graham's bound and parallel machine approximation.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive LPT Parallel-Machine Load Balance module.
Try LPT Parallel-Machine Load Balance on Riano →