Stochastic Machine Scheduling with Precedence Constraints

DOI10.1137/S0097539702415007zbMath1075.68008MaRDI QIDQ5317175

Martin Skutella, Marc Uetz

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

parallel machinesstochastic schedulingrelease datesprecedence constraintsapproximation algorithmsLP-relaxationlist scheduling algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Linear programming (90C05) Stochastic scheduling theory in operations research (90B36) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Related Items (19)

Unrelated Machine Scheduling with Stochastic Processing Times ⋮ Minimizing conditional-value-at-risk for stochastic scheduling problems ⋮ Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling ⋮ Online stochastic optimization under time constraints ⋮ Coping with Incomplete Information in Scheduling — Stochastic and Online Models ⋮ Approximation algorithms for scheduling problems with a modified total weighted tardiness objective ⋮ Scheduling jobs with normally distributed processing times on parallel machines ⋮ Distributionally robust scheduling on parallel machines under moment uncertainty ⋮ Distributionally robust single machine scheduling with risk aversion ⋮ A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity ⋮ Hedging uncertainty: approximation algorithms for stochastic optimization problems ⋮ Risk-averse single machine scheduling: complexity and approximation ⋮ On index policies for stochastic minsum scheduling ⋮ A novel parallel quantum genetic algorithm for stochastic job shop scheduling ⋮ Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines ⋮ Online Linear Optimization for Job Scheduling Under Precedence Constraints ⋮ A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Stochastic Online Scheduling Revisited

This page was built for publication: Stochastic Machine Scheduling with Precedence Constraints