A c/μ‐Rule for Job Assignment in Heterogeneous Group‐Server Queues

Li Xia, Zhe George Zhang and Quan‐Lin Li

Production and Operations Management, 2022, vol. 31, issue 3, 1191-1215

Abstract: We study a dynamic job assignment problem in queueing systems with one class of Poisson arrivals and K groups of heterogeneous servers. A scheduling policy prescribes the job assignment among servers in each group at every state n (number of jobs in the system). Our goal is to obtain the optimal policy to minimize the long‐run average cost, which involves the increasingly convex holding cost for jobs and the operating cost for working servers. This problem has wide application scenarios in operations management, such as job scheduling in manufacturing systems, packet routing in communication systems, and staffing in service systems. We prove that the optimal policy has monotone structures and quasi bang–bang control forms. Specifically, we discover that the optimal policy is governed by the marginal cost rate c − μG(n), where c is the operating cost rate, μ is the service rate, and G(n) is called the perturbation realization factor at state n. Under the condition of scale economies which can be guaranteed by any increasingly concave operating cost in μ, we prove that the optimal policy obeys a so‐called c/μ‐rule: Servers with a smaller c/μ should be occupied by jobs with higher priority. Optimality of multi‐threshold type policies is further proved when the c/μ‐rule is applied. Our c/μ‐rule in group‐server queues can be viewed as a counterpart of the famous cμ‐rule in polling queues, which both significantly reduce the complexity of optimization problems. By utilizing these optimality structures, we also develop computational‐efficient algorithms to determine the optimal policy numerically. Simulation experiments demonstrate the good scalability and robustness of the c/μ‐rule, which are important for managerial practice.

Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1111/poms.13605

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:popmgt:v:31:y:2022:i:3:p:1191-1215

Ordering information: This journal article can be ordered from
http://onlinelibrary ... 1111/(ISSN)1937-5956

Access Statistics for this article

Production and Operations Management is currently edited by Kalyan Singhal

More articles in Production and Operations Management from Production and Operations Management Society
Bibliographic data for series maintained by Wiley Content Delivery ().