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

DOI10.1007/s00291-016-0431-5zbMath1339.90128OpenAlexW2304111770MaRDI QIDQ280185

Oliver Braun, Ronald L. Graham, Fan R. K. Chung

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

schedulingworst-case analysislongest processing time firstLPT algorithmtime restrictions

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Editorial ``Project management and scheduling, On the NP-hardness of scheduling with time restrictions, On the minimum number of resources for a perfect schedule, EPTAS for parallel identical machine scheduling with time restrictions, Better permutations for the single-processor scheduling with time restrictions, The single-processor scheduling problem with time restrictions: complexity and related problems

Cites Work

• Single-processor scheduling with time restrictions
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Unnamed Item