Examples of solving problems of queuing systems. Smo with definitions and formulas failures
Examples of solving problems of queuing systems
You need to solve problems 1–3. The initial data are given in table. 2–4.
Some notations used in queuing theory for formulas:
n – number of channels in the QS;
λ – intensity of the incoming flow of requests P in;
v – intensity of the outgoing flow of requests P out;
μ – intensity of service flow P ob;
ρ – system load indicator (traffic);
m – the maximum number of places in the queue, limiting the length of the queue of applications;
i – number of application sources;
p k – probability of the kth state of the system;
p o - the probability of downtime of the entire system, i.e. the probability that all channels are free;
p syst – probability of acceptance of an application into the system;
p reject – probability of refusal of an application to be accepted into the system;
p ob – the probability that the application will be serviced;
A is the absolute capacity of the system;
Q – relative system capacity;
Och – average number of applications in the queue;
About – average number of requests under service;
Syst – average number of applications in the system;
Och – average waiting time for an application in the queue;
Tb - average time of service of the request, related only to the serviced requests;
Sys is the average time an application stays in the system;
Ож – average time limiting waiting for an application in the queue;
– average number of occupied channels.
The absolute throughput of QS A is the average number of applications that the system can serve per unit of time.
Relative QS throughput Q is the ratio of the average number of requests served by the system per unit of time to the average number of requests received during this time.
When solving queuing problems, it is necessary to adhere to the following sequence:
1) determination of the type of QS according to table. 4.1;
2) selection of formulas in accordance with the type of QS;
3) problem solving;
4) formulating conclusions on the problem.
1. Scheme of death and reproduction. We know that, given a labeled state graph, we can easily write Kolmogorov equations for state probabilities, and also write and solve algebraic equations for final probabilities. For some cases the last equations are possible
decide in advance, in letter form. In particular, this can be done if the state graph of the system is the so-called "death and reproduction scheme".
The state graph for the death and reproduction scheme has the form shown in Fig. 19.1. The peculiarity of this graph is that all states of the system can be drawn into one chain, in which each of the average states ( S 1 , S 2 ,…,S n-1) is connected by a forward and backward arrow with each of the neighboring states - right and left, and the extreme states (S 0 , S n) - with only one neighboring state. The term "scheme of death and reproduction" originates from biological problems, where a change in the size of a population is described by such a scheme.
The scheme of death and reproduction is very often found in various practical problems, in particular in queuing theory, so it is useful, once and for all, to find the final probabilities of states for it.
Let us assume that all event flows that transfer the system along the arrows of the graph are the simplest (for brevity, we will also call the system S and the process occurring in it are the simplest).
Using the graph in Fig. 19.1, we will compose and solve algebraic equations for the final probabilities of the state), existence follows from the fact that from each state one can go to each other, in a finite number of states). For the first state S 0 we have:
(19.1)
For the second state S1:
By virtue of (19.1), the last equality is reduced to the form
Where k accepts all values from 0 to P. So, the final probabilities p 0 , p 1 ,..., p n satisfy the equations
(19.2)
in addition, it is necessary to take into account the normalization condition
p 0 + p 1 + p 2 +…+ p n =1. (19.3)
Let's solve this system of equations. From the first equation (19.2) we express p 1 through R 0 :
p 1 = p 0. (19.4)
From the second, taking into account (19.4), we obtain:
(19.5)
From the third, taking into account (19.5),
(19.6)
and in general, for anyone k(from 1 to n):
(19.7)
Let us pay attention to formula (19.7). The numerator is the product of all intensities standing at the arrows leading from left to right (from the beginning to the given state S k), and in the denominator - the product of all intensities standing at the arrows leading from right to left (from the beginning to S k).
Thus, all state probabilities R 0 , p 1 , ..., р n expressed through one of them ( R 0). Let us substitute these expressions into the normalization condition (19.3). We get, taking it out of brackets R 0:
from here we get the expression for R 0 :
(we raised the bracket to the power -1 so as not to write two-story fractions). All other probabilities are expressed through R 0 (see formulas (19.4) - (19.7)). Note that the coefficients for R 0 in each of them are nothing more than successive terms of the series after one in formula (19.8). So, calculating R 0 , we have already found all these coefficients.
The resulting formulas are very useful in solving the simplest problems of queuing theory.
^2. Little's formula. Now we will derive one important formula relating (for the limiting, stationary mode) the average number of applications L systems located in the queuing system (i.e., being served or standing in a queue), and the average time a request stays in the system W syst.
Let's consider any QS (single-channel, multi-channel, Markov, non-Markov, with an unlimited or limited queue) and two flows of events associated with it: the flow of requests arriving at the QS, and the flow of requests leaving the QS. If a limiting, stationary mode has been established in the system, then the average number of applications arriving at the QS per unit time is equal to the average number of applications leaving it: both flows have the same intensity λ.
Let's denote: X(t) - the number of applications that arrived at the QS until the moment t. Y(t) - number of applications that left the CMO
until the moment t. Both functions are random and change abruptly (increase by one) when orders arrive (X(t)) and withdrawals of applications (Y(t)). Type of functions X(t) and Y(t) shown in Fig. 19.2; both lines are stepped, the top one is X(t), lower- Y(t). Obviously, for any moment t their difference Z(t)= X(t) - Y(t) is nothing more than the number of applications in the CMO. When the lines X(t) And Y(t) merge, there are no requests in the system.
Consider a very long period of time T(mentally continuing the graph far beyond the drawing) and calculate for it the average number of applications in the QS. It will be equal to the integral of the function Z(t) on this interval divided by the length of the interval T:
L syst. = . (19.9) o
But this integral is nothing more than the area of the figure shaded in Fig. 19.2. Let's take a good look at this drawing. The figure consists of rectangles, each of which has a height equal to one and a base equal to the time the corresponding request (first, second, etc.) spent in the system. Let's designate these times t 1, t 2,... True, at the end of the interval T some rectangles will enter the shaded figure not completely, but partially, but with a sufficiently large T these little things won't matter. Thus, we can assume that
(19.10)
where the amount applies to all applications received during the time T.
Divide the right and left sides (.19.10) by the length of the interval T. We obtain, taking into account (19.9),
L syst. = . (19.11)
Divide and multiply the right side of (19.11) by the intensity X:
L syst. = .
But the magnitude Tλ is nothing more than the average number of applications received over time ^ T. If we divide the sum of all times t i by the average number of applications, we get the average time an application remains in the system W syst. So,
L syst. = λ W syst. ,
W syst. = . (19.12)
This is Little’s wonderful formula: for any QS, for any nature of the flow of requests, for any distribution of service time, for any service discipline the average time an application stays in the system is equal to the average number of applications in the system divided by the intensity of the application flow.
In exactly the same way, Little’s second formula is derived, relating the average time an application stays in the queue ^W very good and the average number of applications in the queue L Pts:
W och = . (19.13)
For output it is enough instead of the bottom line in Fig. 19.2 take function U(t)- the number of applications left before t not from the system, but from the queue (if an application that comes into the system does not get into the queue, but immediately goes into service, we can still assume that it gets into the queue, but spends zero time in it).
Little's formulas (19.12) and (19.13) play a large role in the theory of queuing. Unfortunately, in most existing manuals these formulas (proven in general form relatively recently) are not given 1).
§ 20. The simplest queuing systems and their characteristics
In this section, we will consider some of the simplest QS and derive expressions for their characteristics (performance indicators). At the same time, we will demonstrate the main methodological techniques characteristic of the elementary, “Markov” theory of queuing. We will not pursue the number of QS samples for which the final expressions of characteristics will be derived; This book is not a reference book on the theory of queuing (this role is much better fulfilled by special manuals). Our goal is to introduce the reader to some "little tricks" to ease the way through the theory of queuing, which in a number of available (even claiming to be popular) books can seem like a rambling collection of examples.
All flows of events that transfer QS from state to state, in this section, we will consider the simplest (without stipulating this each time specifically). Among them will be the so-called "service flow". It means the flow of requests serviced by one continuously busy channel. In this stream, the interval between events, as always in the simplest stream, has an exponential distribution (many manuals say instead: "service time is exponential", we ourselves will use this term in the future).
1) In a popular book, a somewhat different, compared to the above, derivation of Little's formula is given. In general, acquaintance with this book (“Second Conversation”) is useful for an initial acquaintance with the theory of queuing.
In this section, the exponential distribution of service time will go without saying, as always for the “simplest” system.
We will introduce the performance characteristics of the QS under consideration as we proceed.
^ 1. P-channel queuing system with failures(Erlang problem). Here we will consider one of the first, “classical” problems of queuing theory;
this problem arose from the practical needs of telephony and was solved at the beginning of this century by the Danish mathematician Erlant. The problem is stated as follows: there is P channels (communication lines) that receive a flow of requests with intensity λ. The service flow has an intensity μ (the reciprocal of the average service time t about). Find the final probabilities of the QS states, as well as the characteristics of its effectiveness:
^A- absolute throughput, i.e. the average number of applications served per unit of time;
Q- relative throughput, i.e. the average share of incoming applications served by the system;
^ R otk- the probability of failure, i.e. the fact that the application will leave the QS unserved;
k- average number of busy channels.
Solution. System states ^S(SMO) will be numbered according to the number of requests in the system (in this case it coincides with the number of occupied channels):
S 0 - there is not a single application in the CMO,
S 1 - there is one request in the QS (one channel is busy, the rest are free),
S k - located in SMO k applications ( k channels are busy, the rest are free),
S n - located in SMO P applications (all n channels are busy).
The state graph of the SMO corresponds to the pattern of death during reproduction (Fig. 20.1). Let's mark this graph - mark the intensity of event flows next to the arrows. From S 0 in S 1 the system is transferred by a flow of requests with intensity λ (as soon as a request arrives, the system jumps from S 0 V S 1). The same flow of applications translates
The system from any left state to the neighboring right one (see the upper arrows in Fig. 20.1).
Let's put the intensities at the bottom arrows. Let the system be in the state ^S 1 (one channel works). It produces μ service per unit time. We put down at the arrow S 1 →S 0 intensity μ. Now imagine that the system is in a state S 2(two channels work). For her to go to S1, it is necessary that either the first channel or the second one finishes servicing; the total intensity of their service flows is 2μ; We put it next to the corresponding arrow. The total service flow provided by the three channels has an intensity of 3μ, k channels - kμ. We mark these intensities at the bottom arrows in Fig. 20.1.
And now, knowing all the intensities, we will use ready-made formulas (19.7), (19.8) for the final probabilities in the scheme of death and reproduction. Using formula (19.8) we obtain:
Expansion terms 
will be the coefficients for p 0 in expressions for p 1
Note that in formulas (20.1), (20.2) the intensities λ and μ are not included separately, but only in the form of the ratio λ/μ. Let's denote
λ/μ = ρ (20.3)
And we will call the value p “the reduced intensity of the flow of applications.” Its meaning is the average number of requests received during the average time of servicing one request. Using this notation, we rewrite formulas (20.1), (20.2) in the form:
Formulas (20.4), (20.5) for the final probabilities of states are called Erlang formulas - in honor of the founder of queuing theory. Most of the other formulas of this theory (today there are more of them than mushrooms in the forest) do not bear any special names.
Thus, the final probabilities have been found. Using them, we will calculate the performance characteristics of the QS. First we'll find ^ R otk. - the probability that an incoming application will be rejected (will not be serviced). For this it is necessary that everything P channels were busy, so
R otk = R n = . (20.6)
From here we find the relative throughput - the probability that the request will be served:
Q = 1 - P open = 1 - (20.7)
We obtain the absolute throughput by multiplying the intensity of the flow of requests λ by Q:
A = λQ = λ . (20.8)
It remains only to find the average number of busy channels k. This value could be found “directly”, as the mathematical expectation of a discrete random variable with possible values 0, 1, ..., P and the probabilities of these values р 0 р 1 , ..., р n:
k = 0 · p 0 + 1 · p 1 + 2 · p 2 + ... + p · pn.
Substituting expressions (20.5) here for R k, (k = 0, 1, ..., P) and carrying out the appropriate transformations, we would eventually obtain the correct formula for k. But we will derive it much more simply (here it is, one of the “little tricks”!) In fact, we know the absolute throughput A. This is nothing more than the intensity of the flow of applications served by the system. Each busy i.sal serves on average |l requests per unit of time. This means that the average number of occupied channels is
k = A/μ, (20.9)
or, given (20.8),
k = 
(20.10)
We recommend that the reader solve the example on his own. There is a communication station with three channels ( n= 3), intensity of the flow of applications λ = 1.5 (applications per minute); average time to service one request t rev = 2 (min.), all flows of events (as in this entire paragraph) are the simplest. Find the final probabilities of states and characteristics of the effectiveness of the QS: A, Q, P open, k. Just in case, here are the answers: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, p 3 = 9/26 ≈ 0,346,
A≈ 0,981, Q ≈ 0,654, P otk ≈ 0.346, k ≈ 1,96.
From the answers it is clear, by the way, that our QS is significantly overloaded: out of three channels, on average, about two are occupied, and of the incoming applications, about 35% remain unserved. We invite the reader, if he is curious and not lazy, to find out: how many channels will be required in order to satisfy at least 80% of incoming requests? And what proportion of channels will be idle?
There is already some hint of optimization. In fact, the maintenance of each channel per unit of time costs a certain amount. At the same time, each serviced application generates some income. Multiplying this income by the average number of applications A, serviced per unit of time, we will receive the average income from the CMO per unit of time. Naturally, with an increase in the number of channels, this income grows, but the costs associated with the maintenance of channels also grow. What will outweigh - an increase in income or expenses? It depends on the conditions of the operation, on the "application service fee" and on the cost of maintaining the channel. Knowing these values, you can find the optimal number of channels, the most cost-effective. We will not solve such a problem, leaving the same “non-lazy and curious reader” to come up with an example and solve it. In general, inventing problems develops more than solving those already set by someone.
^ 2. Single-channel QS with unlimited queue. In practice, one-channel QS with a queue is quite common (a doctor serving patients; a pay phone with one booth; a computer fulfilling user orders). In the theory of queuing, single-channel QSs with a queue also occupy a special place (most of the analytical formulas obtained so far for non-Markovian systems belong to such QSs). Therefore, we will pay special attention to single-channel QS with a queue.
Let there be 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). This QS receives a flow of requests with intensity λ ; the servicing flow has an intensity μ, inverse to the average request servicing time t about. It is required to find the final probabilities of the QS states, as well as characteristics of its effectiveness:
L syst. - average number of applications in the system,
W syst. - average residence time of the application in the system,
^ L och- the average number of applications in the queue,
W very good - the average time an application spends in the queue,
P zan - the probability that the channel is busy (the degree of loading of the channel).
As for the absolute throughput A and relative Q, then there is no need to calculate them:
due to the fact that the queue is unlimited, each application will be serviced sooner or later, therefore A = λ, for the same reason Q = 1.
Solution. As before, we will number the states of the system according to the number of applications in the QS:
S 0 - the channel is free,
S 1 - channel is busy (serving a request), there is no queue,
S 2 - channel is busy, one request is in queue,
S k - channel is busy, k- 1 applications are in queue,
Theoretically, the number of states is unlimited (infinite). The state graph has the form shown in Fig. 20.2. This is a scheme of death and reproduction, but with an infinite number of states. Along all arrows, the flow of requests with intensity λ moves the system from left to right, and from right to left - the flow of service with intensity μ.
First of all, let’s ask ourselves, are there final probabilities in this case? After all, the number of states of the system is infinite, and, in principle, when t → ∞ The queue can grow indefinitely! Yes, that’s how it is: the final probabilities for such a QS do not always exist, but only when the system is not overloaded. It can be proven that if ρ is strictly less than one (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t→ ∞ grows indefinitely. This fact seems especially “incomprehensible” when ρ = 1. It would seem that there are no impossible requirements imposed on the system: during the time of servicing one request, on average one request arrives, and everything should be in order, but in reality it is not so. When ρ = 1, the QS copes with the flow of requests only if this flow is regular, and the service time is also not random, equal to the interval between requests. In this “ideal” case, there will be no queue at all, the channel will be continuously busy and will regularly issue serviced requests. But as soon as the flow of applications or the flow of service becomes even a little random, the queue will grow indefinitely. In practice, this does not happen only because “an infinite number of applications in the queue” is an abstraction. These are the gross errors that can result from replacing random variables with their mathematical expectations!
But let's return to our single-channel QS with an unlimited queue. Strictly speaking, we derived the formulas for the final probabilities in the scheme of death and reproduction only for the case of a finite number of states, but let us take the liberty of using them for an infinite number of states. Let's calculate the final probabilities of states using formulas (19.8), (19.7). In our case, the number of terms in formula (19.8) will be infinite. We get an expression for p 0:
p 0 = -1 =
\u003d (1 + p + p 2 + ... + p k + ... .) -1. (20.11)
The series in formula (20.11) is a geometric progression. We know that for ρ< 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний p 0 , p 1 , ..., p k , ... exist only for r<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем
1 + ρ + ρ 2 + ... + ρ k + ... = ,
p 0 = 1 - ρ. (20.12)
Probabilities p 1 , p 2 , ..., p k ,... will be found using the formulas:
p 1 = ρ p 0 , p 2= ρ 2 p 0 ,…,p k = ρ p 0, ...,
From where, taking into account (20.12), we finally find:
p 1= ρ (1 - ρ), p2= ρ 2 (1 - ρ), . . . , p k =ρ k(1 - ρ), . . .(20.13)
As you can see, the probabilities p 0, p 1, ..., pk,... form a geometric progression with denominator p. Oddly enough, the maximum of them p 0 - the probability that the channel will be completely free. No matter how loaded a system with a queue is, if it can cope with the flow of requests at all (ρ<1), самое вероятное число заявок в системе будет 0.
Let's find the average number of applications to the CMO ^ L syst. . Here you will have to tinker a little. Random value Z- number of applications in the system - has possible values 0, 1, 2, .... k, ... with probabilities p 0, p 1, p 2, ..., p k, ... Its mathematical expectation is
L syst = 0 · p 0 + 1 · p 1+2 p 2 +…+k · p k +…= (20.14)
(the sum is taken not from 0 to ∞, but from 1 to ∞, since the zero term is equal to zero).
Let us substitute into formula (20.14) the expression for p k (20.13):
L syst. = 
Now let’s take ρ (1-ρ) out of the sum sign:
L syst. = ρ (1-ρ)
Here we will again use a “little trick”: kρ k-1 is nothing more than the derivative with respect to ρ from the expression ρ k; Means,
L syst. = ρ (1-ρ)
Reversing the operations of differentiation and summation, we obtain:
L syst. = ρ (1-ρ) (20.15)
But the sum in formula (20.15) is nothing more than the sum of an infinitely decreasing geometric progression with the first term ρ and the denominator ρ; this amount
is equal to , and its derivative . Substituting this expression into (20.15), we obtain:
L syst = . (20.16)
Well, now we apply Little’s formula (19.12) and find the average time an application stays in the system:
W syst = (20.17)
Let's find the average number of applications in the queue L very good We will reason like this: the number of applications in the queue is equal to the number of applications in the system minus the number of applications under service. This means (according to the rule of adding mathematical expectations), the average number of applications in the queue L och is equal to the average number of requests in the system L syst minus the average number of requests under service. The number of requests under service can be either zero (if the channel is free) or one (if it is busy). The mathematical expectation of such a random variable is equal to the probability that the channel is busy (we denoted it R zan). Obviously, R zan equals one minus probability p 0 that the channel is free:
R zan = 1 - R 0 = ρ. (20.18)
Therefore, the average number of requests under service is
^L about= ρ, (20.19)
L och = L syst – ρ =
and finally
L och = (20.20)
Using Little's formula (19.13), we find the average time an application stays in the queue:
(20.21)
Thus, all characteristics of the effectiveness of the QS have been found.
We invite the reader to solve an example on his own: a single-channel QS is a railway marshalling station, which receives the simplest flow of trains with an intensity of λ = 2 (trains per hour). Service (disbandment)
composition lasts a random (indicative) time with an average value t rev = 20(min.). The station's arrival park has two tracks on which arriving trains can wait for service; if both tracks are busy, trains are forced to wait on the outer tracks. It is required to find (for the limiting, stationary operating mode of the station): average, number of trains l systems associated with the station, average time W system of train presence at the station (on internal tracks, on external tracks and under maintenance), average number L Pt of trains waiting in line to be disbanded (no matter on which tracks), average time W Pts stay of the train in line. Also, try to find the average number of trains waiting to disband on the outer tracks L external and average time of this waiting W ext (the last two quantities are related by Little’s formula). Finally, find the total daily fine Sh that the station will have to pay for train downtime on external tracks, if the station pays a fine a (rubles) for one hour of downtime of one train. Just in case, here are the answers: L syst. = 2 (composition), W syst. = 1 (hour), L points = 4/3 (composition), W och = 2/3 (hours), L external = 16/27 (composition), W external = 8/27 ≈ 0.297 (hours). The average daily fine Ш for waiting for trains on external tracks is obtained by multiplying the average number of trains arriving at the station per day, the average waiting time for trains on external tracks and the hourly fine A: W ≈ 14.2 A.
^ 3. re-channel QS with unlimited queue. Quite similar to problem 2, but a little more complicated, the problem of n-channel QS with unlimited queue. The numbering of states is again based on the number of applications in the system:
S 0- there are no requests in the SMO (all channels are free),
S 1 - one channel is occupied, the rest are free,
S 2 - two channels are occupied, the rest are free,
S k- busy k channels, the rest are free,
S n- everyone is busy P channels (no queue),
S n+1- everyone is busy n channels, one application is in queue,
S n+r - busy weight P channels, r applications are in queue,
The state graph is shown in Fig. 20.3. We invite the reader to think for himself and justify the values of the intensities indicated by the arrows. Graph Fig. 20.3
λ λ λ λ λ λ λ λ λ
μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ
there is a pattern of death and reproduction, but with an infinite number of states. Let us report without proof the natural condition for the existence of final probabilities: ρ/ n<1. Если ρ/n≥ 1, the queue grows to infinity.
Let us assume that the condition ρ/ n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для p 0 there will be a series of terms containing factorials, plus the sum of an infinitely decreasing geometric progression with the denominator ρ/ n. Summing it up, we find
(20.22)
Now let’s find the performance characteristics of the QS. The easiest way to find the average number of occupied channels is k== λ/μ, = ρ (this is generally true for any QS with an unlimited queue). Let's find the average number of applications in the system L system and average number of applications in queue L very good Of these, it is easier to calculate the second, using the formula
L och =
performing the appropriate transformations according to the example of task 2
(with differentiation of the series), we get:
L och = 
(20.23)
Adding to it the average number of requests under service (it is also the average number of occupied channels) k =ρ, we get:
L syst = L och + ρ. (20.24)
Dividing expressions for L och and L syst on λ , Using Little’s formula, we obtain the average time an application stays in the queue and in the system:
(20.25)
Now let's solve an interesting example. A railway ticket office with two windows is a two-channel QS with an unlimited queue located at two windows at once (if one window becomes vacant, the passenger closest in line takes it). The box office sells tickets to two points: A and IN. Intensity of the flow of applications (passengers wanting to buy a ticket) for both points A and B is the same: λ A = λ B = 0.45 (passengers per minute), and in total they form a total flow of requests with intensity λ A + λB = 0.9. A cashier spends an average of two minutes serving a passenger. Experience shows that queues accumulate at the ticket office, passengers complain about the slowness of service. A rationalization proposal has been received: instead of one ticket office selling tickets and A and in IN, create two specialized ticket offices (one window in each), selling tickets, one - only to the point A, the other - only to the point IN. The wisdom of this proposal is controversial - some argue that the queues will remain the same. It is necessary to check the usefulness of the proposal by calculation. Since we can calculate characteristics only for the simplest QS, let’s assume that all flows of events are the simplest (this will not affect the qualitative side of the conclusions).
Well, let's get down to business. Let's consider two options for organizing ticket sales - existing and proposed.
Option I (existing). The two-channel QS receives a flow of requests with intensity λ = 0.9; service flow intensity μ = 1/2 = 0.5; ρ = λ/μ = l.8. Since ρ/2 = 0.9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0.0525. The average number of applications in the queue is found using formula (20.23): L och ≈ 7.68; the average time spent by an application in the queue (according to the first of formulas (20.25)) is equal to W och ≈ 8.54 (min.).
Option II (proposed). It is necessary to consider two single-channel QS (two specialized windows); each receives a flow of applications with intensity λ = 0.45; μ . still equal to 0.5; ρ = λ/μ = 0.9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L och = 8.1.
Here's one for you! The length of the queue, it turns out, not only did not decrease, but increased! Maybe the average waiting time in line has decreased? Let's see. Sharing L och at λ = 0.45, we get W very ≈ 18 (minutes).
So much for rationalization! Instead of decreasing, both the average length of the queue and the average waiting time in it increased!
Let's try to guess why this happened? Having thought about it, we come to the conclusion: this happened because in the first option (two-channel QS) the average proportion of time that each of the two cashiers is idle is less: if he is not busy serving a passenger buying a ticket to the point A, he can engage in servicing a passenger buying a ticket to a point IN, and vice versa. In the second option, there is no such interchangeability: the unoccupied cashier just sits with his hands folded...
Well , okay,” the reader is ready to agree, “the increase can be explained, but why is it so significant? Is there an error in the calculation here?
And we will answer this question. There is no error. The thing is , that in our example both QSs are operating at the limit of their capabilities; As soon as you slightly increase the service time (i.e., reduce μ), they will no longer cope with the flow of passengers, and the queue will begin to increase without limit. And the “extra downtime” of the cashier is in some sense equivalent to a decrease in his productivity μ.
Thus, the result of calculations, which at first seems paradoxical (or even simply incorrect), turns out to be correct and explainable.
The theory of queuing is rich in such paradoxical conclusions, the reason for which is by no means obvious. The author himself was repeatedly “surprised” by the results of calculations, which later turned out to be correct.
Reflecting on the last problem, the reader can pose the question this way: after all, if the box office sells tickets to only one point, then, naturally, the service time should decrease, well, not by half, but at least somewhat, but we thought that it was still the average is 2 (min.). We invite such a picky reader to answer the question: how much should it be reduced in order for the “rationalization proposal” to become profitable? Again we encounter, albeit an elementary, but still an optimization problem. With the help of approximate calculations, even on the simplest Markov models, it is possible to clarify the qualitative side of the phenomenon - how it is profitable to act, and how it is unprofitable. In the next section we will introduce some elementary non-Markov models that will further expand our capabilities.
After the reader has become familiar with the methods of calculating the final probabilities of states and efficiency characteristics for the simplest QS (he has mastered the scheme of death and reproduction and Little's formula), he can be offered two more simple QS for independent consideration.
^ 4. Single-channel QS with limited queue. The problem differs from problem 2 only in that the number of requests in the queue is limited (cannot exceed a certain specified T). If a new application arrives at a time when all places in the queue are occupied, it leaves the QS unserved (received a refusal).
We need to find the final probabilities of states (by the way, in this problem they exist for any ρ - after all, the number of states is finite), the probability of failure R open, absolute throughput A, probability that the channel is busy R busy, average queue length L very good, average number of applications to the CMO L sist , average waiting time in queue W very good , average time an application stays in the CMO W syst. When calculating the characteristics of a queue, you can use the same technique that we used in Problem 2, with the difference that you need to sum up not an infinite progression, but a finite one.
^ 5. Closed QS with one channel and m sources of applications. To be specific, let’s pose the problem in the following form: one worker serves T machines, each of which requires adjustment (correction) from time to time. The demand flow intensity of each operating machine is λ . If a machine breaks down while a worker is free, it immediately goes into service. If it fails while a worker is busy, it gets in line and waits for the worker to become free. Average machine setup time t rev = 1/μ. The intensity of the flow of requests coming to the worker depends on how many machines are working. If it works k machines, it is equal kλ. Find the final state probabilities, the average number of working machines, and the probability that a worker will be busy.
Note that in this QS the final probabilities
will exist for any values of λ and μ = 1/ t about, since the number of states of the system is finite.
Task 1. The dispatching console receives a flow of requests, which is a second-order Erlang flow. The intensity of the flow of applications is 6 applications per hour. If the dispatcher leaves the console at a random moment, then at the first next request he must return to the console. Find the distribution density of the waiting time for the next request and plot its graph. Calculate the probability that the dispatcher can be absent from 10 to 20 minutes. Solution. Since the Erlang flow of the second order is a stationary flow with limited aftereffect, then the Palm formula is valid for it
Where f1(θ)-
probability distribution density for the waiting time of the first nearest event;
λ
- flow intensity;
- flow order;
(θ)
is the probability distribution function for the time between two adjacent events of the Erlang flow of order (E).
It is known that the distribution function for the flow E has the form
. (2)
According to the conditions of the problem, the flow of applications is Erlang of order =2. Then from (1) and (2) we obtain
.
From the last relation for λ=6 we will have
f1(θ)=3е-6θ(1+6θ), θ≥0. (3)
Let's plot the function f1(θ) . At θ <0 we have f1(θ) =0 . At θ =0 , f1(0)=3. Consider the limit
When calculating the limit for the disclosure of type ambiguity, the L'Hopital rule was used. Based on the research results, we build a graph of the function f1(θ)
(Fig. 1).
Let's pay attention to the dimensions of time in the text of the task: for intensity, these are applications per hour, for time, minutes. Let's move on to one time unit: 10 min = 1/6 hour, 20 min = 1/3 hour. For these values we can calculate f1(θ) and clarify the nature of the curve
These ordinates are indicated on the graph above the corresponding points on the curve.
From the course of probability theory it is known that the probability of hitting a random variable X into the segment [α, β] is numerically equal to the area under the probability density distribution curve f(x). This area is expressed by a definite integral
Therefore, the required probability is equal to
This integral can be easily calculated by parts if we put
U=1+6θ And dV=e-6θdθ. Then dU=6dθ And V=
.
Using formula 
we get 
Answer: the probability that the dispatcher will be absent from 10 to 20 minutes is 0.28.
Task 2. The display room has 5 displays. The user flow is simple. The average number of users visiting the display room per day is 140. The time for processing information by one user on one display is distributed according to an exponential law and averages 40 minutes. Determine whether there is a stationary operating mode for the hall; the likelihood that the user will find all displays busy; average number of users in the display room; average number of users in queue; average waiting time for a free display; average time a user spends in the display room. Solution. The QS considered in the problem belongs to the class of multi-channel systems with an unlimited queue. Number of channels =5. Let us find the λ-intensity of the flow of applications: where 
(hours) - the average time between two consecutive requests from the incoming user flow. Then 
user/hour
Let's find the intensity of the service flow: 
, where M[T serv.]=40 min=0.67 hours is the average time for servicing one user with one display,
Then 
user/hour
Thus, the classifier of this system has the form QS (5, ∞; 5.85; 1.49).
Let's calculate the load factor of the QS 
. It is known that for a QS of this class, a stationary mode exists if the ratio of the system load factor to the number of channels is less than one. Finding this relationship 
.
Therefore, a stationary regime exists. The limiting probability distribution of states is calculated using the formulas
Since =5, we have
Let's calculate P* - the probability that the user will find all displays busy. Obviously, it is equal to the sum of the probabilities of such events: all displays are busy, there is no queue (p5); all displays are busy, one user is in queue (p6); all displays are busy, two users are in queue (p7) and so on. Since for a complete group of events the sum of the probabilities of these events is equal to one, then the equality is true
P*=p5+p6+p7+…=1 - po - p1 - p2 - p3 - p4.
Let's find these probabilities: ro=0,014; p1=3,93*0,014; p2=7,72*0,014; p3=10,12*0,014; p4=9,94*0,014.
Taking the common factor out of brackets, we get
P*=1-0.0148*(1+3.93+7.72+10.12+9.94)=1-0.014*32.71=1-0.46=0.54.
Using formulas to calculate performance indicators? let's find:
- 1. average number of users in queue
2. average number of users in the display room
3. average waiting time for a free display
4. average time a user spends in the display room
Answer: a stationary mode of operation of the display room exists and is characterized by the following indicators R*=0.54; user; user; ; .
Task 3. A two-channel queuing system (QS) with failures receives a stationary Poisson flow of requests. The time between the arrivals of two consecutive requests is distributed according to an exponential law with the parameter λ=5 requests per minute. The duration of servicing each request is 0.5 minutes. Using the Monte Carlo method, find the average number of requests served in a time of 4 minutes. Direction: Carry out three tests. Solution. Let us depict statistical modeling of the operation of a given QS using time diagrams. Let us introduce the following notation for the time axes:In-incoming flow of applications, here ti- moments of receipt of applications; Ti- time intervals between two consecutive applications. It's obvious that ti=ti-1 +Ti.
K1 is the first service channel;
K2-second service channel; here the thick lines on the time axis indicate channel occupancy intervals. If both channels are free, then the request becomes serviced in channel K1; if it is busy, the request is served by channel K2.
If both channels are busy, then the request leaves the QS unserved.
Out OB - outgoing flow of serviced requests.
Out PT - outgoing flow of lost requests due to QS failures (the case of occupancy of both channels).
Statistical testing continues over the time interval. Obviously, any excess of time tmax entails dumping the request into the outgoing stream Output PT. So in fig. 3 application No. 10, which came into the system at the moment t10, does not have time to be served until the moment tmax, because t10+Tol.>tmax. Consequently, it is not accepted by the free channel K1 for service and is reset to the Output PT, receiving a refusal.
Rice. 3
From the time diagrams it is clear that it is necessary to learn how to model intervals Ti. Let's apply the method of inverse functions. Since the random variable Ti distributed according to the exponential law with the parameter λ =5, then the distribution density has the form f(τ)=5е-5τ. Then the value F(Ti) the probability distribution function is determined by the integral
.
It is known that the range of the distribution function F(T)
there is a segment. We select a number from the table of random numbers and determine Ti from equality, whence. However, if . Therefore, you can immediately get implementations from the table of random numbers. Hence,
e-5Ti=
ri, or –5Ti=
lnri, where . It is convenient to enter the calculation results into a table.
To conduct test No. 1, random numbers were taken from Appendix 2, starting from the first number of the first line. Next, the selection was carried out by rows. Let's do two more tests.
Pay attention to the selection of random numbers from the table in Appendix 2, if in test No. 1 the last random number for application No. 16 was 0.37 (the first random number in the second line), then test No. 2 begins with the following random number 0.54 . Trial 2 contains the last random number 0.53 (the fifth number in the third row). Therefore, the third trial will start with the number 0.19. In general, within one series of tests, random numbers from the table are selected without gaps or insertions in a certain order, for example, by rows.
Table 1. TEST No. 1
Application No. |
Sl. number |
-ln ri |
Moment of application receipt |
Moment of end of service. |
Application counter |
|||
| K1 | ||||||||
Application No. |
Sl. number |
-ln ri |
Moment of application receipt |
Moment of end of service. |
Application counter |
|||
Application No. |
Sl. number |
-ln ri |
Moment of application receipt |
Moment of end of service. |
Application counter |
||||
| K1 | |||||||||
Thus, based on the results of three tests, the number of applications served was respectively: x1=9, x2=9, x3=8. Let's find the average number of requests served:
Answer: the average number of applications served by the QS in 4 minutes is 8.6(6).
When solving control problems, including command and control of troops, a number of similar problems often arise:
- assessment of the capacity of a communication direction, railway junction, hospital, etc.;
- assessment of the effectiveness of the repair base;
- determining the number of frequencies for a radio network, etc.
All of these tasks are similar in the sense that they involve massive demand for service. A certain set of elements is involved in satisfying this demand, forming a queuing system (QS) (Fig. 2.9).
The elements of the QS are:
- input (incoming) demand flow(requests) for service;
- service devices (channels);
- queue of applications awaiting service;
- day off ( outgoing) flow processed applications;
- flow of unserved applications;
- queue of free channels (for multi-channel QS).
Incoming flow is a collection of service requests. Often the application is identified with its bearer. For example, a flow of faulty radio equipment entering a workshop of an association represents a flow of requests - requirements for service in this QS.
As a rule, in practice we deal with so-called recurrent flows - flows that have the following properties:
- stationarity;
- ordinary;
- limited aftereffect.
We defined the first two properties earlier. As for the limited aftereffect, it lies in the fact that the intervals between incoming applications are independent random variables.
There are many recurrent threads. Each interval distribution law generates its own recurrent flow. Recurrent flows are otherwise called Palm flows.
A flow with a complete absence of aftereffect, as already noted, is called stationary Poisson. His random intervals between orders have an exponential distribution:
here is the flow intensity.
The name of the flow - Poisson - comes from the fact that for this flow probability the appearance of orders during the interval is determined by Poisson’s law:
A flow of this type, as noted earlier, is also called the simplest. This is exactly the flow that designers assume when developing a QS. This is due to three reasons.
Firstly, a flow of this type in queuing theory is similar to the normal distribution law in probability theory in the sense that the simplest flow is achieved by passing to the limit for a flow that is the sum of flows with arbitrary characteristics with an infinite increase in terms and a decrease in their intensity. That is, the sum of arbitrary independent (without dominance) flows with intensities is the simplest flow with intensity
Secondly, if the serving channels (devices) are designed for the simplest flow of requests, then servicing other types of flows (with the same intensity) will be provided with no less efficiency.
Third, it is precisely this flow that determines the Markov process in the system and, consequently, the simplicity of the analytical analysis of the system. For other flows, analysis of the functioning of the QS is complex.
There are often systems in which the flow of input requests depends on the number of requests being serviced. Such SMOs are called closed(otherwise - open). For example, the work of an association communication workshop can be represented by a closed-loop QS model. Let this workshop be intended to service the radio stations that are in the association. Each of them has failure rate. The input flow of the failed equipment will have the following intensity:
where is the number of radio stations already in the workshop for repair.
Applications may have different eligibility to begin service. In this case, they say that applications heterogeneous. The advantages of some application flows over others are determined by the priority scale.
An important characteristic of the input stream is the coefficient of variation:
where is the mathematical expectation of the interval length;
Standard deviation of a random variable (interval length).
For the simplest flow 
For most real threads.
When the flow is regular, deterministic.
The coefficient of variation- a characteristic reflecting the degree of unevenness in the receipt of applications.
Service channels (devices). The QS may have one or more servicing devices (channels). According to this, QSs are called single-channel or multi-channel.
Multichannel The QS can consist of the same or different types of devices. Servicing devices can be:
- communication lines;
- repair technicians;
- runways;
- vehicles;
- berths;
- hairdressers, sellers, etc.
The main characteristic of a channel is service time. As a rule, service time is a random value.
Typically, practitioners believe that service time has an exponential distribution law:
where is the service intensity, ;
Mathematical expectation of service time.
That is, the service process is Markovian, and this, as we now know, provides significant convenience in analytical mathematical modeling.
In addition to the exponential distribution, there are Erlang distributions, hyperexponential distributions, triangular distributions, and some others. This should not confuse us, since it has been shown that the value of the QS efficiency criteria depends little on the type of probability distribution law for service time.
When studying QS, the essence of service is lost from consideration, quality of service.
Channels can be absolutely reliable, that is, not to fail. Or rather, this can be accepted during research. Channels may have ultimate reliability. In this case, the QS model is much more complicated.
Application queue. Due to the random nature of the flow of requests and servicing, an arriving request may find the channel(s) busy servicing the previous request. In this case, it will either leave the QS unserved or remain in the system, waiting for its service to begin. In accordance with this, they distinguish:
- QS with failures;
- SMO with anticipation.
CMO with anticipation characterized by the presence of queues. A queue can have limited or unlimited capacity: 
.
The researcher is usually interested in the following statistical characteristics associated with the stay of applications in the queue:
- the average number of applications in the queue during the study interval;
- average time spent (waiting) for an application in the queue. QS with limited queue capacity referred to as a mixed type QS.
Often there are CMOs in which applications have limited time in queue regardless of its capacity. Such QSs are also classified as mixed type QSs.
Output stream is the flow of serviced applications leaving the QS.
There are cases when requests pass through several QS: transit communication, production conveyor, etc. In this case, the outgoing flow is incoming for the next QS. A set of sequentially interconnected QSs is called multiphase queuing system or QS networks.
The incoming flow of the first QS, passing through subsequent QSs, is distorted and this complicates modeling. However, it should be kept in mind that with the simplest input stream and exponential service (that is, in Markov systems), the output stream is also simplest. If the service time has a non-exponential distribution, then the outgoing flow is not only not the simplest, but also not recurrent.
Note that the intervals between requests of the outgoing flow are not the same as service intervals. After all, it may turn out that after the end of the next service, the QS is idle for some time due to the lack of applications. In this case
The flow of orders is Poisson if 3 conditions are met:
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:
The probability of an event (arrival of an application) in a short time interval is proportional to the length of this interval.
The probability of 2 events over a small interval is negligible.
The belief that an application is received does not depend on previous events.
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.
The simplest QS and their characteristics. Multi-channel and single-channel lossless systems with unlimited latency and a source with an infinite number of demands. Condition for the existence of a finite average queue for multi-channel systems.
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 simplest QS with waiting is a single-channel system that receives a stream of requests with a defined intensity. A request that arrives at a time when the channel is busy gets into a queue and waits for service.
MCUs are used to simulate several parallel operating objects. MCU modeling is similar to device modeling: a transaction enters the device, occupies a certain number of channels, is serviced for some time, and then leaves the MCU, freeing the channels it occupies.
Conditions in a real object that are necessary to use MCU for their representation in the model:
Objects must have the same service time distribution function
Same parameters for this function.
Unlike the device, the capacity of the cat is always equal to one, the capacity of the MKU d.b. defined by the programmer. To do this, use a special command STORAGE (DEFINE MCU).
Team Name STORAGE A
The CommandName field is the symbolic name of the MCU, and field A is its capacity (the number of service channels), operand A may be specified only as a positive integer.
Ex: MKU1 STORAGE 5 TRAKT STORAGE 30 (the capacity of an MKU named MKU1 is defined as 5, an MKU named TRAKT is defined as 30).
The event associated with the occupation of service channels is modeled by the ENTER block, and the channel release event is modeled by the LEAVE block.
A is the name of MKU. B – number of units of MCU capacity the cat must occupy (release) the transaction. Default =1.
Ex: 1) ENTER BLOK3 (enter the MCU with the name BLOK3);
2)LEAVE SEANS,3 (release 3 units of MCU capacity with the name SEANS).
Between the ENTER and LEAVE blocks there can be any number of blocks. In particular, the delay during service time in the MCU is simulated using the ADVANCE block.
If the number of capacity units specified by operand B of the LEAVE block exceeds the number of MCU channels currently occupied, the interpreter stops the simulation and displays an error message.
For transactions awaiting MCU occupation, the “first to match with passes” rule applies.
When a transaction enters the LEAVE block, the interpreter pauses its progress, allowing the next transaction from the delay chain of this MCU to enter the ENTER block, and only after that advances the transaction that left the MCU in the model. The transaction that leaves the MCU delay chain is transferred to the DTS and becomes the last one in its priority class.
MCUs have the following NAVs: S - current contents of the MCU; R is the free capacity of the MCU; SR - utilization rate in fractions of 1000; SA - integer part of the average content of the MKU; SM - maximum contents of the MCU; SC - number of MKU classes; ST is an integer part of the average time of MKU occupation.
Seize and Release blocks are used to design single-channel devices
SEIZEA(occupy) - occupation of the device by a transaction. A- name of the device entry point.
RELEASEA(release) – release of the device by the transaction after the service time has expired.
