OPTIMAL-CONTROL OF ARRIVALS TO QUEUES WITH DELAYED QUEUE LENGTH INFORMATION

We consider discrete-time versions of two classical problems in the op timal 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. We extend the formulation of these prob lems to permit a k step delay in the observation of the queue lengths by the controller. For geometric inter-arrival times and geometric ser vice times the problems are formulated as controlled Markov chains wit h expected total discounted cost as the minimization objective. For pr oblem i) we show that when k = 1, the optimal policy is to allocate an arrival to the queue with the smaller expected queue length (JSEQ: Jo in the Shortest Expected Queue). We also show that for this problem, f or k greater than or equal to 2, JSEQ is not optimal. For problem ii) we show that when k = 1, the optimal policy is a threshold policy. The re are, however, two thresholds m(0) greater than or equal to m(1) > 0 , such that mo is used when the previous action was to reject, and mi is used when the previous action was to accept.