State Space Collapse in Many-Server Diffusion Limits ofParallel Server Systems and Applications

State Space Collapse;Halfin-Whitt regime;Diffusion limits;Queueing systems

Tezcan, Tolga ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: State Space Collapse;    Halfin-Whitt regime;    Diffusion limits;    Queueing systems;   

Others  :  https://smartech.gatech.edu/bitstream/1853/11548/1/tezcan_tolga_200608_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

We consider a class of queueing systems that consist of server pools in parallel and multiple customer classes. Customer service times are assumed to be exponentially distributed. We study the asymptotic behavior of these queueing systems in a heavy traffic regime that is known as the Halfin and Whitt many-server asymptotic regime. Our main contribution is a general framework for establishing state space collapse results in the Halfin and Whitt many-server asymptotic regime for parallel server systems having multiple customer classes. In our work, state space collapse refers to a decrease in the dimension of the processes tracking the number of customers ineach class waiting for service and the number of customers in each class being served by various server pools. We define and introduce a state space collapse function, which governs the exact details of the state space collapse.Our methodology is similar in spirit to that in Bramson (1998); however, Bramson studies an asymptotic regime in which the number of servers is fixed and Bramson does not require a state space collapse function.We illustrate the applications of our results in three different parallel server systems. The first system is adistributed parallel server system under the minimum-expected-delay faster-server-first (MED-FSF) or minimumexpected-delay load-balancing (MED-LB) policies. We prove that the MED-FSF policy minimizes the stationarydistribution of total number of customers in the system. However, under the MED-FSF policy all the servers in ourdistributed system except those with the lowest service rate experience 100% utilization but under the MED-LBpolicy, on the other hand, the utilizations of all the server pools are equal. The second system we consider is knownas the N-model. We show that when the service times only depend on the server pool providing service a staticpriority rule is asymptotically optimal. Finally, we study two results conjectured in the literature for V-systems.We show for all of these systems that the conditions on the hydrodynamic limits can easily be checked using thestandard tools that have been developed in the literature to analyze fluid models.