Optimal Routing to Parallel Servers in Heavy Traffic

Heng-Qing Ye ()
Additional contact information
Heng-Qing Ye: Faculty of Business, Hong Kong Polytechnic University, Hong Kong, China

Operations Research, 2025, vol. 73, issue 1, 483-509

Abstract: We study a system with heterogeneous parallel servers, each with an infinite waiting room. Upon arrival, a job is routed to the queue of one of the servers, possibly depending on the dynamic state information such as the real-time queue lengths, the arrival, and service history of jobs. The objective is to find the routing policy that best uses the available state information to minimize the expected stationary queue length. In this paper, we establish the diffusion limit for the round-robin policy (respectively, arrival-chasing policy, service-chasing policy), and show that with properly chosen parameters, it achieves the optimal performance asymptotically within the class of admissible policies that require no state information (respectively, require arrival history, service history). Like the jointhe-shortest-queue and the balanced routing policies that use real-time queue length information, the optimal service-chasing policy is also asymptotically optimal over all admissible policies. Further analysis of the diffusion limits yields a number of insights into the performance of these routing policies and reveals the value of various state information. We numerically demonstrate the effectiveness of the estimators derived from the diffusion limits for the policies being studied and obtain interesting observations. We also address the problem of interchange of limits under the aforementioned policies, which justifies the stationary performance of the diffusion limit as a valid approximation to that of the original system under respective policies. Methodologically, this study contributes to the application of the BIGSTEP method for constructing control policy to optimize stationary performance and the recipe for justifying the interchange of limits in the heavy traffic analysis of stochastic processing networks.

Keywords: Stochastic Model; parallel server system; routing control; round robin; arrival chasing; service chasing; heavy traffic analysis (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.0055 (application/pdf)

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:inm:oropre:v:73:y:2025:i:1:p:483-509

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().