Informatics and Applications

2019, Volume 13, Issue 4, pp 60-67

DISCRETE-TIME Geo/G/l/infinity LIFO QUEUE WITH RESAMPLING POLICY

L. A. Meykhanadzhyan
R. V. Razumchik

Abstract

Consideration is given to the problem of estimation of the true stationary mean response time in the discrete-time single-server queue of infinite capacity, with Bernoulli input, round-robin scheduling, and inaccurate information about the service time distribution which is considered to be general arithmetic. It is shown that the upper bound for the true value may be provided by the mean response time in the discrete-time single-server queue with LIFO (last in, first out) service discipline and resampling policy. The latter implies that a customer arriving to the nonidle system assigns new remaining service time for the customer in the server. For the case when the true service time distribution is geometric and the error in the service times is of multiplicative type, conditions are provided which, when satisfied, guarantee that the proposed method yields the upper bound across all possible values of the system's load.

[+] References (28)

Daduna, H., and R. Schassberger. 1981. A discretetime round-Robin queue with Bernoulli input and general arithmetic service time distributions. Acta Inform. 15(3):251-263.
Pechinkin, A. V., and R.V. Razumchik. 2018. Sistemy massovogo obsluzhivaniya v diskretnom vremeni [Discrete time queuing systems]. Moscow: Fizmatlit. 432 p.
Schassberger, R. 1981. On the response time distribution in a discrete round-Robin queue. Acta Inform. 16(1):57-62.
Tatashev, A. G. 1999. On an inverse servicing discipline in a queue with customers of different types. Automat. Rem. Contr. 60(7):1050-1053.
Tatashev, A. G. 2003. A queueing system with inverse dis-cipline, two types of customers, and Markov input flow. Automat. Rem. Contr. 64(11):1755-1759.
Fiems, D., B. Steyaert, and H. Bruneel. 2004. Discretetime queues with generally distributed service times and renewal-type server interruptions. Perform. Eval. 55(3-4):277-298.
Walraevens, J., D. Fiems, and H. Bruneel. 2006. The discrete-time preemptive repeat identical priority queue. Queueing Sy. 53(4):231-243.
Pechinkin, A., and S. Shorgin. 2008. The discrete-time queueing system with inversive service order and prob abilistic priority. 3rd Conference (International) on Performance Evaluation Methodologies and Tools Proceedings. Brussels: ICST. Art. No. 20. 6 p.
Milovanova, T. A. 2009. BMAP/G/1/то system with last come first served probabilistic priority. Automat. Rem. Contr. 70(5):885-896.
Pechinkin, A. V., and I.V. Stalchenko. 2010. Sistema MAP/G/1/infinity s inversionnym poryadkom obsluzhivaniya i veroyatnostnym prioritetom, funktsioniruyushchaya v diskretnom vremeni [The MAP/G/1/то discrete-time queueing system with inversive service order and proba-bilistic priority]. Vestnik Rossiyskogo Universiteta Druzhby Narodov. Ser. Matematika. Informatika. Fizika [Bulletin of Peoples' Friendship University ofRussia. Ser. Mathemat-ics. Information Sciences. Physics] 2:26-36.
Milovanova, T.A., and A.V Pechinkin. 2013. Statsionarnye kharakteristiki sistemy obsluzhivaniya s inversion- nym poryadkom obsluzhivaniya, veroyatnostnym priori- tetom i gisterezisnoy politikoy [Stationary characteristics of queuing system with an inversion procedure service probabilistic priority and hysteresis policy]. Informatika i ee Primeneniya - Inform. Appl. 7(1):22-35.
Meykhanadzhyan, L. A. 2016. Statsionarnye veroyatnosti sostoyaniy v sisteme obsluzhivaniya konechnoy emkosti s inversionnym poryadkom obsluzhivaniya i obobshchennym veroyatnostnym prioritetom [Stationary character-istics of the finite capacity queueing system with inverse service order and generalized probabilistic priority]. Infor-matika i ee Primeneniya - Inform. Appl. 10(62):123-131.
Afanaseva, L. G., andA.W. Tkachenko. 2019. Stability conditions for queueing systems with regenerative flow of interruptions. Theor. Probab. Appl. 63(4):507-531.
Razumchik, R. 2019. Two-priority queueing system with LCFS service, probabilistic priority and batch arrivals. AIPConf Proc. 2116(1):090011-1-090011-3.
Pechinkina, O.A. 1995. Asimptoticheskoe raspredelenie dliny ocheredi v sisteme M/G/1 s inversionnoy veroyat- nostnoy distsiplinoy obsluzhivaniya [Queue size asymp-totic distribution for M/G/1 system with inverse proba-bilistic service discipline]. Vestnik Rossiyskogo Universiteta Druzhby Narodov. Ser. Matematika. Informatika. Fizika [Bulletin of Peoples' Friendship University of Russia. Ser. Mathematics. Information Sciences. Physics] 1:87-100.
Horvath, I., R. Razumchik, and M. Telek. 2019. The resampling M/G/1 non-preemptive LIFO queue and its application to systems with uncertain service time. Per-form. Evaluation 134:102000. 13 p.
Limic, V. 2001. A LIFO queue in heavy traffic. Ann. Appl. Probab. 11(2):301-331.
Asmussen, S., and P.W. Glynn. 2017. On preemptive- repeat LIFO queues. Queueing Sy. 87(1-2):1-22.
Finch, P. D. 1959. The output process of the queueing system M/G/1. J. Roy. Stat. Soc. B Met. 21(2):375-380.
Dell'Amico, M., D. Carra, and P. Michiardi. 2016. PSBS: Practical size-based scheduling. IEEE T. Comput. 65(7): 2199-2212.
Milovanova, T.A., L.A. Meykhanadzhyan, and R. V. Razumchik. 2018. Bounding moments of Sojourn time in M/G/1 FCFS queue with inaccuratejob size information and additive error: Some observations from numerical experiments. CEUR Workshop Proceedings 2236:2430.
Klefsjo, B. 1983. A useful ageing property based on the Laplace transform. J. Appl. Probab. 20(3):615-626.
Barlow, R., and F. Proschan. 1965. Mathematical theory of reliability. New York, NY: Wiley. 274 p.
Stoyan, D. 1977. Qualitative Eigenschaften und Abschtzun- gen stochastischer Modelle. Berlin: Akademie-Verlag. 198 p.
Klefsjo, B. 1982. The hnbue and hnwue classes of life distributions. Nav. Res. Log. 29(2):331-344.
Conti, P. L. J. 1997. An asymptotic test for a geometric process against a lattice distribution with monotone hazard. Ital. Stat. Soc. 6(3):213-231.
Artikis, T, A. Voudouri, and M. Malliaris. 1994. Certain selecting and underreporting processes. Math. Comput. Model. 20(1):103-106.
Korolev, V.Yu., A.Yu. Korchagin, and A.I. Zeifman. 2016. Teorema Puassona dlya skhemy ispytaniy Bernulli so sluchaynoy veroyatnost'yu uspekha i diskretnyy ana-log raspredeleniya Veybulla [The Poisson theorem for Bernoulli trials with a random probability of success and a discrete analog of the Weibull distribution]. Informatika iee Primeneniya - Inform. Appl. 10(4):11-20.

[+] About this article