A Tight 2-Approximation for Preemptive Stochastic Scheduling
From MaRDI portal
Publication:5247621
DOI10.1287/moor.2014.0653zbMath1312.90027OpenAlexW2059443493WikidataQ57399741 ScholiaQ57399741MaRDI QIDQ5247621
Publication date: 24 April 2015
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.2014.0653
Related Items (6)
Online Appointment Scheduling in the Random Order Model ⋮ Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ An adversarial model for scheduling with testing ⋮ On index policies for stochastic minsum scheduling
Cites Work
- Unnamed Item
- Unnamed Item
- Competitive analysis of preemptive single-machine scheduling
- On-line scheduling to minimize average completion time revisited.
- LP-based online scheduling: From single to parallel machines
- The power of \(\alpha\)-points in preemptive single machine scheduling.
- Approximation Techniques for Average Completion Time Scheduling
- Approximation in stochastic scheduling
- Completion Time Scheduling and the WSRPT Algorithm
- Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
- Scheduling tasks with exponential service times on parallel processors
- Scheduling for Minimum Total Loss Using Service Time Distributions
- Stochastic scheduling problems I — General strategies
- On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions
- Scheduling Stochastic Jobs with a Two-Point Distribution on Two Parallel Machines
- Efficient Algorithms for Average Completion Time Scheduling
- Stochastic Scheduling with Release Dates and Due Dates
- Stochastic scheduling problems II-set strategies-
- Optimal Scheduling of Jobs with Exponential Service Times on Identical Parallel Processors
- Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions
- Sequencing Tasks with Exponential Service Times to Minimize the Expected Flow Time or Makespan
- Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtime
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Scheduling Unrelated Machines by Randomized Rounding
- On almost optimal priority rules for preemptive scheduling of stochastic jobs on parallel machines
- Stochastic Machine Scheduling with Precedence Constraints
- Models and Algorithms for Stochastic Online Scheduling
- Coping with Incomplete Information in Scheduling — Stochastic and Online Models
- Approximation in Preemptive Stochastic Online Scheduling
- Stochastic Online Scheduling Revisited
- A note on time sharing with preferred customers
- A note on time-sharing
- Scheduling with Random Service Times
- Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
This page was built for publication: A Tight 2-Approximation for Preemptive Stochastic Scheduling