Unrelated Machine Scheduling with Stochastic Processing Times

DOI10.1287/moor.2015.0757zbMath1342.90072OpenAlexW2285796902MaRDI QIDQ3186530

M. I. Sviridenko, Martin Skutella, Marc Uetz

Publication date: 10 August 2016

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/12db8b9e0b8793cb533be3cc0ab09fb522f3746d

zbMATH Keywords

approximation algorithmstochastic schedulinglinear programming relaxation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (14)

Performance of the Smallest-Variance-First Rule in Appointment Sequencing ⋮ Unnamed Item ⋮ Performance analysis of fixed assignment policies for stochastic online scheduling on uniform parallel machines ⋮ A state-of-the-art survey on multi-scenario scheduling ⋮ Parameterized multi-scenario single-machine scheduling problems ⋮ An improved greedy algorithm for stochastic online scheduling on unrelated machines ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ Approximations to Stochastic Dynamic Programs via Information Relaxation Duality ⋮ Static Routing in Stochastic Scheduling: Performance Guarantees and Asymptotic Optimality ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ A new approximation algorithm for unrelated parallel machine scheduling with release dates ⋮ On index policies for stochastic minsum scheduling ⋮ Scheduling in multi-scenario environment with an agreeable condition on job processing times ⋮ Randomized selection algorithm for online stochastic unrelated machines scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation results in parallel machines stochastic scheduling
• LP-based online scheduling: From single to parallel machines
• When greediness fails: examples from stochastic scheduling.
• A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
• Structure of a simple scheduling polyhedron
• Polynomial time approximation algorithms for machine scheduling: Ten open problems
• The expected competitive ratio for weighted completion time scheduling
• Approximation Techniques for Average Completion Time Scheduling
• A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines
• Non-Approximability Results for Scheduling Problems with Minsum Criteria
• Stochastic Scheduling on Unrelated Machines
• Approximation in stochastic scheduling
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Convex quadratic and semidefinite programming relaxations in scheduling
• 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
• Turnpike Optimality of Smith's Rule in Parallel Machines Stochastic Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms
• Beyond Competitive Analysis
• Scheduling Unrelated Machines by Randomized Rounding
• A Tight 2-Approximation for Preemptive Stochastic Scheduling
• Stochastic Machine Scheduling with Precedence Constraints
• Models and Algorithms for Stochastic Online Scheduling
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits
• Stochastic Online Scheduling Revisited
• Scheduling with Random Service Times
• A new average case analysis for completion time scheduling

This page was built for publication: Unrelated Machine Scheduling with Stochastic Processing Times