DocumentCode :
3782062
Title :
Rollout algorithms for stochastic scheduling problems
Author :
D.P. Bertsekas;D.A. Castanon
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., MIT, Cambridge, MA, USA
Volume :
2
fYear :
1998
Firstpage :
2143
Abstract :
Stochastic scheduling problems are difficult stochastic control problems with combinatorial decision spaces. We focus on a class of stochastic scheduling problems, the quiz problem and its variations. We discuss the use of heuristics for their solution, and we propose rollout algorithms based on these heuristics which approximate the stochastic dynamic programming algorithm. We show how the rollout algorithms can be implemented efficiently, with considerable savings in computation over optimal algorithms. We delineate circumstances under which the rollout algorithms are guaranteed to perform better than the heuristics on which they are based. We also show computational results which suggest that the performance of the rollout policies is near-optimal, and is substantially better than the performance of their underlying heuristics.
Keywords :
"Scheduling algorithm","Stochastic processes","Processor scheduling","Heuristic algorithms","Laboratories","Vehicles","Routing","Traveling salesman problems"
Publisher :
ieee
Conference_Titel :
Decision and Control, 1998. Proceedings of the 37th IEEE Conference on
ISSN :
0191-2216
Print_ISBN :
0-7803-4394-8
Type :
conf
DOI :
10.1109/CDC.1998.758655
Filename :
758655
Link To Document :
بازگشت