Improved algorithm for a generalized on-line scheduling problem on identical machines

DOI10.1016/J.EJOR.2005.06.061MaRDI QIDQ2432940zbMATHOpenAlexFDO

Authors Rongheng Li, Huei-Chuen Huang

Publication date 25 October 2006

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2005.06.061

zbMATH Keywords

heuristicschedulingcompetitive ratiolist schedulingon-line

Mathematics Subject Classification ID

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

Recommendations

• On-line scheduling for jobs with arbitrary release times
• A Note on Online Scheduling for Jobs with Arbitrary Release Times
• On-line scheduling revisited
• On an on-line scheduling problem for parallel jobs
• A \(2.28\)-competitive algorithm for online scheduling on identical machines

Cites work

• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Better Bounds for Online Scheduling
• Bounds on Multiprocessing Timing Anomalies
• New algorithms for an ancient scheduling problem.
• New lower and upper bounds for on-line scheduling
• On-line scheduling for jobs with arbitrary release times
• On-line scheduling revisited

Cited in

(2)

• Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines
• Online scheduling of malleable parallel jobs with setup times on two identical machines

This page was built for publication: Improved algorithm for a generalized on-line scheduling problem on identical machines

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