Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines

DOI10.1007/S10114-005-0829-5MaRDI QIDQ856832zbMATH OpenOpenAlexFDO

Authors Yiwei Jiang, Hao Zhou, Yong He

Publication date 13 December 2006

Published in Acta Mathematica Sinica, English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10114-005-0829-5

zbMATH Keywords

competitive ratiopreemptive schedulingsemi-onlineuniform machines

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Semi-online scheduling on two uniform machines with the known largest size
• An Optimal On-Line Algorithm for Preemptive Scheduling on Two Uniform Machines in the ℓ p Norm
• Preemptive stochastic online scheduling on two uniform machines
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• Optimal and online preemptive scheduling on uniformly related machines
• STACS 2004
• Optimal preemptive semi-online scheduling on two uniform processors
• Semi-online scheduling with known maximum job size on two uniform machines
• OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES

Cites work

• scientific article; zbMATH DE number 1182760 (Why is no real title available?)
• A Level Algorithm for Preemptive Scheduling
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• On-line machine covering
• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Preemptive Scheduling of Uniform Processor Systems
• Preemptive machine covering on parallel machines
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• Randomized on-line and semi-on-line scheduling on identical machines
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Semi-online scheduling with decreasing job sizes
• The exact LPT-bound for maximizing the minimum completion time
• The optimal on-line parallel machine scheduling

Cited in

(6)

• Optimal semi-online preemptive algorithms for machine covering on two uniform machines
• OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Linear time algorithms for parallel machine scheduling
• Semi-online scheduling on two uniform parallel machines with initial lookahead

This page was built for publication: Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines

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