Optimal Control for Parallel Queues with a Single Batch Server

Abstract

We consider a queueing system with multiple Poisson arrival queues and a single batch server which can serve all the customers in a certain queue within a fixed amount of time. We study the optimal control problem in which the decision maker chooses which queue to serve at each time period and the objective is to minimize the long-run average waiting cost. We first formulate the problem as a Markov Decision Process. However, the large state space prohibits an exact solution to this problem. To address this difficulty, we analyze a corresponding fluid model. We show that for the fluid model, the optimal policy is to serve the queue with the maximal product of the current queue length, the waiting cost coefficient and a “future” serving time at each time step. By further assuming the “future” serving time to be stationary, we propose a Cost-Arrival Weighted (CAW) policy. In particular, at each decision epoch, the CAW policy weighs each queue by the square root of the ratio between the waiting cost coefficient and the arrival rate, and chooses the longest weighted queue to serve. The CAW policy can be easily adapted to the stochastic model. By extensive numerical experiments, we show that the CAW policy enjoys superior performance in both the fluid and the stochastic models.