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

DOI10.1007/978-3-540-93980-1_4MaRDI QIDQ3602828zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• On-line scheduling to maximize task completions.
• Online Scheduling of Equal-Length Jobs on Parallel Machines
• Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
• Online Scheduling with Hard Deadlines
• 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
• Online scheduling with preemption or non-completion penalties
• Multi-machine scheduling lower bounds using decision diagrams

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)