Optimal control of arrivals to queues with delayed queue length information

Abstract

Considers discrete-time versions of two classical problems in the optimal control of admission to a queueing system: (i) optimal routing of arrivals to two parallel queues and (ii) optimal acceptance/rejection of arrivals to a single queue. The authors extend the formulation of these problems to permit a k step delay in the observation of the queue lengths by the controller. For geometric inter-arrival times and geometric service times the problems are formulated as controlled Markov chains with expected total discounted cost as the minimization objective. For problem (i) the authors show that when k=1, the optimal policy is to allocate an arrival to the queue with the smaller expected queue length (JSEQ: Join the Shortest Expected Queue). The authors also show that for this problem, for k≥2, JSEQ is not optimal. For problem (ii) the authors show that when k=1, the optimal policy is a threshold policy. There are, however, two thresholds m₀≥m₁ > 0, such that m₀ is used when the previous action was to reject, and m₁ is used when the previous action was to accept.