Heuristic procedures for a stochastic batch service problem

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


This paper considers a multi-class batch service problem that involves a class-dependent waiting cost and a service cost in determining customer batch sizes. Unlike a fixed service cost used widely in standard models, the service cost considered in this work is incurred only if the total service time is over the capacity. We formulate this problem as an infinite horizon Markov decision process, and exploit its structural properties to establish theoretical results, including bounds on the optimal action space. We use the results to improve the value iteration procedure. Furthermore, we design heuristic algorithms for large problems. The numerical experiments demonstrate that the class-dependent waiting cost has a considerable influence on the optimal customer batch size. Finally, we evaluate the efficiency of the proposed value iteration procedure and the quality of the heuristic solutions.

Original languageEnglish
Pages (from-to)157-174
Number of pages18
Issue number2
StatePublished - Jun 2014


  • Heuristic procedures
  • Markov decision process
  • Monotonicity
  • Multi-class batch service problem
  • Value iteration


Dive into the research topics of 'Heuristic procedures for a stochastic batch service problem'. Together they form a unique fingerprint.

Cite this