On time-to-buffer overflow distribution in a single-machine discrete-time system with finite capacity
Abstract
A model of a single-machine production system with finite magazine capacity is investigated. The input flow of jobs is organized according to geometric distribution of interarrival times, while processing times are assumed to be generally distributed. The closed-form formula for the generating function of the time to the first buffer overflow distribution conditioned by the initial buffer state is found. The analytical approach based on the idea of embedded Markov chain, the formula of total probability and linear algebra is applied. The corresponding result for next buffer overflows is also given. Numerical examples are attached as well.
Keyword : buffer overflow, geometric distribution, production line, queueing model, transient analysis
How to Cite
Kempa, W. M. (2020). On time-to-buffer overflow distribution in a single-machine discrete-time system with finite capacity. Mathematical Modelling and Analysis, 25(2), 289-302. https://doi.org/10.3846/mma.2020.10433
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
J. Abate, G.L. Choudhury and W. Whitt. An introduction to numerical transform inversion and its application to probability models. In W. Grassmann(Ed.), Computational Probability, pp. 257–323, Boston, 2000. Kluwer Academic Publishers.
S. Asmussen, M. Jobmann and H.-P. Schwefel. Exact buffer overflow calculations for queues via martingales. Queueing Syst., 42(1):63–90, 2002. https://doi.org/10.1023/A:1019994728099
H. Bruneel and B.G. Kim. Discrete-time models for communication systems including ATM. Kluwer Academic Publishers, Boston, 1993. https://doi.org/10.1007/978-1-4615-3130-2
M.L. Chaudhry and Y.Q. Zhao. First-passage-time and busy-period distributions of discrete-time Markovian queues: Geom(n)/geom(n)/1/n. Queueing Syst., 18:5–26, 1994. https://doi.org/10.1007/BF01158772
A. Chydziński. Time ot buffer overflow in a MMPP queue. In Proceedings of the International Conference on Research Networking: NETWORKING 2007, volume 4479 of Lecture Notes in Computer Science, pp. 879–889, 2007.
A. Chydziński. Time to reach buffer capacity in a BMAP queue. Stoch. Models, 23:95–209, 2007. https://doi.org/10.1080/15326340701300746
A. Duda. Transient diffusion approximation for some queueing systems. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. ACM, 1983. https://doi.org/10.1145/800040.801399
A. Al Hanbali. Busy period analysis of the level dependent PH/PH/1/K queue. Queueing Syst., 67:221–249, 2011. https://doi.org/10.1007/s11134-011-9213-6
J.J. Hunter. Mathematical techniques of applied probability, vol. II, Discrete-time models: techniques and applications. Academic Press, New York, 1983.
W.M. Kempa. A comprehensive study on the queue-size distribution in a finitebuffer system with a general independent input flow. Perform. Evaluation, 108:1–15, 2017. https://doi.org/10.1016/j.peva.2016.11.002
W.M. Kempa. Time to start a crowded period in a finite-buffer queue with Poisson input flow and general processing times. In I. Dimov, I. Farago and L. Vulkov(Eds.), Finite difference methods theory and applications. 7th International conference, FDM 2018, Lozenetz, Bulgaria, June 11-16, 2018, volume 11386 of Lecture Notes in Computer Science, pp. 329–336, 2018.
W.M. Kempa and M. Kobielnik. Time to buffer overflow in a queueing model with working vacation policy. In P. Gaj, M. Sawicki, G. Suchacka and A. Kwiecień (Eds.), Computer networks. 25th International conference (CN 2018), Gliwice, Poland, June 19-22, 2018, volume 860 of Communications in Computer and Information Science, pp. 219–231, Cham, 2018. Springer.
W.M. Kempa and R. Marjasz. Distribution of the time to buffer overflow in the M/G/1/N-type queueing model with batch arrivals and multiple vacation policy. J. Oper. Res. Soc., 2019. https://doi.org/10.1080/01605682.2019.1567651
W.M. Kempa and I. Paprocka. Time to buffer overflow in a finite-capacity queueing model with setup and closedown times. In J. Światek, Z. Wilimowska, L. Borzemski and A. Grzech (Eds.), Information systems architecture and technology. Proceedings of 37th International Conference on Information Systems Architecture and Technology (ISAT 2016), volume 523 of Advances in Intelligent Systems and Computing, pp. 215–224, Cham, 2017. Springer.
W.M. Kempa, I. Paprocka, C. Grabowik and K. Kalinowski. Distribution of time to buffer overflow in a finite-buffer manufacturing model with unreliable machine. In L. Slatineanu et al. (Ed.), 21st Innovative Manufacturing Engineering & Energy International Conference (IManE&E 2017), Iasi, Romania, May 2427, 2017, volume 112 of MATEC Web of Conferences, pp. 1–6, Les Ulis, 2017. EDP Sciences. https://doi.org/10.1051/matecconf/201711205005
T. Kimura, K. Ohno and H. Mine. Diffusion approximation for GI/G.G/1 queuing system with finite capacity: I - the first overflow time. J. Oper. Res. Soc. Jpn., 22:41–68, 1979. https://doi.org/10.15807/jorsj.22.41
V.S. Korolyuk. Boundary-Value Problems for Compound Poisson Processes. Naukowa Dumka, Kiev, 1975.
E.Y. Lee and K.K.J. Kinateder. The expected wet period of finite dam with exponential inputs. Stoch. Proc. Appl., 90:175–180, 2000. https://doi.org/10.1016/S0304-4149(00)00034-X
F. Machihara. First passage times of PH/PH/1/K and PH/PH/1 queues. J. Oper. Res. Soc. Jpn., 30, 1987. https://doi.org/10.15807/jorsj.30.1
S.M. Ross and S. Seshadri. Hitting time in an M/G/1 queue. J. Appl. Probab., 36:934–940, 1999. https://doi.org/10.1017/S0021900200017691
H. Takagi. Queueing analysis - a foundation of performance evaluation, Vol. 3. Discrete-Time Systems. North-Holland, Amsterdam, 1993.
S. Asmussen, M. Jobmann and H.-P. Schwefel. Exact buffer overflow calculations for queues via martingales. Queueing Syst., 42(1):63–90, 2002. https://doi.org/10.1023/A:1019994728099
H. Bruneel and B.G. Kim. Discrete-time models for communication systems including ATM. Kluwer Academic Publishers, Boston, 1993. https://doi.org/10.1007/978-1-4615-3130-2
M.L. Chaudhry and Y.Q. Zhao. First-passage-time and busy-period distributions of discrete-time Markovian queues: Geom(n)/geom(n)/1/n. Queueing Syst., 18:5–26, 1994. https://doi.org/10.1007/BF01158772
A. Chydziński. Time ot buffer overflow in a MMPP queue. In Proceedings of the International Conference on Research Networking: NETWORKING 2007, volume 4479 of Lecture Notes in Computer Science, pp. 879–889, 2007.
A. Chydziński. Time to reach buffer capacity in a BMAP queue. Stoch. Models, 23:95–209, 2007. https://doi.org/10.1080/15326340701300746
A. Duda. Transient diffusion approximation for some queueing systems. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems. ACM, 1983. https://doi.org/10.1145/800040.801399
A. Al Hanbali. Busy period analysis of the level dependent PH/PH/1/K queue. Queueing Syst., 67:221–249, 2011. https://doi.org/10.1007/s11134-011-9213-6
J.J. Hunter. Mathematical techniques of applied probability, vol. II, Discrete-time models: techniques and applications. Academic Press, New York, 1983.
W.M. Kempa. A comprehensive study on the queue-size distribution in a finitebuffer system with a general independent input flow. Perform. Evaluation, 108:1–15, 2017. https://doi.org/10.1016/j.peva.2016.11.002
W.M. Kempa. Time to start a crowded period in a finite-buffer queue with Poisson input flow and general processing times. In I. Dimov, I. Farago and L. Vulkov(Eds.), Finite difference methods theory and applications. 7th International conference, FDM 2018, Lozenetz, Bulgaria, June 11-16, 2018, volume 11386 of Lecture Notes in Computer Science, pp. 329–336, 2018.
W.M. Kempa and M. Kobielnik. Time to buffer overflow in a queueing model with working vacation policy. In P. Gaj, M. Sawicki, G. Suchacka and A. Kwiecień (Eds.), Computer networks. 25th International conference (CN 2018), Gliwice, Poland, June 19-22, 2018, volume 860 of Communications in Computer and Information Science, pp. 219–231, Cham, 2018. Springer.
W.M. Kempa and R. Marjasz. Distribution of the time to buffer overflow in the M/G/1/N-type queueing model with batch arrivals and multiple vacation policy. J. Oper. Res. Soc., 2019. https://doi.org/10.1080/01605682.2019.1567651
W.M. Kempa and I. Paprocka. Time to buffer overflow in a finite-capacity queueing model with setup and closedown times. In J. Światek, Z. Wilimowska, L. Borzemski and A. Grzech (Eds.), Information systems architecture and technology. Proceedings of 37th International Conference on Information Systems Architecture and Technology (ISAT 2016), volume 523 of Advances in Intelligent Systems and Computing, pp. 215–224, Cham, 2017. Springer.
W.M. Kempa, I. Paprocka, C. Grabowik and K. Kalinowski. Distribution of time to buffer overflow in a finite-buffer manufacturing model with unreliable machine. In L. Slatineanu et al. (Ed.), 21st Innovative Manufacturing Engineering & Energy International Conference (IManE&E 2017), Iasi, Romania, May 2427, 2017, volume 112 of MATEC Web of Conferences, pp. 1–6, Les Ulis, 2017. EDP Sciences. https://doi.org/10.1051/matecconf/201711205005
T. Kimura, K. Ohno and H. Mine. Diffusion approximation for GI/G.G/1 queuing system with finite capacity: I - the first overflow time. J. Oper. Res. Soc. Jpn., 22:41–68, 1979. https://doi.org/10.15807/jorsj.22.41
V.S. Korolyuk. Boundary-Value Problems for Compound Poisson Processes. Naukowa Dumka, Kiev, 1975.
E.Y. Lee and K.K.J. Kinateder. The expected wet period of finite dam with exponential inputs. Stoch. Proc. Appl., 90:175–180, 2000. https://doi.org/10.1016/S0304-4149(00)00034-X
F. Machihara. First passage times of PH/PH/1/K and PH/PH/1 queues. J. Oper. Res. Soc. Jpn., 30, 1987. https://doi.org/10.15807/jorsj.30.1
S.M. Ross and S. Seshadri. Hitting time in an M/G/1 queue. J. Appl. Probab., 36:934–940, 1999. https://doi.org/10.1017/S0021900200017691
H. Takagi. Queueing analysis - a foundation of performance evaluation, Vol. 3. Discrete-Time Systems. North-Holland, Amsterdam, 1993.