TY - JOUR
T1 - Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem
AU - Papadaki, Katerina P.
AU - Powell, Warren Buckler
N1 - Funding Information:
This research was supported in part by grant AFOSR-F49620-93-1-0098 from the Air Force Office of Scientific Research, and grant DMI00-85368 from the National Science Foundation. We would also like to acknowledge the comments and careful proofreading of a conscientious reviewer.
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2002/10/1
Y1 - 2002/10/1
N2 - The purpose of this paper is to illustrate the importance of using structural results in dynamic programming algorithms. We consider the problem of approximating optimal strategies for the batch service of customers at a service station. Customers stochastically arrive at the station and wait to be served, incurring a waiting cost and a service cost. Service of customers is performed in groups of a fixed service capacity. We investigate the structure of cost functions and establish some theoretical results including monotonicity of the value functions. Then, we use our adaptive dynamic programming monotone algorithm that uses structure to preserve monotonicity of the estimates at each iterations to approximate the value functions. Since the problem with homogeneous customers can be solved optimally, we have a means of comparison to evaluate our heuristic. Finally, we compare our algorithm to classical forward dynamic programming methods.
AB - The purpose of this paper is to illustrate the importance of using structural results in dynamic programming algorithms. We consider the problem of approximating optimal strategies for the batch service of customers at a service station. Customers stochastically arrive at the station and wait to be served, incurring a waiting cost and a service cost. Service of customers is performed in groups of a fixed service capacity. We investigate the structure of cost functions and establish some theoretical results including monotonicity of the value functions. Then, we use our adaptive dynamic programming monotone algorithm that uses structure to preserve monotonicity of the estimates at each iterations to approximate the value functions. Since the problem with homogeneous customers can be solved optimally, we have a means of comparison to evaluate our heuristic. Finally, we compare our algorithm to classical forward dynamic programming methods.
KW - Dynamic programming
KW - Inventory theory
UR - http://www.scopus.com/inward/record.url?scp=0036795808&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0036795808&partnerID=8YFLogxK
U2 - 10.1016/S0377-2217(01)00297-1
DO - 10.1016/S0377-2217(01)00297-1
M3 - Article
AN - SCOPUS:0036795808
SN - 0377-2217
VL - 142
SP - 108
EP - 127
JO - European Journal of Operational Research
JF - European Journal of Operational Research
IS - 1
ER -