Dedication to Igor Mykolayovych Kovalenko who died shortly after the writing of this book
Ukrainian and world science is mourning the loss of a brilliant scientist, Professor Igor Mykolayovych Kovalenko, who died on October 19, 2019, after a difficult fight with heart disease.
Prof. Igor Kovalenko was a prominent Ukrainian mathematician in the field of probability theory and its practical applications, a disciple and associate of Boris Gnedenko and Vladimir Korolyuk. He became famous worldwide for his book Introduction to Queueing Theory, written together with Gnedenko. He founded a scientific school in the theory of reliability, queueing theory and cryptography, well known in Ukraine and all over the world.
Igor Kovalenko was born on March 16, 1935 in Kyiv, Ukraine. After graduating from the Faculty of Mechanics and Mathematics of Kyiv Taras Shevchenko University, he worked at the Computing Centre of the Academy of Sciences of Ukraine. From 1962 till 1971, Kovalenko worked in Moscow, where he headed a laboratory at the Moscow Institute of Electronic Engineering, and together with other Gnedenko’s disciples, was the head of the seminar on queueing theory at Moscow State University. Many leading scientists of the former Soviet Union and foreign countries attended this seminar.
Based on the model of piecewise linear Markov processes developed by him, Kovalenko built a mathematical model of a complex defence system reliability and developed numerical algorithms for its implementation based on the method of a small parameter.
In 1964, Igor Kovalenko became a Doctor of Technical Sciences. He formulated the principle of monotonous failures, which, while maintaining high accuracy, significantly simplified the calculations of system reliability. In 1970, Kovalenko was awarded the degree of Doctor of Physics and Mathematics for another thesis on the probabilistic theory of systems of random Boolean equations. Being a doctor twice over is a very rare practice in the scientific world.
After returning to Kyiv in 1971, Prof. Kovalenko founded and headed the Department of Mathematical Methods of the Theory of Complex Systems Reliability at the V.M. Glushkov Institute of Cybernetics. Two areas of research formed the mainstream of investigations: approximate combined analytical and statistical methods of reliability analysis, and theoretical and applied cryptography, systems and methods for data protection. Under his guidance, the first national standard in the field of cryptographic information security was developed in Ukraine.
Prof. Kovalenko is the author of 25 monographs and more than 200 articles. He was elected as an Academician of the National Academy of Sciences of Ukraine in 1978 (Corresponding Member since 1972). He was an extremely hard-working, honest and sincere person, a competent manager and, thanks to his human qualities, professional experience and knowledge, highly respected among his colleagues.
Prof. Igor Kovalenko left many disciples, among them there are many professors and associate professors. All of them preserve in their memory the unforgettable days of joining the science and independent creativity under the guidance of a Great Scientist and Teacher, hours of direct communication with a person of great erudition and high culture.
1
Discrete Time Single-server Queues with Interdependent Interarrival and Service Times
Attahiru Sule ALFA
University of Manitoba, Canada and University of Pretoria, South Africa
Discrete time single-server queues in which the interarrival and service times are interdependent are presented. First, we study the simple Geo/Geo/1 system, let the interarrival times depend on the service times and then consider special cases. The idea is then extended to the PH/PH/1 system. We then consider the case where the interarrival times are constructed from a combination of a set of interarrival times driven by the service times distribution. The initiating vector for the resulting combined PH distribution for the interarrival times is constructed as a function of the service times distribution, so that any changes in the service time distributions are reflected in this initiating vector. We capitalize on the structures of discrete phase type distributions in generalizing the resulting interarrival times. Finally, we introduce a general case where there is interdependence between service and interarrival times. We present a generalized matrix version of the bivariate geometric distribution, which can be used to capture some interdependence between the interarrival and service times.
1.1. Introduction
Most of the queueing models in the literature usually assume that the interarrival times and service times are independent of each other. While this may be true in some instances, it was pointed out by Cidon et al. (1993) that there are instances where there are dependencies between the two distributions. They mentioned that in communication systems where finite speed of communications links constrain the amount of data that can be received, one finds the interarrival times and service times to be correlated. They studied communication systems in which the interarrival time between nth and
Chao (1965) captured the interdependence between interarrival times and service times by using a bivariate exponential distribution to capture the two processes. By defining the correlation between the interarrival and service times as ρ, Chao (1965) pointed out that a customer’s waiting time is monotonically decreasing in ρ in increasing convex ordering sense. While this seems common sense, it was the first confirmation based on rigorous analysis. Later, Muller (2000) studied the waiting times when there is dependency between amount of work (service time) brought by a customer and the subsequent interarrival times. He showed that the stronger the dependency is between interarrival times and service times, the more the waiting time decreases in increasing convex ordering sense (similar to Chao 1995). Hadidi (1981a, 1981b) used bivariate exponential distribution for the joint interarrival and services times to capture the dependency, and carried out simulation and numerical studies to understand the effects of the correlation coefficient on waiting times.
One of the most recent works on this subject is by Iyer and Manjunanth (2006) who also studied the interarrival and service times of queue by using mixtures of bivariates. Panda et al. (2017), in a work similar to the one by Iyer and Manunanth (2006), studied queues in which batch interarrival and service times are correlated by representing them with a bivariate mixture of rational (R) distributions.
Generally, most of the reported works focus on proportional relationships between interarrival times and service times. This is quite limiting. In this chapter, this aspect is relaxed, and the interdependence between the interarrival times and services is captured in a one-way dependence of interarrival time on service time and later in a two-way dependence. However, that dependence is allowed to be general. In the one-way case, we start by considering the Geo/Geo/1 system in which the arrival probability depends on service completion probability. Specifically in the general one-way case, we assume that there is a set of several, but finite, number of interarrival times. At the end of a service completion, the next interarrival time of a user is selected based on the service time. Even though