Figure 1.
Mean response for a customer of class $ p $
-
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
Professor Emeritus, University of Tsukuba, Faculty of Engineering, Information and Systems, 1-1-1 Tennoudai, Tsukuba-shi, Ibaraki 305-8573, Japan |
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 and 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. |
| [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. |
| [3] |
R. B. Cooper,
Introduction to Queueing Theory, 2nd edition, Elsevier North Holland, New York, 1981. |
| [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.
|
| [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.
|
| [6] |
V. G. Kulkarni,
Modeling and Analysis of Stochastic Systems, Chapman & Hall, Boca Raton, Florida, 1995. |
| [7] |
M. Segal,
A multiserver system with preemptive priorities, Operations Research, 18 (1970), 316-323.
doi: 10.1287/opre.18.2.316. |
| [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. |
| [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. |
| [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).
|
| [11] |
H. M. Taylor and S. Karlin,
An Introduction to Stochastic Modeling, 3rd edition, Academic Press, San Diego, California, 1998. |
| [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. |
| [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. |
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. |
| [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. |
| [3] |
R. B. Cooper,
Introduction to Queueing Theory, 2nd edition, Elsevier North Holland, New York, 1981. |
| [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.
|
| [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.
|
| [6] |
V. G. Kulkarni,
Modeling and Analysis of Stochastic Systems, Chapman & Hall, Boca Raton, Florida, 1995. |
| [7] |
M. Segal,
A multiserver system with preemptive priorities, Operations Research, 18 (1970), 316-323.
doi: 10.1287/opre.18.2.316. |
| [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. |
| [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. |
| [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).
|
| [11] |
H. M. Taylor and S. Karlin,
An Introduction to Stochastic Modeling, 3rd edition, Academic Press, San Diego, California, 1998. |
| [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. |
| [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. |
Figure 2.
Mean waiting time for a customer of class $ p $
Figure 3.
State transition diagram for a customer of class $ p $ until service completion.
Figure 4.
Second moment of the response time for a customer of class $ p $
Figure 5.
Third moment of the response time for a customer of class $ p $
Figure 6.
State transition diagram for a customer of class $ p $ until service preemption or completion.
Figure 7.
Second moment of the waiting time for a customer of class $ p $
Figure 8.
Third moment of the waiting time for a customer of class $ p $
Figure 9.
Covariance of the total waiting time and the total service time for a customer of class $ p $
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 $
| 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 | 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2017, 13 (4) : 1901-1926. doi: 10.3934/jimo.2017024 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]