19.1. The subject of queuing theory

Over the past decades, in various areas of practice, it has become necessary to solve peculiar probabilistic problems associated with the work of so-called queuing systems. Examples of such systems can be: telephone exchanges, repair shops, ticket offices, help desks, hairdressers, etc. Each such system consists of a certain number of service units, which we will call service “channels”. The channels may include: communication lines; persons performing those other operations; various devices, etc. Systems of mass service can be both one-and multi-channel.

The work of any queuing system consists in fulfilling the stream of demands or requests arriving at it. Applications are received one after another at some, generally speaking, random moments of time. The service of the incoming application continues for some time, after which the channel is released and is again ready to receive the next application. Each queuing system, depending on the number of channels and their performance, has some sort of bandwidth, which allows it to more or less successfully cope with the flow of requests. The subject of queuing theory is the establishment of a relationship between the nature of the flow of requests, the performance of a single channel, the number of channels and the success (efficiency) of service. Depending on the conditions of the task and the objectives of the study, various quantities and functions can be used as characteristics of service efficiency, for example: the average percentage of applications that are rejected and leave the system unserved; average idle time of individual channels and the system as a whole; average waiting time in the queue; the likelihood that the incoming application will be immediately accepted for service; the law of distribution of the queue length, etc. Each of these characteristics describes, from one side or the other, the degree of the system's ability to perform the flow of requests, in other words, its capacity.

In the narrow sense of the word, “throughput” is usually understood as the average number of applications that a system can service per unit of time. Along with it, the relative throughput is often considered - the average ratio of the number of requests served to the number of applications. The capacity (both absolute and relative) generally depends not only on the system parameters, but also on the nature of the flow of requests. If the applications were received regularly, at precisely defined intervals, and the maintenance of each application also had a strictly defined duration, the calculation of the system's throughput would not present any difficulty. In practice, usually the moments of receipt of applications are random; for the most part random and the duration of the service application. In this regard, the process of the system is irregular: in the flow of applications local thickenings and dilutions are formed. Thickening can lead to either denial of service or queuing. Dilution can lead to unproductive downtime of individual channels or the system as a whole. These accidents, associated with the heterogeneity of the flow of requests, are also superimposed by accidents associated with delays in servicing individual applications. Thus, the process of functioning of a queuing system is a random process. To make recommendations on the rational organization of the system, find out its capacity and make demands on it, it is necessary to study the random process occurring in the system and describe it mathematically. This is the theory of queuing.

Note that in recent years, the field of application of mathematical methods of the theory of mass service has been continuously expanding and is increasingly going beyond the tasks associated with the "service organizations" in the literal sense of the word. Many production automation tasks are close to queuing theory: the flow of parts arriving to perform various operations on them can be considered as “application flows”, the rhythm of receipt of which is disrupted due to random reasons. The peculiar tasks of the theory of queuing arise in connection with the problem of the organization of transport and the message system. Close to the queuing theory are tasks related to the reliability of technical devices: their characteristics, such as the average uptime, the required number of spare parts, the average downtime due to repairs, etc., are determined by methods directly borrowed from the theory queuing service.

Problems related to tasks of mass service constantly arise in military affairs. Guidance channels, communication lines, airfields, devices for collecting and processing information are peculiar queuing systems with their mode of operation and capacity.

It is even difficult to list all the areas of practice in which queuing theory methods are used. In recent years, it has become one of the fastest growing branches of probability theory.

In this chapter, we will present some elementary information on the theory of mass service, the knowledge of which is necessary for any engineer dealing with issues of organization in the field of industry, national economy, communications, and also in military affairs.