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
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
