A note on LPT scheduling

DOI10.1016/0167-6377(93)90024-BMaRDI QIDQ5906502zbMATH OpenOpenAlexFDO

Authors 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

heuristicsidentical parallel machineslargest processing-time-firstparallel-machine schedulingworst-case performance

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• A note on LPT scheduling
• A note on the Coffman-Sethi bound for LPT scheduling
• New approximation bounds for LPT scheduling
• A note on generalizing the maximum lateness criterion for scheduling
• A note on ``The general lotsizing and scheduling problem
• Performance of the LPT algorithm in multiprocessor scheduling
• A note to independent sets in scheduling
• Tighter approximation bounds for LPT scheduling in two special cases
• Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
• A note on single processor scheduling with time restrictions

Cites work

• `` Strong NP-Completeness Results
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 3521517 (Why is no real title available?)
• Worst-case analysis of heuristics for open shops with parallel machines

Cited in

(19)

• The rate of convergence to optimality of the LPT rule
• The exact LPT-bound for maximizing the minimum completion time
• The \(k\)-partitioning problem
• Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
• The longest processing time rule for identical parallel machines revisited
• A note on the Coffman-Sethi bound for LPT scheduling
• New approximation bounds for LPT scheduling
• A note on posterior tight worst-case bounds for longest processing time schedules
• A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
• Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems
• A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem
• Comparing the minimum completion times of two longest-first scheduling-heuristics
• Graham's example is the only tight one for \(P \parallel C_{max}\)
• scientific article; zbMATH DE number 8821 (Why is no real title available?)
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• PERMUTATION-BASED GENETIC, TABU, AND VARIABLE NEIGHBORHOOD SEARCH HEURISTICS FOR MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS
• Performance of the LPT algorithm in multiprocessor scheduling
• The LPT heuristic for minimizing total load on a proportionate openshop
• Approximation ratio of LD algorithm for multi-processor scheduling and the Coffman-Sethi conjecture

This page was built for publication: A note on LPT scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906502)