Semi-online preemptive scheduling: one algorithm for all variants
From MaRDI portal
Publication:537921
DOI10.1007/s00224-010-9287-2zbMath1217.68249OpenAlexW2114146991MaRDI QIDQ537921
Publication date: 23 May 2011
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1840/
Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Online algorithms; streaming algorithms (68W27)
Related Items
A survey on makespan minimization in semi-online environments ⋮ Semi-online scheduling: a survey ⋮ 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 ⋮ Parallel solutions for preemptive makespan scheduling on two identical machines ⋮ The online knapsack problem: advice and randomization ⋮ Unnamed Item ⋮ On the optimality of the LP-based algorithm for online scheduling with GoS eligibility constraints ⋮ A lower bound on deterministic online algorithms for scheduling on related machines without preemption ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs
Cites Work
- Optimal preemptive semi-online scheduling on two uniform processors
- Semi-online scheduling problems on two identical machines with inexact partial information
- Preemptive online scheduling: Optimal algorithms for all speeds
- Optimal and online preemptive scheduling on uniformly related machines
- Semi on-line algorithms for the partition problem
- Semi on-line scheduling on two identical machines
- Preemptive on-line scheduling for two uniform processors
- Optimal preemptive semi-online scheduling to minimize makespan on two related machines
- Semi-on-line problems on two identical machines with combined partial information
- A note on on-line scheduling with partial information
- Optimal algorithms for semi-online preemptive scheduling problems on two uniform machines
- Competitive paging with locality of reference
- An optimal algorithm for preemptive on-line scheduling
- A lower bound for on-line scheduling on uniformly related machines
- Semi-online scheduling with ``end of sequence information
- Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information
- The Power of Reordering for Online Minimum Makespan Scheduling
- A Level Algorithm for Preemptive Scheduling
- Preemptive Scheduling of Uniform Processor Systems
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Preemptive Online Scheduling with Reordering
- Semi-online scheduling with decreasing job sizes
- Randomized on-line scheduling on two uniform machines
