Randomized on-line scheduling on two uniform machines
From MaRDI portal
Publication:5937432
DOI10.1002/jos.60zbMath0989.90059OpenAlexW2119226317MaRDI QIDQ5937432
Gerhard J. Woeginger, Jiří Sgall, John Noga, Steve Seiden, Leah Epstein
Publication date: 12 July 2001
Published in: Journal of Scheduling (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jos.60
Related Items (51)
Online-bounded analysis ⋮ A survey on makespan minimization in semi-online environments ⋮ Optimal preemptive semi-online scheduling on two uniform processors ⋮ Online Hierarchical Scheduling on Two Uniform Machines with Bounded Job Sizes ⋮ Separating online scheduling algorithms with the relative worst order ratio ⋮ On-line scheduling on parallel machines to minimize the makespan ⋮ Semi-online machine covering on two uniform machines with known total size ⋮ Semi-online scheduling with bounded job sizes on two uniform machines ⋮ A note on hierarchical scheduling on two uniform machines ⋮ Semi-online scheduling problems on two uniform machines under a grade of service provision ⋮ Online algorithms for scheduling with machine activation cost on two uniform machines ⋮ Semi-online scheduling with known maximum job size on two uniform machines ⋮ Lower bounds for online makespan minimization on a small number of related machines ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Semi-online early work maximization problems on two hierarchical uniform machines with partial information of processing time ⋮ Bin stretching with migration on two hierarchical machines ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ Optimal semi-online algorithm for scheduling with rejection on two uniform machines ⋮ Scheduling on two identical machines with a speed-up resource ⋮ Competitive ratio of list scheduling on uniform machines and randomized heuristics ⋮ Online scheduling with rejection and withdrawal ⋮ Approximate strong equilibria in job scheduling games with two uniformly related machines ⋮ Preemptive scheduling on a small number of hierarchical machines ⋮ Optimal on-line algorithms to minimize makespan on two machines with resource augmentation ⋮ Robust algorithms for preemptive scheduling ⋮ Semi-online scheduling with ``end of sequence information ⋮ Semi-online scheduling on two uniform machines with the known largest size ⋮ Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling ⋮ Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ Semi-online scheduling on two uniform processors ⋮ Semi-online preemptive scheduling: one algorithm for all variants ⋮ Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data ⋮ Optimal semi-online preemptive algorithms for machine covering on two uniform machines ⋮ Online scheduling with a buffer on related machines ⋮ Online scheduling with reassignment on two uniform machines ⋮ Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios ⋮ Online scheduling of jobs with favorite machines ⋮ OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES ⋮ Preemptive online scheduling: Optimal algorithms for all speeds ⋮ Online scheduling on two uniform machines to minimize the makespan ⋮ Starting time minimization for the maximum job variant ⋮ Online scheduling on three uniform machines ⋮ Tight lower bounds for semi-online scheduling on two uniform machines with known optimum ⋮ Optimal and online preemptive scheduling on uniformly related machines ⋮ Optimal online algorithms for MapReduce scheduling on two uniform machines ⋮ On-line preemptive machine scheduling with \(\ell _p\) norm on two uniform machines ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption ⋮ Preemptive machine covering on parallel machines ⋮ Optimal preemptive semi-online scheduling to minimize makespan on two related machines ⋮ Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines
Cites Work
- Unnamed Item
- A better lower bound on the competitive ratio of the randomized 2-server problem
- A strongly competitive randomized paging algorithm
- New algorithms for an ancient scheduling problem.
- Preemptive on-line scheduling for two uniform processors
- Online randomized multiprocessor scheduling
- A randomized algorithm for two servers on the line.
- New lower and upper bounds for on-line scheduling
- A lower bound for on-line scheduling on uniformly related machines
- A comment on scheduling on uniform machines under chain-type precedence constraints
- Bounds for List Schedules on Uniform Processors
- Better Bounds for Online Scheduling
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- Bounds for Certain Multiprocessing Anomalies
This page was built for publication: Randomized on-line scheduling on two uniform machines
