When solving control problems, including command and control of troops, a number of similar problems often arise:

• grade bandwidth communication directions, 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. In satisfying this demand, a certain set of elements is involved, forming a system queuing(SMO) (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 normal law distributions 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 Markov process in the system and, therefore, the ease of 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 - expected value 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 service, 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

Brief theory

As indicators of the effectiveness of a QS with failures, we will consider:

The absolute capacity of the QS, i.e. average number of applications served per unit of time;

Relative throughput, i.e. the average share of incoming applications serviced by the system;

Probability of failure, i.e. that the application will leave the QS unserved;

Average number of busy channels.

Let's consider the classical Erlang problem.

There are channels that receive a flow of applications with an intensity of . The service flow has intensity. Find the limiting probabilities of system states and indicators of its efficiency.

The system (SMO) has following states(we number them according to the number of requests in the system): , where is the state of the system when there are requests in it, that is, the channels are occupied.

The state graph of the QS corresponds to the process of death and reproduction and is shown in the figure.

The flow of requests sequentially transfers the system from any left state to the adjacent right one with the same intensity. The intensity of the flow of services that transfer the system from any right state to the adjacent left state constantly changes depending on the state. Indeed, if the QS is in the state (two channels are busy), then it can switch to the state (one channel is busy) when either the first or the second channel finishes servicing, that is, the total intensity of their service flows will be . Similarly, the total service flow that transfers the QS from the state (three channels are busy) to will have an intensity , that is, any of the three channels can be released, and so on.

For the scheme of death and reproduction we obtain for the limiting probability of the state:

where the terms of the expansion will be the coefficients in the expressions for the marginal probabilities. Magnitude

is called the reduced demand flow intensity or channel load intensity. It expresses the average number of requests received during the average time of servicing one request. Now:

The latest formulas for marginal probabilities are called Erlang formulas in honor of the founder of queuing theory.

The probability of QS failure is the maximum probability that all channels of the system will be busy, that is:

Relative throughput – the probability that a request will be served:

Absolute throughput:

The average number of occupied channels is the mathematical expectation of the number of occupied channels:

where are the limiting probabilities of states

However, the average number of occupied channels can be found more easily if we consider that the absolute throughput of the system is nothing more than the intensity of the flow of requests served by the system (per unit time). Since each busy channel serves on average requests (per unit time), the average number of busy channels is:

Example of problem solution

The task

Control finished products The firms are carried out by three controllers. If the product arrives for inspection when all inspectors are busy checking finished products, then it remains unverified. The average number of products produced by the company is 20 items/hour. The average time to check one product is 7 minutes.

Determine the performance indicators of the technical control department. How many controllers must be installed to ensure that the service probability is at least 97%?

Did you find yourself on this page trying to solve a problem for an exam or test? If you still couldn’t pass the exam, next time agree in advance on the website about Online help on methods of optimal solutions.

The solution of the problem

Control is an open multi-channel queuing system with denial of service.

Let's choose the hour as the unit of time. We will assume that the control operates in a steady state. According to the conditions of the problem

– number of service channels

Products per hour – the intensity of the flow of applications

Products per hour – service flow intensity

Let us calculate the relative intensities of transitions from state to state:

Let's calculate:

Probability of failure:

Probability of service

Absolute system throughput:

– the average number of requests served by the system per unit of time.

Average number of channels servicing an application:

Let's calculate how many controllers need to be installed so that the probability of service is at least 97%:

Thus, in order for the probability of service to be at least 97%, it is necessary to have 6 controllers.

Average solution cost test work 700 - 1200 rubles (but not less than 300 rubles for the entire order). The price is greatly influenced by the urgency of the decision (from a day to several hours). The cost of online help for an exam/test is from 1000 rubles. for solving the ticket.

You can leave a request directly in the chat, having previously sent the conditions of the tasks and informed you of the deadlines for the solution you need. Response time is a few minutes.

Examples of related problems

QS with unlimited queue
The necessary theoretical information and a sample solution to the problem on the topic “Multi-channel queuing system with an unlimited queue” are provided; the indicators of a multi-channel queuing system (QS) with waiting for service are discussed in detail - the average number of channels occupied by servicing an order, the length of the queue, the probability of queue formation, the probability free state of the system, average waiting time in queue.

Optimal resource allocation problem
The basic principles of dynamic programming (dynamic planning) are briefly outlined and the Bellman equations are considered. The problem of optimal distribution of resources between enterprises is solved in detail.

Lagrange multiplier method
The page discusses the location conditional extremum Lagrange multiplier method. The construction of the Lagrange function is shown using the example of solving a nonlinear programming problem. The solved problem is preceded by a brief theory.

Final consumption vector and gross output vector
Using the example of solving a problem, Leontiev's intersectoral model is considered. The calculation of the matrix of coefficients of direct material costs, the matrix of “input-output”, the matrix of coefficients of indirect costs, vectors of final consumption and gross output is shown.

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 – maximum number 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 idleness 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;

About – the average time for servicing an application, relating only to serviced applications;

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 requests that the system can service per unit of time.

Relative capacity of QS Q is the ratio of the average number of applications served by the system per unit of time to the average number of applications received during this time.

When solving queuing problems, you must 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 a 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) connected by direct and reverse 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 similar scheme describes changes in population size.

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 output one important formula, connecting (for the limiting, stationary mode) the average number of requests 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) are merged, there are no applications 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 application (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 right side(19.11) for 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 view relatively recently) are not given 1).

§ 20. The simplest queuing systems and their characteristics

In this section we will look at some of the simplest QSs 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 chase the number of QS samples for which we will develop final expressions characteristics; 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” that make the path easier through the theory of queuing, which in a number of existing (even pretending to be popular) books may seem like an incoherent set of examples.

In this section, we will consider all flows of events that transfer the QS from state to state to be the simplest (without specifically stipulating this each time). Among them will be the so-called “service flow”. It refers to the flow of requests served by one continuously busy channel. In this flow, the interval between events, as always in the simplest flow, has an exponential distribution (in many manuals they say instead: “service time is exponential”; we ourselves will use this term in the future).

1) In a popular book, a slightly different derivation of Little’s formula is given, compared to the above. In general, familiarization 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;

^ P open- the probability of refusal, i.e., 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 applications in the system (in 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 occupied, the rest are free),

S k - located in SMO k applications ( k channels are occupied, 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. Place it at the arrow S 1 →S 0 intensity μ. Now imagine that the system is in a state S 2(two channels work). So that she can 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 ^ P open. - the probability that an incoming application will be rejected (will not be serviced). For this it is necessary that everything P channels were busy, which means

R open = 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)

All that remains is to find the average number of occupied 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, taking into account (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, as the number of channels increases, this income increases, but the costs associated with maintaining the channels also increase. What will outweigh - an increase in income or expenses? It depends on the terms of the operation, the “fee for servicing the application” and 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 it to 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 posed by someone.

^ 2. Single-channel QS with unlimited queue. In practice, it is quite common to find single-channel medical services with a queue (a doctor serving patients; a pay phone with one booth; a computer executing user orders). In queuing theory, single-channel QS with a queue also occupy a special place (most of the analytical formulas obtained so far for non-Markov systems belong to such QS). 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 time an application stays in the system,

^ L och- average number of applications in the queue,

W very good - average time an application spends in queue,

P zan - the probability that the channel is busy (channel load).

Regarding 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 without limit. 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 obtain an expression for p 0:

p 0 = -1 =

= (1 + р + р 2 + ... + р k +….) -1 . (20.11)

The series in formula (20.11) is a geometric progression. We know that for ρ< 1 ряд сходится - это бесконечно убывающая geometric progression with denominator p. For p ≥ 1, the series diverges (which is indirect, although not strict, evidence that the final probabilities of states p 0 , p 1 , ..., p k , ... exist only at p<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

p 0 = 1 - ρ. (20.12)

Probabilities r 1, r 2, ..., r 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 och = 4/3 (composition), W och = 2/3 (hours), L ext = 16/27 (composition), W ext = 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 very good 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.

So much 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 performance 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.

Let's consider methods for computer modeling of flows of requests entering a queuing system. First, let us dwell on a fairly simple and at the same time the most common case, when an ordinary stationary flow of homogeneous events with a limited aftereffect (Palm-type flow) enters the system.

Any Palm type flow can be specified by the density function of random intervals between successive moments - the receipt of requests. To simulate it on a computer, it is enough to construct the required number of flow implementations, i.e., such non-random sequences of moments

receipt of applications into the system, the intervals between which would be possible values ​​of random variables described by the density function

The sequence construction procedure is as follows. First, the density function can be determined through Palm's formula (4.4). Then, based on the presence in the computer of an electronic or algorithmic random number sensor with a uniform distribution in the interval (0,1), we proceed to the formation. To do this, using one of the methods discussed in Chapter P, we transform the random number into a random number having a density function. Having received, we assume

Subsequently, the procedure for obtaining any one coincides with the procedure for generating it, i.e., the next random number is transformed into a random number that has a density function and

Let's look at some examples that are often encountered when solving practical problems using statistical modeling.

Example 1. The simplest (Pausson) flow.

As noted above, the simplest (Paussonian) flow is a stationary ordinary flow of homogeneous events without aftereffect, i.e., one of the possible special cases of Palm-type flows. The density function for the simplest flow has the form of exponential distribution (4.6):

where is the flow intensity, which determines the average value of the number of applications arriving per unit of time.

To determine the density function for the first interval, we use Palm's formula.

After simple calculations we get:

It follows that the density function of the first interval for the simplest flow has the same form as this property. In the general case, other flows of the Palm type do not have this property.

Thus, to generate implementations of the simplest flow, it is necessary to have a sequence of random numbers having exponential distribution (4.6) with parameter K. We considered the method for obtaining such a sequence in Chapter II. In accordance with (2.15), random numbers can be obtained using the formula

where are random numbers with a uniform distribution in the interval (0,1).

The sequence of times for receiving applications will be as follows:

Example 2: Uniformly spaced flow

The density function of the flow under consideration has the form of a uniform distribution:

It can be shown that the average value (mathematical expectation) of a random variable is equal to Therefore, the average number of applications received per unit of time (flow intensity):

Let's define the density function for the first interval. According to the Palma formula, it is similar to formula (4.11):

Note that the average value of the duration of the first interval can be obtained as the mathematical expectation of a random variable having a density function (4.16):

Let's move on to the formation of the first interval. To do this, having random numbers with a uniform distribution law in the interval (0,1), it is necessary to obtain a random number corresponding to the density function (4.16). Let us transform relation (4.16) as follows. Instead of the quantity, let us substitute its value from equality (4.15). Then we can write the density function

It should be noted that the flows considered in examples 1 and 2 have a favorable feature: the integrals in the Palma formula and the random number transformation formulas are taken in their final form. In the general case, these integrals may not be taken. In addition, density functions are sometimes specified in tables based on the results of processing statistical material. In practice, in such situations, approximate methods are used. The integral in the Palma formula is usually calculated for a given set by numerical methods. This does not significantly affect the volume of calculations, since the Palma formula is used only once for a given flow.The transformation of random numbers is performed, as a rule, by the method of piecewise approximation of the density function in accordance with relations (2.23), (2.24) and (2.25).

Task 1. The control panel receives a stream of requests, which is a second-order Erlang stream. The intensity of the flow of applications is 6 applications per hour. If the dispatcher accidentally leaves the remote control, then at the first next request he must return to the remote control. Find the distribution density of the waiting time for the next application and construct its graph. Calculate the probability that the dispatcher will be absent from 10 to 20 minutes. Solution. Since the second-order Erlang flow is a stationary flow with limited aftereffect, then Palm’s formula is valid for it

Where f1(θ)- probability distribution density for the waiting time for the first nearest event;
λ - flow intensity;
- flow order;
(θ) - probability distribution function for the time between two neighboring Erlang flow events - first 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 requests is Erlang order =2. Then from (1) and (2) we get
.
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 to reveal type uncertainty, L'Hopital's rule was used. Based on the research results, we build a graph of the function f1(θ) (Fig. 1).

Let's pay attention to the time dimensions in the text of the problem: for intensity these are requests 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 probability theory course we know that the probability of a random variable hitting 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=е-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. We find this relation
.
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 distribution function range 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 obtain 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. i	Sl. number ri		-ln ri Ti	Moment of application receipt ti=ti-1+Ti	Moment of end of service. ti+0.50		Application counter
					K1

Table 2 TEST No. 2

Application No. i	Sl. number ri		-ln ri Ti	Moment of application receipt ti=ti-1+Ti	Moment of end of service. ti+0.50		Application counter

Table No. 3 TEST No. 3

Application No. i		Sl. number ri		-ln ri Ti	Moment of application receipt ti=ti-1+Ti	Moment of end of service. ti+0.50		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).

Return