OPTIMALITY OF THE SHORTEST LINE DISCIPLINE WITH STATE-DEPENDENT SERVICE RATES

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 > O and also minimizes the long run average response (waiting) time. The problem arises when arrivals to a system must decide to join one of many queues in parallel, wait for a server to become available, receive service and then depart from the system. 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.