Steady‐state analysis of load balancing with Coxian‐2 distributed service times. (9th March 2021)

• Record Type: Journal Article
• Authors: Liu, Xin; Gong, Kang; Ying, Lei
• Is Part Of: Naval research logistics. Volume 69:Number 1(2022)
• Page Start: 57
• Page End: 75
• Publication Date: 2021-03-09
• Subjects: Coxian‐2 service -- heavy traffic regime -- load balancing -- state space collapse -- steady‐state analysis -- Stein's method; Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21986
• Languages: English
• ISSNs: 0894-069X

Abstract

Abstract: This paper studies load balancing for many‐server ( N servers) systems. Each server has a buffer of size b − 1, and can have at most one job in service and b − 1 jobs in the buffer. The service time of a job follows the Coxian‐2 distribution. We focus on steady‐state performance of load balancing policies in the heavy traffic regime such that the normalized load of system is λ = 1 − N − α for 0 < α < 0.5. We identify a set of policies that achieve asymptotic zero waiting. The set of policies include several classical policies such as join‐the‐shortest‐queue (JSQ), join‐the‐idle‐queue (JIQ), idle‐one‐first (I1F) and power‐of‐ d ‐choices (Po d ) with d = O ( N α log N ). The proof of the main result is based on Stein's method and state space collapse. A key technical contribution of this paper is the iterative state space collapse approach that leads to a simple generator approximation when applying Stein's method.