Federal Agency for Education of the Russian Federation
FGOU SPO "Perevozsky Construction College"
Course work
in the discipline "Mathematical methods"
on the topic “SMO with limited waiting time. Closed QS"
Introduction........................................................ ........................................................ ....... 2
1. Fundamentals of queuing theory............................................................ ...... 3
1.1 The concept of a random process.................................................... .................... 3
1.2 Markov random process.................................................... ................ 4
1.3 Event streams................................................................... ........................................... 6
1.4 Kolmogorov equations for state probabilities. Final state probabilities.............................................................. ........................................................ ........ 9
1.5 Problems of queuing theory.................................................... .. 13
1.6 Classification of queuing systems.................................................. 15
2. Queuing systems with waiting.................................................... 16
2.1 Single-channel QS with waiting.................................................... ........... 16
2.2 Multi-channel QS with waiting.................................................... ......... 25
3. Closed QS.................................................... ............................................... 37
The solution of the problem................................................ ........................................... 45
Conclusion................................................. ........................................................ . 50
Bibliography................................................ ..................................... 51
In this course we will look at various queuing systems (QS) and queuing networks (Queuing).
A queuing system (QS) is understood as a dynamic system designed to efficiently service the flow of requests (service requirements) under restrictions on system resources.
QS models are convenient for describing individual subsystems of modern computing systems, such as the processor subsystem - main memory, input-output channel, etc. A computing system as a whole is a set of interconnected subsystems, the interaction of which is probabilistic. An application for solving a certain problem entering a computing system goes through a sequence of stages of counting, accessing external storage devices and input-output devices. After completing a certain sequence of such stages, the number and duration of which depends on the complexity of the program, the request is considered serviced and leaves the computer system. Thus, the computing system as a whole can be represented by a set of QS, each of which reflects the process of functioning of an individual device or a group of similar devices that are part of the system.
A set of interconnected QSs is called a queuing network (stochastic network).
To begin with, we will look at the basics of the theory of QS, then we will move on to familiarize ourselves in detailed content with QS with expectation and closed QS. The course also includes a practical part, in which we will learn in detail how to apply theory in practice.
Queuing theory is one of the branches of probability theory. This theory considers probabilistic problems and mathematical models (before that we considered deterministic mathematical models). Recall that:
Deterministic mathematical model reflects the behavior of an object (system, process) from the perspective full certainty in the present and future.
Probabilistic mathematical model takes into account the influence of random factors on the behavior of an object (system, process) and, therefore, evaluates the future from the standpoint of the probability of certain events.
Those. here, as, for example, in game theory problems are considered in conditions uncertainty .
Let us first consider some concepts that characterize “stochastic uncertainty,” when the uncertain factors included in the problem are random variables (or random functions), the probabilistic characteristics of which are either known or can be obtained from experience. Such uncertainty is also called “favorable”, “benign”.
Strictly speaking, random disturbances are inherent in any process. It is easier to give examples of a random process than a “non-random” process. Even, for example, the process of running a clock (it seems to be a strictly calibrated work - “works like a clock”) is subject to random changes (moving forward, lagging behind, stopping). But as long as these disturbances are insignificant and have little effect on the parameters of interest to us, we can neglect them and consider the process as deterministic, non-random.
Let there be some system S(technical device, group of such devices, technological system - machine, site, workshop, enterprise, industry, etc.). In system S leaks random process, if it changes its state over time (passes from one state to another), moreover, in a previously unknown random manner.
Examples:
1. System S– technological system (machine section). Machines break down from time to time and are repaired. The process taking place in this system is random.
2. System S- an aircraft flying at a given altitude along a specific route. Disturbing factors - weather conditions, crew errors, etc., consequences - bumpiness, violation of the flight schedule, etc.
A random process occurring in a system is called Markovsky, if for any moment of time t 0 probabilistic characteristics of a process in the future depend only on its state at the moment t 0 and do not depend on when and how the system reached this state.
Let the system be in a certain state at the moment t 0 S 0 . We know the characteristics of the state of the system in the present and everything that happened during t <t 0 (process history). Can we predict (predict) the future, i.e. what will happen when t >t 0? Not exactly, but some probabilistic characteristics of the process can be found in the future. For example, the probability that after some time the system S will be able S 1 or will remain in state S 0, etc.
Example. System S- a group of aircraft participating in air combat. Let x– number of “red” planes, y– number of “blue” aircraft. By the time t 0 number of surviving (not shot down) aircraft, respectively – x 0 , y 0 . We are interested in the probability that at a moment in time the numerical superiority will be on the side of the “reds”. This probability depends on what state the system was in at the time t 0, and not on when and in what sequence those shot down died until the moment t 0 planes.
In practice, Markov processes in their pure form are usually not encountered. But there are processes for which the influence of “prehistory” can be neglected. And when studying such processes, Markov models can be used (queuing theory does not consider Markov queuing systems, but the mathematical apparatus that describes them is much more complex).
In operations research, Markov random processes with discrete states and continuous time are of great importance.
The process is called discrete state process, if its possible states S 1 , S 2, ... can be determined in advance, and the transition of the system from state to state occurs “in a jump,” almost instantly.
The process is called continuous time process, if the moments of possible transitions from state to state are not fixed in advance, but are uncertain, random and can occur at any moment.
Example. Technological system (section) S consists of two machines, each of which can fail (fail) at a random moment in time, after which the repair of the unit immediately begins, which also continues for an unknown, random time. The following system states are possible:
S 0 - both machines are working;
S 1 - the first machine is being repaired, the second is working;
S 2 - the second machine is being repaired, the first one is working;
S 3 - both machines are being repaired.
System transitions S from state to state occur almost instantly, at random moments when a particular machine fails or a repair is completed.
When analyzing random processes with discrete states, it is convenient to use a geometric scheme - state graph. The vertices of the graph are the states of the system. The arcs of the graph are possible transitions from state to state. For our example, the state graph is shown in Fig. 1.
Rice. 1. System state graph
Note. Transition from state S 0 in S 3 is not indicated in the figure, because it is assumed that the machines fail independently of each other. We neglect the possibility of simultaneous failure of both machines.
Event stream– a sequence of homogeneous events following one after another at some random moments in time.
In the previous example, this is a flow of failures and a flow of restorations. Other examples: the flow of calls at a telephone exchange, the flow of customers in a store, etc.
The flow of events can be visually represented by a series of points on the time axis O t- rice. 2.
Rice. 2. Image of the flow of events on the time axis
The position of each point is random, and only one implementation of the flow is depicted here.
Event flow intensity ( ) is the average number of events per unit of time.
Let's look at some properties (types) of event streams.
The stream of events is called stationary, if its probabilistic characteristics do not depend on time.
In particular, the intensity of the stationary flow is constant. The flow of events inevitably has condensations or rarefactions, but they are not of a regular nature, and the average number of events per unit of time is constant and does not depend on time.
The stream of events is called flow without consequences, if for any two non-overlapping sections of time and (see Fig. 2) the number of events that fall on one of them does not depend on how many events fall on the other. In other words, this means that the events that form the flow appear at certain points in time independently of each other and are each caused by its own causes.
The stream of events is called ordinary, if events appear in it one by one, and not in groups of several at once.
The stream of events is called simplest (or stationary Poisson), if it has three properties at once:
1) stationary;
2) ordinary;
3) has no consequences.
The simplest flow has the simplest mathematical description. It plays the same special role among flows as the law of normal distribution does among other distribution laws. Namely, when superimposing a sufficiently large number of independent, stationary and ordinary flows (comparable to each other in intensity), a flow close to the simplest is obtained.
For the simplest flow with intensity interval T between neighboring events has a so-called exponential distribution with density:
where is the parameter of the exponential law.
For a random variable T, which has an exponential distribution, the mathematical expectation is the reciprocal of the parameter, and the standard deviation is equal to the mathematical expectation:
Considering Markov processes with discrete states and continuous time, it is assumed that all transitions of the system S from state to state occur under the influence of simple event flows (call flows, failure flows, recovery flows, etc.). If all event streams transferring the system S from state to state of the simplest, then the process occurring in the system will be Markovian.
So, a system in state is affected by a simple flow of events. As soon as the first event of this flow appears, the system “jumps” from state to state (on the state graph along the arrow).
For clarity, on the system state graph, for each arc, the intensity of the flow of events that moves the system along this arc (arrow) is indicated. - intensity of the flow of events that transfers the system from state to . Such a graph is called marked. For our example, the labeled graph is shown in Fig. 3.
Rice. 3. Labeled system state graph
In this figure - the intensity of the failure flow; - intensity of recovery flow.
We assume that the average time to repair a machine does not depend on whether one machine is repaired or both at once. Those. Each machine is repaired by a separate specialist.
Let the system be in the state S 0 . In state S 1 it is translated by the flow of failures of the first machine. Its intensity is equal to:
where is the average failure-free operation time of the first machine.
Out of state S 1 in S 0 the system is transferred by the flow of “repair completions” of the first machine. Its intensity is equal to:
where is the average repair time for the first machine.
The intensities of event flows that transfer the system along all arcs of the graph are calculated in a similar way. Having at our disposal a labeled graph of system states, we construct mathematical model this process.
Let the system under consideration S has -possible states. The probability of the th state is the probability that at the moment of time, the system will be in the state. It is obvious that for any moment in time the sum of all state probabilities is equal to one:
To find all probabilities of states as functions of time, compose and solve Kolmogorov equations– a special type of equation in which the unknown functions are the probabilities of states. The rule for composing these equations is presented here without proof. But before introducing it, let’s explain the concept final probability of state .
What will happen to the state probabilities at ? Will they strive for any limits? If these limits exist and do not depend on the initial state of the system, then they are called final state probabilities .
where is the finite number of system states.
Final state probabilities– these are no longer variable quantities (functions of time), but constant numbers. It's obvious that:
Final state probability is essentially the average relative time the system remains in this state.
For example, the system S has three states S 1 , S 2 and S 3 . Their final probabilities are respectively 0.2; 0.3 and 0.5. This means that a system in a limiting stationary state spends on average 2/10 of its time in the state S 1, 3/10 – able S 2 and 5/10 – able S 3 .
The rule for composing the Kolmogorov system of equations: in each equation of the system on the left side is the final probability of a given state, multiplied by the total intensity of all flows, leading from this state, A in his right parts– the sum of the products of the intensities of all flows, included in -th state, on the probabilities of the states from which these flows come.
Using this rule, we write a system of equations for our example :
.
This system of four equations with four unknowns, it would seem, can be completely solved. But these equations are homogeneous (they do not have a free term), and, therefore, they determine the unknowns only up to an arbitrary factor. However, you can use the normalization condition: 
and use it to solve the system. In this case, one (any) of the equations can be discarded (it follows as a consequence of the others).
Continuation of the example. Let the flow intensities be equal to: .
We discard the fourth equation and add a normalization condition instead:
.
Those. in the limiting, stationary mode the system S on average 40% of the time will be spent in a state of S 0 (both machines are operational), 20% - in good condition S 1 (the first machine is being repaired, the second is working), 27% - in condition S 2 (the second machine is being repaired, the first one is working), 13% - in condition S 3 (both machines are being repaired). Knowing these final probabilities can help estimate the average efficiency of the system and the workload of repair organs.
Let the system S able S 0 (fully operational) brings in an income of 8 conventional units per unit of time, able S 1 – income 3 conventional units, able S 2 – income 5 conventional units, able S 3 – does not generate income. Then, in the limiting, stationary mode, the average income per unit of time will be equal to: conventional units.
Machine 1 is repaired in a fraction of the time equal to: . Machine 2 is repaired in a fraction of the time equal to: . Arises optimization problem. Even though we can reduce the average repair time of the first or second machine (or both), it will cost us a certain amount. The question is, will the increased revenue associated with faster repairs pay for the increased repair costs? You will need to solve a system of four equations with four unknowns.
Examples of queuing systems (QS): telephone exchanges, repair shops, ticket offices, information desks, machine tools and other technological systems, control systems of flexible production systems, etc.
Each QS consists of a certain number of service units, which are called service channels(these are machines, transport carts, robots, communication lines, cashiers, salespeople, etc.). Every QS is designed to serve some kind of flow of applications(requirements) arriving at some random moments in time.
Service of the request continues for some, generally speaking, random time, after which the channel is freed and ready to receive the next request. The random nature of the flow of applications and service time leads to the fact that at some periods of time an excessively large number of applications accumulate at the input of the QS (they either queue up or leave the QS unserved). In other periods, the system will work with underload or be completely idle.
The QS operation process is a random process with discrete states and continuous time. The state of the QS changes abruptly when certain events occur (the arrival of a new application, the end of service, the moment when an application that is tired of waiting leaves the queue).
Subject of queuing theory– construction of mathematical models that connect the given operating conditions of the QS (number of channels, their productivity, operating rules, nature of the flow of requests) with the characteristics that interest us - indicators of the effectiveness of the QS. These indicators describe the ability of the CMO to cope with the flow of applications. They can be: the average number of applications served by the QS per unit of time; average number of busy channels; average number of applications in queue; average waiting time for service, etc.
Mathematical analysis of the work of a QS is greatly facilitated if the process of this work is Markovian, i.e. streams of events that transfer the system from state to state are the simplest. Otherwise, the mathematical description of the process becomes very complicated and it is rarely possible to bring it to specific analytical dependencies. In practice, non-Markov processes are reduced to Markov processes with approximation. The following mathematical apparatus describes Markov processes.
First division (based on the presence of queues):
1. QS with failures;
2. Queue with a queue.
In QS with failures an application received at a time when all channels are busy is rejected, leaves the QS and is not serviced in the future.
In SMO with a queue an application that arrives at a time when all channels are busy does not leave, but gets in a queue and waits for the opportunity to be served.
QS with queues are subdivided into different types depending on how the queue is organized - limited or unlimited. Restrictions may concern both the length of the queue and the waiting time, “service discipline”.
So, for example, the following QSs are considered:
· CMO with impatient requests (queue length and service time are limited);
· QS with priority service, i.e. some applications are processed out of turn, etc.
In addition, QSs are divided into open QSs and closed QSs.
In an open QS the characteristics of the flow of requests do not depend on the state of the QS itself (how many channels are occupied). In a closed QS– depend. For example, if one worker services a group of machines that require adjustment from time to time, then the intensity of the flow of “demands” from the machines depends on how many of them are already operational and awaiting adjustment.
The classification of SMO is far from limited to the above varieties, but this is enough.
Let's consider the simplest QS with waiting - a single-channel system (n - 1), which receives a flow of requests with intensity ; service intensity (i.e., on average, a continuously busy channel will issue serviced requests per unit (of time). A request received at a time when the channel is busy is queued and awaits service.
System with limited queue length. Let us first assume that the number of places in the queue is limited by the number m, i.e. if an application arrives at a time when there are already m-applications in the queue, it leaves the system unserved. In the future, by directing m to infinity, we will obtain the characteristics of a single-channel QS without restrictions on the queue length.
We will number the states of the QS according to the number of applications in the system (both being serviced and awaiting service):
The channel is free;
The channel is busy, there is no queue;
The channel is busy, one application is in queue;
The channel is busy, k-1 applications are in queue;
The channel is busy, applications are in queue.
The GSP is shown in Fig. 4. All intensities of event flows moving into the system along arrows from left to right are equal to , and from right to left - . Indeed, the flow of requests moves the system along the arrows from left to right (as soon as a request arrives, the system goes to the next state), from right to left - the flow of “releases” of a busy channel, which has an intensity (as soon as the next request is serviced, the channel will either become free or decrease number of applications in queue).
Rice. 4. Single-channel QS with waiting
Shown in Fig. 4 diagram is a diagram of reproduction and death. Let us write expressions for the limiting probabilities of states:
(5)
or using: :
(6)
The last line in (6) contains a geometric progression with the first term 1 and the denominator p, from which we obtain:
(7)
in connection with which the limiting probabilities take the form:
(8).
Expression (7) is valid only for< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Let us determine the characteristics of the QS: probability of failure, relative throughput q, absolute throughput A, average queue length, average number of applications associated with the system, average waiting time in the queue, average time spent by an application in the QS.
Probability of failure. Obviously, the application is rejected only if the channel is busy and all t-places in the queue are also busy:
(9).
Relative Bandwidth:
(10).
Average queue length. Let's find the average number of applications in the queue as the mathematical expectation of a discrete random variable R-number of applications in the queue:
With probability there is one application in the queue, with probability there are two applications, in general with probability there are k-1 applications in the queue, etc., from which:
(11).
Since , the sum in (11) can be interpreted as a derivative of the sum of the geometric progression:
Substituting this expression into (11) and using from (8), we finally obtain:
(12).
The average number of applications in the system. Next, we obtain a formula for the average number of -requests associated with the system (both standing in queue and being serviced). Since , where is the average number of applications under service, and k is known, it remains to determine . Since there is only one channel, the number of serviced requests can be 0 (with probability ) or 1 (with probability 1 - ), from which:
.
and the average number of applications associated with the QS is:
(13).
Average waiting time for an application in the queue. Let's denote it ; if a request comes into the system at some point in time, then with probability the service channel will not be busy, and it will not have to wait in line (the waiting time is zero). Most likely, she will come into the system while some request is being served, but there will be no queue in front of her, and the request will wait for the start of its servicing for a period of time (the average time of servicing one request). There is a probability that there will be another application in the queue before the application being considered, and the average waiting time will be equal to , etc.
If k=m+1, i.e. when a newly arriving request finds the service channel busy and m-requests in the queue (probability of this), then in this case the request does not queue (and is not served), so the waiting time is zero. The average waiting time will be:
if we substitute expressions for probabilities (8) here, we get:
(14).
Here we use relations (11), (12) (derivative of a geometric progression), as well as from (8). Comparing this expression with (12), we note that in other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the application flow.
(15).
Average time an application stays in the system. Let us denote the mathematical expectation of a random variable as the time a request stays in the QS, which is the sum of the average waiting time in the queue and the average service time. If the system load is 100%, obviously, otherwise:
.
Example 1. A gas station (gas station) is a service station with one service channel (one pump).
The area at the station allows no more than three cars to be in line for refueling at the same time (m = 3). If there are already three cars in the queue, the next car arriving at the station does not join the queue. The flow of cars arriving for refueling has an intensity = 1 (car per minute). The refueling process lasts an average of 1.25 minutes.
Define:
probability of failure;
relative and absolute capacity of gas stations;
average number of cars waiting to refuel;
average number of cars at a gas station (including those being serviced);
average waiting time for a car in line;
average time a car spends at a gas station (including service).
In other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the application flow.
We first find the reduced intensity of the flow of applications: =1/1.25=0.8; =1/0.8=1.25.
According to formulas (8):
Probability of failure is 0.297.
Relative capacity of the QS: q=1-=0.703.
Absolute throughput of QS: A==0.703 cars per minute.
We find the average number of cars in the queue using formula (12):
those. The average number of cars waiting in line to fill the gas station is 1.56.
Adding to this value the average number of vehicles under service:
we get the average number of cars associated with a gas station.
Average waiting time for a car in queue according to formula (15):
Adding to this value, we get the average time that a car spends at a gas station:
Systems with unlimited waiting. In such systems, the value of m is not limited and, therefore, the main characteristics can be obtained by passing to the limit in previously obtained expressions (5), (6), etc.
Note that the denominator in the last formula (6) is the sum of an infinite number of terms of the geometric progression. This sum converges when the progression is infinitely decreasing, i.e. at<1.
It can be proven that<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
If, then relations (8) take the form:
(16).
If there are no restrictions on the length of the queue, each application that comes into the system will be serviced, therefore q=1, 
.
We obtain the average number of applications in the queue from (12) at:
The average number of applications in the system according to formula (13) at:
.
The average waiting time is obtained from formula (14) with:
.
Finally, the average time an application stays in the QS is:
System with limited queue length. Let's consider a channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel); number of places in the queue.
System states are numbered according to the number of requests associated with the system:
no queue:
All channels are free;
One channel is occupied, the rest are free;
-channels are occupied, the rest are not;
All channels are occupied, there are no free channels;
there is a queue:
All n-channels are occupied; one application is in the queue;
All n-channels, r-requests in the queue are occupied;
All n-channels, r-requests in the queue are occupied.
GSP is shown in Fig. 17. Each arrow is marked with the corresponding intensities of event flows. Along the arrows from left to right, the system is always transferred by the same flow of requests with an intensity of
Rice. 17. Multi-channel QS with waiting
The graph is typical for the processes of reproduction and death, for which the solution was previously obtained. Let's write expressions for the limiting probabilities of states using the notation: (here we use the expression for the sum of a geometric progression with a denominator).
Thus, all state probabilities have been found.
Let us determine the performance characteristics of the system.
Probability of failure. An incoming request is rejected if all n-channels and all m-places in the queue are occupied:
(18)
The relative throughput complements the probability of failure to one:
Absolute throughput of QS:
(19)
Average number of busy channels. For QS with refusals, it coincided with the average number of applications in the system. For a QS with a queue, the average number of busy channels does not coincide with the average number of applications in the system: the latter value differs from the first by the average number of applications in the queue.
Let us denote the average number of occupied channels by . Each busy channel serves on average A-claims per unit of time, and the QS as a whole serves on average A-claims per unit of time. Dividing one by the other, we get:
The average number of requests in a queue can be calculated directly as the mathematical expectation of a discrete random variable:
(20)
Here again (the expression in parentheses) the derivative of the sum of the geometric progression occurs (see above (11), (12) - (14)), using the relation for it, we obtain:
Average number of applications in the system:
Average waiting time for an application in the queue. Let's consider a number of situations that differ in the state in which a newly arrived request will find the system and how long it will have to wait for service.
If a request does not find all channels busy, it will not have to wait at all (the corresponding terms in the mathematical expectation are equal to zero). If a request arrives at a time when all n-channels are busy and there is no queue, it will have to wait on average for a time equal to (because the “release flow” of -channels has intensity ). If a request finds all channels busy and one request in front of it in the queue, it will have to wait on average for a period of time (for each request in front), etc. If a request finds itself in a queue of -requests, it will have to wait on average for time If a newly arrived request finds m-requests already in the queue, then it will not wait at all (but will not be served). We find the average waiting time by multiplying each of these values by the corresponding probabilities:
(21)
Just as in the case of a single-channel QS with waiting, we note that this expression differs from the expression for the average queue length (20) only by the factor , i.e.
.
The average residence time of a request in the system, as well as for a single-channel QS, differs from the average waiting time by the average service time multiplied by the relative throughput:
.
Systems with unlimited queue length. We considered a channel QS with waiting, when no more than m-requests can be in the queue at the same time.
Just as before, when analyzing systems without restrictions, it is necessary to consider the obtained relations for .
We obtain the probabilities of states from the formulas by passing to the limit (at ). Note that the sum of the corresponding geometric progression converges at and diverges at >1. Assuming that<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Probability of failure, relative and absolute throughput. Since each request will sooner or later be serviced, the characteristics of the QS throughput will be:
The average number of applications in the queue is obtained from (20):
,
and the average waiting time is from (21):
.
The average number of occupied channels, as before, is determined through the absolute throughput:
.
The average number of applications associated with the QS is defined as the average number of applications in the queue plus the average number of applications under service (average number of busy channels):
Example 2. A gas station with two pumps (n = 2) serves a flow of cars with an intensity of =0.8 (cars per minute). Average service time per machine:
There is no other gas station in the area, so the line of cars in front of the gas station can grow almost unlimitedly. Find the characteristics of the QS.
Because the<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
etc.
We will find the average number of busy channels by dividing the absolute capacity of the QS A = = 0.8 by the service intensity = 0.5:
The probability of no queue at a gas station will be:
Average number of cars in queue:
Average number of cars at gas stations:
Average waiting time in queue:
Average time a car spends at a gas station:
QS with limited waiting time. Previously, we considered systems with waiting limited only by the queue length (the number of m-requests simultaneously in the queue). In such a QS, an application that has grown in a queue does not leave it until it waits for service. In practice, there are other types of QS in which an application, after waiting for some time, can leave the queue (so-called “impatient” applications).
Let's consider a QS of this type, assuming that the waiting time constraint is a random variable.
Let us assume that there is an n-channel QS with waiting, in which the number of places in the queue is unlimited, but the time a request stays in the queue is some random variable with a mean value, thus, each request in the queue is subject to a kind of Poisson " flow of care” with intensity:
If this flow is Poisson, then the process occurring in the QS will be Markovian. Let us find the state probabilities for it. The numbering of system states is associated with the number of applications in the system - both being served and standing in queue:
no queue:
All channels are free;
One channel is busy;
Two channels are busy;
All n-channels are occupied;
there is a queue:
All n-channels are occupied, one request is in the queue;
All n-channels are occupied, r-requests are in queue, etc.
The graph of states and transitions of the system is shown in Fig. 23.
Rice. 23. QS with limited waiting time
Let's mark this graph as before; all arrows leading from left to right will indicate the intensity of the flow of applications. For states without a queue, the arrows leading from them from right to left will, as before, indicate the total intensity of the flow servicing all occupied channels. As for states with a queue, the arrows leading from them from right to left will have the total intensity of the service flow of all n-channels plus the corresponding intensity of the flow of departures from the queue. If there are r-applications in the queue, then the total intensity of the flow of departures will be equal to .
As can be seen from the graph, there is a pattern of reproduction and death; using general expressions for the limiting probabilities of states in this scheme (using abbreviated notations, we write:
(24)
Let us note some features of a QS with limited waiting compared to the previously considered QS with “patient” requests.
If the length of the queue is not limited and the requests are “patient” (do not leave the queue), then the stationary limit regime exists only in the case (at , the corresponding infinite geometric progression diverges, which physically corresponds to unlimited growth of the queue at ).
On the contrary, in a QS with “impatient” requests leaving the queue sooner or later, the established service mode at is always achieved, regardless of the reduced intensity of the flow of requests. This follows from the fact that the series for in the denominator of formula (24) converges for any positive values of and .
For a QS with “impatient” requests, the concept of “probability of failure” does not make sense - each request gets in line, but may not wait for service, leaving ahead of time.
Relative throughput, the average number of requests in the queue. The relative capacity q of such a QS can be calculated as follows. Obviously, all applications will be serviced, except those that leave the queue ahead of schedule. Let's calculate the average number of applications that leave the queue early. To do this, we calculate the average number of applications in the queue:
Each of these applications is subject to a “flow of departures” with an intensity of . This means that out of the average number of -applications in the queue, on average, -applications will leave without waiting for service, -applications per unit of time and in total per unit of time, on average -applications will be served. The relative capacity of the QS will be:
We still obtain the average number of occupied channels by dividing the absolute bandwidth A by:
(26)
Average number of applications in queue. Relation (26) allows you to calculate the average number of applications in the queue without summing the infinite series (25). From (26) we obtain:
and the average number of occupied channels included in this formula can be found as the mathematical expectation of a random variable Z, taking values 0, 1, 2,..., n with probabilities ,:
In conclusion, we note that if in formulas (24) we go to the limit at (or, what is the same, at ), then formulas (22) will be obtained, i.e., “impatient” applications will become “patient”.
So far we have considered systems in which the incoming flow is in no way connected with the outgoing flow. Such systems are called open-loop. In some cases, serviced requests are again received at the input after a delay. Such QSs are called closed. A clinic serving a given area, a team of workers assigned to a group of machines, are examples of closed systems.
In a closed QS, the same finite number of potential requirements circulates. Until a potential requirement has been realized as a service request, it is considered to be in a delay block. At the moment of implementation, it enters the system itself. For example, workers maintain a group of machines. Each machine is a potential requirement, turning into a real one at the moment of its breakdown. While the machine is working, it is in the delay block, and from the moment of breakdown until the end of the repair, it is in the system itself. Each worker is a service channel.
Let n- number of service channels, s- number of potential applications, n <s , - the intensity of the flow of applications for each potential requirement, μ - the intensity of service:
The probability of system downtime is determined by the formula
R
0
= 
.
Final probabilities of system states:
Pk= at k
The average number of occupied channels is expressed through these probabilities
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) or
=P 1 + 2P 2 +…+(n- 1)Pn- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Using this we find the absolute throughput of the system:
as well as the average number of applications in the system
M=s- =s- .
Example 1. The input of a three-channel QS with failures receives a flow of requests with an intensity =4 requests per minute, time for servicing a request by one channel t obs =1/μ =0.5 min. From the point of view of QS capacity, is it profitable to force all three channels to service requests at once, and the average service time is reduced by three times? How will this affect the average time an application spends in the CMO?
Solution. We find the probability of downtime of a three-channel QS using the formula
ρ = /μ =4/2=2, n=3,
P 0 = = = 0,158.
The probability of failure is determined by the formula:
P open = P n ==
P open = 0.21.
Relative system throughput:
R obsl = 1-R open 1-0,21=0,79.
Absolute system throughput:
A= P obsl 3,16.
The average number of occupied channels is determined by the formula:
1.58, share of channels occupied by servicing,
q = 0,53.
The average time an application stays in the QS is found as the probability that the application is accepted for service, multiplied by the average service time: t SMO 0.395 min.
Combining all three channels into one, we get a single-channel system with parameters μ= 6, ρ= 2/3. For a single-channel system, the probability of downtime is:
R 0 = = =0,6,
probability of failure:
P open =ρ P 0 = = 0,4,
relative throughput:
R obsl = 1-R open =0,6,
absolute throughput:
A=P obs =2.4.
t SMO =P obsl= =0.1 min.
As a result of combining channels into one, the system throughput decreased as the probability of failure increased. The average time an application spends in the system has decreased.
Example 2. The input of a three-channel QS with an unlimited queue receives a flow of requests with an intensity =4 applications per hour, average time to service one application t=1/μ=0.5 h. Find the system performance indicators.
For the system under consideration n =3, =4, μ=1/0.5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
We find the average number of applications in the queue using the formula:
L
=
.
L = = .
We calculate the average waiting time for an application in the queue using the formula:
t= = 0.22 hours.
Average time an application stays in the system:
T=t+ 0,22+0,5=0,72.
Example 3. There are 3 hairdressers working in the hairdressing salon, and there are 3 chairs in the waiting room. The flow of clients has intensity =12 clients per hour. Average service time t obsl =20 min. Determine the relative and absolute throughput of the system, the average number of occupied chairs, the average length of the queue, the average time that the client spends in the hairdresser.
For this task n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. The probability of downtime is determined by the formula:
R
0
=
.
P
0
= 
0,012.
The probability of denial of service is determined by the formula
P open =P n+m = .
P open =P n + m 0,307.
Relative system capacity, i.e. service probability:
P obsl =1-P open 1-0,307=0,693.
Absolute throughput:
A= P obsl 12 .
Average number of busy channels:
.
The average queue length is determined by the formula:
L
=
L= 
1,56.
Average waiting time for service in queue:
t= h.
Average number of applications to the CMO:
M=L + .
Average time an application stays in the CMO:
T=M/ 0.36 hours
Example 4. A worker operates 4 machines. Each machine fails with intensity =0.5 failures per hour, average repair time t rem=1/μ=0.8 h. Determine the throughput of the system.
This problem considers a closed QS, μ =1.25, ρ=0.5/1.25=0.4. The probability of worker downtime is determined by the formula:
R
0
=
.
P
0
= 
.
Probability of worker employment R zan = 1-P 0 . A=( 1-P 0 )μ =0.85μ machines per hour.
Task:
Two workers operate a group of four machines. Stops of a working machine occur on average after 30 minutes. The average setup time is 15 minutes. Operating and setup time are distributed according to an exponential law.
Find the average share of free time for each worker and the average operating time of the machine.
Find the same characteristics for a system in which:
a) each worker is assigned two machines;
b) two workers always service the machine together, and with double intensity;
c) the only faulty machine is serviced by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first describe the system in terms of the processes of death and birth).
Solution:
The following states of system S are possible:
S 0 – all machines are operational;
S 1 – 1 machine is being repaired, the rest are in good working order;
S 2 – 2 machine is being repaired, the rest are in working order;
S 3 – 3 machine is being repaired, the rest are in working order;
S 4 – 4 machine is being repaired, the rest are in good working order;
S 5 – (1, 2) machines are being repaired, the rest are in good working order;
S 6 – (1, 3) machines are being repaired, the rest are in working order;
S 7 – (1, 4) machines are being repaired, the rest are in working order;
S 8 – (2, 3) machines are being repaired, the rest are in good working order;
S 9 – (2, 4) machines are being repaired, the rest are in good working order;
S 10 – (3, 4) machines are being repaired, the rest are in good working order;
S 11 – (1, 2, 3) machines are being repaired, 4 machine is operational;
S 12 – (1, 2, 4) machines are being repaired, 3 machine is operational;
S 13 – (1, 3, 4) machines are being repaired, machine 2 is operational;
S 14 – (2, 3, 4) machines are being repaired, 1 machine is operational;
S 15 – all machines are repaired.
System state graph...
This system S is an example of a closed system, since each machine is a potential requirement, turning into a real one at the moment of its breakdown. While the machine is working, it is in the delay block, and from the moment of breakdown until the end of the repair, it is in the system itself. Each worker is a service channel.
If a worker is busy, he sets up μ-machines per unit time, system capacity:
Answer:
The average share of free time for each worker is ≈ 0.09.
Average machine operating time ≈ 3.64.
a) Each worker is assigned two machines.
The probability of worker downtime is determined by the formula:
Probability of worker employment:
If a worker is busy, he sets up μ-machines per unit time, system capacity:
Answer:
The average share of free time for each worker is ≈ 0.62.
Average machine operating time ≈ 1.52.
b) Two workers always service the machine together, and with double intensity.
c) The only faulty machine is serviced by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first describe the system in terms of the processes of death and birth).
Comparison of 5 answers:
The most effective way to organize workers at machines will be the initial version of the task.
Examples of the simplest queuing systems (QS) were discussed above. The term “protozoa” does not mean “elementary”. Mathematical models of these systems are applicable and successfully used in practical calculations.
The possibility of applying decision theory in queuing systems is determined by the following factors:
1. The number of applications in the system (which is considered as a QS) must be quite large (massively).
2. All applications received at the input of the QS must be of the same type.
3. To calculate using formulas, you need to know the laws that determine the receipt of applications and the intensity of their processing. Moreover, the order flows must be Poisson.
4. Structure of the QS, i.e. the set of incoming requirements and the sequence of application processing must be strictly fixed.
5. It is necessary to exclude subjects from the system or describe them as requirements with a constant processing intensity.
To the restrictions listed above, we can add one more, which has a strong impact on the dimension and complexity of the mathematical model.
6. The number of priorities used should be minimal. The priorities of applications must be constant, i.e. they cannot change during processing within the QS.
In the course of the work, the main goal was achieved - the main material of “QS with limited waiting time” and “Closed QS” was studied, which was set by the teacher of the academic discipline. We also got acquainted with the application of the acquired knowledge in practice, i.e. consolidated the material covered.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolution..
5) Fomin G.P. Mathematical methods and models in commercial activities. M: Finance and Statistics, 2001.
6) Gmurman V.E. Theory of Probability and Mathematical Statistics. M: Higher School, 2001.
7) Sovetov B.A., Yakovlev S.A. Systems Modeling. M: Higher School, 1985.
8) Lifshits A.L. Statistical modeling of QS. M., 1978.
9) Ventzel E.S. Operations research. M: Nauka, 1980.
10) Ventzel E.S., Ovcharov L.A. Probability theory and its engineering applications. M: Nauka, 1988.
Consider a multi-channel QS (P> 1), the input of which receives a Poisson flow of requests with intensity and the service intensity of each channel is p, the maximum possible number of places in the queue is limited by the value T. The discrete states of the QS are determined by the number of applications received by the system, which can be written down:
Sq - all channels are free, k = 0;
S- only one channel is occupied (any), k = 1;
*5*2 - only two channels (any) are occupied, k = 2;
S n- everyone is busy P channels, k = p.
While the QS is in any of these states, there is no queue. After all service channels are occupied, subsequent requests form a queue, thereby determining the further state of the system:
S n + - everyone is busy P channels and one application is in queue, k = P + 1;
S n +2 - everyone is busy P channels and two applications are in queue, k = P + 2;
S n+m - everyone is busy P ropes and everything T places in line k = n + m.
State graph and-channel SMO With queue, limited T in some places, shown in Fig. 5.18.
The transition of the QS to a state with large numbers is determined by the flow of incoming requests with an intensity
Rice. 5.18
whereas, according to the condition, they take part in servicing these requests P identical channels with a service flow intensity equal to p for each channel. In this case, the total intensity of the service flow increases with the connection of new channels up to this state Sn, when all P channels will be busy. With the appearance of the queue, the service intensity no longer increases, since it has already reached the maximum value equal to ph.
Let us write down expressions for the limiting probabilities of states
The expression for rho can be transformed using the geometric progression formula for the sum of terms with denominator p /P:
The formation of a queue is possible when a newly received application finds in the system at least P requirements, i.e. when the system will be p, p + 1, P + 2, (P + T- 1) requirements. These events are independent, so the probability that all channels are busy is equal to the sum of the corresponding probabilities r yu Rp+bPp+2 > ->Рп+т- 1- Therefore, the probability of queue formation is
The possibility of denial of service occurs when all P channels and everything T places in line are full
The relative throughput will be equal to
Absolute throughput
Average number of busy channels
Average number of idle channels
Channel Occupancy (Usage) Ratio
Channel downtime ratio
Average number of applications in queues
if r/n = 1, this formula takes a different form:
The average waiting time in a queue is determined by Little's formulas 
The average time an application stays in the QS, as for a single-channel QS, is greater than the average waiting time in the queue by the average service time equal to 1/p, since the application is always served by only one channel:
Example 5.21. The minimarket receives a flow of customers with an intensity of six customers per minute, who are served by three cashiers with an intensity of two customers per minute. The queue length is limited to five customers. Determine the characteristics of the QS and evaluate its performance.
Solution
n = 3; T = 5; X=6; p = 2; p =X/x = 3; r/n = 1.
We find the limiting probabilities of the QS states:
Share of downtime for cashiers
The probability that only one channel is occupied with servicing is
The probability that two channels are occupied with servicing is
The probability that all three channels are busy is
The probability that all three channels and five places in the queue are occupied is
The possibility of denial of service occurs when k = t + n = = 5 + 3 = 8 and is р$ = р OTK = 0,127.
The relative and absolute capacities of the QS are respectively equal Q = 1 - r open= 0.873 and L = 0.873A. = 5.24 (customers/min).
The average number of busy channels and the average queue length are:
The average waiting time in the queue n stay in the QS is correspondingly equal to:
The minimarket's service system deserves high praise, since the average length of the queue and the average time a customer spends in the queue are small.
Example 5.22. On average, vehicles with fruit and vegetable products arrive at the fruit and vegetable depot every 30 minutes. The average time for unloading one truck is 1.5 hours. Unloading is carried out by two teams of loaders. On the territory of the base, no more than four vehicles may be in line at the landing stage, waiting for unloading. We will determine the indicators and evaluate the performance of the QS.
Solution
SMO two-channel, P= 2 with limited number of places in line m= 4, incoming flow intensity l. = 2 av/h, service intensity c = 2/3 av/h, load intensity p = A./p = 3, r/n = 3/2 = 1,5.
We determine the characteristics of the QS:
The probability that all crews are not loaded when there are no vehicles is
The probability of failure when there are two cars under unloading and four cars in the queue,
Average number of cars in queue
The share of loaders' downtime is very small and amounts to only 1.58% of working time, and the probability of refusal is high - 36% of applications received are refused unloading, both teams are almost fully occupied, the employment coefficient is close to one and equal to 0.96, relative the throughput is low - only 64% of the received applications will be serviced, the average length of the queue is 2.6 cars, therefore, SM O cannot cope with the fulfillment of requests for service and it is necessary to increase the number of teams of loaders and make wider use of the landing stage's capabilities.
Example 5.23. A commercial company receives early vegetables from the greenhouses of a suburban state farm at random times with an intensity of 6 units. in a day. Utility rooms, equipment and labor resources allow us to process and store products in the amount of 2 units. The company employs four people, each of whom, on average, can process the products of one delivery within 4 hours. The duration of the working day during shift work is 12 hours. What should be the capacity of the warehouse so that the complete processing of products would be at least 97% of the number of deliveries made?
Solution
Let's solve the problem by sequentially determining the QS indicators for different storage capacity values T= 2, 3, 4, 5, etc. and comparison at each stage of calculating the probability of service with a given value р 0 ()С = 0,97.
Determine the intensity of the load:
We find the probability, or fraction of time, of downtime for t = 2:
Probability of denial of service, or the proportion of lost applications,
The probability of service, or the proportion of applications served out of those received, is
Since the obtained value is less than the specified value of 0.97, we continue the calculations for T= 3. For this value, the indicators of the QS states have the values
The probability of service in this case is also less than the specified value, so we continue the calculations for the next t = 4, for which the state indicators have the following values: p$ = 0.12; Rotk = 0.028; Pofc = 0.972. Now the obtained value of the service probability satisfies the conditions of the problem, since 0.972 > 0.97, therefore, the capacity of the warehouse must be increased to a volume of 4 units.
To achieve a given probability of service, you can select in the same way the optimal number of people to process vegetables by sequentially calculating the QS indicators for n = 3, 4, 5, etc. A compromise solution can be found by comparing and contrasting for different options for CMO organizations the costs associated with both an increase in the number of employees and the creation of special technological equipment for processing vegetables in a commercial enterprise.
Thus, queuing models in combination with economic methods of setting tasks make it possible to analyze existing QS systems, develop recommendations for their reorganization to improve operational efficiency, and also determine the optimal performance of newly created QS systems.
Example 5.24. On average, nine cars arrive at a car wash per hour, but if there are already four cars in the queue, newly arriving customers, as a rule, do not join the queue, but drive by. The average time to wash a car is 20 minutes, and there are only two places to wash it. The average cost of washing a car is 70 rubles. Determine the average loss of revenue for a car wash during the day.
Solution
X= 9 cars/h; = 20 min; p = 2;t = 4.
Finding the load intensity 
Determining the percentage of car wash downtime
Probability of failure
Relative capacity is equal to Absolute capacity Average number of cars in queue
Average number of applications being serviced
Average waiting time in queue
Average time a car spends at a car wash
Thus, 34% of applications will not be serviced, the loss for 12 hours of work one day will amount to an average of 2570 rubles. (12*9* 0.34 70), i.e. 52% of total revenue, because r open = 0,52 p 0 ^ s.
- relative throughput, or probability of service, absolute throughput, average number of occupied crews, occupancy rate of loader crews
Waiting systems with unlimited incoming flow
n identical channels receive the simplest flow of requests with intensity λ . If at the time of receipt of a request all channels are busy, then this request is queued and waits for servicing to begin. The service time of each request is a random variable that obeys an exponential distribution law with the parameter μ .Calculation formulas
Probability that all channels are free
Probability that it is busy k channels, provided that the total number of requests being serviced does not exceed the number of channels,
The probability that the system contains k requests, if their number is greater than the number of channels,
The probability that all channels are busy is
Average waiting time for an application to start servicing in the system
Average queue length
Average number of channels free from service
A gas station with two pumps serves a Poisson flow of cars with an intensity of λ=0.8 cars per minute. The service time for one machine obeys an exponential law with an average value of 2 minutes. There is no other gas station in the area, so the queue in front of the gas station can grow almost unlimitedly. Find:
1) average number of occupied columns;
2) the probability of no queue at the gas station;
3) the likelihood that you will have to wait for service to begin;
4) the average number of cars in the queue;
5) average waiting time in line;
6) the average time a car spends at a gas station;
7) average number of cars at gas stations.
Solution. According to the conditions of the problem n=2, λ=0.8; μ=1/t obs =0.5; ρ=λ/μ=1.6
Because the ρ /n=0,8<1, то очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы системы массового обслуживания.
We find the probabilities of the QS states:
Average number of occupied columns:
N zan =n-N 0 = 2-(2 p 0 +1 p 1) = 2-2 0.1111 - 0.1778 = 1.6
Probability of no queue at the gas station:
The probability that you will have to wait for the service to start is equal to the probability that all columns are occupied:
p 0 +p 1 +p 2 = 0.1111+0.1778+0.1422 = 0.4311
Average number of cars in queue:
Average waiting time in queue:
Average time a car spends at a gas station:
t preb =t obs +t cool = 2+3.5556 = 5.5556 min.
Average number of cars at gas stations:
N zan +L och = 1.6+2.8444 = 4.4444
Consider a single-channel QS with expectations, in which the number of channels is equal to one n= 1, the intensity of requests is λ, the intensity of service is μ. An application received at a time when the channel is busy is queued and awaits service. The number of places in the queue is limited and equal to m. If all places in the queue are occupied, then the application leaves the queue unserved. Let's analyze the state of the system:
- S 0 – channel is free;
- S 1 – channel busy;
- S 2 – channel is busy, one request is in queue;
- Sk– channel is busy, (k–1) requests are in queue;
- Sm+ 1 – channel busy, in queue m applications.
Rice. 25
Using Erlang formulas, we will find the probabilities of events consisting in the fact that the QS is in a state S 1 , S 2 , …, S m+1: 
(28)
In this case, the probability that an application arriving in the system will find it free is equal to 
. (29)
The ratio of the intensity of receipt of requests λ to the intensity of servicing requests μ is the reduced intensity μ, i.e.
ρ=λ/μ
Let us replace the ratio λ/&mu in formulas (28) and (29) with ρ, then the expressions will take the form:
(30)
Probability R 0 will be calculated using the following formula:
p 0 = -1 . (31)
Expression for probability P 0 is a geometric progression whose sum will be equal to
.
Thus, formulas (30) and (31) make it possible to determine the probability of any event that can occur in the system, i.e., determine the probability of the system being in any state.
Formula for P 0 is valid for the case when ρ ≠ 1. In the case when ρ = 1, i.e., the intensity of the receipt of applications is equal to the intensity of their servicing, another formula is used to calculate the probability that the system is free:
,
where m is the number of applications in the queue.
Let's define performance characteristics of single-channel QS:
- the probability that the next application arriving in the system will be rejected R otk;
- absolute throughput A,
- relative throughput Q,
- number of occupied channels k,
- average number of requests in the queue r,
- average number of applications associated with the QS, z .
The next request entering the system is rejected when the channel is busy, i.e. another request is being serviced, and that’s all m places in the queue are also filled. then the probability of this event can be calculated using the following formula:
. (32)
The probability that an application will come into the system and either be immediately serviced or there will be places in the queue, i.e. the relative throughput, can be found using the formula
. (33)
The average number of requests that can be serviced per unit of time, i.e. absolute throughput, is calculated as follows:
A=Q·λ (34)
Thus, using formulas (32), (33), (34) it is possible to calculate the main performance indicators for any queuing system. Now we will derive expressions for calculating the characteristics inherent only to this QS.
We define the average number of requests in the queue r as the mathematical expectation of a discrete random variable, where R– the number of applications in the queue.
♦ R 2 is the probability that there is one request in the queue for service;
♦ R 3 – probability that there are two applications in the queue;
♦ Rk– probability that there are (k–1) applications in the queue;
♦ Rm+ 1 – probability that there are m applications in the queue.
Then the average number of applications in the queue can be calculated as follows:
r =1·P 2 +2·P 3 + ... +(k-1)·P k + ... +m·P m+1 . (35)
Let us substitute into formula (35) the previously found probability values calculated in formula (30):
r =1·ρ 2 ·p 0 +2·ρ 3 ·p 0 + ... +(k-1)·ρ k ·p 0 + ... +m·ρ m+1 ·p 0 . (35)
Let's take the probability out of the equation P 0 and R 2, then we get the final formula for calculating the average number of requests in the queue for service:
r =ρ 2 p 0 (1+2 ρ+ ... +(k-1) ρ k-2 + ... +m ρ m-1)
Let us derive a formula for the average number of applications associated with the QS, z, i.e. the number of applications in the queue that are being serviced. Consider the total number of applications associated with the QS, z, as the sum of two values of the average number of applications in the queue r and the number of busy channels k:
z = r +k.
Since there is only one channel, the number of occupied channels k can take the values 0 or 1. The probability that k = 0, i.e. the system is free, corresponds to the probability P 0, the value of which can be found using formula (31). If k = 1, i.e. the channel is busy servicing the request, but there are still places in the queue, then the probability of this event can be calculated using the formula
.
Therefore, z will be equal to:
. (37)
Single-channel QS with waiting
The queuing system has one channel. The incoming flow of service requests is the simplest flow with intensity l. The intensity of the service flow is equal to m (i.e., on average, a continuously busy channel will issue m serviced requests). The duration of service is a random variable subject to the exponential distribution law. The service flow is the simplest Poisson flow of events. A request received when the channel is busy is queued and awaits service.Let us assume that no matter how many requests arrive at the input of the serving system, this system (queue + clients being served) cannot accommodate more than N-requirements (applications), i.e. clients who are not on hold are forced to be served elsewhere . Finally, the source generating service requests has unlimited (infinitely large) capacity.
The state graph of the QS in this case has the form shown in Fig. 3.2.
State graph of a single-channel QS with waiting (scheme of death and reproduction)
The QS states have the following interpretation:
S 0 - channel free
S 1 - channel busy (no queue);
S 2 - channel is busy (one request is in queue);
………………………………
S n - the channel is busy (n - 1 requests are in queue);
……………………………
S N - channel is busy (N - 1 applications are in queue).
The stationary sag in this system will be described by the following system of algebraic equations:
P - status number.
The solution to the above system of equations (3.10) for our QS model has the form
It should be noted that the fulfillment of the stationarity condition for a given QS is not necessary, since the number of applications admitted into the serving system is controlled by introducing a limit on the queue length (which cannot exceed N- 1), and not the ratio between the intensities of the input flow, i.e., not the ratio
l/m = p
Let's define characteristics of a single-channel QS with waiting and limited queue length equal to (N- 1):
Let's consider an example of a single-channel QS with waiting.
Example 3.2. The specialized diagnostic post is a single-channel QS. The number of parking lots for cars awaiting diagnostics is limited and equal to 3 [(N- 1) = 3]. If all parking lots are occupied, i.e., there are already three cars in the queue, then the next car that arrives for diagnostics will not be placed in the queue for service. The flow of cars arriving for diagnostics is distributed according to Poisson's law and has an intensity l= 0.85 (vehicles per hour). The vehicle diagnostic time is distributed according to an exponential law and averages 1.05 hours.
Need to determine probabilistic characteristics of a diagnostic station operating in a stationary mode.
Solution
1. Vehicle maintenance flow parameter:
2. The reduced intensity of traffic flow is defined as the ratio of intensities l and m, i.e.
3. Let's calculate the final probabilities of the system:
P 1 =ρ P 0 = 0.893 0.248 = 0.221
P 2 =ρ 2 P 0 = 0.893 2 0.248 = 0.198
P 3 =ρ 3 P 0 = 0.893 3 0.248 = 0.177
P 4 =ρ 4 P 0 = 0.893 2 0.248 = 0.158
4. Probability of failure to service the vehicle:
P open =P 4 =ρ 4 ·P 0 ≈ 0.158
5. Relative throughput of the diagnostic post:
q=1-P open = 1-0.158 = 0.842
6. Absolute throughput of the diagnostic station
A=λ·q = 0.85·0.842 = 0.716 (vehicles per hour)
7. Average number of cars being serviced and in queue (i.e. in the queuing system):
8. Average time a car stays in the system:
9. Average length of stay of an application in the queue for service:
W q =W S -1/μ = 2.473-1/0.952 = 1.423 hours
10. Average number of applications in the queue (queue length): Lq= A,(1 - P N) W q= 0,85
L q =λ(1-P N) W q = 0.85 (1-0.158) 1.423 = 1.02
The work of the considered diagnostic post can be considered satisfactory, since the diagnostic post does not service cars on average in 15.8% of cases (R open= 0.158). As indicators of the effectiveness of the QS with expectation, in addition to the already known indicators - absolute A and relative Q throughput, probability of failure P reject. , the average number of occupied channels (for a multi-channel system) we will also consider the following: L syst. - average number of applications to the system; T syst. - average time an application stays in the system; L very - average number of applications in the queue (queue length); T och. - average time an application stays in the queue; Rzan.. - the probability that the channel is busy (the degree of channel load).
Single-channel system with unlimited queue
In practice, single-channel QSs with an unlimited queue are often encountered (for example, a pay phone with one booth).Let's consider the problem.
There is a single-channel QS with a queue on which no restrictions are imposed (neither on the length of the queue, nor on the waiting time). The flow of requests arriving at the QS has an intensity λ, and the servicing flow has an intensity μ. It is necessary to find the limiting probabilities of states and performance indicators of the QS.
The system can be in one of the states S 0 , S 1 , S 2 , …, S k , according to the number of requests in the QS: S 0 - channel is free; S 1 - channel is busy (serving a request), there is no queue, S 2 - channel is busy, one request is in the queue; ... S k - channel is busy, (k-1) applications are in queue, etc.
The state graph of the QS is shown in Fig. 8.
Rice. 8
This is a process of death and reproduction, but with an infinite number of states, in which the intensity of the flow of applications is equal to λ, and the intensity of the flow of services is μ.
Before writing down the formulas for limiting probabilities, you need to be sure of their existence, because in the case when time t→∞, the queue can increase without limit. Proved that Ifρ<1, those. the average number of incoming applications is less than the average number of serviced applications (per unit time), then limiting probabilities exist. Ifρ≥1, the queue grows indefinitely.
To determine the limiting probabilities of states, we will use formulas (16), (17) for the process of death and reproduction (here we admit a certain lack of rigor, since these formulas were previously obtained for the case of a finite number of states of the system). We get(32)
Since limiting probabilities exist only for ρ< 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
p 0 =1-ρ, (33)
and taking into account relations (17)
p 1 =ρ·p 0 ; p 2 =ρ 2 ·p 0 ; ... ; p k =ρ k ·p 0 ; ...
let's find the limiting probabilities of other states
p 1 =ρ·(1-ρ); p 2 =ρ 2 ·(1-ρ); ... ; p k =ρ k ·(1-ρ); ... (34)
The limiting probabilities p 0 , p 1 , p 2 , …, p k , … form a decreasing geometric profession with denominator p< 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Average number of applications in the system L system. we will determine using the mathematical expectation formula, which, taking into account (34), will take the form 
(35)
(summation from 1 to ∞, since the zero term is 0·p 0 =0).
It can be shown that formula (35) transforms (at ρ< 1) к виду
(36)
Let's find the average number of applications in the queue L very. It's obvious that
L och =L syst -L rev (37)
where L vol. - the average number of applications being serviced.
The average number of requests under service is determined by the formula for the mathematical expectation of the number of requests under service, taking the value 0 (if the channel is free) or 1 (if the channel is busy):
L och =0 p 0 +1 (1-p 0)
those. the average number of requests under service is equal to the probability that the channel is busy:
L och =P zan =1-p 0 , (38)
In force (33)
L och =P zan ρ, (39)
Now according to formula (37) taking into account (36) and (39)
(40)
Proved that for any nature of the flow of applications, for any distribution of service time, for any service discipline, the average time a request stays in the system (queue) is equal to the average number of applications in the system (in the queue) divided by the intensity of the flow of applications, those. 
(41)
(42)
Formulas (41) and (42) are called Little's formulas. They stem from the fact that in the limiting, stationary mode, the average number of applications arriving in the system is equal to the average number of applications leaving it: both flows of requests have the same intensity λ.
Based on formulas (41) and (42), taking into account (36) and (40), the average time an application stays in the system will be determined by the formula: 
(43)
and the average time an application stays in queue
(44)
Single-channel QS with waiting without limitation on the capacity of the waiting block
The stationary operating mode of this QS exists at t→∞ for any n=0,1,2,... and when l< m.Система алгебраических уравнений, описывающих работу СМО при t®¥ для любого n = 0, 1, 2...., имеет видThe solution to this system of equations has the form
P n =(1-ρ)·ρ n , n=0,1,2,... (3.21)
where ρ=λ/μ< 1
The characteristics of a single-channel QS with waiting, without restrictions on the queue length, are as follows:
average number of clients (requests) for service in the system:
average duration of a client's stay in the system:
Example 3.3. Let us recall the situation considered in example 3.2, where we are talking about the functioning of a diagnostic post. Let the diagnostic post in question have an unlimited number of parking areas for vehicles arriving for service, i.e., the length of the queue is unlimited.
It is required to determine the final values of the following probabilistic characteristics:
- probabilities of system states (diagnostic station);
- the average number of cars in the system (under service and in queue);
- the average duration of a vehicle’s stay in the system (for service and in queue);
- average number of cars in queue for service;
- the average length of time a car stays in line.
Solution
1. The service flow parameter m and the reduced intensity of vehicle flow p are defined in example 3.2:
m = 0.952; p = 0.893.
2. Calculate the limiting probabilities of the system using the formulas
P 0 =1-ρ = 1-0.893 = 0.107
P 1 =(1-ρ) ρ = (1-0.893) 0.893 = 0.096
P 2 =(1-ρ) ρ 2 = (1-0.893) 2 0.893 = 0.085
P 3 =(1-ρ) ρ 3 = (1-0.893) 3 0.893 = 0.076
P 4 =(1-ρ) ρ 4 = (1-0.893) 4 0.893 = 0.068
P 5 =(1-ρ) ρ 5 = (1-0.893) 5 0.893 = 0.061
etc.
It should be noted that P o determines the proportion of time during which the diagnostic post is forced to be inactive (idle). In our example it is 10.7%, since R o= 0,107.
3. Average number of cars in the system (under service and in queue):
4. Average duration of a client’s stay in the system:
6. Average duration of a car’s stay in the queue -
7. Relative system throughput:
i.e., every application that comes into the system will be serviced.
8. Absolute throughput: A= l q= 0.85 1 = 0.85
It should be noted that a company that performs car diagnostics is primarily interested in the number of customers who will visit the diagnostic post when the restriction on the length of the queue is lifted.
Let's say that in the original version the number of parking spaces for arriving cars was equal to three (see example 3.2). Frequency m of situations when a car arriving at a diagnostic post is not able to join the queue:
T= l P N
In our example, with N = 3 + 1 = 4 and p = 0.893,
m = l P o p 4 = 0.85·0.248·0.8934·0.134 cars per hour.
With a 12-hour operating mode of the diagnostic station, this is equivalent to the fact that the diagnostic station, on average, will lose 12·0.134 = 1.6 cars per shift (day).
Removing the restriction on the length of the queue allows us to increase the number of clients served in our example by an average of 1.6 cars per shift (12 hours of work) at the diagnostic station. It is clear that the decision to expand the parking area for vehicles arriving at the diagnostic station must be based on an assessment of the economic damage caused by the loss of customers when there are only three parking spaces for these vehicles.
Multichannel QS with unlimited queue
Let's consider the problem. There is an n-channel QS with an unlimited queue. The flow of requests arriving at the QS has an intensity λ, and the servicing flow has an intensity μ. It is necessary to find the limiting probabilities of the QS states and indicators of its effectiveness.The system can be in one of the states S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - numbered according to the number of applications in the QS: S 0 - there are no applications in the system (all channels are free) ; S 1 - one channel is occupied, the rest are free; S 2 - two channels are busy, the rest are free;..., S k - k channels are busy, the rest are free;..., S n - all n channels are busy (no queue); S n+1 - all n channels are busy, there is one request in the queue;..., S n+r - all are busy n channels, r applications are in line...
The system state graph is shown in Fig. 9. Let us note that, unlike the previous QS, the intensity of the service flow (transferring the system from one state to another from right to left) does not remain constant, and as the number of requests in the QS increases from 0 to n, it increases from m to nm , since the number of service channels increases accordingly. When the number of requests in the QS is greater than n, the intensity of the service flow remains equal to nm.
average number of applications in queue 
, (50)
average number of applications in the system
L syst =L och +ρ, (51)
The average time an application stays in the queue and the average time an application stays in the system, as before, are found using Little’s formulas (42) and (41).
Comment. For a QS with an unlimited queue at r< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q=1, and the absolute throughput is equal to the intensity of the incoming flow of requests, i.e. A=l.
QS with limited queue
QS with limited queue. Ques with a limited queue differ from the problems considered above only in that the number of applications in the queue is limited (cannot exceed a certain specified T). If a new request arrives at a time when all places in the queue are occupied, it leaves the QS unserved, i.e. gets rejected.Obviously: to calculate the limiting probabilities of states and efficiency indicators of such QSs, the same approach as above can be used, with the difference that it is necessary to summarize not an infinite progression (as, for example, we did when deriving formula (33)), but a finite one .
The average time an application stays in the queue and in the system, as before, is determined by Little’s formulas (44) and (43).
QS with limited waiting time. In practice, QMSs with so-called “impatient” requests are often encountered. Such applications may leave the queue if the waiting time exceeds a certain value. In particular, such requests arise in various technological systems, in which a delay in the start of service can lead to loss of product quality, in operational management systems, when urgent messages lose value (or even meaning) if they are not received for service within a certain time.
In the simplest mathematical models of such systems, it is assumed that a request can remain in the queue for a random time, distributed according to an exponential law with a certain parameter υ, i.e. we can conditionally assume that each request standing in the queue for service can leave the system with intensity υ.
The corresponding time-limited QS performance indicators are obtained based on the results obtained for the death and reproduction process.
In conclusion, we note that in practice there are often closed service systems in which the incoming flow of applications significantly depends on the state of the QS itself. As an example, we can cite the situation when some machines arrive at the repair depot from the places of operation: it is clear that the more machines are in a state of repair, the fewer of them continue to be used and the less intense the flow of machines newly arriving for repair. A closed QS is characterized by a limited number of request sources, and each source is “blocked” while its request is being served (i.e., it does not issue new requests). In such systems, with a finite number of QS states, limiting probabilities will exist for any values of the intensity of application flows and servicing. They can be calculated by revisiting the process of death and reproduction.
Let's consider the simplest QS with waiting - a single-channel system that receives a flow of requests with intensity; service intensity (i.e., on average, a continuously busy channel will issue serviced requests per unit (of time). A request arriving at a time when the channel is busy is queued and awaits service.
System with limited queue length. Let us first assume that the number of places in the queue is limited by the number , i.e. if an application arrives at a time when there are already applications in the queue, it leaves the system unserved. In the future, rushing to infinity, we will obtain the characteristics of a single-channel QS without restrictions on the queue length.
We will number the states of the QS according to the number of applications in the system (both being serviced and awaiting service):
The channel is free;
The channel is busy, there is no queue;
The channel is busy, one application is in queue;
The channel is busy, applications are in queue;
The channel is busy, tons of applications are in queue.
The GSP is shown in Fig. 5.8. All intensities of event flows moving into the system along arrows from left to right are equal to , and from right to left - . Indeed, the flow of requests moves the system along the arrows from left to right (as soon as a request arrives, the system goes to the next state), while from right to left there is a flow of “releases” of a busy channel, which has an intensity (as soon as the next request is serviced, the channel will either become free or decrease number of applications in queue).
Rice. 5.8. Single-channel QS with waiting
Shown in Fig. 5.8 diagram is a diagram of reproduction and death. Using the general solution (5.32)-(5.34), we write expressions for the limiting probabilities of states (see also (5.40)):
or using:
The last line in (5.45) contains a geometric progression with the first term 1 and the denominator p; where we get:
in connection with which the limiting probabilities take the form:
Expression (5.46) is valid only for (for it gives uncertainty of the form ). The sum of a geometric progression with a denominator is equal to , and in this case
Let us determine the characteristics of the QS: probability of failure, relative throughput, absolute throughput, average queue length, average number of applications associated with the system, average waiting time in the queue, average time spent in the QS
Probability of failure. Obviously, the application is rejected only if the channel is busy and all t places in the queue are also busy:
Relative Bandwidth:
Absolute throughput:
Average queue length. Let's find the average number of applications in the queue as the mathematical expectation of a discrete random variable - the number of applications in the queue:
With probability there is one application in the queue, with probability there are two applications, in general with probability there are applications in the queue, etc., from where:
Since , the sum in (5.50) can be interpreted as a derivative with respect to the sum of a geometric progression:
Substituting this expression into (5.50) and using from (5.47), we finally obtain:
The average number of applications in the system. Next, we obtain a formula for the average number of applications associated with the system (both those standing in the queue and those being serviced). Since , where is the average number of applications under service, is known, it remains to determine . Since there is only one channel, the number of serviced requests can be equal to (with probability ) or 1 (with probability ), from which:
and the average number of applications associated with the QS is
Average waiting time for an application in the queue. Let's denote it ; if a request comes into the system at some point in time, then with probability the service channel will not be busy, and it will not have to wait in line (the waiting time is zero). Most likely, she will come into the system while some request is being served, but there will be no queue in front of her, and the request will wait for the start of its servicing for a period of time (the average time of servicing one request). There is a probability that there will be another application in the queue before the application being considered, and the average waiting time will be equal to , etc.
If, i.e., when a newly arriving request finds the service channel busy and applications in the queue (probability of this), then in this case the request does not get into the queue (and is not served), so the waiting time is zero. The average waiting time will be:
if we substitute expressions for probabilities (5.47) here, we get:
Here we use relations (5.50), (5.51) (derivative of a geometric progression), as well as from (5.47). Comparing this expression with (5.51), we note that in other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the application flow.
Average time an application stays in the system. Let us denote the mathematical expectation of a random variable - the time a request stays in the QS, which is the sum of the average waiting time in the queue and the average service time. If the system load is 100%, obviously, otherwise
Example 5.6. A gas station (gas station) is a service station with one service channel (one column).
The area at the station allows no more than three cars to be in line for refueling at the same time. If there are already three cars in the queue, the next car arriving at the station does not join the queue. The flow of cars arriving for refueling has an intensity (car per minute). The refueling process lasts an average of 1.25 minutes.
Define:
probability of failure;
relative and absolute capacity of gas stations;
average number of cars waiting to refuel;
average number of cars at a gas station (including those being serviced);
average waiting time for a car in line;
average time a car spends at a gas station (including service).
in other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the application flow.
We first find the reduced intensity of the flow of applications:
According to formulas (5.47):
Probability of failure.
Relative capacity of QS
Absolute throughput of QS
Cars per min.
We find the average number of cars in the queue using formula (5.51)
i.e., the average number of cars waiting in line to refuel is 1.56.
Adding to this value the average number of vehicles under service
we get the average number of cars associated with a gas station.
Average waiting time for a car in queue according to formula (5.54)
Adding to this value, we get the average time that a car spends at a gas station:
Unlimited Waiting Systems. In such systems, the value of m is not limited and, therefore, the main characteristics can be obtained by passing to the limit in the previously obtained expressions (5.44), (5.45), etc.
Note that the denominator in the last formula (5.45) is the sum of an infinite number of terms of a geometric progression. This sum converges when the progression is infinitely decreasing, i.e. when .
It can be proven that there is a condition under which a limiting steady-state mode exists in a QS with waiting, otherwise such a mode does not exist, and the queue at will increase without limit. Therefore, in what follows it is assumed that .
If , then relations (5.47) take the form:
In the absence of restrictions on the length of the queue, each application that comes into the system will be serviced, therefore,
We obtain the average number of applications in the queue from (5.51) at:
The average number of applications in the system according to formula (5.52) with
We obtain the average waiting time from the formula
(5.53) at:
Finally, the average time an application stays in the QS is
Multi-channel QS with waiting
System with limited queue length. Let's consider a channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel); number of places in the queue.
System states are numbered according to the number of requests associated with the system:
no queue:
All channels are free;
One channel is occupied, the rest are free;
The channels are busy, the rest are not;
All channels are occupied, there are no free channels;
there is a queue:
All n channels are busy; one application is in the queue;
All n channels are busy, r applications are in the queue;
All n channels are busy, r applications are in the queue.
GSP is shown in Fig. 5.9. Each arrow is marked with the corresponding intensities of event flows. Along the arrows from left to right, the system is always transferred by the same flow of requests with an intensity of
Rice. 5.9. Multi-channel QS with waiting
The graph is typical for the processes of reproduction and death, for which the solution was previously obtained (5.29)-(5.33). Let's write expressions for the limiting probabilities of states using the notation: (here we use the expression for the sum of a geometric progression with a denominator).
Thus, all state probabilities have been found.
Let us determine the performance characteristics of the system.
Probability of failure. An received application is rejected if all channels and all places in the queue are occupied:
The relative throughput complements the probability of failure to one:
Absolute throughput of QS:
Average number of busy channels. For QS with refusals, it coincided with the average number of applications in the system. For a QS with a queue, the average number of busy channels does not coincide with the average number of applications in the system: the latter value differs from the first by the average number of applications in the queue.
Let us denote the average number of occupied channels by . Each busy channel serves an average of requests per unit of time, and the QS as a whole serves an average of requests per unit of time. Dividing one by the other, we get:
The average number of requests in a queue can be calculated directly as the mathematical expectation of a discrete random variable:
Here again (the expression in brackets) the derivative of the sum of the geometric progression occurs (see above (5.50), (5.51)-(5.53)), using the relation for it, we obtain:
Average number of applications in the system:
Average waiting time for an application in the queue. Let's consider a number of situations that differ in the state in which a newly arrived request will find the system and how long it will have to wait for service.
If a request does not find all channels busy, it will not have to wait at all (the corresponding terms in the mathematical expectation are equal to zero). If a request arrives at a time when all channels are busy and there is no queue, it will have to wait on average a time equal to (because the “flow of releases” of channels has an intensity of ). If an application finds all channels busy and one application in front of it in the queue, it will have to wait on average for an amount of time (for each application in front), etc. If an application finds itself in a queue of applications, it will have to wait on average for a period of time . If a newly arrived application finds already applications in the queue, then it will not wait at all (but will not be serviced). We find the average waiting time by multiplying each of these values by the corresponding probabilities:
Just as in the case of a single-channel QS with waiting, we note that this expression differs from the expression for the average queue length (5.59) only by the factor , i.e.
The average residence time of a request in the system, as well as for a single-channel QS, differs from the average waiting time by the average service time multiplied by the relative throughput:
Systems with unlimited queue length. We considered a channel QS with waiting, when no more than requests can be in the queue at the same time.
Just as before, when analyzing systems without restrictions, it is necessary to consider the obtained relations for .
We obtain the probabilities of states from formulas (5.56) by passing to the limit (at ). Note that the sum of the corresponding geometric progression converges at and diverges at . Assuming that and directing the value of m to infinity in formulas (5.56), we obtain expressions for the limiting probabilities of states:
Probability of failure, relative and absolute throughput. Since each request will sooner or later be serviced, the characteristics of the QS throughput will be:
We obtain the average number of applications in the queue at from (5.59):
and the average waiting time is from (5.60):
The average number of occupied channels, as before, is determined through the absolute throughput:
The average number of applications associated with the QS is defined as the average number of applications in the queue plus the average number of applications under service (average number of busy channels):
Example 5.7. A gas station with two pumps () serves a flow of cars with intensity (cars per minute). Average service time per machine
There is no other gas station in the area, so the line of cars in front of the gas station can grow almost unlimitedly. Find the characteristics of the QS.
Since , the queue does not grow indefinitely and it makes sense to talk about the limiting stationary mode of operation of the QS. Using formulas (5.61) we find the probabilities of states:
We will find the average number of occupied channels by dividing the absolute throughput of the QS by the service intensity:
The probability of no queue at a gas station will be:
Average number of cars in queue:
Average number of cars at gas stations:
Average waiting time in queue:
Average time a car spends at a gas station:
QS with limited waiting time. Previously, we considered systems with waiting limited only by the length of the queue (the number of applications simultaneously in the queue). In such a QS, an application, once placed in a queue, does not leave it until it waits for service. In practice, there are other types of QS in which an application, after waiting for some time, can leave the queue (so-called “impatient” applications).
Let's consider a QS of this type, assuming that the waiting time constraint is a random variable.
Let us assume that there is a channel QS with waiting, in which the number of places in the queue is not limited, but the time an application stays in the queue is some random variable with the average value , thus, for each application standing in the queue, a kind of Poisson “flow of departures” acts » with the intensity of applications, they stand in line, etc.
The graph of states and transitions of the system is shown in Fig. 5.10.
Rice. 5.10. QS with limited waiting time
Let's mark this graph as before; all arrows leading from left to right will indicate the intensity of the flow of applications. For states without a queue, the arrows leading from them from right to left will, as before, indicate the total intensity of the flow servicing all occupied channels. As for states with a queue, the arrows leading from them from right to left will indicate the total intensity of the service flow of all channels plus the corresponding intensity of the flow of departures from the queue. If there are applications in the queue, then the total intensity of the flow of departures will be equal to .
As can be seen from the graph, there is a pattern of reproduction and death; Using general expressions for the limiting probabilities of states in this scheme (using abbreviated notation), we write:
Let us note some features of a QS with limited waiting compared to the previously considered QS with “patient” requests.
If the length of the queue is not limited and the requests are “patient” (do not leave the queue), then the stationary limit regime exists only in the case (at , the corresponding infinite geometric progression diverges, which physically corresponds to unlimited growth of the queue at ).
On the contrary, in a QS with “impatient” customers leaving the queue sooner or later, the established service mode at is always achieved, regardless of the reduced intensity of the customer flow, without summing the infinite series (5.63). From (5.64) we obtain:
and the average number of occupied channels included in this formula can be found as the mathematical expectation of a random variable that takes values with probabilities:
In conclusion, we note that if in formulas (5.62) we go to the limit at (or, what is the same, at ), then at we obtain formulas (5.61), i.e., “impatient” applications will become “patient”.
Multichannel QS with unlimited queue
Let's consider the problem. Available n-channel QS with unlimited queue. The flow of requests entering the QS has intensity l, and the flow of services has intensity m. It is necessary to find the limiting probabilities of the states of the QS and indicators of its effectiveness.
The system can be in one of the states S0, S1, S2, ..., Sk .., Sn, ..., numbered according to the number of requests in the QS: S0 -- there are no requests in the system (all channels are free); S -- one channel is occupied, the rest are free; S2-- two channels are occupied, the rest are free; Sk -- k channels are occupied, the rest are free; Sn -- all n channels are busy (no queue); Sn+1 -- all n channels are busy, there is one request in the queue; Sn+r -- all n channels are busy, r applications are in queue.
The system state graph is shown in Figure 7. Let us note that, unlike the previous QS, the intensity of the service flow (transferring the system from one state to another from right to left) does not remain constant, but as the number of requests in the QS increases from 0 to n increases from m to n??, since the number of service channels increases accordingly. When the number of requests in the QS is greater than n, the intensity of the service flow remains equal to nm.
Figure 7 - State graph of a multi-channel QS
It can be shown that for c/n< 1 предельные вероятности существуют. Если с/n ? 1, очередь растет до бесконечности. Используя формулы (20) и (21) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью
The probability that an application will be in the queue is
For an n-channel QS with an unlimited queue, using previous techniques, one can find:
average number of busy channels
average number of applications in the system
The average time an application stays in the queue and the average time an application stays in the system, as before, are found using Little’s formulas (48) and (49).
Comment. For a QS with an unlimited queue with< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа Ротк = 0, Q=1, а равна интенсивности входящего потока заявок, т.е. А = л.
QS with limited queue
Ques with a limited queue differ only in that the number of applications in the queue is limited (cannot exceed a certain specified m). If a new request arrives at a time when all places in the queue are occupied, it leaves the QS unserved, i.e. gets rejected.
Single-channel QS with limited queue length
Limit probabilities:
Probability of failure:
Absolute throughput
Relative Bandwidth
Average number of applications in queue
Average number of requests under service (average number of busy channels)
Average number of applications in the system
Multichannel QS with limited queue
Limit probabilities:
Probability of failure:
Absolute throughput
Relative Bandwidth
Average number of applications in queue
Average number of requests under service (average number of busy channels)
