Heuristic procedures for a stochastic batch service problem

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.