New version page

Fluid and Diffusion Limits for Many-Server Queues

Upgrade to remove ads

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

BackgroundPart1Limit theoremsLimProof sketchesPerturbed systemsG/GI/n+GI queuesConcFluid and Diffusion Limits forMany-Server QueuesJim DaiJuly 14, 2009Joint work with Shuangchi He and Tolga Tezcan (UIUC)Jim Dai (Georgia Tech) Many-server queues 1 / 37Who is this?Jim Dai (Georgia Tech) Many-server queues 2 / 37Who is this?Jim Dai (Georgia Tech) Many-server queues 2 / 37Multi-server queuesserver 1server 2server nG/GI /n + GI queues, FIFO queue, a classical modeliid service times and iid patience timesThe number of servers n is large: call centers, web server farms,hospital bedsJim Dai (Georgia Tech) Many-server queues 3 / 37Performance processesAt time t,System size X (t) — the total number of customers in systemˆX (t) = X(t) −nQueue size Q(t) = (ˆX (t))+The number of idle servers I (t) = (ˆX (t))−Offered waiting time at time t: W (t)Examples of performance measures:abandonment probability P{Ab.}average queue size E(Q)average waiting time among those who are served E(W |S)Jim Dai (Georgia Tech) Many-server queues 4 / 37Time-varying arrival rates: Brown et al (05)38 Journal of the American Statistical Association, March 2005center. We have performed similar analyses for other parts ofthe d ata, and in m ost respects the November–December resultsdo not differ noticeably from those based on data from othermonths of the year.3. THE ARRIVAL PROCESSFigure 1 shows, as a function of time of day, the averagerate p er hour at which calls come out of the VRU. These arecomposite plots for weekday calls in November and Decem-ber. The plots show calls accord ing to the major call types.The volume of regular (PS) calls is much greater than tha t ofthe other three types; hence those calls are shown on a sepa-rate plot. [ These plots were fit using the root–unroot methoddescribed by Brown, Zhang, and Zh ao (2001), along with theadaptive free knot spline methodology of Mao and Zhao (2003).For a more precise study of these arrival rates, including confi-dence and prediction intervals, see our Sec. 6 and also Brownet al. 2001, 200 2a,b.]Note the bimodal pattern of PS call-arrival times in Figure 1.It is especially interesting that IN calls do not show a sim ilarbimodal pattern and in fact have a peak volume after 10PM.(This peak can be pa rtially explained by the fact that Internetcustomers are sensitive to teleph one rates, which significantlydecrease in Israel after 10PM, and that they also tend to bepeople who stay late.)3.1 Arrivals Are Inhomogeneous PoissonCommon call center models and practice assume that thearrival process is Poisson with a r ate that remains constantfor blocks of time (e.g., half-hours), with a separate queueingmodel fitted for each block of time. A more natural model forcapturing changes in the arrival rate is a time-inhomogeneousPoisson process. Following common p ractice, we assume thatthe arrival rate function can be well approximated as beingpiecewise constant.We now construct a test of the null hypothesis tha t arrivals ofgiven types of calls form an inhomogeneous Poisson processwith piecewise constant rates. The fir st step in co nstructingour test involves breaking up the duration of a day into rela-tively short blocks of time, short enough so that the arrival ratedoes not change significantly within a block. For convenience,we used blocks of equal time length, L, although this equal-ity assumption could be relaxed. One can t hen consider thearrivals within a subset of blocks—for example, blocks at thesame time on various days or successive block s on a given day.The f ormer case would, for example, test whether the process ishomogeneous within blocks for calls arriving within the giventime span.Let Tijdenote the jth ordered arrival time in the ith block,i = 1, . . . , I. Thus Ti1≤ · · · ≤ TiJ(i), where J(i) denotes the totalnumber of arrivals in the ith block. Then define Ti0= 0 andRij= (J(i) + 1 − j)!− log!L − TijL − Ti,j−1"", j = 1, . . ., J (i).Under the formal null hypothesis that the arrival rate is constantwithin each given time interval, the {Rij} will be independentstandard exponential variables, as we now discuss.Let Uijdenote the jth (unordered) arrival time in the ith block.Then the assumed constant Poisson arrival rate w ithin thisblock implies that, conditionally on J(i), the unordered ar-rival times are independent and uniformly distributed, that is,Uijiid∼ U(0, L). Note that Tij= Ui( j). It follows thatL−TijL−Ti,j−1are independent beta(J(i) + 1 − j, 1) variables [see, e.g., prob-lem 6.14.33(iii) in Lehmann 1986]. A standard change ofvariables then yields the condition al exponentiality of the Rijgiven the value of J(i). [One may alternatively base the teston t he variables R∗ij= j(− logTijTi,j+1), where j = 1, . . . , J(i) andTi,J(i)+1= L. Under the null hypothesis, these will also be in-dependent standard exponential variables.]The null hyp othesis does n ot involve an assumption thatthe arrival rates of different intervals are equal or have anyother prespecified relationship. Any customary test for the ex-ponential distribution can be applied to test the null hypothe-sis. For convenience, we use the familiar Kolmogorov–Smirnovtest, even though this may not have the greatest possible poweragainst the alternatives of most inter est. In addition, exponen-tial Q–Q plots can be very useful in ascertaining goodness of fitto the exponential distribution.(a) (b)Figure 1. Arrivals in Calls/Hour by Time of Day, Weekdays in November–December. (a) PS calls; (b) IN, NW, and NE calls.Operating regimesoverloaded;efficiency-driven (ED)critically loaded; quality-and efficiency-driven(QED); Halfin-Whittregimeunderloaded;quality-driven (QD)ED: fluid model; QED: diffusion modelFocus on QED regimeJim Dai (Georgia Tech) Many-server queues 5 / 37Customer abandonmentGarnett-Mandelbaum-Reiman (02)“.... There is a significantdifference in the distributions ofwaiting time and queue length—inparticular, the average waitingtime and queue length are bothstrikingly shorter whenabandonment is taken intoaccount.”one must modelabandonmentpossibly non-exponentialpatience time distribution380 A. Mandelbaum and S. Zeltyn0 50 100 150 20000.511.522.533.544.55x 10−3time, sechazard rateKaplan−Meyer estimateFig. 2. Hazard rate for patience of regular customersaveraged): this forms the 104 points of the second plot in Figure 1. (The last pointof the aggregated plot is an average of only 38 hour intervals.) We checked that, infact,


Download Fluid and Diffusion Limits for Many-Server Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Fluid and Diffusion Limits for Many-Server Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Fluid and Diffusion Limits for Many-Server Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?