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

DOI10.1016/J.TCS.2005.02.008zbMATH Open1142.90401OpenAlexW1979623539MaRDI QIDQ557905FDOQ557905

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

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

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)

Cites Work

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

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)