A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines

DOI10.1007/978-3-540-93980-1_4zbMATH Open1209.68657OpenAlexW2179080494MaRDI QIDQ3602828FDOQ3602828

Authors: Tomáš Ebenlendr, Jiří Sgall 

Publication date: 12 February 2009

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-93980-1_4

Recommendations

• Online Scheduling of Equal-Length Jobs on Parallel Machines
• Online scheduling of parallel jobs on two machines is 2-competitive
• A better lower bound for on-line scheduling
• scientific article; zbMATH DE number 1559597
• A Note on Online Scheduling for Jobs with Arbitrary Release Times

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Online Scheduling with Hard Deadlines
• On-line scheduling to maximize task completions.
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online Scheduling of Equal-Length Jobs on Parallel Machines
• Online Scheduling with Hard Deadlines on Parallel Machines
• Online, Non-preemptive Scheduling of Equal-Length Jobs on Two Identical Machines

Cited In (4)

• Online scheduling with immediate and reliable lead-time quotation
• A tight lower bound for job scheduling with cancellation
• Multi-machine scheduling lower bounds using decision diagrams
• Online scheduling with preemption or non-completion penalties

This page was built for publication: A Lower Bound for Scheduling of Unit Jobs with Immediate Decision on Parallel Machines

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