Rollout algorithms for stochastic scheduling problems

DOI10.1023/A:1009634810396zbMath0997.90037OpenAlexW3016548437MaRDI QIDQ1806711

Dimitri P. Bertsekas, David A. Castanon

Publication date: 20 December 1999

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1009634810396

zbMATH Keywords

dynamic programmingcomputational experimentsMonte Carlo simulationheuristic approachrolloutdeterministic quiz problemsstochastic quiz problemsstochastic scheduling problemssuboptimal solution algorithms

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Stochastic scheduling theory in operations research (90B36) Dynamic programming (90C39)

Related Items

Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming ⋮ Perspectives of approximate dynamic programming ⋮ Faster rollout search for the vehicle routing problem with stochastic demands and restocking ⋮ Rollout approach to sensor scheduling for remote state estimation under integrity attack ⋮ A 2-OPT procedure to reduce total inspection time in a serial inspection process ⋮ Sensor control for multi-object state-space estimation using random finite sets ⋮ Dynamic parcel pick-up routing problem with prioritized customers and constrained capacity via lower-bound-based rollout approach ⋮ Minimum and worst-case performance ratios of rollout algorithms ⋮ A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs ⋮ Approximate receding horizon approach for Markov decision processes: average reward case ⋮ A unified framework for stochastic optimization ⋮ Simulation-based rolling horizon scheduling for operating theatres ⋮ Planning horizons based proactive rescheduling for stochastic resource-constrained project scheduling problems ⋮ Quadratic approximate dynamic programming for input‐affine systems ⋮ An approximate dynamic programming approach to project scheduling with uncertain resource availabilities ⋮ Single-pass and approximate dynamic-programming algorithms for order acceptance and capacity planning ⋮ Augmenting priority rule heuristics with justification and rollout to solve the resource-constrained project scheduling problem ⋮ A POMDP framework for coordinated guidance of autonomous UAVs for multitarget tracking ⋮ Partially observable Markov decision process approximations for adaptive sensing ⋮ Dynamic programming and suboptimal control: a survey from ADP to MPC ⋮ New Rollout Algorithms for Combinatorial Optimization Problems ⋮ A novel parallel quantum genetic algorithm for stochastic job shop scheduling ⋮ A survey on metaheuristics for stochastic combinatorial optimization ⋮ An approximate dynamic programming approach for the vehicle routing problem with stochastic demands ⋮ Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands ⋮ Average-case performance of rollout algorithms for knapsack problems ⋮ Parallelization strategies for rollout algorithms ⋮ Looking ahead with the pilot method