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

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]

Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323
[2]

Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032
[3]

Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299
[4]

Xu Zhang, Chuang Zheng, Enrique Zuazua. Time discrete wave equations: Boundary observability and control. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 571-604. doi: 10.3934/dcds.2009.23.571
[5]

Angelica Pachon, Federico Polito, Costantino Ricciuti. On discrete-time semi-Markov processes. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1499-1529. doi: 10.3934/dcdsb.2020170
[6]

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

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 - A, 2021  doi: 10.3934/dcds.2021007
[8]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046
[9]

Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137
[10]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336
[11]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339
[12]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444
[13]

Veena Goswami, Gopinath Panda. Optimal customer behavior in observable and unobservable discrete-time queues. Journal of Industrial & Management Optimization, 2021, 17 (1) : 299-316. doi: 10.3934/jimo.2019112
[14]

Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113
[15]

Zhimin Li, Tailei Zhang, Xiuqing Li. Threshold dynamics of stochastic models with time delays: A case study for Yunnan, China. Electronic Research Archive, 2021, 29 (1) : 1661-1679. doi: 10.3934/era.2020085
[16]

Rong Wang, Yihong Du. Long-time dynamics of a diffusive epidemic model with free boundaries. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020360
[17]

Dong-Ho Tsai, Chia-Hsing Nien. On space-time periodic solutions of the one-dimensional heat equation. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3997-4017. doi: 10.3934/dcds.2020037
[18]

Junyong Eom, Kazuhiro Ishige. Large time behavior of ODE type solutions to nonlinear diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3395-3409. doi: 10.3934/dcds.2019229
[19]

Nguyen Huy Tuan, Vo Van Au, Runzhang Xu. Semilinear Caputo time-fractional pseudo-parabolic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020282
[20]

Ming Chen, Hao Wang. Dynamics of a discrete-time stoichiometric optimal foraging model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 107-120. doi: 10.3934/dcdsb.2020264

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (77)
  • HTML views (468)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences