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$ .
-
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
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
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.
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 and 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. |
| [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. |
| [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. |
| [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
The reviewing process of the paper was handled by Wuyi Yue and Yutaka Takahashi as Guest Editors.
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. |
| [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. |
| [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. |
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 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 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.
| [1] |
Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial and 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 and 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 and 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 and Management Optimization, 2021, 17 (1) : 185-204. doi: 10.3934/jimo.2019106 |
| [5] |
Gopinath Panda, Veena Goswami. Effect of information on the strategic behavior of customers in a discrete-time bulk service queue. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1369-1388. doi: 10.3934/jimo.2019007 |
| [6] |
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 and Management Optimization, 2014, 10 (1) : 131-149. doi: 10.3934/jimo.2014.10.131 |
| [7] |
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 |
| [8] |
Simone Vazzoler. A note on the normalization of generating functions. Journal of Geometric Mechanics, 2018, 10 (2) : 209-215. doi: 10.3934/jgm.2018008 |
| [9] |
Barry Simon. Equilibrium measures and capacities in spectral theory. Inverse Problems and Imaging, 2007, 1 (4) : 713-772. doi: 10.3934/ipi.2007.1.713 |
| [10] |
Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial and Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767 |
| [11] |
Fei Cheng, Shanlin Yang, Ram Akella, Xiaoting Tang. An integrated approach for selection of service vendors in service supply chain. Journal of Industrial and Management Optimization, 2011, 7 (4) : 907-925. doi: 10.3934/jimo.2011.7.907 |
| [12] |
Tinghai Ren, Kaifu Yuan, Dafei Wang, Nengmin Zeng. Effect of service quality on software sales and coordination mechanism in IT service supply chain. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021165 |
| [13] |
Xuemei Zhang, Malin Song, Guangdong Liu. Service product pricing strategies based on time-sensitive customer choice behavior. Journal of Industrial and Management Optimization, 2017, 13 (1) : 297-312. doi: 10.3934/jimo.2016018 |
| [14] |
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 and Management Optimization, 2018, 14 (1) : 165-182. doi: 10.3934/jimo.2017041 |
| [15] |
Yayun Zheng, Xu Sun. Governing equations for Probability densities of stochastic differential equations with discrete time delays. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3615-3628. doi: 10.3934/dcdsb.2017182 |
| [16] |
Huiyan Xue, Antonella Zanna. Generating functions and volume preserving mappings. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1229-1249. doi: 10.3934/dcds.2014.34.1229 |
| [17] |
Lijin Wang, Jialin Hong. Generating functions for stochastic symplectic methods. Discrete and Continuous Dynamical Systems, 2014, 34 (3) : 1211-1228. doi: 10.3934/dcds.2014.34.1211 |
| [18] |
Dong-Sheng Ma, Hua-Ming Song. Behavior-based pricing in service differentiated industries. Journal of Dynamics and Games, 2020, 7 (4) : 351-364. doi: 10.3934/jdg.2020027 |
| [19] |
Jun Wu, Shouyang Wang, Wuyi Yue. Supply contract model with service level constraint. Journal of Industrial and Management Optimization, 2005, 1 (3) : 275-287. doi: 10.3934/jimo.2005.1.275 |
| [20] |
Hengyu Li, Junwu Chai. Strategic service investment by retailers confronted by manufacturer encroachment. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022086 |
2021 Impact Factor: 1.411
Tools
Metrics
Other articles
by authors
[Back to Top]