LPT Parallel-Machine Load Balance
Balance known job lengths across identical machines and measure greedy scheduling loss.
Free theory articleBalance known job lengths across identical machines and measure greedy scheduling loss.
Concept & interpretation
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.
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.