• PDF
• Cite
• Share
Article Contents  Article Contents

# Steady-state and first passage time distributions for waiting times in the MAP/M/s+G queueing model with generally distributed patience times

• * Corresponding author: Nail Akar
• We study the $MAP/M/s+G$ queueing model that arises in various multi-server engineering problems including telephone call centers, under the assumption of MAP (Markovian Arrival Process) arrivals, exponentially distributed service times, infinite waiting room, and generally distributed patience times. Using sample-path arguments, we propose to obtain the steady-state distribution of the virtual waiting time and subsequently the other relevant performance metrics of interest via the steady-state solution of a certain Continuous Feedback Fluid Queue (CFFQ). The proposed method is exact when the patience time is a discrete random variable and is asymptotically exact when it is continuous/hybrid, for which case discretization of the patience time distribution is required giving rise to a computational complexity depending linearly on the number of discretization levels. Additionally, a novel method is proposed to accurately obtain the first passage time distributions for the virtual and actual waiting times again using CFFQs while approximating the deterministic time horizons by Erlang distributions or more efficient Concentrated Matrix Exponential (CME) distributions. Numerical results are presented to validate the effectiveness of the proposed numerical method.

Mathematics Subject Classification: Primary: 60K30, 65C40, 68M20, 90B22; Secondary: 60J25.

 Citation: • • Figure 1.  Venn diagram illustrating the relationship between CMFQs, MRMFQs, and CFFQs

Figure 2.  Sample path of the random process $Z_f(t), t\geq 0$

Figure 3.  Sample path of the random process $\tilde{Z}_f(t), t\geq 0$

Figure 4.  Sample path of the random process $Z_f(t), t\geq 0$

Table 1.  Results for the $M/M/s+M$ scenario with $s=10$, $\lambda=10$, $\mu=1$, $E(A)=1$

 Analysis $K=10$ Analysis $K=50$ Analysis $K=250$ Ref.  Simulation Results $\Pr \left\{ {W=0 } \right\}$ 0.46000 0.45802 0.45794 0.45793 $0.45829 \pm 0.00209$ $\Pr \left\{ {W=0|\mathcal{S} } \right\}$ 0.52612 0.52353 0.52343 0.52341 $0.52375 \pm 0.00195$ $\Pr \left\{ {\mathcal{A}} \right\}$ 0.12567 0.12513 0.12511 0.12511 $0.12498 \pm 0.00084$ $E(W|\mathcal{S})$ 0.11648 0.11500 0.11494 0.11494 $0.11491 \pm 0.00077$ $\text{Var}(W|\mathcal{S})$ 0.03377 0.03310 0.03307 0.03307 $0.03299 \pm 0.00030$ $F_{W|\mathcal{S},W >0}(.1)$ 0.28108 0.28100 0.28108 0.28107 $0.28060 \pm 0.00093$ $F_{W|\mathcal{S},W >0}(.2)$ 0.51155 0.51285 0.51283 0.51283 $0.51208 \pm 0.00145$

Table 2.  Comparison of analytical results with simulations for the $MAP/M/s+M$ scenario

 Analysis $K=10$} Analysis $K=50$} Analysis $K=250$} Simulation Results $\Pr \left\{ { W=0 } \right\}$ 0.43620 0.43464 0.43458 $0.43473 \pm 0.00097$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.51361 0.51152 0.51143 $0.51158 \pm 0.00096$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.15073 0.15029 0.15027 $0.15023 \pm 0.00043$ $E(W|\mathcal{S})$ 0.14046 0.13743 0.13737 $0.13718 \pm 0.00043$ $\text{Var}(W|\mathcal{S})$ 0.12746 0.04456 0.04451 $0.04437 \pm 0.00018$ $F_{W|\mathcal{S},W >0}(.1)$ 0.23845 0.23847 0.23854 $0.23854 \pm 0.00066$ $F_{W|\mathcal{S},W >0}(.2)$ 0.44512 0.44644 0.44642 $0.44661 \pm 0.00094$

Table 3.  Comparison of analytical results with simulations for the $MAP/M/s+M_B$ scenario

 Analysis $K=10$} Analysis $K=50$} Analysis $K=250$} Simulation Results $\Pr \left\{ { W=0 } \right\}$ 0.69025 0.68969 0.68968 $0.68977 \pm 0.00034$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.88516 0.88428 0.88425 $0.88430 \pm 0.00019$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.22020 0.22006 0.22006 $0.21999 \pm 0.00024$ $E(W|\mathcal{S})$ 0.01563 0.01483 0.01480 $0.01481 \pm 0.00004$ $\text{Var}(W|\mathcal{S})$ 0.00368 0.00344 0.00343 $0.00344 \pm 0.00001$ $F_{W|\mathcal{S},W>0}(.1)$ 0.53344 0.53371 0.53384 $0.53332\pm 0.00061$ $F_{W|\mathcal{S},W>0}(.2)$ 0.78709 0.78846 0.78846 $0.78832\pm 0.00055$

Table 4.  Comparison of analytical results with simulations for the $MAP/M/s+HE$ scenario

 Analysis $K=10$} Analysis $K=50$} Analysis $K=250$} Simulation Results $\Pr \left\{ { W=0 } \right\}$ 0.39314 0.39104 0.39096 $0.39136 \pm 0.00088$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.45551 0.45276 0.45266 $0.45311 \pm 0.00087$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.13692 0.13632 0.13630 $0.13629 \pm 0.00037$ $E(W|\mathcal{S})$ 0.20596 0.20195 0.20180 $0.20175 \pm 0.00061$ $\text{Var}(W|\mathcal{S})$ 0.08667 0.08281 0.08266 $0.08266 \pm 0.00039$ $F_{W|\mathcal{S},W>0}(.1)$ 0.18329 0.18628 0.18639 $0.18610\pm 0.00054$ $F_{W|\mathcal{S},W>0}(.2)$ 0.35371 0.35537 0.35547 $0.35501\pm 0.00085$

Table 5.  Comparison of analytical results with simulations for the $MAP/M/s+D$ scenario

 Analysis Simulation Results $\Pr \left\{ { W=0} \right\}$ 0.37989 $0.38040 \pm 0.00091$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.43851 $0.43893 \pm 0.00090$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.13367 $0.13334 \pm 0.00042$ $E(W|\mathcal{S})$ 0.14990 $0.14974 \pm 0.00033$ $\text{Var}(W|\mathcal{S})$ 0.02964 $0.02962 \pm 0.00004$ $F_{W|\mathcal{S},W>0}(.1)$ 0.17763 $0.17778 \pm 0.00047$ $F_{W|\mathcal{S},W>0}(.2)$ 0.35825 $0.35855 \pm 0.00072$

Table 6.  Comparison of analytical results with simulations for the $MAP/M/s+W$ scenario

 Analysis $K=10$ Analysis $K=50$ Analysis $K=250$ Simulation Results $\Pr \left\{ { W=0 } \right\}$ 0.34776 0.33324 0.33138 $0.33166 \pm 0.00097$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.39620 0.37774 0.37538 $0.37557 \pm 0.00098$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.12227 0.11778 0.11721 $0.11693 \pm 0.00042$ $E(W|\mathcal{S})$ 0.31926 0.25150 0.25138 $0.25104 \pm 0.00065$ $\text{Var}(W|\mathcal{S})$ 3.91308 0.12642 0.08071 $0.07974 \pm 0.00018$ $F_{W|\mathcal{S},W>0}(.1)$ 0.13862 0.13371 0.13361 $0.13401 \pm 0.00046$ $F_{W|\mathcal{S},W>0}(.2)$ 0.27149 0.26618 0.26670 $0.26723 \pm 0.00070$

Table 7.  Comparison of analytical results with simulations for the $MAP/M/s+E_2$ scenario

 Analysis $K=10$ Analysis $K=50$ Analysis $K=250$ Simulation Results $\Pr \left\{ { W=0 } \right\}$ 0.30664 0.29490 0.29380 $0.29336 \pm 0.00115$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.34379 0.32928 0.32793 $0.32737 \pm 0.00115$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.10806 0.10442 0.10408 $0.10393 \pm 0.00048$ $E(W|\mathcal{S})$ 0.37254 0.37450 0.37482 $0.37475 \pm 0.00138$ $\text{Var}(W|\mathcal{S})$ 0.17112 0.17499 0.17560 $0.17527 \pm 0.00075$ $F_{W|\mathcal{S},W>0}(.1)$ 0.109761 0.10744 0.10785 $0.10782 \pm 0.00047$ $F_{W|\mathcal{S},W>0}(.2)$ 0.21430 0.21334 0.21375 $0.21371 \pm 0.00082$

Table 8.  Comparison of analytical results with simulations for the $MAP/M/s+E_3$ scenario

 Analysis $K=10$ Analysis $K=50$ Analysis $K=250$ Simulation Results $\Pr \left\{ { W=0 } \right\}$ 0.24365 0.22187 0.21925 $0.21946 \pm 0.00106$ $\Pr \left\{ { W=0|\mathcal{S}} \right\}$ 0.26659 0.24087 0.23780 $0.23791 \pm 0.00108$ $\Pr \left\{ { \mathcal{A} } \right\}$ 0.08603 0.07886 0.07801 $0.07757 \pm 0.00044$ $E(W|\mathcal{S})$ 0.63951 0.65123 0.65284 $0.65137 \pm 0.00222$ $\text{Var}(W|\mathcal{S})$ 0.34263 0.38303 0.38981 $0.39046 \pm 0.00157$ $F_{W|\mathcal{S},W>0}(.1)$ 0.07563 0.06845 0.06783 $0.06795 \pm 0.00035$ $F_{W|\mathcal{S},W>0}(.2)$ 0.14729 0.13513 0.13433 $0.13458 \pm 0.00061$

Table 9.  The cdf of the virtual waiting time evaluated at time $\tau$, $F_v^{a,b,\pi_0,\theta_0}(\tau)$, obtained by the proposed method using Erlang-$\ell$ and CME-$\ell$ distributions for three values of the parameter $\ell$, and for the scenario $\theta_0 = [\begin{smallmatrix} 1 & 0 \end{smallmatrix}]$

 Erlang-$\ell$ CME-$\ell$ $\tau$ $b$ Simulation $\ell=25$ $\ell=51$ $\ell=101$ $\ell=25$ $\ell=51$ $\ell=101$ $1/4$ 0.61906$\pm$0.00027 0.59251 0.60529 0.61200 0.61705 0.61883 0.61922 $1/2$ 0.39325$\pm$0.00050 0.38744 0.39032 0.39185 0.39309 0.39345 0.39354 $1$ $1$ 0.11791$\pm$0.00065 0.13245 0.12551 0.12189 0.11922 0.11822 0.11800 $2$ 0.00323$\pm$0.00044 0.00607 0.00456 0.00388 0.00345 0.00328 0.00324 $4$ 0.00000$\pm$0.00002 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 $1/4$ 0.97700$\pm$0.00022 0.97692 0.97698 0.97700 0.97690 0.97699 0.97700 $1/2$ 0.96964$\pm$0.00029 0.96910 0.96949 0.96960 0.96953 0.96965 0.96967 $5$ $1$ 0.95339$\pm$0.00031 0.94898 0.95163 0.95257 0.95294 0.95326 0.95331 $2$ 0.86128$\pm$0.00039 0.82707 0.84443 0.85283 0.85859 0.86077 0.86124 $4$ 0.14516$\pm$0.00050 0.16177 0.15408 0.14986 0.14667 0.14544 0.14517 $1/4$ 0.98695$\pm$0.00016 0.98684 0.98691 0.98694 0.98693 0.84307 0.98697 $1/2$ 0.98274$\pm$0.00020 0.98261 0.98270 0.98274 0.98273 0.98278 0.98278 $25$ $1$ 0.97408$\pm$0.00022 0.97381 0.97394 0.97400 0.97399 0.97405 0.97406 $2$ 0.95078$\pm$0.00035 0.95051 0.95073 0.95084 0.95084 0.95093 0.95094 $4$ 0.86036$\pm$0.00035 0.85903 0.85979 0.86006 0.86011 0.86027 0.86030

Table 10.  The cdf of the virtual waiting time evaluated at time $\tau$, $F_v^{a,b,\pi_0,\theta_0}(\tau)$, obtained by the proposed method using Erlang-$\ell$ and CME-$\ell$ distributions for three values of the parameter $\ell$, and for the scenario $\theta_0 = [\begin{smallmatrix} 0 & 1 \end{smallmatrix}]$

 Erlang-$\ell$ CME-$\ell$ $\tau$ $b$ Simulation $\ell=25$ $\ell=51$ $\ell=101$ $\ell=25$ $\ell=51$ $\ell=101$ $1/4$ 0.00663$\pm$0.00010 0.00703 0.00681 0.00671 0.00664 0.00661 0.00660 $1/2$ 0.00355$\pm$0.00006 0.00400 0.00377 0.00365 0.00357 0.00354 0.00353 $1$ $1$ 0.00081$\pm$0.00003 0.00111 0.00096 0.00089 0.00084 0.00082 0.00082 $2$ 0.00002$\pm$0.00001 0.00004 0.00002 0.00002 0.00002 0.00002 0.00002 $4$ 0.00000$\pm$0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 $1/4$ 0.11115$\pm$0.00032 0.11067 0.11085 0.11094 0.11100 0.11102 0.11103 $1/2$ 0.10346$\pm$0.00031 0.10305 0.10323 0.10332 0.10338 0.10340 0.10341 $5$ $1$ 0.08827$\pm$0.00026 0.08794 0.08809 0.08816 0.08823 0.08824 0.08825 $2$ 0.05324$\pm$0.00020 0.05382 0.05349 0.05334 0.05326 0.05322 0.05321 $4$ 0.00365$\pm$0.00005 0.00538 0.00453 0.00412 0.00382 0.00372 0.00369 $1/4$ 0.49669$\pm$0.00059 0.49161 0.49415 0.49537 0.49620 0.49653 0.49660 $1/2$ 0.48996$\pm$0.00058 0.48497 0.48751 0.48872 0.48956 0.48989 0.48996 $25$ $1$ 0.47661$\pm$0.00058 0.47159 0.47410 0.47531 0.47614 0.47647 0.47654 $2$ 0.44349$\pm$0.00059 0.43858 0.44104 0.44223 0.44304 0.44336 0.44343 $4$ 0.33702$\pm$0.00049 0.33222 0.33441 0.33547 0.33622 0.33649 0.33654

Table 11.  The cdf of the actual waiting time evaluated at time $\tau$, $F_a^{a,b,\pi_0,\theta_0}(\tau)$, obtained by the proposed method using Erlang-$\ell$ and CME-$\ell$ distributions for three values of the parameter $\ell$, and for the scenario $\theta_0 = [\begin{smallmatrix} 1 & 0 \end{smallmatrix}]$

 Erlang-$\ell$ CME-$\ell$ $\tau$ $b$ Simulation $\ell=25$ $\ell=51$ $\ell=101$ $\ell=25$ $\ell=51$ $\ell=101$ $1/4$ 0.52092$\pm$0.00051 0.50227 0.51121 0.51598 0.51964 0.52089 0.52117 $1/2$ 0.31345$\pm$0.00049 0.31514 0.31438 0.31397 0.31375 0.31358 0.31355 $1$ $1$ 0.08271$\pm$0.00028 0.09792 0.09062 0.08685 0.08408 0.08305 0.08282 $2$ 0.00184$\pm$0.00004 0.00382 0.00273 0.00226 0.00197 0.00186 0.00183 $4$ 0.00000$\pm$0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 $1/4$ 0.97418$\pm$0.00020 0.97393 0.97406 0.97409 0.97400 0.97409 0.97411 $1/2$ 0.96674$\pm$0.00023 0.96574 0.96635 0.96652 0.96649 0.96662 0.96664 $5$ $1$ 0.94941$\pm$0.00023 0.94345 0.94692 0.94819 0.94876 0.94915 0.94922 $2$ 0.84264$\pm$0.00052 0.80496 0.82380 0.83310 0.83960 0.84204 0.84256 $4$ 0.11830$\pm$0.00040 0.13624 0.12782 0.12323 0.11975 0.11844 0.11815 $1/4$ 0.98533$\pm$0.00015 0.98517 0.98524 0.98528 0.98527 0.98530 0.98531 $1/2$ 0.98108$\pm$0.00018 0.98089 0.98098 0.98103 0.98102 0.98106 0.98107 $25$ $1$ 0.97205$\pm$0.00017 0.97180 0.97193 0.97200 0.97199 0.97205 0.97206 $2$ 0.94819$\pm$0.00020 0.94767 0.94789 0.94800 0.94801 0.94810 0.94811 $4$ 0.85268$\pm$0.00038 0.85115 0.85203 0.85234 0.85240 0.85257 0.85260

Table 12.  The cdf of the actual waiting time evaluated at time $\tau$, $F_a^{a,b,\pi_0,\theta_0}(\tau)$, obtained by the proposed method using Erlang-$\ell$ and CME-$\ell$ distributions for three values of the parameter $\ell$, and for the scenario $\theta_0 = [\begin{smallmatrix} 0 & 1 \end{smallmatrix}]$

 Erlang-$\ell$ CME-$\ell$ $\tau$ $b$ Simulation $\ell=25$ $\ell=51$ $\ell=101$ $\ell=25$ $\ell=51$ $\ell=101$ $1/4$ 0.00502$\pm$0.00005 0.00553 0.00529 0.00517 0.00509 0.00506 0.00505 $1/2$ 0.00257$\pm$0.00004 0.00307 0.00283 0.00271 0.00263 0.00260 0.00260 $1$ $1$ 0.00053$\pm$0.00003 0.00078 0.00066 0.00060 0.00056 0.00054 0.00054 $2$ 0.00001$\pm$0.00000 0.00002 0.00002 0.00001 0.00001 0.00001 0.00001 $4$ 0.00000$\pm$0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 $1/4$ 0.10802$\pm$0.00030 0.10761 0.10780 0.10789 0.10795 0.10797 0.10798 $1/2$ 0.10030$\pm$0.00029 0.10000 0.10018 0.10026 0.10033 0.10035 0.10035 $5$ $1$ 0.08481$\pm$0.00026 0.08463 0.08476 0.08483 0.08489 0.08491 0.08491 $2$ 0.04944$\pm$0.00022 0.05027 0.04985 0.04966 0.04954 0.04949 0.04948 $4$ 0.00283$\pm$0.00007 0.00438 0.00362 0.00324 0.00298 0.00289 0.00287 $1/4$ 0.49362$\pm$0.00051 0.48896 0.49149 0.49271 0.49355 0.49387 0.49394 $1/2$ 0.48698$\pm$0.00051 0.48230 0.48483 0.48605 0.48688 0.48721 0.48727 $25$ $1$ 0.47332$\pm$0.00051 0.46860 0.47111 0.47232 0.47315 0.47347 0.47354 $2$ 0.43941$\pm$0.00051 0.43475 0.43720 0.43839 0.43920 0.43951 0.43958 $4$ 0.32884$\pm$0.00048 0.32438 0.32654 0.32759 0.32832 0.32859 0.32865
• Figures(4)

Tables(12)

## Article Metrics  DownLoad:  Full-Size Img  PowerPoint