Optimal semi-online preemptive algorithms for machine covering on two uniform machines

DOI10.1016/J.TCS.2005.02.008MaRDI QIDQ557905zbMATH OpenOpenAlexFDO

Authors Yiwei Jiang, Yong He

Publication date 30 June 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2005.02.008

zbMATH Keywords

Competitive ratioMachine coveringOnline algorithmPreemptive scheduling

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
• Preemptive machine covering on parallel machines
• Optimal preemptive online algorithms for scheduling with known largest size on two uniform machines
• Semi-online machine covering for two uniform machines
• Semi-online machine covering on two uniform machines with known total size

Cites work

• scientific article; zbMATH DE number 1182760 (Why is no real title available?)
• A Level Algorithm for Preemptive Scheduling
• A lower bound for randomized on-line multiprocessor scheduling
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• An optimal algorithm for preemptive on-line scheduling
• Bin stretching revisited
• On-line bin-stretching
• On-line machine covering
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Ordinal algorithms for parallel machine scheduling
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Preemptive Scheduling of Uniform Processor Systems
• Preemptive machine covering on parallel machines
• Preemptive on-line scheduling for two uniform processors
• Randomized on-line and semi-on-line scheduling on identical machines
• Randomized on-line scheduling on two uniform machines
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• Semi-on-line problems on two identical machines with combined partial information
• Semi-on-line scheduling with ordinal data on two uniform machines
• 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

(8)

• General max-min fair allocation
• Approximation schemes for scheduling and covering on unrelated machines
• Polynomial-time combinatorial algorithm for general max-min fair allocation
• Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information
• Approximation and Online Algorithms
• Semi-online machine covering for two uniform machines
• Preemptive semi-online algorithms for parallel machine scheduling with known total size
• Preemptive machine covering on parallel machines

This page was built for publication: Optimal semi-online preemptive algorithms for machine covering on two uniform machines

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