Optimal Control of Two Differing Servers

Customers arrive at a buffer in a Poisson stream. The buffer is served by two servers, both having an exponentially distributed service time, but with different mean service times. The goal is minimize the average time spent in the system by the customers, or equivalently, the mean number of customers in the system. Customers can be assigned from the buffer to an idle server. The service is non-preemptive, i.e. a customer, once assigned to a server, completes his service without interruption. One motivation for this problem arises in communication systems. Here messages are received at a buffer where they are stored until transmittal. Two transmission lines to the destination are available, with each transmission line having a different mean transmission time. What is the policy governing the transmission of messages? We show here that the optimal policy is of threshold type. Whenever the faster service becomes idle, it should be fed a customer from the buffer (provided of course that the buffer is nonempty). However, the slower server, when it becomes idle, should not always be fed a customer from the buffer. It should be fed a customer only when the number of customers in the buffer exceeds a readily computable threshold value. This proof that the optimal policy is of threshold type verifies an earlier conjecture of Larsen [1].