American Institute of Mathematical Sciences

Advanced
July  2017, 13(3): 1237-1254. doi: 10.3934/jimo.2016070

Stability of a queue with discriminatory random order service discipline and heterogeneous servers

Jeongsim Kim 1, and  Bara Kim 2,,

1. 

Department of Mathematics Education, Chungbuk National University, 1 Chungdae-ro, Seowon-gu, Cheongju, Chungbuk, 28644, Korea
2. 

Department of Mathematics, Korea University, 145 Anam-ro, Seongbuk-gu, Seoul, 02841, Korea

* Corresponding author: Bara Kim

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

Received  September 2015 Published  October 2016

We consider a queueing system with two classes of customers, two heterogeneous servers, and discriminatory random order service (DROS) discipline. The two servers may have either the same or different DROS weights for each class. Customers of each class arrive according to a Poisson process and the service times of each class of customers are assumed to be exponentially distributed with service rate depending on both the customer's class and the servers. We provide stability and instability conditions for this two-class two-server queue with DROS discipline.

Keywords: Stability, discriminatory random order service discipline, Markov process, test function.
Mathematics Subject Classification: Primary: 60K25; Secondary: 60J27.
Citation: Jeongsim Kim, Bara Kim. Stability of a queue with discriminatory random order service discipline and heterogeneous servers. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1237-1254. doi: 10.3934/jimo.2016070
References:
[1]

W. J. Anderson, Continuous-Time Markov Chains: An Applications-Oriented Approach, Springer-Verlag, 1991. doi: 10.1007/978-1-4612-3038-0.  Google Scholar

[2]

U. Ayesta, A. Izagirre and I. M. Verloop, Heavy-traffic analysis of the discriminatory random-order-service discipline, Performance Evaluation Review -Special Issue on IFIP Performance 2011 -29th International Symposium on Computer Performance, Modeling, Measurement and Evaluation, 39 (2011), 41-43.   Google Scholar

[3]

G. Fayolle, V. A. Malyshev and M. V. Menshikov, Topics in the Constructive Theory of Countable Markov Chains, Cambridge University Press, 1995. doi: 10.1017/CBO9780511984020.  Google Scholar

[4]

H. R. Gail, S. L. Hantler and B. A. Taylor, Analysis of a non-preemptive priority multiserver queue, Advances in Applied Probability, 20 (1988), 852-879.  doi: 10.2307/1427364.  Google Scholar

[5]

T. Hanschke, Explicit formulas for the characteristics of the M/M/2/2 queue with repeated attempts, Journal of Applied Probability, 24 (1987), 486-494.  doi: 10.1017/S0021900200031120.  Google Scholar

[6]

T. Hanschke, A matrix continued fraction algorithm for the multiserver repeated order queue, Mathematical and Computer Modelling, 30 (1999), 159-170.  doi: 10.1016/S0895-7177(99)00139-9.  Google Scholar

[7]

M. Haviv and J. van der Wal, Equilibrium strategies for processor sharing and queues with relative priorities, Probability in the Engineering and Informational Sciences, 11 (1997), 403-412.  doi: 10.1017/S0269964800004940.  Google Scholar

[8]

Q.-M. He, H. Li and Y. Q. Zhao, Ergodicity of the $BMAP/PH/s/s + K$ retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347.  doi: 10.1023/A:1019110631467.  Google Scholar

[9]

A. Izagirre, U. Ayesta and I. M. Verloop, Heavy-traffic analysis of a non-preemptive multi-class queue with relative priorities, Probability in the Engineering and Informational Sciences, 29 (2015), 153-180.  doi: 10.1017/S0269964814000278.  Google Scholar

[10]

B. Kim and J. Kim, Stability of a two-class two-server retrial queueing system, Performance Evaluation, 88/89 (2015), 1-17.  doi: 10.1016/j.peva.2015.02.002.  Google Scholar

[11]

B. Kim and I. Lee, Tests for nonergodicity of denumerable continuous time Markov processes, Computers and Mathematics with Applications, 55 (2008), 1310-1321.  doi: 10.1016/j.camwa.2007.07.003.  Google Scholar

[12]

J. Kim, J. Kim and B. Kim, Analysis of the M/G/1 queue with discriminatory random order service policy, Performance Evaluation, 68 (2011), 256-270.  doi: 10.1016/j.peva.2010.12.001.  Google Scholar

[13]

S. P. Meyn and R. L. Tweedie, Stability of Markovian processes III: Foster-Lyapunov criteria for continuous-time processes, Advances in Applied Probability, 25 (1993), 518-548.  doi: 10.2307/1427522.  Google Scholar

[14]

Y. W. Shin and D. H. Moon, M/M/c retrial queue with multiclass of customers, Methodology and Computing in Applied Probability, 16 (2014), 931-949.  doi: 10.1007/s11009-013-9340-0.  Google Scholar

[15]

R. L. Tweedie, Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes, Journal of Applied Probability, 18 (1981), 122-130.  doi: 10.1017/S0021900200097667.  Google Scholar

show all references

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

References:
[1]

W. J. Anderson, Continuous-Time Markov Chains: An Applications-Oriented Approach, Springer-Verlag, 1991. doi: 10.1007/978-1-4612-3038-0.  Google Scholar

[2]

U. Ayesta, A. Izagirre and I. M. Verloop, Heavy-traffic analysis of the discriminatory random-order-service discipline, Performance Evaluation Review -Special Issue on IFIP Performance 2011 -29th International Symposium on Computer Performance, Modeling, Measurement and Evaluation, 39 (2011), 41-43.   Google Scholar

[3]

G. Fayolle, V. A. Malyshev and M. V. Menshikov, Topics in the Constructive Theory of Countable Markov Chains, Cambridge University Press, 1995. doi: 10.1017/CBO9780511984020.  Google Scholar

[4]

H. R. Gail, S. L. Hantler and B. A. Taylor, Analysis of a non-preemptive priority multiserver queue, Advances in Applied Probability, 20 (1988), 852-879.  doi: 10.2307/1427364.  Google Scholar

[5]

T. Hanschke, Explicit formulas for the characteristics of the M/M/2/2 queue with repeated attempts, Journal of Applied Probability, 24 (1987), 486-494.  doi: 10.1017/S0021900200031120.  Google Scholar

[6]

T. Hanschke, A matrix continued fraction algorithm for the multiserver repeated order queue, Mathematical and Computer Modelling, 30 (1999), 159-170.  doi: 10.1016/S0895-7177(99)00139-9.  Google Scholar

[7]

M. Haviv and J. van der Wal, Equilibrium strategies for processor sharing and queues with relative priorities, Probability in the Engineering and Informational Sciences, 11 (1997), 403-412.  doi: 10.1017/S0269964800004940.  Google Scholar

[8]

Q.-M. He, H. Li and Y. Q. Zhao, Ergodicity of the $BMAP/PH/s/s + K$ retrial queue with PH-retrial times, Queueing Systems, 35 (2000), 323-347.  doi: 10.1023/A:1019110631467.  Google Scholar

[9]

A. Izagirre, U. Ayesta and I. M. Verloop, Heavy-traffic analysis of a non-preemptive multi-class queue with relative priorities, Probability in the Engineering and Informational Sciences, 29 (2015), 153-180.  doi: 10.1017/S0269964814000278.  Google Scholar

[10]

B. Kim and J. Kim, Stability of a two-class two-server retrial queueing system, Performance Evaluation, 88/89 (2015), 1-17.  doi: 10.1016/j.peva.2015.02.002.  Google Scholar

[11]

B. Kim and I. Lee, Tests for nonergodicity of denumerable continuous time Markov processes, Computers and Mathematics with Applications, 55 (2008), 1310-1321.  doi: 10.1016/j.camwa.2007.07.003.  Google Scholar

[12]

J. Kim, J. Kim and B. Kim, Analysis of the M/G/1 queue with discriminatory random order service policy, Performance Evaluation, 68 (2011), 256-270.  doi: 10.1016/j.peva.2010.12.001.  Google Scholar

[13]

S. P. Meyn and R. L. Tweedie, Stability of Markovian processes III: Foster-Lyapunov criteria for continuous-time processes, Advances in Applied Probability, 25 (1993), 518-548.  doi: 10.2307/1427522.  Google Scholar

[14]

Y. W. Shin and D. H. Moon, M/M/c retrial queue with multiclass of customers, Methodology and Computing in Applied Probability, 16 (2014), 931-949.  doi: 10.1007/s11009-013-9340-0.  Google Scholar

[15]

R. L. Tweedie, Criteria for ergodicity, exponential ergodicity and strong ergodicity of Markov processes, Journal of Applied Probability, 18 (1981), 122-130.  doi: 10.1017/S0021900200097667.  Google Scholar

Figure 1.  The curve dividing the two regions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  The stable and unstable regions of Example 1 (when $\mu_{11}=0.9$, $\mu_{12}=0.1$, and $\mu_{21}=\mu_{22}=0.5)$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Simulation results for $N_1(t)$ and $N_2(t)$ in Example 1 (when $\mu_{11}=0.9$, $\mu_{12}=0.1$, $\mu_{21}=\mu_{22}=0.5$, and $\lambda_1=\lambda_2=0.5$)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  The curve dividing the stable and unstable regions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The stable and unstable regions of Example 2 (when $\mu_{11}=0.9$ and $\mu_{12}=0.1$)
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Zsolt Saffer, Miklós Telek, Gábor Horváth. Analysis of Markov-modulated fluid polling systems with gated discipline. Journal of Industrial & Management Optimization, 2021, 17 (2) : 575-599. doi: 10.3934/jimo.2019124
[2]

Willem Mélange, Herwig Bruneel, Bart Steyaert, Dieter Claeys, Joris Walraevens. A continuous-time queueing model with class clustering and global FCFS service discipline. Journal of Industrial & Management Optimization, 2014, 10 (1) : 193-206. doi: 10.3934/jimo.2014.10.193
[3]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261
[4]

Pikkala Vijaya Laxmi, Obsie Mussa Yesuf. Analysis of a finite buffer general input queue with Markovian service process and accessible and non-accessible batch service. Journal of Industrial & Management Optimization, 2010, 6 (4) : 929-944. doi: 10.3934/jimo.2010.6.929
[5]

Gábor Horváth, Zsolt Saffer, Miklós Telek. Queue length analysis of a Markov-modulated vacation queue with dependent arrival and service processes and exhaustive service policy. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1365-1381. doi: 10.3934/jimo.2016077
[6]

Achyutha Krishnamoorthy, Anu Nuthan Joshua. A $ {BMAP/BMSP/1} $ queue with Markov dependent arrival and Markov dependent service batches. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2925-2941. doi: 10.3934/jimo.2020101
[7]

Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279
[8]

Johnathan M. Bardsley. Gaussian Markov random field priors for inverse problems. Inverse Problems & Imaging, 2013, 7 (2) : 397-416. doi: 10.3934/ipi.2013.7.397
[9]

Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems, 2008, 22 (1&2) : 131-164. doi: 10.3934/dcds.2008.22.131
[10]

Felix X.-F. Ye, Yue Wang, Hong Qian. Stochastic dynamics: Markov chains and random transformations. Discrete & Continuous Dynamical Systems - B, 2016, 21 (7) : 2337-2361. doi: 10.3934/dcdsb.2016050
[11]

Manfred Denker, Yuri Kifer, Manuel Stadlbauer. Corrigendum to: Thermodynamic formalism for random countable Markov shifts. Discrete & Continuous Dynamical Systems, 2015, 35 (1) : 593-594. doi: 10.3934/dcds.2015.35.593
[12]

Daoyi Xu, Yumei Huang, Zhiguo Yang. Existence theorems for periodic Markov process and stochastic functional differential equations. Discrete & Continuous Dynamical Systems, 2009, 24 (3) : 1005-1023. doi: 10.3934/dcds.2009.24.1005
[13]

Jean-Pierre Conze, Y. Guivarc'h. Ergodicity of group actions and spectral gap, applications to random walks and Markov shifts. Discrete & Continuous Dynamical Systems, 2013, 33 (9) : 4239-4269. doi: 10.3934/dcds.2013.33.4239
[14]

Peter E. Kloeden, Victor Kozyakin. Asymptotic behaviour of random tridiagonal Markov chains in biological applications. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 453-465. doi: 10.3934/dcdsb.2013.18.453
[15]

Tom Goldstein, Xavier Bresson, Stan Osher. Global minimization of Markov random fields with applications to optical flow. Inverse Problems & Imaging, 2012, 6 (4) : 623-644. doi: 10.3934/ipi.2012.6.623
[16]

Xiangnan He, Wenlian Lu, Tianping Chen. On transverse stability of random dynamical system. Discrete & Continuous Dynamical Systems, 2013, 33 (2) : 701-721. doi: 10.3934/dcds.2013.33.701
[17]

Alvaro Sandroni, Eran Shmaya. A prequential test for exchangeable theories. Journal of Dynamics & Games, 2014, 1 (3) : 497-505. doi: 10.3934/jdg.2014.1.497
[18]

Li Li, Xinzhen Zhang, Zheng-Hai Huang, Liqun Qi. Test of copositive tensors. Journal of Industrial & Management Optimization, 2019, 15 (2) : 881-891. doi: 10.3934/jimo.2018075
[19]

Michal Málek, Peter Raith. Stability of the distribution function for piecewise monotonic maps on the interval. Discrete & Continuous Dynamical Systems, 2018, 38 (5) : 2527-2539. doi: 10.3934/dcds.2018105
[20]

Fernando Luque-Vásquez, J. Adolfo Minjárez-Sosa. Average optimal strategies for zero-sum Markov games with poorly known payoff function on one side. Journal of Dynamics & Games, 2014, 1 (1) : 105-119. doi: 10.3934/jdg.2014.1.105

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (64)
  • HTML views (462)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy