Optimal serving schedules for multiple queues with size-independent service times

Abstract

We consider a service system with two Poisson arrival queues. There is a single server that chooses which queue to serve at each moment. Once a queue is served, all the customers are served within a fixed time. This model is useful in studying airport shuttling or certain online computing systems. In this thesis, we first establish a Markov. Decision Process (MDP) model for this problem and study its structures. We then propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well. If the service time of both queues equals to one unit of time, we prove that the optimal state-independent policy has the following structure: serve the queue with the smaller arrival rate once followed by serving the other queue k times, and we obtain an explicit formula to capture k. We conduct numerical tests for our policy and it performs very well. We also extend our discussions to a more general case in which the service time of the queues can be any integer. We also obtain the optimal the optimal state-independent policies in that case.