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

DOI10.1016/j.tcs.2005.02.008zbMath1142.90401OpenAlexW1979623539MaRDI QIDQ557905

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

Online algorithmCompetitive ratioMachine coveringPreemptive scheduling

Mathematics Subject Classification ID

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

Related Items (6)

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

Cites Work

• Unnamed Item
• Unnamed Item
• A lower bound for randomized on-line multiprocessor scheduling
• The exact LPT-bound for maximizing the minimum completion time
• Semi on-line algorithms for the partition problem
• Semi on-line scheduling on two identical machines
• Preemptive on-line scheduling for two uniform processors
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Bin stretching revisited
• The optimal on-line parallel machine scheduling
• Ordinal on-line scheduling for maximizing the minimum machine completion time
• Optimal preemptive semi-online scheduling to minimize makespan on two related machines
• Semi-on-line problems on two identical machines with combined partial information
• An optimal algorithm for preemptive on-line scheduling
• Ordinal algorithms for parallel machine scheduling
• Preemptive machine covering on parallel machines
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• A Level Algorithm for Preemptive Scheduling
• Preemptive Scheduling of Uniform Processor Systems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• On-line machine covering
• Semi-online scheduling with decreasing job sizes
• Randomized on-line scheduling on two uniform machines
• Semi-on-line scheduling with ordinal data on two uniform machines
• On-line bin-stretching

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