The Generalized c/μ Rule for Queues with Heterogeneous Server Pools

We study the optimal control of a queueing model with a single customer class and heterogeneous server pools. The main objective is to strike a balance between the holding cost of the queue and the operating costs of the server pools. We introduce a target-allocation policy, which assigns higher priority to the queue or pools without enough customers for general cost functions. Although we can prove its asymptotic optimality, implementation requires solving a nonlinear optimization problem. When the cost functions are convex, we propose a dynamic priority policy referred to as the Gc/µ rule, which is much easier to implement. When the cost functions are concave, it turns out that a fixed priority policy is optimal. We also consider an extension to minimize the operating cost of the server pools and satisfy a service-level target for customers waiting in the queue. We develop hybrid routing policies, combining a threshold policy for the queue and the aforementioned policies for the server pools, for different types of operating cost functions. Moreover, the hybrid routing policies coincide with several classic policies in the literature in special cases. Extensive simulation experiments demonstrate the efficacy of our proposed policies.

Funding: Z. Long received support from the National Natural Science Foundation of China [Grants 72101112 and 72132005] and Jiangsu Province, China [Grant BK20210171]. H. Zhang received support from the National Natural Science Foundation of China [Grants 72192805 and 72201231], the Shenzhen Science and Technology Innovation Commission [Grant RCYX20210609103124047], and the Shenzhen Research Institute of Big Data [Grant T00120220004]. J. Zhang received support from the Hong Kong Research Grants Council [GRF Grants 16208120 and 16214121]. Z.G. Zhang received support from the Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2019-06364].

Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.2472.