Optimality of threshold policies for heterogeneous server systems

The problem of optimally controlling a multiserver queuing system is studied. Arriving customers join a single queue, which is served by N servers, S₁, S₂, . . ., S_N. The servers are exponential, but of different rates. The goal is to determine the policy that minimizes the total expected time a customer spends in the system. It is shown that the optical policy is of threshold type, i.e., it activates server S_i only when m_i does not depend on the condition of other (slower) servers at the decision instant. The optimal control problem is reformulated as a linear program and a novel argument is used based on the structure of the constraint matrix, in order to establish the results