American Institute of Mathematical Sciences

Advanced
October  2017, 13(4): 1901-1926. doi: 10.3934/jimo.2017024

Analysis of a discrete-time queue with general service demands and phase-type service capacities

Michiel De Muynck , , Herwig Bruneel and  Sabine Wittevrongel

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

* Corresponding author: Michiel De Muynck.

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

Received  October 2015 Published  April 2017

In this paper, we analyze a non-classical discrete-time queueing model where customers demand variable amounts of work from a server that is able to perform this work at a varying rate. The service demands of the customers are integer numbers of work units. They are assumed to be independent and identically distributed (i.i.d.) random variables. The service capacities, i.e., the numbers of work units that the server can process in the consecutive slots, are also assumed to be i.i.d. and their common probability generating function (pgf) is assumed to be rational. New customers arrive in the queueing system according to a general independent arrival process. For this queueing model we present an analysis method, which is based on complex contour integration. Expressions are obtained for the pgfs, the mean values and the tail probabilities of the customer delay and the system content in steady state. The analysis is illustrated by means of some numerical examples.

Keywords: Queueing theory, discrete time, service demands, service capacities, probability generating functions.
Mathematics Subject Classification: Primary: 60K25, 90B22; Secondary: 68M20.
Citation: 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
References:
[1]

J. Abate and W. Whitt, Numerical inversion of probability generating functions, Oper. Res. Letters, 12 (1992), 245-251.  doi: 10.1016/0167-6377(92)90050-D.  Google Scholar

[2]

I. J. B. F. Adan and V. G. Kulkarni, Single-server queue with Markov-dependent inter-arrival and service times, Queueing Systems, 45 (2003), 113-134.  doi: 10.1023/A:1026093622185.  Google Scholar

[3]

I. J. B. F. Adan, J. S. H. van Leeuwaarden and E. M. M. Winands, On the application of Rouché's theorem in queueing theory, Oper. Res. Letters, 34 (2006), 355-360.  doi: 10.1016/j.orl.2005.05.012.  Google Scholar

[4]

S. Ayed, D. Sofiene and R. Nidhal, Joint optimisation of maintenance and production policies considering random demand and variable production rate, International Journal Of Production Research, 50 (2011), 6870-6885.  doi: 10.1080/00207543.2011.631601.  Google Scholar

[5]

J. W. Bosman, R. D. van der Mei and R. Nunez-Queija, A fluid model analysis of streaming media in the presence of time-varying bandwidth, Proc. ITC 24, 2012, 177-184. Google Scholar

[6]

O. J. Boxma and I. A. Kurkova, The M/G/1 queue with two service speeds, Advances in Applied Probability, 33 (2001), 520-540.  doi: 10.1239/aap/999188327.  Google Scholar

[7]

H. Bruneel and B. G. Kim, Discrete-time Models for Communication Systems Including ATM, Kluwer Academic, Boston, USA, 1993. doi: 10.1007/978-1-4615-3130-2.  Google Scholar

[8]

H. Bruneel, S. Wittevrongel, D. Claeys and J. Walraevens, Discrete-time queues with variable service capacity: A basic model and its analysis, Annals of Operations Research, 239 (2016), 359-380.  doi: 10.1007/s10479-013-1428-y.  Google Scholar

[9]

H. Bruneel, W. Rogiest, J. Walraevens and S. Wittevrongel, On queues with general service demands and constant service capacity, LNCS, 8657 (2014), 210-225.  doi: 10.1007/978-3-319-10696-0_17.  Google Scholar

[10]

M. Chen, X. Jin, Y. Wang, X. Q. Cheng and G. Min, Modelling priority queuing systems with varying service capacity, Frontiers of Computer Science, 7 (2013), 571-582.  doi: 10.1007/s11704-013-2365-2.  Google Scholar

[11]

M. De Muynck, S. Wittevrongel and H. Bruneel, Analysis of discrete-time queues with general service demands and finite-support service capacities, Annals of Operations Research, accepted for publication, (2015), 1-26.  doi: 10.1007/s10479-015-2060-9.  Google Scholar

[12]

M. De Muynck, H. Bruneel and S. Wittevrongel, Delay analysis of a queue with general service demands and phase-type service capacities, AISC, 383 (2015), 29-39.  doi: 10.1007/978-3-319-22267-7_3.  Google Scholar

[13]

B. Feyaerts, S. De Vuyst, H. Bruneel and S. Wittevrongel, Performance analysis of buffers with train arrivals and correlated output interruptions, Journal of Industrial and Management Optimization, 11 (2015), 829-848.  doi: 10.3934/jimo.2015.11.829.  Google Scholar

[14]

S. Gao and J. Wang, On a discrete-time GIX/Geo/1/N-G queue with randomized working vacations and at most J vacations, Journal of Industrial and Management Optimization, 11 (2015), 779-806.  doi: 10.3934/jimo.2015.11.779.  Google Scholar

[15]

B. Giri, W. Yun and T. Dohi, Optimal design of unreliable production-inventory systems with variable production rate, European Journal of Operational Research, 162 (2005), 372-386.  doi: 10.1016/j.ejor.2003.10.015.  Google Scholar

[16]

M. O. González, Classical Complex Analysis, Marcel Dekker, New York, 1992.  Google Scholar

[17]

U. C. Gupta and V. Goswami, Performance analysis of finite buffer discrete-time queue with bulk service, Computers & Operations Research, 29 (2002), 1331-1341.  doi: 10.1016/S0305-0548(01)00034-X.  Google Scholar

[18]

S. Halfin, Steady-state distribution for the buffer content of an M/G/1 queue with varying service rate, SIAM Journal on Applied Mathematics, 23 (1972), 356-363.  doi: 10.1137/0123037.  Google Scholar

[19]

X. Jin, G. Min, S. Velentzas and J. Jiang, Quality-of-service analysis of queuing systems with long-range-dependent network traffic and variable service capacity, IEEE Transactions on Wireless Communications, 11 (2012), 562-570.  doi: 10.1109/TWC.2011.120511.100867.  Google Scholar

[20]

E. Kafetzakis, K. Kontovasilis and I. Stavrakakis, Effective-capacity-based stochastic delay guarantees for systems with time-varying servers, with an application to IEEE 802.11 WLANs, Performance Evaluation, 68 (2011), 614-628.  doi: 10.1016/j.peva.2011.03.010.  Google Scholar

[21]

B. Kim and J. Kim, A single server queue with Markov modulated service rates and impatient customers, Performance Evaluation, 83/84 (2015), 1-15.  doi: 10.1016/j.peva.2014.11.002.  Google Scholar

[22]

L. Kleinrock, Queueing Systems, Volume I: Theory, Wiley, New York, 1976. doi: 10.1002/net.3230060210.  Google Scholar

[23]

G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, Society for Industrial and Applied Mathematics, 1987. doi: 10.1137/1.9780898719734.  Google Scholar

[24]

S. R. Mahabhashyam and N. Gautam, On queues with Markov modulated service rates, Queueing Systems, 51 (2005), 89-113.  doi: 10.1007/s11134-005-2158-x.  Google Scholar

[25]

I. Mitrani, Modelling of Computer and Communication Systems, Cambridge University Press, Cambridge, 1987. Google Scholar

[26]

Z. Saffer and M. Telek, Analysis of BMAP vacation queue and its application to IEEE 802.16e sleep mode, Journal of Industrial and Management Optimization, 6 (2010), 661-690.  doi: 10.3934/jimo.2010.6.661.  Google Scholar

[27]

Z. Saffer and W. Yue, M/M/c multiple synchronous vacation model with gated discipline, Journal of Industrial and Management Optimization, 8 (2012), 939-968.  doi: 10.3934/jimo.2012.8.939.  Google Scholar

[28]

T. Takine, Single-server queues with Markov-modulated arrivals and service speed, Queueing Systems, 49 (2005), 7-22.  doi: 10.1007/s11134-004-5553-9.  Google Scholar

[29]

B. Vinck and H. Bruneel, Analyzing the discrete-time G(G)/Geo/1 queue using complex contour integration, Queueing Systems, 18 (1994), 47-67.  doi: 10.1007/BF01158774.  Google Scholar

[30]

M. Vlasiou, I. J. B. F. Adan and O. J. Boxma, A two-station queue with dependent preparation and service times, European Journal of Operational Research, 195 (2009), 104-116.  doi: 10.1016/j.ejor.2008.01.027.  Google Scholar

[31]

J. Walraevens, H. Bruneel, D. Claeys and S. Wittevrongel, The discrete-time queue with geometrically distributed service capacities revisited, LNCS, 7984 (2013), 443-456.  doi: 10.1007/978-3-642-39408-9_31.  Google Scholar

[32]

Y. Yao and D. Wei-Chung Miao, Sample-path analysis of general arrival queueing systems with constant amount of work for all customers, Queueing Systems, 76 (2014), 283-308.  doi: 10.1007/s11134-013-9361-y.  Google Scholar

show all references

References:
[1]

J. Abate and W. Whitt, Numerical inversion of probability generating functions, Oper. Res. Letters, 12 (1992), 245-251.  doi: 10.1016/0167-6377(92)90050-D.  Google Scholar

[2]

I. J. B. F. Adan and V. G. Kulkarni, Single-server queue with Markov-dependent inter-arrival and service times, Queueing Systems, 45 (2003), 113-134.  doi: 10.1023/A:1026093622185.  Google Scholar

[3]

I. J. B. F. Adan, J. S. H. van Leeuwaarden and E. M. M. Winands, On the application of Rouché's theorem in queueing theory, Oper. Res. Letters, 34 (2006), 355-360.  doi: 10.1016/j.orl.2005.05.012.  Google Scholar

[4]

S. Ayed, D. Sofiene and R. Nidhal, Joint optimisation of maintenance and production policies considering random demand and variable production rate, International Journal Of Production Research, 50 (2011), 6870-6885.  doi: 10.1080/00207543.2011.631601.  Google Scholar

[5]

J. W. Bosman, R. D. van der Mei and R. Nunez-Queija, A fluid model analysis of streaming media in the presence of time-varying bandwidth, Proc. ITC 24, 2012, 177-184. Google Scholar

[6]

O. J. Boxma and I. A. Kurkova, The M/G/1 queue with two service speeds, Advances in Applied Probability, 33 (2001), 520-540.  doi: 10.1239/aap/999188327.  Google Scholar

[7]

H. Bruneel and B. G. Kim, Discrete-time Models for Communication Systems Including ATM, Kluwer Academic, Boston, USA, 1993. doi: 10.1007/978-1-4615-3130-2.  Google Scholar

[8]

H. Bruneel, S. Wittevrongel, D. Claeys and J. Walraevens, Discrete-time queues with variable service capacity: A basic model and its analysis, Annals of Operations Research, 239 (2016), 359-380.  doi: 10.1007/s10479-013-1428-y.  Google Scholar

[9]

H. Bruneel, W. Rogiest, J. Walraevens and S. Wittevrongel, On queues with general service demands and constant service capacity, LNCS, 8657 (2014), 210-225.  doi: 10.1007/978-3-319-10696-0_17.  Google Scholar

[10]

M. Chen, X. Jin, Y. Wang, X. Q. Cheng and G. Min, Modelling priority queuing systems with varying service capacity, Frontiers of Computer Science, 7 (2013), 571-582.  doi: 10.1007/s11704-013-2365-2.  Google Scholar

[11]

M. De Muynck, S. Wittevrongel and H. Bruneel, Analysis of discrete-time queues with general service demands and finite-support service capacities, Annals of Operations Research, accepted for publication, (2015), 1-26.  doi: 10.1007/s10479-015-2060-9.  Google Scholar

[12]

M. De Muynck, H. Bruneel and S. Wittevrongel, Delay analysis of a queue with general service demands and phase-type service capacities, AISC, 383 (2015), 29-39.  doi: 10.1007/978-3-319-22267-7_3.  Google Scholar

[13]

B. Feyaerts, S. De Vuyst, H. Bruneel and S. Wittevrongel, Performance analysis of buffers with train arrivals and correlated output interruptions, Journal of Industrial and Management Optimization, 11 (2015), 829-848.  doi: 10.3934/jimo.2015.11.829.  Google Scholar

[14]

S. Gao and J. Wang, On a discrete-time GIX/Geo/1/N-G queue with randomized working vacations and at most J vacations, Journal of Industrial and Management Optimization, 11 (2015), 779-806.  doi: 10.3934/jimo.2015.11.779.  Google Scholar

[15]

B. Giri, W. Yun and T. Dohi, Optimal design of unreliable production-inventory systems with variable production rate, European Journal of Operational Research, 162 (2005), 372-386.  doi: 10.1016/j.ejor.2003.10.015.  Google Scholar

[16]

M. O. González, Classical Complex Analysis, Marcel Dekker, New York, 1992.  Google Scholar

[17]

U. C. Gupta and V. Goswami, Performance analysis of finite buffer discrete-time queue with bulk service, Computers & Operations Research, 29 (2002), 1331-1341.  doi: 10.1016/S0305-0548(01)00034-X.  Google Scholar

[18]

S. Halfin, Steady-state distribution for the buffer content of an M/G/1 queue with varying service rate, SIAM Journal on Applied Mathematics, 23 (1972), 356-363.  doi: 10.1137/0123037.  Google Scholar

[19]

X. Jin, G. Min, S. Velentzas and J. Jiang, Quality-of-service analysis of queuing systems with long-range-dependent network traffic and variable service capacity, IEEE Transactions on Wireless Communications, 11 (2012), 562-570.  doi: 10.1109/TWC.2011.120511.100867.  Google Scholar

[20]

E. Kafetzakis, K. Kontovasilis and I. Stavrakakis, Effective-capacity-based stochastic delay guarantees for systems with time-varying servers, with an application to IEEE 802.11 WLANs, Performance Evaluation, 68 (2011), 614-628.  doi: 10.1016/j.peva.2011.03.010.  Google Scholar

[21]

B. Kim and J. Kim, A single server queue with Markov modulated service rates and impatient customers, Performance Evaluation, 83/84 (2015), 1-15.  doi: 10.1016/j.peva.2014.11.002.  Google Scholar

[22]

L. Kleinrock, Queueing Systems, Volume I: Theory, Wiley, New York, 1976. doi: 10.1002/net.3230060210.  Google Scholar

[23]

G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling, Society for Industrial and Applied Mathematics, 1987. doi: 10.1137/1.9780898719734.  Google Scholar

[24]

S. R. Mahabhashyam and N. Gautam, On queues with Markov modulated service rates, Queueing Systems, 51 (2005), 89-113.  doi: 10.1007/s11134-005-2158-x.  Google Scholar

[25]

I. Mitrani, Modelling of Computer and Communication Systems, Cambridge University Press, Cambridge, 1987. Google Scholar

[26]

Z. Saffer and M. Telek, Analysis of BMAP vacation queue and its application to IEEE 802.16e sleep mode, Journal of Industrial and Management Optimization, 6 (2010), 661-690.  doi: 10.3934/jimo.2010.6.661.  Google Scholar

[27]

Z. Saffer and W. Yue, M/M/c multiple synchronous vacation model with gated discipline, Journal of Industrial and Management Optimization, 8 (2012), 939-968.  doi: 10.3934/jimo.2012.8.939.  Google Scholar

[28]

T. Takine, Single-server queues with Markov-modulated arrivals and service speed, Queueing Systems, 49 (2005), 7-22.  doi: 10.1007/s11134-004-5553-9.  Google Scholar

[29]

B. Vinck and H. Bruneel, Analyzing the discrete-time G(G)/Geo/1 queue using complex contour integration, Queueing Systems, 18 (1994), 47-67.  doi: 10.1007/BF01158774.  Google Scholar

[30]

M. Vlasiou, I. J. B. F. Adan and O. J. Boxma, A two-station queue with dependent preparation and service times, European Journal of Operational Research, 195 (2009), 104-116.  doi: 10.1016/j.ejor.2008.01.027.  Google Scholar

[31]

J. Walraevens, H. Bruneel, D. Claeys and S. Wittevrongel, The discrete-time queue with geometrically distributed service capacities revisited, LNCS, 7984 (2013), 443-456.  doi: 10.1007/978-3-642-39408-9_31.  Google Scholar

[32]

Y. Yao and D. Wei-Chung Miao, Sample-path analysis of general arrival queueing systems with constant amount of work for all customers, Queueing Systems, 76 (2014), 283-308.  doi: 10.1007/s11134-013-9361-y.  Google Scholar

Figure 3.  Mean system content versus the mean service demand $\tau$ for Poisson arrivals with $\lambda=0.9$, shifted geometric service demands and various service-capacity distributions (as indicated), with mean $\mu = \tau$.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 1.  Mean customer delay versus the load $\rho$, for Poisson arrivals with varying $\lambda$, deterministic service demands with $\tau=11$ and various service-capacity distributions (as indicated), all with mean $\mu=10$.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Variance of the customer delay versus the load $\rho$, for Poisson arrivals with varying $\lambda$, deterministic service demands with $\tau=11$ and various service-capacity distributions (as indicated), all with mean $\mu=10$.
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Dominant-pole approximation of the tail probabilities of the system content, for Poisson arrivals with $\lambda=3$, uniformly distributed service demands from 1 to 10 work units, and negative binomial service capacities with $\mu=10$ and various values of the parameter $m$, as well as deterministic service capacities.
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Jian Zhang, Tony T. Lee, Tong Ye, Liang Huang. An approximate mean queue length formula for queueing systems with varying service rate. Journal of Industrial & Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106
[2]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167
[3]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046
[4]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339
[5]

Veena Goswami, Gopinath Panda. Optimal customer behavior in observable and unobservable discrete-time queues. Journal of Industrial & Management Optimization, 2021, 17 (1) : 299-316. doi: 10.3934/jimo.2019112
[6]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166
[7]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[8]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[9]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098
[10]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029
[11]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117
[12]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458
[13]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051
[14]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[15]

Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024
[16]

Tahir Aliyev Azeroğlu, Bülent Nafi Örnek, Timur Düzenli. Some results on the behaviour of transfer functions at the right half plane. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020106
[17]

Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323
[18]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276
[19]

Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299
[20]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (80)
  • HTML views (432)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences