Flexible Server Allocation and Customer Routing Policies for Two Parallel Queues When Service Rates Are Not Additive

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 with both routing and station-dependent holding costs, but add an important twist. We allow the combined service rate (when the servers work at the same station) to be superadditive or subadditive. This captures positive or negative externalities that arise during collaboration. We seek an optimal control policy under the discounted or long-run average cost criteria.

Our results show that in the superadditive 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 nonidling priority rule based on the holding costs. In the subadditive 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.