Stochastic Machine Scheduling with Precedence Constraints

DOI10.1137/S0097539702415007MaRDI QIDQ5317175zbMATH OpenFDO

Authors Marc Uetz, Martin Skutella

Publication date 16 September 2005

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

Full work available at URL https://doi.org/10.1137/S0097539702415007

zbMATH Keywords

approximation algorithmslist scheduling algorithmsLP-relaxationparallel machinesprecedence constraintsrelease datesstochastic scheduling

Mathematics Subject Classification ID

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

Recommendations

• Time complexity of single machine scheduling with stochastic precedence constraints
• Scheduling precedence-constrained jobs with stochastic processing times on parallel machines
• Stochastic identical parallel machine scheduling with OR precedence constraints
• Stochastic Scheduling with Variable Profile and Precedence Constraints
• Heuristic procedures for parallel-machine scheduling problems with stochastic precedence constraints
• A Stochastic Scheduling Problem with Intree Precedence Constraints
• On Stochastic Scheduling with In-Tree Precedence Constraints
• Machine scheduling with soft precedence constraints

Cited in

(36)

• A novel parallel quantum genetic algorithm for stochastic job shop scheduling
• A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem
• Heuristic procedures for parallel-machine scheduling problems with stochastic precedence constraints
• Distributionally robust single machine scheduling with risk aversion
• Online stochastic optimization under time constraints
• Heuristic algorithms for job-shop scheduling problems with stochastic precedence constraints
• Distributionally robust scheduling on parallel machines under moment uncertainty
• Scheduling jobs with normally distributed processing times on parallel machines
• Machine scheduling with soft precedence constraints
• Risk-averse single machine scheduling: complexity and approximation
• On index policies for stochastic minsum scheduling
• Approximation algorithms for scheduling problems with a modified total weighted tardiness objective
• Hedging uncertainty: approximation algorithms for stochastic optimization problems
• Scheduling precedence-constrained jobs with stochastic processing times on parallel machines
• Online Linear Optimization for Job Scheduling Under Precedence Constraints
• Unrelated machine scheduling with stochastic processing times
• Stochastic identical parallel machine scheduling with OR precedence constraints
• scientific article; zbMATH DE number 4158355 (Why is no real title available?)
• Stochastic single machine scheduling problem with precedence constraints
• scientific article; zbMATH DE number 1187165 (Why is no real title available?)
• Minimizing conditional-value-at-risk for stochastic scheduling problems
• Algorithms for single-machine scheduling with stochastic outtree precedence relations to minimize expected weighted flow time or maximum expected lateness
• Stochastic Scheduling with Variable Profile and Precedence Constraints
• On Stochastic Scheduling with In-Tree Precedence Constraints
• A Stochastic Scheduling Problem with Intree Precedence Constraints
• scientific article; zbMATH DE number 1418273 (Why is no real title available?)
• Greed works -- online algorithms for unrelated machine stochastic scheduling
• A tight 2-approximation for preemptive stochastic scheduling
• Coping with Incomplete Information in Scheduling — Stochastic and Online Models
• A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity
• Stochastic Online Scheduling Revisited
• New partitioning techniques and faster algorithms for approximate interval scheduling
• Configuration balancing for stochastic requests
• Sequencing stochastic jobs with a single sample
• Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines
• On the asymptotic probabilistic analysis of scheduling problems in the presence of precedence constraints

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5317175)