Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions

DOI10.1007/S00291-016-0431-5MaRDI QIDQ280185zbMATH OpenOpenAlexFDO

Authors Oliver Braun, Fan Chung, Ron Graham

Publication date 4 May 2016

Published in OR Spectrum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00291-016-0431-5

zbMATH Keywords

schedulinglongest processing time firstLPT algorithmtime restrictionsworst-case analysis

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Single-processor scheduling with time restrictions
• A note on LPT scheduling
• Performance of the LPT algorithm in multiprocessor scheduling
• scientific article; zbMATH DE number 1094170
• Scheduling Independent Tasks on Uniform Processors

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Single-processor scheduling with time restrictions

Cited in

(10)

• A Worst-case Performance of the Shortest-processing-time Heuristic for Single Machine Scheduling
• On the NP-hardness of scheduling with time restrictions
• Editorial ``Project management and scheduling
• Single-processor scheduling with time restrictions
• The single-processor scheduling problem with time restrictions: complexity and related problems
• On the minimum number of resources for a perfect schedule
• Lower bounds for online scheduling on four processors
• scientific article; zbMATH DE number 1094170 (Why is no real title available?)
• EPTAS for parallel identical machine scheduling with time restrictions
• Better permutations for the single-processor scheduling with time restrictions

This page was built for publication: Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions

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