
-
Previous Article
Single server retrial queues with speed scaling: Analysis and performance evaluation
- JIMO Home
- This Issue
-
Next Article
A new analytical model for optimized cognitive radio networks based on stochastic geometry
Analysis of a discrete-time queue with general service demands and phase-type service capacities
SMACS Research Group, Department of Telecommunications and Information Processing, Ghent University, Sint-Pietersnieuwstraat 41, 9000 Ghent, Belgium |
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.
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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[16] |
M. O. González,
Classical Complex Analysis, Marcel Dekker, New York, 1992. |
[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. |
[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. |
[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. |
[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. |
[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. |
[22] |
L. Kleinrock,
Queueing Systems, Volume I: Theory, Wiley, New York, 1976.
doi: 10.1002/net.3230060210. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[16] |
M. O. González,
Classical Complex Analysis, Marcel Dekker, New York, 1992. |
[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. |
[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. |
[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. |
[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. |
[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. |
[22] |
L. Kleinrock,
Queueing Systems, Volume I: Theory, Wiley, New York, 1976.
doi: 10.1002/net.3230060210. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |




[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, 2017, 13 (5) : 0-0. 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, 2017, 13 (5) : 1-20. doi: 10.3934/jimo.2019007 |
[7] |
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 |
[8] |
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 |
[9] |
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 |
[10] |
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 |
[11] |
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 |
[12] |
Simone Vazzoler. A note on the normalization of generating functions. Journal of Geometric Mechanics, 2018, 10 (2) : 209-215. doi: 10.3934/jgm.2018008 |
[13] |
Barry Simon. Equilibrium measures and capacities in spectral theory. Inverse Problems & Imaging, 2007, 1 (4) : 713-772. doi: 10.3934/ipi.2007.1.713 |
[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 |
2018 Impact Factor: 1.025
Tools
Metrics
Other articles
by authors
[Back to Top]