Flexible Server Allocation and Customer Routing Policies for

Two Parallel Queues when Service Rates are not Additive

Mark E. Lewis
Cornell University
School of Operations Research and Information Engineering
226 Rhodes Hall
Ithaca, New York 14853

Hyun-soo Ahn

Operations and Management Science, Ross School of Business

University of Michigan

701 Tappan Street

Ann Arbor, Michigan 48109-1234

We consider the question of how routing and allocation can be coordinated to meet the

challenge of demand variability in a parallel queueing system serving two types of customers.

A decision-maker decides whether to keep customers at the station at which they arrived or to

reroute them to the other station. At the same time, the decision-maker has two servers and

must decide where to allocate their effort. We analyze this joint decision-making scenario, but

add two important twists. First, we allow the combined service rate (when the servers work

at the same station) to be super-additive or sub-additive. This captures positive or negative

externalities that arise during collaboration. Second, routing costs are allowed to be strictly

positive. We seek an optimal control policy under the discounted or long-run average cost

criteria.

Our results show that in the super-additive case jobs should never be routed away from

the lower cost queue. When jobs are rerouted from the higher cost queue to the low cost

queue the optimal control is monotone in the respective queue lengths. Moreover, we show

that the optimal allocation is a non-idling priority rule based on the holding costs. In the

sub-additive case we find that the optimal policy need not exhibit such a simple structure.

In fact, the optimal allocation need not prioritize one station (it may split the servers), and

the optimal routing need not be monotone in the number of customers in each queue. We

characterize the optimal policy for a few canonical cases, and discuss why intuitive policies

need not be optimal in the general case. An extensive numerical study examines the benefit

of dynamically controlling both routing and resource allocation; we discuss when using one of

the two levers – dynamic routing and dynamic allocation – is sufficient and when using both

controls is warranted.