A Tight 2-Approximation for Preemptive Stochastic Scheduling

DOI10.1287/moor.2014.0653zbMath1312.90027OpenAlexW2059443493WikidataQ57399741 ScholiaQ57399741MaRDI QIDQ5247621

Tjark Vredeveld, Nicole Megow

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

zbMATH Keywords

schedulingapproximation algorithmstochastictotal weighted completion time

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36) Approximation algorithms (68W25)

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