In this paper, the shortest line discipline, also known as the join the shortest queue (JSQ) rule, is extended to queues with state-dependent, exponential, service rates, which include queues with multiple exponential servers. 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. The JSQ rule is well known in the literature. The problem arises when arrivals to a system must decide to joint one of many queues in parallel, wait for a server to become available, receive service and then depart from the system. The only information available for making this decision is the number of customers in each queue. The elapsed service times of the customers in service are not known and jockeying between queues or defecting from queues is not allowed. So far, the JSQ rule has been shown to be optimal only (with respect to stochastic order) for a single, identical server in each queue with a service rate that does not depend on the number of customers in the queue. This paper shows that with Poisson arrivals the result can be generalized to include single exponential servers with state-dependent service rates provided that the sequence {μk} of service rates is nondecreasing and bounded with the property that the increment μkÅ+1-μk is nonincreasing in k.
