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]

Tuan Phung-Duc, Ken'ichi Kawanishi. Multiserver retrial queue with setup time and its application to data centers. Journal of Industrial & Management Optimization, 2019, 15 (1) : 15-35. doi: 10.3934/jimo.2018030
[2]

Hideaki Takagi. Times until service completion and abandonment in an M/M/$ m$ preemptive-resume LCFS queue with impatient customers. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1701-1726. doi: 10.3934/jimo.2018028
[3]

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
[4]

Shaojun Lan, Yinghui Tang. Performance analysis of a discrete-time $ Geo/G/1$ retrial queue with non-preemptive priority, working vacations and vacation interruption. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1421-1446. doi: 10.3934/jimo.2018102
[5]

Yung Chung Wang, Jenn Shing Wang, Fu Hsiang Tsai. Analysis of discrete-time space priority queue with fuzzy threshold. Journal of Industrial & Management Optimization, 2009, 5 (3) : 467-479. doi: 10.3934/jimo.2009.5.467
[6]

Yutaka Sakuma, Atsushi Inoie, Ken’ichi Kawanishi, Masakiyo Miyazawa. Tail asymptotics for waiting time distribution of an M/M/s queue with general impatient time. Journal of Industrial & Management Optimization, 2011, 7 (3) : 593-606. doi: 10.3934/jimo.2011.7.593
[7]

Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[8]

Qiuying Li, Lifang Huang, Jianshe Yu. Modulation of first-passage time for bursty gene expression via random signals. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1261-1277. doi: 10.3934/mbe.2017065
[9]

Massimiliano Tamborrino. Approximation of the first passage time density of a Wiener process to an exponentially decaying boundary by two-piecewise linear threshold. Application to neuronal spiking activity. Mathematical Biosciences & Engineering, 2016, 13 (3) : 613-629. doi: 10.3934/mbe.2016011
[10]

Biao Xu, Xiuli Xu, Zhong Yao. Equilibrium and optimal balking strategies for low-priority customers in the M/G/1 queue with two classes of customers and preemptive priority. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1599-1615. doi: 10.3934/jimo.2018113
[11]

Zhanyou Ma, Wenbo Wang, Linmin Hu. Performance evaluation and analysis of a discrete queue system with multiple working vacations and non-preemptive priority. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1135-1148. doi: 10.3934/jimo.2018196
[12]

Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767
[13]

Yoshiaki Kawase, Shoji Kasahara. Priority queueing analysis of transaction-confirmation time for Bitcoin. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1077-1098. doi: 10.3934/jimo.2018193
[14]

Andrey Shishkov. Waiting time of propagation and the backward motion of interfaces in thin-film flow theory. Conference Publications, 2007, 2007 (Special) : 938-945. doi: 10.3934/proc.2007.2007.938
[15]

Bara Kim, Jeongsim Kim. Explicit solution for the stationary distribution of a discrete-time finite buffer queue. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1121-1133. doi: 10.3934/jimo.2016.12.1121
[16]

Yongjiang Guo, Yuantao Song. The (functional) law of the iterated logarithm of the sojourn time for a multiclass queue. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1049-1076. doi: 10.3934/jimo.2018192
[17]

Thomas Demoor, Joris Walraevens, Dieter Fiems, Stijn De Vuyst, Herwig Bruneel. Influence of real-time queue capacity on system contents in DiffServ's expedited forwarding per-hop-behavior. Journal of Industrial & Management Optimization, 2010, 6 (3) : 587-602. doi: 10.3934/jimo.2010.6.587
[18]

Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1369-1388. doi: 10.3934/jimo.2019007
[19]

Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. The impact of the $NT$-policy on the behaviour of a discrete-time queue with general service times. Journal of Industrial & Management Optimization, 2014, 10 (1) : 131-149. doi: 10.3934/jimo.2014.10.131
[20]

Michiel De Muynck, Herwig Bruneel, Sabine Wittevrongel. Analysis of a discrete-time queue with general service demands and phase-type service capacities. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1901-1926. doi: 10.3934/jimo.2017024

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (150)
  • HTML views (471)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy