A note on LPT scheduling

DOI10.1016/0167-6377(93)90024-BzbMath0803.90075OpenAlexW1987426319MaRDI QIDQ5906502

Bo Chen

Publication date: 12 April 1994

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(93)90024-b

zbMATH Keywords

heuristicsworst-case performanceidentical parallel machinesparallel-machine schedulinglargest processing-time-first

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem ⋮ The longest processing time rule for identical parallel machines revisited ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ The LPT heuristic for minimizing total load on a proportionate openshop ⋮ A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem ⋮ PERMUTATION-BASED GENETIC, TABU, AND VARIABLE NEIGHBORHOOD SEARCH HEURISTICS FOR MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS ⋮ Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems ⋮ The \(k\)-partitioning problem ⋮ Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs ⋮ A note on the Coffman-Sethi bound for LPT scheduling

Cites Work

• Unnamed Item
• Worst-case analysis of heuristics for open shops with parallel machines
• `` Strong NP-Completeness Results
• Bounds on Multiprocessing Timing Anomalies