American Institute of Mathematical Sciences

Advanced
  • Previous Article
    An integrated inventory model with variable transportation cost, two-stage inspection, and defective items
  • JIMO Home
  • This Issue
  • Next Article
    Single server retrial queues with speed scaling: Analysis and performance evaluation
October  2017, 13(4): 1945-1973. doi: 10.3934/jimo.2017026

Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue

Hideaki Takagi ,

Professor Emeritus, University of Tsukuba, Faculty of Engineering, Information and Systems, 1-1-1 Tennoudai, Tsukuba-shi, Ibaraki 305-8573, Japan

* Corresponding author

Received  September 2015 Published  April 2017

Fund Project: The author is supported by the Grant-in-Aid for Scientific Research (C) No. 26330354 from the Japan Society for the Promotion of Science (JSPS) in 2015.

We present a unified and refined analysis of the response time and waiting time in the M/M/$ m $ FCFS preemptive-resume priority queueing system in the steady state by scrutinizing and extending the previous studies such as Brosh (1969), Segal (1970), Buzen and Bondi (1983), Tatashev (1984), and Zeltyn et al. (2009). In particular, we analyze the durations of interleaving waiting times and service times during the response time of a tagged customer of each priority class that is preempted by the arrivals of higher-priority class customers. Our new contribution includes the explicit formulas for the second and third moments of the response time and the third moment of the waiting time. We also clarify the dependence between the waiting time and the total service time. Numerical examples are shown in order to demonstrate the computation of theoretical formulas.

Keywords: Multiserver priority queue, preemptive-resume, response time, waiting time, first passage time.
Mathematics Subject Classification: Primary: 60K25; Secondary: 68M28, 90B22.
Citation: Hideaki Takagi. Unified and refined analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1945-1973. doi: 10.3934/jimo.2017026
References:
[1]

I. Brosh, Preemptive priority assignment in multichannel systems, Operations Research, 17 (1969), 526-535.  doi: 10.1287/opre.17.3.526.  Google Scholar

[2]

J. P. Buzen and A. B. Bondi, The response times of priority classes under preemptive resume in M/M/m queues, Operations Research, 31 (1983), 456-465.  doi: 10.1287/opre.31.3.456.  Google Scholar

[3]

R. B. Cooper, Introduction to Queueing Theory, 2nd edition, Elsevier North Holland, New York, 1981.  Google Scholar

[4]

M. Fujiki, (Japanese) Fundamental theory and application on communication traffic. 5 queueing theory (part 2), Transactions of the Institute of Electronics and Communication Engineers of Japan, 55 (1972), 1194-1200.   Google Scholar

[5]

D. P. Gaver Jr., A waiting line with interrupted service, including priorities, Journal of the Royal Statistical Society, Series B (Methodological), 24 (1962), 73-90.   Google Scholar

[6]

V. G. Kulkarni, Modeling and Analysis of Stochastic Systems, Chapman & Hall, Boca Raton, Florida, 1995.  Google Scholar

[7]

M. Segal, A multiserver system with preemptive priorities, Operations Research, 18 (1970), 316-323.  doi: 10.1287/opre.18.2.316.  Google Scholar

[8]

H. Takagi, Detailed analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue, in Queueing Theory and Network Applications (eds. T. V. Do, Y. Takahashi, W. Yue and V.-Ha Nguen), Springer, (2016), 3–17. Google Scholar

[9]

H. Takagi, Analysis of the response and waiting times in the M/M/m LCFS preemptive-resume priority queue, International Journal of Pure and Applied Mathematics, 109 (2016), 325-370.  doi: 10.12732/ijpam.v.109i2.12.  Google Scholar

[10]

A. G. Tatashev, Calculation of the distribution of the waiting time in a multiple-channel queueing system with fixed priorities, Engineering Cybernetics, 22 (1984), 59-62, (Originally published in Tekhnicheskaya Kibernetika, 1983, 163--166).   Google Scholar

[11]

H. M. Taylor and S. Karlin, An Introduction to Stochastic Modeling, 3rd edition, Academic Press, San Diego, California, 1998.  Google Scholar

[12]

H. White and L. S. Christie, Queuing with preemptive priorities or with breakdown, Operations Research, 6 (1958), 79-95.  doi: 10.1287/opre.6.1.79.  Google Scholar

[13]

S. Zeltyn, Z. Feldman and S. Wasserkrug, Waiting and sojourn times in a multi-server queue with mixed priorities, Queueing Systems, 61 (2009), 305-328.  doi: 10.1007/s11134-009-9110-4.  Google Scholar

show all references

The reviewing process of the paper was handled by Wuyi Yue and Yutaka Takahashi as Guest Editors.

References:
[1]

I. Brosh, Preemptive priority assignment in multichannel systems, Operations Research, 17 (1969), 526-535.  doi: 10.1287/opre.17.3.526.  Google Scholar

[2]

J. P. Buzen and A. B. Bondi, The response times of priority classes under preemptive resume in M/M/m queues, Operations Research, 31 (1983), 456-465.  doi: 10.1287/opre.31.3.456.  Google Scholar

[3]

R. B. Cooper, Introduction to Queueing Theory, 2nd edition, Elsevier North Holland, New York, 1981.  Google Scholar

[4]

M. Fujiki, (Japanese) Fundamental theory and application on communication traffic. 5 queueing theory (part 2), Transactions of the Institute of Electronics and Communication Engineers of Japan, 55 (1972), 1194-1200.   Google Scholar

[5]

D. P. Gaver Jr., A waiting line with interrupted service, including priorities, Journal of the Royal Statistical Society, Series B (Methodological), 24 (1962), 73-90.   Google Scholar

[6]

V. G. Kulkarni, Modeling and Analysis of Stochastic Systems, Chapman & Hall, Boca Raton, Florida, 1995.  Google Scholar

[7]

M. Segal, A multiserver system with preemptive priorities, Operations Research, 18 (1970), 316-323.  doi: 10.1287/opre.18.2.316.  Google Scholar

[8]

H. Takagi, Detailed analysis of the response time and waiting time in the M/M/m FCFS preemptive-resume priority queue, in Queueing Theory and Network Applications (eds. T. V. Do, Y. Takahashi, W. Yue and V.-Ha Nguen), Springer, (2016), 3–17. Google Scholar

[9]

H. Takagi, Analysis of the response and waiting times in the M/M/m LCFS preemptive-resume priority queue, International Journal of Pure and Applied Mathematics, 109 (2016), 325-370.  doi: 10.12732/ijpam.v.109i2.12.  Google Scholar

[10]

A. G. Tatashev, Calculation of the distribution of the waiting time in a multiple-channel queueing system with fixed priorities, Engineering Cybernetics, 22 (1984), 59-62, (Originally published in Tekhnicheskaya Kibernetika, 1983, 163--166).   Google Scholar

[11]

H. M. Taylor and S. Karlin, An Introduction to Stochastic Modeling, 3rd edition, Academic Press, San Diego, California, 1998.  Google Scholar

[12]

H. White and L. S. Christie, Queuing with preemptive priorities or with breakdown, Operations Research, 6 (1958), 79-95.  doi: 10.1287/opre.6.1.79.  Google Scholar

[13]

S. Zeltyn, Z. Feldman and S. Wasserkrug, Waiting and sojourn times in a multi-server queue with mixed priorities, Queueing Systems, 61 (2009), 305-328.  doi: 10.1007/s11134-009-9110-4.  Google Scholar

Figure 1.  Mean response for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Mean waiting time for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  State transition diagram for a customer of class $ p $ until service completion.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Second moment of the response time for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Third moment of the response time for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  State transition diagram for a customer of class $ p $ until service preemption or completion.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  Second moment of the waiting time for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  Third moment of the waiting time for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Covariance of the total waiting time and the total service time for a customer of class $ p $
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Mean and the second and third moments of the initial waiting time $ W _p ^\circ $ and the waiting time $ W _p $ for a customer of class $ p = 4 $
$ \lambda $ $ E [W _4 ^\circ] $ $ E [W _4] $ $ E [( W _4 ^\circ ) ^2] $ $ E [( W _4 ) ^2] $ $ E [( W _4 ^\circ ) ^3] $ $ E [( W _4 ) ^3] $
1 0.00113 0.00306 0.00076 0.00208 0.00084 0.00233
2 0.02843 0.06234 0.03404 0.07668 0.06965 0.15964
3 0.21468 0.37324 0.51808 0.92966 2.12874 3.88666
4 1.38528 1.86222 9.00433 12.3304 95.5844 131.932
4.5 4.69227 5.47392 69.7454 81.9532 1623.17 1911.54
4.8 16.1018 17.1546 634.213 676.740 37923.0 40476.7
Table Options

Download as excel

$ \lambda $ $ E [W _4 ^\circ] $ $ E [W _4] $ $ E [( W _4 ^\circ ) ^2] $ $ E [( W _4 ) ^2] $ $ E [( W _4 ^\circ ) ^3] $ $ E [( W _4 ) ^3] $
1 0.00113 0.00306 0.00076 0.00208 0.00084 0.00233
2 0.02843 0.06234 0.03404 0.07668 0.06965 0.15964
3 0.21468 0.37324 0.51808 0.92966 2.12874 3.88666
4 1.38528 1.86222 9.00433 12.3304 95.5844 131.932
4.5 4.69227 5.47392 69.7454 81.9532 1623.17 1911.54
4.8 16.1018 17.1546 634.213 676.740 37923.0 40476.7
[1]

Omer Gursoy, Kamal Adli Mehr, Nail Akar. Steady-state and first passage time distributions for waiting times in the $ MAP/M/s+G $ queueing model with generally distributed patience times. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021078
[2]

Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199
[3]

Qiwei Wu, Liping Luan. Large-time behavior of solutions to unipolar Euler-Poisson equations with time-dependent damping. Communications on Pure & Applied Analysis, 2021, 20 (3) : 995-1023. doi: 10.3934/cpaa.2021003
[4]

Elimhan N. Mahmudov. Second order discrete time-varying and time-invariant linear continuous systems and Kalman type conditions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021010
[5]

Olivier Ley, Erwin Topp, Miguel Yangari. Some results for the large time behavior of Hamilton-Jacobi equations with Caputo time derivative. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3555-3577. doi: 10.3934/dcds.2021007
[6]

Meiqiao Ai, Zhimin Zhang, Wenguang Yu. First passage problems of refracted jump diffusion processes and their applications in valuing equity-linked death benefits. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021039
[7]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075
[8]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183
[9]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493
[10]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189
[11]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[12]

Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195
[13]

Horst R. Thieme. Discrete-time dynamics of structured populations via Feller kernels. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021082
[14]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2891-2905. doi: 10.3934/dcds.2020390
[15]

Xiaochen Mao, Weijie Ding, Xiangyu Zhou, Song Wang, Xingyong Li. Complexity in time-delay networks of multiple interacting neural groups. Electronic Research Archive, , () : -. doi: 10.3934/era.2021022
[16]

Peng Zhang, Yongquan Zeng, Guotai Chi. Time-consistent multiperiod mean semivariance portfolio selection with the real constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1663-1680. doi: 10.3934/jimo.2020039
[17]

Paul Deuring. Spatial asymptotics of mild solutions to the time-dependent Oseen system. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021044
[18]

Changjun Yu, Lei Yuan, Shuxuan Su. A new gradient computational formula for optimal control problems with time-delay. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021076
[19]

Ying Sui, Huimin Yu. Singularity formation for compressible Euler equations with time-dependent damping. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021062
[20]

Tianhu Yu, Jinde Cao, Chuangxia Huang. Finite-time cluster synchronization of coupled dynamical systems with impulsive effects. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3595-3620. doi: 10.3934/dcdsb.2020248

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (88)
  • HTML views (470)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences