Optimality of the shortest line discipline with state-dependent service rates (Q1122239)

The paper deals with the shortest line discipline, also known as the join the shortest queue (JSQ) rule extended to queues with state-dependent, exponential service rates, which include queues with multiple exponential servers. It is assumed that arrivals occur according to an independent Poisson process. Service times are exponentially distributed. There is a single server in each queue whose service rate depends on the number of customers in its queue. In particular if there are k customers in the queue, then the service rate is \(\mu_ k\). The sequence \(\{\mu_ k\}\) of service rates is assumed to be non-decreasing and bounded with the concavity property that the increment \(\mu_{k+1}-\mu_ k\) is non- increasing in k. It is shown that JSQ stochastically minimizes the number of customers in the system at any time \(t>0\) and also minimizes the long run average response (waiting) time.