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

DOI10.1016/j.ejor.2008.02.008zbMath1161.90396OpenAlexW2013292956MaRDI 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

schedulingapproximation algorithmsLPTuniform parallel machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

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 ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ Distributionally robust scheduling on parallel machines under moment uncertainty ⋮ Scheduling identical parallel machines with tooling constraints ⋮ Uniform parallel machine scheduling with resource consumption constraint ⋮ Online scheduling of malleable parallel jobs with setup times on two identical machines ⋮ 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