Heterogeneous queueing system with Markov renewal arrivals and service times dependent on states of arrival process

Cover Page

Cite item

Full Text

Abstract

In the proposed work, we consider a heterogeneous queueing system with a Markov renewal process and an unlimited number of servers. The service time for requests on the servers is a positive random variable with an exponential probability distribution. The service parameters depend on the state of the Markov chain nested over the renewal moments. It should be noted that these parameters do not change their values until the end of maintenance. Thus, the devices in the system under consideration are heterogeneous. The object of the study is a multidimensional random process - the number of servers of each type being served with different intensities in the stationary regime. The method of asymptotic analysis under the condition of equivalent growing of service times in the units of servers is applied for the study. The method of asymptotic analysis is implemented in the construction of a sequence of asymptotic of increasing order, in which the asymptotic of the first order determines the asymptotic mean value of the number of occupied servers. The second-order asymptotic allows one to construct a Gaussian approximation of the probability distribution of the number of occupied servers in the system. It is shown that this approximation coincides with the Gaussian distribution.

Full Text

1. Introduction Queueing theory is a field of applied mathematics that deals with the study and analysis of processes in various service, production, management, and communication systems in which homogeneous events are repeated many times. Examples of such systems include consumer services; systems for receiving, processing, and transmitting information, automatic production lines, telecommunication systems, and others [1]. The independence of processes in queueing systems is generally assumed when developing queueing models. However, real systems often involve several process dependencies, and failure to consider these can lead to a serious under errors in the estimation of the performance measures. Semi-Markov processes are used in modeling stochastic control problems arising in Markovian dynamic systems where the sojourn time in each state is a general continuous random variable. They are powerful, natural tools for the optimization of queues, production scheduling, reliability/maintenance [2, 3]. For example, in a machine replacement problem with deteriorating performance over time, a decision-maker, after observing the current state of the machine, decides whether to continue its usage, initiate maintenance (preventive or corrective) repair or replace the machine. Semi-Markov Processes include renewal processes and continuous-time Markov chains as special cases. In a semi-Markov process similar to Markov chains, state changes occur according to the Markov property, i.e., states in the future do not depend on the states in the past given the present. However, the sojourn time in a state is a continuous random variable with distribution depending on that state and the next state. A renewal process is a generalization of a Poisson process that allows arbitrary holding times. Its applications include such as planning for replacing worn-out machinery in a factory. A Markov renewal process is a generalization of a renewal process that the sequence of holding times is not independent and identically distributed. Their distributions depend on the states in a Markov chain. The Markov renewal processes were studied by Pyke in the 1960s [4, 5]. In the proposed work, we consider a heterogeneous queueing system (QS) with a Markov renewal process (MRP) for the process of its arrival and an unlimited number of servers. The service time for requests have an exponential probability distribution. Parameter of the service depends on the state of the Markov chain nested over the renewal moments. It should be noted that these parameters do not change their values until the end of maintenance. Thus, the devices in the system under consideration are heterogeneous.This problem for the Queueing System
×

About the authors

Evgeny P. Polin

National Research Tomsk State University; National Research Tomsk Polytechnic University

Email: polin_evgeny@mail.ru
ORCID iD: 0000-0002-0250-2368

Assistant of Department of Probability Theory and Mathematical Statistics

36, Lenin Avenue, Tomsk, 634050, Russian Federation; 30, Lenin Avenue, Tomsk, 634050, Russian Federation

Svetlana P. Moiseeva

National Research Tomsk State University

Email: smoiseeva@mail.ru
ORCID iD: 0000-0001-9285-1555
Scopus Author ID: 56436490300

Doctor in Physics and Mathematics, Professor at Department of Probability Theory and Mathematical Statistics

36, Lenin Avenue, Tomsk, 634050, Russian Federation

Alexander N. Moiseev

National Research Tomsk State University

Author for correspondence.
Email: moiseev.tsu@gmail.com
ORCID iD: 0000-0003-2369-452X
Scopus Author ID: 55646953800
ResearcherId: N-7189-2014

Doctor in Physics and Mathematics, Head of the Department of Software Engineering

36, Lenin Avenue, Tomsk, 634050, Russian Federation

References

  1. A. Dudin, V. Klimenok, and V. Vishnevsky, The Theory of Queuing Systems with Correlated Flow. Springer Nature, 2020. doi: 10.1007/9783-030-32072-0.
  2. V. K. Malinovskii, “Asymptotic expansions in the central limit theorem for recurrent Markov renewal processes,” Theory of Probability & Its Applications, vol. 51, no. 3, pp. 523–526, 1987. doi: 10.1137/1131073.
  3. Y. Lim, S. Hur, and J. Seung, “Departure process of a single server queueing system with Markov renewal input and general service time distribution,” Computers & Industrial Engineering, vol. 51, no. 3, pp. 519– 525, 2006. doi: 10.1016/j.cie.2006.08.011.
  4. R. Pyke, “Markov renewal processes: definitions and preliminary properties,” Ann. Math. Statist., vol. 32, pp. 1231–1242, 1961. doi: 10.1214/aoms/1177704863.
  5. R. Pyke and R. Schaufele, “Stationary measures for Markov renewal processes,” Ann. Math. Statist., vol. 37, pp. 1439–1462, 1966. doi: 10.1214/aoms/1177699138.
  6. J. Sztrik and D. Kouvatsos, “Asymptotic analysis of a heterogeneous multiprocessor system in a randomly changing environment,” IEEE Transactions on Software Engineering, vol. 17, no. 10, pp. 1069–1075, 1991. doi: 10.1109/32.99194.
  7. E. P. Polin, S. P. Moiseeva, and S. V. Rozhkova, “Asymptotic analysis of heterogeneous queueing system M|M|∞ in a Markov random enviroment [Asimptoticheskiy analiz neodnorodnoy sistemy massovogo obsluzhivaniya M|M|∞ v markovskoy sluchaynoy srede],” Tomsk State University Jounal of Control and Computer Science [Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitelnaja tehnika i informatika], vol. 47, pp. 75–83, 2019, in Russian. doi: 10.17223/19988605/ 47/9.
  8. E. P. Polin, S. P. Moiseeva, and A. N. Moiseev, “Heterogeneous queueing system MR(S)|M(S)|∞ with service parameters depending on the state of the underlying Markov chain [Analiz veroyatnostnykh kharakteristik geterogennoy SMO vida MR(S)|M(S)|∞ s parametrami obsluzhivaniya, zavisyashchimi ot sostoyaniya vlozhennoy tsepi Markova],” Saratov University News. New Series. Series Mathematics. Mechanics. Informatics [Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform.], vol. 20, no. 3, pp. 388–399, 2020, in Russian. doi: 10.18500/1816-9791-2020-20-3-388-399.
  9. B. D’Auria, “M|M|∞ queues in semi-Markovian random environment,” Queueing Systems, vol. 58, pp. 221–237, 2008. doi: 10.1007/s11134-008-9068-7.
  10. H. M. Jansen, “A large deviations principle for infinite-server queues in a random environment,” Queueing Systems, vol. 82, pp. 199–235, 2016. doi: 10.1007/s11134-015-9470-x.
  11. J. Blom, M. Mandjes, and H. Thorsdottir, “Time-scaling limits for Markov-modulated infinite-server queues,” Stochastic Models, vol. 29, pp. 112–127, 2012. doi: 10.1080/15326349.2013.750536.

Copyright (c) 2023 Polin E.P., Moiseeva S.P., Moiseev A.N.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies