We consider a system of N parallel queues with identical exponential service rates and a single dispatcher where tasks arrive as a Poisson process. When a task arrives, the dispatcher always assigns it to an idle server, if there is any, and to a server with the shortest queue among d randomly selected servers otherwise (1≤d≤N). This load balancing scheme subsumes the so-called join-the-idle queue policy (d=1) and the celebrated join-the-shortest queue policy (d=N) as two crucial special cases. We develop a stochastic coupling construction to obtain the diffusion limit of the queue process in the Halfin‒Whitt heavy-traffic regime, and establish that it does not depend on the value of d, implying that assigning tasks to idle servers is sufficient for diffusion level optimality.

Let Ln be the number of losses during a busy period of an M/GI/1/n queueing system. We develop a coupling between Ln and Ln+1 and use the resulting relationship to provide a simple proof that when the mean service time equals the mean interarrival time, ELn = 1 for all n. We also show that Ln is increasing in the convex sense when the mean service time equals the mean interarrival time, and it is increasing in the increasing convex sense when the mean service time is less than the mean interarrival time.

This paper studies optimal routing and jockeying policies in a two-station parallel queueing system. It is assumed that jobs arrive to the system in a Poisson stream with rate λand are routed to one of two parallel stations. Each station has a single server and a buffer of infinite capacity. The service times are exponential with server-dependent rates, μ1 and μ2. Jockeying between stations is permitted. The jockeying cost is cij when a job in station i jockeys to station j, i ≠ j. There is no cost when a new job joins either station. The holding cost in station j is hj, h1 ≦ h2, per job per unit time. We characterize the structure of the dynamic routing and jockeying policies that minimize the expected total (holding plus jockeying) cost, for both discounted and long-run average cost criteria. We show that the optimal routing and jockeying controls are described by three monotonically non-decreasing functions. We study the properties of these control functions, their relationships, and their asymptotic behavior. We show that some well-known queueing control models, such as optimal routing to symmetric and asymmetric queues, preemptive or non-preemptive scheduling on homogeneous or heterogeneous servers, are special cases of our system.