A modified LPT algorithm for the two uniform parallel machine makespan minimization problem

DOI10.1016/j.ejor.2008.02.008zbMath1161.90396MaRDI QIDQ2378450

Christos P. Koulamas, Kyparisis, George J.

Publication date: 8 January 2009

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2008.02.008

zbMATH Keywords

scheduling; approximation algorithms; LPT; uniform parallel machines

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C59: Approximation methods and heuristics in mathematical programming

Related Items

The LPT heuristic for minimizing total load on a proportionate openshop, A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem, Minimizing resource consumption on uniform parallel machines with a bound on makespan, Online scheduling of malleable parallel jobs with setup times on two identical machines, Scheduling identical parallel machines with tooling constraints, Distributionally robust scheduling on parallel machines under moment uncertainty, Uniform parallel machine scheduling with resource consumption constraint, Single parameter analysis of power of preemption on two and three uniform machines

Cites Work

• An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines
• A heuristic for maximizing the number of on-time jobs on two uniform parallel machines
• Bounds for LPT Schedules on Uniform Processors
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• Bounds on Multiprocessing Timing Anomalies
• Optimal non-preemptive semi-online scheduling on two related machines