Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem

Katerina P. Papadaki, Warren Buckler Powell

Research output: Contribution to journalArticle

36 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)108-127
Number of pages20
JournalEuropean Journal of Operational Research
Volume142
Issue number1
DOIs
StatePublished - Oct 1 2002

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Dynamic programming
  • Inventory theory

Fingerprint Dive into the research topics of 'Exploiting structure in adaptive dynamic programming algorithms for a stochastic batch service problem'. Together they form a unique fingerprint.

  • Cite this