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]

Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial & Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167
[2]

Wai-Ki Ching, Sin-Man Choi, Min Huang. Optimal service capacity in a multiple-server queueing system: A game theory approach. Journal of Industrial & Management Optimization, 2010, 6 (1) : 73-102. doi: 10.3934/jimo.2010.6.73
[3]

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

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, 2019  doi: 10.3934/jimo.2019106
[5]

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 & Management Optimization, 2014, 10 (1) : 131-149. doi: 10.3934/jimo.2014.10.131
[6]

Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1369-1388. doi: 10.3934/jimo.2019007
[7]

Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial & Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767
[8]

Barry Simon. Equilibrium measures and capacities in spectral theory. Inverse Problems & Imaging, 2007, 1 (4) : 713-772. doi: 10.3934/ipi.2007.1.713
[9]

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

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

Fei Cheng, Shanlin Yang, Ram Akella, Xiaoting Tang. An integrated approach for selection of service vendors in service supply chain. Journal of Industrial & Management Optimization, 2011, 7 (4) : 907-925. doi: 10.3934/jimo.2011.7.907
[12]

Xuemei Zhang, Malin Song, Guangdong Liu. Service product pricing strategies based on time-sensitive customer choice behavior. Journal of Industrial & Management Optimization, 2017, 13 (1) : 297-312. doi: 10.3934/jimo.2016018
[13]

Bin Dan, Huali Gao, Yang Zhang, Ru Liu, Songxuan Ma. Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints. Journal of Industrial & Management Optimization, 2018, 14 (1) : 165-182. doi: 10.3934/jimo.2017041
[14]

Yayun Zheng, Xu Sun. Governing equations for Probability densities of stochastic differential equations with discrete time delays. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3615-3628. doi: 10.3934/dcdsb.2017182
[15]

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

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

Jun Wu, Shouyang Wang, Wuyi Yue. Supply contract model with service level constraint. Journal of Industrial & Management Optimization, 2005, 1 (3) : 275-287. doi: 10.3934/jimo.2005.1.275
[18]

Tao Jiang, Liwei Liu. Analysis of a batch service multi-server polling system with dynamic service control. Journal of Industrial & Management Optimization, 2018, 14 (2) : 743-757. doi: 10.3934/jimo.2017073
[19]

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

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (76)
  • HTML views (411)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences