• Previous Article
    Transient analysis of N-policy queue with system disaster repair preventive maintenance re-service balking closedown and setup times
  • JIMO Home
  • This Issue
  • Next Article
    A robust reduced-order observers design approach for linear discrete periodic systems
November  2020, 16(6): 2813-2842. doi: 10.3934/jimo.2019082

Analysis of the queue lengths in a priority retrial queue with constant retrial policy

1. 

Department of Telecommunications and Information Processing, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium

2. 

Division of Policy and Planning Sciences, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan

* Corresponding author: Arnaud Devos

Received  October 2018 Revised  March 2019 Published  November 2020 Early access  July 2019

In this paper, we analyze a priority queueing system with a regular queue and an orbit. Customers in the regular queue have priority over the customers in the orbit. Only the first customer in the orbit (if any) retries to get access to the server, if the queue and server are empty (constant retrial policy). In contrast with existing literature, we assume different service time distributions for the high- and low-priority customers. Closed-form expressions are obtained for the probability generating functions of the number of customers in the queue and orbit, in steady-state. Another contribution is the extensive singularity analysis of these probability generating functions to obtain the stationary (asymptotic) probability mass functions of the queue and orbit lengths. Influences of the service times and the retrial policy are illustrated by means of some numerical examples.

Citation: Arnaud Devos, Joris Walraevens, Tuan Phung-Duc, Herwig Bruneel. Analysis of the queue lengths in a priority retrial queue with constant retrial policy. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2813-2842. doi: 10.3934/jimo.2019082
References:
[1]

J. Abate and W. Whitt, Asymptotics for M/G/1 low-priority waiting-time tail probabilities, Queueing Systems, 25 (1997), 173-233.  doi: 10.1023/A:1019104402024.

[2]

J. AbateG. L. Choudhury and W. Whitt, Waiting-time tail probabilities in queues with long-tail service-time distributions, Queueing Systems, 16 (1994), 311-338.  doi: 10.1007/BF01158960.

[3]

J. R. Artalejo, Accessible bibliography on retrial queues: Progress in 2000–2009, Mathematical and Computer Modelling, 51 (2010), 1071-1081.  doi: 10.1016/j.mcm.2009.12.011.

[4]

J. R. Artalejo and A. Gómez-Corral, Retrial Queueing Systems, Springer-Verlag Berlin Heidelberg, 2008. doi: 10.1007/978-3-540-78725-9.

[5]

I. Atencia and P. Moreno, A single-server retrial queue with general retrial times and Bernoulli schedule, Applied Mathematics and Computation, 162 (2005), 855-880.  doi: 10.1016/j.amc.2003.12.128.

[6]

N. H. Bingham, C. M. Goldie and J. L. Teugels, Regular Variation, Cambridge University Press, 1986. doi: 10.1017/CBO9780511721434.

[7]

B. D. ChoiK. K. Park and C. E. M. Pearce, An M/M/1 retrial queue with control policy and general retrial times, Queueing Systems, 14 (1993), 275-292.  doi: 10.1007/BF01158869.

[8]

B. D. Choi and Y. Chang, Single server retrial queues with priority calls, Mathematical and Computer Modelling, 30 (1999), 7-32.  doi: 10.1016/S0895-7177(99)00129-6.

[9]

A. Devos, J. Walraevens and H. Bruneel, A priority retrial queue with constant retrial policy, International Conference on Queueing Theory and Network Applications, (2018), 3–21. doi: 10.1007/978-3-319-93736-6_1.

[10]

G. Falin and J. G. Templeton, Retrial Queues, CRC Press, 1997. doi: 10.1007/978-1-4899-2977-8.

[11]

K. Farahmand, Single line queue with repeated demands, Queueing Systems, 6 (1990), 223-228.  doi: 10.1007/BF02411475.

[12]

G. Fayolle, A simple telephone exchange with delayed feedbacks, Proc. of the International Seminar on Teletraffic Analysis and Computer Performance Evaluation, (1986), 245–253.

[13]

P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM Journal on Discrete Mathematics, 3 (1990), 216-240.  doi: 10.1137/0403019.

[14]

P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009. doi: 10.1017/CBO9780511801655.

[15]

S. Gao, A preemptive priority retrial queue with two classes of customers and general retrial times, Operational Research, 15 (2015), 233-251.  doi: 10.1007/s12351-015-0175-z.

[16]

A. Gómez-Corral, Stochastic analysis of a single server retrial queue with general retrial times, Naval Research Logistics (NRL), 46 (1999), 561-581.  doi: 10.1002/(SICI)1520-6750(199908)46:5<561::AID-NAV7>3.0.CO;2-G.

[17]

J. KimB. Kim and S. S. Ko, Tail asymptotics for the queue size distribution in an M/G/1 retrial queue, Journal of Applied Probability, 44 (2007), 1111-1118.  doi: 10.1239/jap/1197908829.

[18]

H. Li and Y. Q. Zhao, Exact tail asymptotics in a priority queue characterizations of the non-preemptive model, Queueing Systems, 68 (2011), 165-192.  doi: 10.1007/s11134-011-9252-z.

[19]

T. MaertensJ. Walraevens and H. Bruneel, Priority queueing systems: from probability generating functions to tail probabilities, Queueing Systems, 55 (2007), 27-39.  doi: 10.1007/s11134-006-9003-8.

[20]

T. Phung-DucW. RogiestY. Takahashi and H. Bruneel, Retrial queues with balanced call blending: Analysis of single-server and multiserver model, Annals of Operations Research, 239 (2016), 429-449.  doi: 10.1007/s10479-014-1598-2.

[21]

T. Phung-Duc and W. Rogiest, Two way communication retrial queues with balanced call blending, International Conference on Analytical and Stochastic Modeling Techniques and Applications, (2012), 16–31. doi: 10.1007/978-3-642-30782-9_2.

[22]

W. ShangL. Liu and Q. Li, Tail asymptotics for the queue length in an M/G/1 retrial queue, Queueing Systems, 52 (2006), 193-198.  doi: 10.1007/s11134-006-5223-1.

[23]

J. Walraevens, Discrete-Time Queueing Models With Priorities, Ph.D thesis, Ghent University, 2004.

[24]

J. Walraevens, D. Claeys and T. Phung-Duc, Asymptotics of queue length distributions in priority retrial queues, arXiv: 1801.06993, (2018). doi: 10.1016/j.peva.2018.10.004.

[25]

J. Walraevens and B. Steyaert and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling, Computers & Operations Research, 30 (2003), 2003. doi: 10.1007/s10479-006-0053-4.

show all references

References:
[1]

J. Abate and W. Whitt, Asymptotics for M/G/1 low-priority waiting-time tail probabilities, Queueing Systems, 25 (1997), 173-233.  doi: 10.1023/A:1019104402024.

[2]

J. AbateG. L. Choudhury and W. Whitt, Waiting-time tail probabilities in queues with long-tail service-time distributions, Queueing Systems, 16 (1994), 311-338.  doi: 10.1007/BF01158960.

[3]

J. R. Artalejo, Accessible bibliography on retrial queues: Progress in 2000–2009, Mathematical and Computer Modelling, 51 (2010), 1071-1081.  doi: 10.1016/j.mcm.2009.12.011.

[4]

J. R. Artalejo and A. Gómez-Corral, Retrial Queueing Systems, Springer-Verlag Berlin Heidelberg, 2008. doi: 10.1007/978-3-540-78725-9.

[5]

I. Atencia and P. Moreno, A single-server retrial queue with general retrial times and Bernoulli schedule, Applied Mathematics and Computation, 162 (2005), 855-880.  doi: 10.1016/j.amc.2003.12.128.

[6]

N. H. Bingham, C. M. Goldie and J. L. Teugels, Regular Variation, Cambridge University Press, 1986. doi: 10.1017/CBO9780511721434.

[7]

B. D. ChoiK. K. Park and C. E. M. Pearce, An M/M/1 retrial queue with control policy and general retrial times, Queueing Systems, 14 (1993), 275-292.  doi: 10.1007/BF01158869.

[8]

B. D. Choi and Y. Chang, Single server retrial queues with priority calls, Mathematical and Computer Modelling, 30 (1999), 7-32.  doi: 10.1016/S0895-7177(99)00129-6.

[9]

A. Devos, J. Walraevens and H. Bruneel, A priority retrial queue with constant retrial policy, International Conference on Queueing Theory and Network Applications, (2018), 3–21. doi: 10.1007/978-3-319-93736-6_1.

[10]

G. Falin and J. G. Templeton, Retrial Queues, CRC Press, 1997. doi: 10.1007/978-1-4899-2977-8.

[11]

K. Farahmand, Single line queue with repeated demands, Queueing Systems, 6 (1990), 223-228.  doi: 10.1007/BF02411475.

[12]

G. Fayolle, A simple telephone exchange with delayed feedbacks, Proc. of the International Seminar on Teletraffic Analysis and Computer Performance Evaluation, (1986), 245–253.

[13]

P. Flajolet and A. Odlyzko, Singularity analysis of generating functions, SIAM Journal on Discrete Mathematics, 3 (1990), 216-240.  doi: 10.1137/0403019.

[14]

P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009. doi: 10.1017/CBO9780511801655.

[15]

S. Gao, A preemptive priority retrial queue with two classes of customers and general retrial times, Operational Research, 15 (2015), 233-251.  doi: 10.1007/s12351-015-0175-z.

[16]

A. Gómez-Corral, Stochastic analysis of a single server retrial queue with general retrial times, Naval Research Logistics (NRL), 46 (1999), 561-581.  doi: 10.1002/(SICI)1520-6750(199908)46:5<561::AID-NAV7>3.0.CO;2-G.

[17]

J. KimB. Kim and S. S. Ko, Tail asymptotics for the queue size distribution in an M/G/1 retrial queue, Journal of Applied Probability, 44 (2007), 1111-1118.  doi: 10.1239/jap/1197908829.

[18]

H. Li and Y. Q. Zhao, Exact tail asymptotics in a priority queue characterizations of the non-preemptive model, Queueing Systems, 68 (2011), 165-192.  doi: 10.1007/s11134-011-9252-z.

[19]

T. MaertensJ. Walraevens and H. Bruneel, Priority queueing systems: from probability generating functions to tail probabilities, Queueing Systems, 55 (2007), 27-39.  doi: 10.1007/s11134-006-9003-8.

[20]

T. Phung-DucW. RogiestY. Takahashi and H. Bruneel, Retrial queues with balanced call blending: Analysis of single-server and multiserver model, Annals of Operations Research, 239 (2016), 429-449.  doi: 10.1007/s10479-014-1598-2.

[21]

T. Phung-Duc and W. Rogiest, Two way communication retrial queues with balanced call blending, International Conference on Analytical and Stochastic Modeling Techniques and Applications, (2012), 16–31. doi: 10.1007/978-3-642-30782-9_2.

[22]

W. ShangL. Liu and Q. Li, Tail asymptotics for the queue length in an M/G/1 retrial queue, Queueing Systems, 52 (2006), 193-198.  doi: 10.1007/s11134-006-5223-1.

[23]

J. Walraevens, Discrete-Time Queueing Models With Priorities, Ph.D thesis, Ghent University, 2004.

[24]

J. Walraevens, D. Claeys and T. Phung-Duc, Asymptotics of queue length distributions in priority retrial queues, arXiv: 1801.06993, (2018). doi: 10.1016/j.peva.2018.10.004.

[25]

J. Walraevens and B. Steyaert and H. Bruneel, Performance analysis of a single-server ATM queue with a priority scheduling, Computers & Operations Research, 30 (2003), 2003. doi: 10.1007/s10479-006-0053-4.

Figure 1.  Mean values of the queue and orbit lengths versus the mean class-2 service times ($ \rho = 0.7 $, $ \beta_1 = 1 $ and $ \nu = 3 $)
Figure 2.  Mean values of the queue and orbit lengths versus the mean class-1 service times ($ \rho = 0.7 $, $ \beta_2 = 1.5 $ and $ \nu = 3 $)
Figure 3.  Mean values of the queue and orbit lengths versus the mean class-1 service times ($ \rho = 0.7 $, $ \beta_2 = 1.5 $ and $ R^*(s) = 1 $)
Figure 4.  Variances of the queue and orbit length versus the load ($ \beta_1 = \beta_2 = 1.1 $ and $ \nu = 4 $)
Figure 5.  Regions for the tail behaviour as a function of the mean service times of both classes ($ \lambda_1 = \lambda_2 = 0.3 $ and $ \nu = 3 $)
Figure 6.  Regions for the tail behaviour as a function of the mean service times of both classes ($ \lambda_1 = \lambda_2 = 0.3 $ and $ R^*(s) = 1 $)
Figure 7.  Tail behaviour of the orbit length for different service time distributions ($ \lambda_1 = \lambda_2 = 0.3 $, $ \beta_1 = 1.2 $, $ \beta_2 = 1 $, $ \nu = 3 $ and $ \alpha_1 = \alpha_2 = -2.5 $)
[1]

Raina Raj, Vidyottama Jain. Optimization of traffic control in $ MMAP\mathit{[2]}/PH\mathit{[2]}/S$ priority queueing model with $ PH $ retrial times and the preemptive repeat policy. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022044

[2]

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

[3]

Zhanyou Ma, Wuyi Yue, Xiaoli Su. Performance analysis of a Geom/Geom/1 queueing system with variable input probability. Journal of Industrial and Management Optimization, 2011, 7 (3) : 641-653. doi: 10.3934/jimo.2011.7.641

[4]

Włodzimierz M. Tulczyjew, Paweł Urbański. Regularity of generating families of functions. Journal of Geometric Mechanics, 2010, 2 (2) : 199-221. doi: 10.3934/jgm.2010.2.199

[5]

Simone Vazzoler. A note on the normalization of generating functions. Journal of Geometric Mechanics, 2018, 10 (2) : 209-215. doi: 10.3934/jgm.2018008

[6]

Dequan Yue, Wuyi Yue, Zsolt Saffer, Xiaohong Chen. Analysis of an M/M/1 queueing system with impatient customers and a variant of multiple vacation policy. Journal of Industrial and Management Optimization, 2014, 10 (1) : 89-112. doi: 10.3934/jimo.2014.10.89

[7]

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

[8]

Huiyan Xue, Antonella Zanna. Generating functions and volume preserving mappings. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1229-1249. doi: 10.3934/dcds.2014.34.1229

[9]

Lijin Wang, Jialin Hong. Generating functions for stochastic symplectic methods. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1211-1228. doi: 10.3934/dcds.2014.34.1211

[10]

Dhanya Shajin, A. N. Dudin, Olga Dudina, A. Krishnamoorthy. A two-priority single server retrial queue with additional items. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2891-2912. doi: 10.3934/jimo.2019085

[11]

Zhanyou Ma, Pengcheng Wang, Wuyi Yue. Performance analysis and optimization of a pseudo-fault Geo/Geo/1 repairable queueing system with N-policy, setup time and multiple working vacations. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1467-1481. doi: 10.3934/jimo.2017002

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

Gang Chen, Zaiming Liu, Jinbiao Wu. Optimal threshold control of a retrial queueing system with finite buffer. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1537-1552. doi: 10.3934/jimo.2017006

[14]

Bara Kim. Stability of a retrial queueing network with different classes of customers and restricted resource pooling. Journal of Industrial and Management Optimization, 2011, 7 (3) : 753-765. doi: 10.3934/jimo.2011.7.753

[15]

Arthur Fleig, Lars Grüne. Strict dissipativity analysis for classes of optimal control problems involving probability density functions. Mathematical Control and Related Fields, 2021, 11 (4) : 935-964. doi: 10.3934/mcrf.2020053

[16]

Domingo Gómez-Pérez, László Mérai. Algebraic dependence in generating functions and expansion complexity. Advances in Mathematics of Communications, 2020, 14 (2) : 307-318. doi: 10.3934/amc.2020022

[17]

Rakesh Nandi, Sujit Kumar Samanta, Chesoong Kim. Analysis of $ D $-$ BMAP/G/1 $ queueing system under $ N $-policy and its cost optimization. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3603-3631. doi: 10.3934/jimo.2020135

[18]

Madhu Jain, Sudeep Singh Sanga. Admission control for finite capacity queueing model with general retrial times and state-dependent rates. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2625-2649. doi: 10.3934/jimo.2019073

[19]

Yi Peng, Jinbiao Wu. On the $ BMAP_1, BMAP_2/PH/g, c $ retrial queueing system. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3373-3391. doi: 10.3934/jimo.2020124

[20]

Ana Paula S. Dias, Paul C. Matthews, Ana Rodrigues. Generating functions for Hopf bifurcation with $ S_n$-symmetry. Discrete and Continuous Dynamical Systems, 2009, 25 (3) : 823-842. doi: 10.3934/dcds.2009.25.823

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (330)
  • HTML views (862)
  • Cited by (0)

[Back to Top]