Optimization of Priority Queues—A Semi-Markov Decision Chain Approach

We consider the problem of optimally controlling a semi-Markov chain with countable state space and unbounded costs. We assume that a particular control is suspected of being optimal and derive conditions for checking whether this is so. The result is applied to the following queueing system. A single server serves two types of customers who arrive at random and join separate queues. The two types of customer differ in respect of their arrival rates, waiting costs and service time distributions. The server has control over which queue to serve at any time and may interrupt the service of a customer in order to serve a customer of the other queue. In the latter case, however, an interruption cost is incurred which reflects the disruption or loss of goodwill entailed. The server requires a policy for determining when he should switch queues which minimises the long run expected cost per unit time. We find that such a policy specifies that one of the queues has higher priority. When the service time distribution of the other queue is exponential, this priority is pre-emptive if the length of the higher priority queue exceeds a critical value and is otherwise postponable. When the distribution is Erlang-2, the priority depends both on the length of the priority queue and the phase of service.