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

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

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.

Citation: Jeongsim Kim, Bara Kim. Stability of a queue with discriminatory random order service discipline and heterogeneous servers. Journal of Industrial and 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.

[2]

U. AyestaA. 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. 

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

[4]

H. R. GailS. 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.

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

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

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

[8]

Q.-M. HeH. 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.

[9]

A. IzagirreU. 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.

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

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

[12]

J. KimJ. 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.

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

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

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

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.

[2]

U. AyestaA. 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. 

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

[4]

H. R. GailS. 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.

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

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

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

[8]

Q.-M. HeH. 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.

[9]

A. IzagirreU. 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.

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

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

[12]

J. KimJ. 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.

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

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

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

Figure 1.  The curve dividing the two regions
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 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 4.  The curve dividing the stable and unstable regions
Figure 5.  The stable and unstable regions of Example 2 (when $\mu_{11}=0.9$ and $\mu_{12}=0.1$)
[1]

Zsolt Saffer, Miklós Telek, Gábor Horváth. Analysis of Markov-modulated fluid polling systems with gated discipline. Journal of Industrial and 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 and 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 and Continuous Dynamical Systems, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

[4]

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 and Management Optimization, 2017, 13 (3) : 1365-1381. doi: 10.3934/jimo.2016077

[5]

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 and Management Optimization, 2010, 6 (4) : 929-944. doi: 10.3934/jimo.2010.6.929

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Daoyi Xu, Yumei Huang, Zhiguo Yang. Existence theorems for periodic Markov process and stochastic functional differential equations. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Games, 2014, 1 (1) : 105-119. doi: 10.3934/jdg.2014.1.105

2020 Impact Factor: 1.801

Metrics

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

Other articles
by authors

[Back to Top]