Smo with unlimited queue. QS with waiting (queue). Multi-channel smo with unlimited queue
federal agency by education of the Russian Federation
FGOU SPO "Perevozsky Construction College"
in the discipline "Mathematical Methods"
on the topic “QS with limited waiting time. Closed QS»
Introduction ................................................ ................................................. ....... 2
1. Fundamentals of the theory queuing.................................................. 3
1.1 The concept of a random process.................................................... .................... 3
1.2 Markov stochastic process............................................................... ................ 4
1.3 Event Streams............................................................... ......................................... 6
1.4 Kolmogorov's equations for state probabilities. Final probabilities of states............................................................... ................................................. ........ nine
1.5 Tasks of the theory of queuing....................................................... .. 13
1.6 Classification of queuing systems............................................... 15
2. Waiting queuing systems....................................................... 16
2.1 Single-channel latency QS....................................................................... ........... 16
2.2 Multi-channel latency QS .............................................................. ......... 25
3. Closed QS ....................................................... ......................................... 37
The solution of the problem................................................ ............................................. 45
Conclusion................................................. ................................................. . fifty
Bibliography................................................ ............................................... 51
In this course, we will consider various queuing systems (QS) and queuing networks (QNS).
A queuing system (QS) is understood as a dynamic system designed to efficiently service the flow of applications (requirements for service) under restrictions on system resources.
QS models are convenient for describing individual subsystems of modern computing systems, such as the subsystem processor - main memory, input-output channel, etc. The computing system as a whole is a collection of interconnected subsystems, the interaction of which is probabilistic. An application for solving a certain problem that enters the computing system goes through a sequence of stages of counting, accessing external storage devices and input-output devices. After completing a certain sequence of such stages, the number and duration of which depend on the complexity of the program, the request is considered serviced and leaves the computing system. Thus, the computing system as a whole can be represented by a set of QS, each of which displays the process of functioning of a separate device or a group of devices of the same type that are part of the system.
A set of interconnected QS is called a queuing network (stochastic network).
To begin with, we will consider the basics of the QS theory, then we will move on to familiarizing ourselves with the detailed content of QS with expectation and closed QS. The course also includes a practical part, in which we will get acquainted in detail with how to apply the theory in practice.
Queuing theory is one of the branches of probability theory. This theory considers probabilistic problems and mathematical models (before that, we considered deterministic mathematical models). Recall that:
Deterministic mathematical model reflects the behavior of an object (system, process) from the standpoint complete certainty in the present and future.
Probabilistic mathematical model takes into account the influence of random factors on the behavior of an object (system, process) and, therefore, evaluates the future from the standpoint of the probability of certain events.
Those. here, as, for example, in game theory, problems are considered in conditions uncertainty .
Let us first consider some concepts that characterize "stochastic uncertainty", when the uncertain factors included in the problem are random variables (or random functions), the probabilistic characteristics of which are either known or can be obtained from experience. Such uncertainty is also called "favorable", "benign".
Strictly speaking, random perturbations are inherent in any process. It is easier to give examples of a random process than a "non-random" process. Even, for example, the process of running a watch (it seems to be a strict, well-considered work - “works like a clock”) is subject to random changes (going ahead, lagging behind, stopping). But as long as these perturbations are insignificant and have little effect on the parameters of interest to us, we can neglect them and consider the process as deterministic, nonrandom.
Let there be some system S (technical device, a group of such devices, a technological system - a machine tool, a site, a workshop, an enterprise, an industry, etc.). In system S leaks random process, if it changes its state over time (transitions from one state to another), moreover, in a randomly unknown way.
Examples:
1. System S– technological system (machine section). Machines break down and get repaired from time to time. The process taking place in this system is random.
2. System S- an aircraft flying at a given altitude along a certain route. Disturbing factors - weather conditions, crew errors, etc., consequences - "chatter", violation of the flight schedule, etc.
The random process in the system is called Markovsky if for any moment of time t 0 the probabilistic characteristics of the process in the future depend only on its state at the moment t 0 and do not depend on when and how the system came to this state.
Let the system be in a certain state at the present moment t 0 S 0 . We know the characteristics of the state of the system in the present and everything that happened during t <t 0 (process history). Can we foresee (predict) the future, i.e. what will happen when t >t 0? Not exactly, but some probabilistic characteristics of the process can be found in the future. For example, the probability that after some time the system S will be able S 1 or stay in state S 0 etc.
Example. System S- a group of aircraft involved in air combat. Let be x- the number of "red" aircraft, y- the number of "blue" aircraft. By the time t 0 the number of surviving (not shot down) aircraft, respectively - x 0 , y 0 . We are interested in the probability that at the moment of time the numerical superiority will be on the side of the "Reds". This probability depends on the state of the system at the time t 0 , and not on when and in what sequence those shot down died until the moment t 0 aircraft.
On practice Markov processes usually not found in pure form. But there are processes for which the influence of "prehistory" can be neglected. And when studying such processes, Markov models can be used (in the theory of queuing, non-Markov queuing systems are also considered, but the mathematical apparatus that describes them is much more complicated).
In operations research, Markov stochastic processes with discrete states and continuous time are of great importance.
The process is called discrete state process if its possible states S 1 , S 2 , … can be determined in advance, and the transition of the system from state to state occurs in a “jump”, almost instantly.
The process is called continuous time process, if the moments of possible transitions from state to state are not fixed in advance, but are indefinite, random and can occur at any time.
Example. Technological system (section) S consists of two machines, each of which at a random moment of time can fail (fail), after which the repair of the unit immediately begins, also continuing for an unknown, random time. The following system states are possible:
S 0 - both machines are working;
S 1 - the first machine is being repaired, the second is serviceable;
S 2 - the second machine is being repaired, the first is serviceable;
S 3 - both machines are being repaired.
System transitions S from state to state occur almost instantly, at random moments of failure of one or another machine or the completion of repairs.
When analyzing random processes with discrete states, it is convenient to use a geometric scheme - state graph. The vertices of the graph are the states of the system. Graph arcs are possible transitions from state to state. For our example, the state graph is shown in Fig. one.
Rice. 1. Graph of system states
Note. State Transition S 0 in S 3 is not indicated in the figure, because machines are assumed to fail independently of each other. We neglect the probability of simultaneous failure of both machines.
Stream of events- a sequence of homogeneous events following one after another at some random time.
In the previous example, this is a failure stream and a recovery stream. Other examples: call flow at a telephone exchange, customer flow in a store, etc.
The flow of events can be visualized by a series of points on the time axis O t- rice. 2.
Rice. 2. Image of the flow of events on the time axis
The position of each point is random, and only one implementation of the flow is shown here.
The intensity of the flow of events ( ) is the average number of events per unit of time.
Let's consider 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 a stationary flow is constant. The flow of events inevitably has concentrations or rarefaction, 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-intersecting time intervals 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 stream appear at certain points in time. independently of each other and each for its own reasons.
The stream of events is called ordinary, if the events in it appear singly, and not in groups of several at once.
The stream of events is called the simplest (or stationary Poisson), if it has three properties at once:
1) stationary;
2) ordinary;
3) has no consequences.
The simplest flow has the most simple mathematical description. It plays the same special role among flows, as does the law of normal distribution among other laws of distribution. Namely, when a sufficiently large number of independent, stationary and ordinary flows (comparable to each other in intensity) are superimposed, a flow close to the simplest is obtained.
For the simplest flow with intensity interval T between neighboring events has the so-called exponential (exponential) distribution with density:
where is the parameter of the exponential law.
For a random variable T, which has an exponential distribution, the mathematical expectation is the reciprocal of the parameter, and the standard deviation is equal to the mathematical expectation:
Considering Markov processes with discrete states and continuous time, it is understood that all transitions of the system S from state to state occur under the influence of the simplest event flows (call flows, failure flows, recovery flows, etc.). If all streams of events translating the system S from the state to the state of the simplest, then the process occurring in the system will be Markovian.
So, the system in the state is affected by the simplest flow of events. As soon as the first event of this flow appears, the system “jumps” from state to state (on the state graph, along the arrow ).
For clarity, on the graph of system states, each arc is marked with the intensity of the flow of events that transfers the system along this arc (arrow). - the intensity of the flow of events, transferring the system from the state to . Such a graph is called labeled. For our example, the labeled graph is shown in Fig. 3.
Rice. 3. Labeled system state graph
In this figure - the intensity of the flow of failures; - the intensity of the recovery flow.
We assume that the average time to repair a machine does not depend on whether one machine is being repaired or both at once. Those. Each machine is repaired by a separate specialist.
Let the system be in the state S 0 . In state S 1 it is translated by the failure stream of the first machine. Its intensity is:
where is the average uptime of the first machine.
Out of state S 1 in S 0 the system is transferred by the flow of “ends of repairs” of the first machine. Its intensity is:
where is the average repair time of the first machine.
Similarly, the intensities of the flows of events that transfer the system along all graph arcs are calculated. Having at its disposal a labeled graph of system states, a mathematical model this process.
Let the system under consideration S has -possible states . The probability of the th state is the probability that at time , the system will be in state . Obviously, for any moment of time, the sum of all state probabilities is equal to one:
To find all the probabilities of the states as functions of time, we compose and solve Kolmogorov equations– a special type of equation in which the unknown functions are the probabilities of states. We give here the rule for compiling these equations without proof. But before introducing it, let us explain the concept final state probability .
What will happen to the probabilities of states at ? Will they strive for any limits? If these limits exist and do not depend on the initial state of the system, then they are called final state probabilities .
where is the finite number of system states.
Final state probabilities are no longer variables (functions of time), but constant numbers. It's obvious that:
Final State Probability is essentially the average relative time the system spends in this state.
For example, the system S has three states S 1 , S 2 and S 3 . Their final probabilities are 0.2, respectively; 0.3 and 0.5. This means that the system in the limiting stationary state spends on average 2/10 of the time in the state S 1 , 3/10 - able S 2 and 5/10 - able S 3 .
The rule for compiling a system of Kolmogorov equations: in each equation of the system on the left side of it is the final probability of this state, multiplied by the total intensity of all flows, leading from this state, but in his right parts is the sum of the products of the intensities of all flows, included in -th state, on the probabilities of those states from which these flows originate.
Using this rule, we write the system of equations for our example :
.
It would seem that this system of four equations with four unknowns can be completely solved. But these equations are homogeneous (have no free term), and, therefore, they determine the unknowns only up to an arbitrary factor. However, you can use the normalization condition: 
and use it to solve the system. In this case, one (any) of the equations can be discarded (it follows as a consequence of the rest).
Continuation of the example. Let the values of the flow intensities be equal to: .
We discard the fourth equation, adding the normalization condition instead:
.
Those. in the limiting, stationary mode, the system S on average 40% of the time will be spent in a state S 0 (both machines are in good condition), 20% - in good condition S 1 (the first machine is being repaired, the second one is working), 27% - in good condition S 2 (the second machine is being repaired, the first one is working), 13% - in condition S 3 (both machines are being repaired). Knowing these final probabilities can help estimate the average efficiency of the system and the load on repair organs.
Let the system S capable of S 0 (fully serviceable) brings in a unit of time an income of 8 conventional units, in a state S 1 - income 3 conventional units, able to S 2 – income of 5 conventional units, able to S 3 - does not generate income. Then, in the limiting, stationary mode, the average income per unit of time will be equal to: conventional units.
Machine 1 is being repaired for a fraction of time equal to: . Machine 2 is being repaired for a fraction of the time equal to: . Arises optimization problem. Suppose we can reduce the average repair time of the first or second machine (or both), but this will cost us a certain amount. The question is, will the increase in income associated with faster repairs pay for the increased repair costs? It will be necessary to solve a system of four equations with four unknowns.
Examples of queuing systems (QS): telephone exchanges, repair shops, ticket offices, information desks, machine tools and others technological systems, flexible control system production systems etc.
Each QS consists of a certain number of service units, which are called service channels(these are machine tools, transport carts, robots, communication lines, cashiers, sellers, etc.). Every QS is designed to serve some application flow(requirements) arriving at some random time.
The service of the request continues for some, generally speaking, random time, after which the channel is released and is ready to receive the next request. The random nature of the flow of applications and service time leads to the fact that at some time periods an unnecessarily large number of applications accumulate at the entrance of the QS (they either enter the queue or leave the QS unserved). In other periods, the QS will work with underload or even stand idle.
The QS operation process is a random process with discrete states and continuous time. The state of the QS changes abruptly at the moments of occurrence of some events (the arrival of a new request, the end of service, the moment when the request, which is tired of waiting, leaves the queue).
The subject of queuing theory– construction mathematical models, linking the given operating conditions of the QS (the number of channels, their performance, operating rules, the nature of the flow of applications) with the characteristics of interest to us - indicators of the QS efficiency. These indicators describe the ability of the CMO to cope with the flow of requests. They can be: the average number of applications served by the QS per unit of time; average number of busy channels; the average number of applications in the queue; average waiting time for service, etc.
Mathematical analysis of the work of the QS is greatly facilitated if the process of this work is Markovian, i.e. event flows that transfer the system from state to state are the simplest. Otherwise, the mathematical description of the process becomes very complicated and it is rarely possible to bring it to specific analytical dependencies. In practice, non-Markov processes are reduced to Markov processes with approximation. The following mathematical apparatus describes Markov processes.
The first division (by the presence of queues):
1. QS with failures;
2. CMO with a queue.
In CMO with failures a request that arrives at the moment when all channels are busy is rejected, leaves the QS, and is not served further.
In the CMO with a queue an application that arrives at a time when all channels are busy does not leave, but queues up and waits for an opportunity to be served.
QS with queues are subdivided on the different types depending on how the queue is organized - limited or not limited. Restrictions can relate to both the length of the queue and the waiting time, "service discipline".
So, for example, the following QS are considered:
· QS with impatient requests (queue length and service time is limited);
· QS with priority service, i.e. some applications are served out of turn, etc.
In addition, QS are divided into open QS and closed QS.
In open CMO the characteristics of the flow of applications do not depend on the state of the QS itself (how many channels are busy). In a closed QS- depend. For example, if one worker maintains a group of machines that from time to time require adjustment, then the intensity of the flow of "requirements" from the machines depends on how many of them are already in good order and waiting for adjustment.
The classification of CMOs is far from being limited to the above varieties, but this is enough.
Consider the simplest QS with expectation - a single-channel system (n - 1), which receives a flow of requests with intensity ; service intensity (i.e., on average, a continuously busy channel will issue serviced requests per unit (time). A request that arrived at the moment when the channel is busy becomes queued and awaits service.
A system with a limited queue length. Assume first that the number of places in the queue is limited by the number m, i.e. if a customer arrives at a time when there are already m-customers in the queue, it leaves the system unserved. In the future, if m tends to infinity, we obtain the characteristics of a single-channel QS without restrictions on the queue length.
We will number the QS states according to the number of requests in the system (both serviced and awaiting service):
The channel is free;
The channel is busy, there is no queue;
The channel is busy, one application is in the queue;
The channel is busy, k-1 requests are in the queue;
The channel is busy, t-applications are in the queue.
The GSP is shown in fig. 4. All the intensities of the flows of events that transfer to the system along the arrows from left to right are equal, and from right to left - . Indeed, according to the arrows from left to right, the system is transferred by the flow of requests (as soon as a request arrives, the system goes to the next state), from right to left - the flow of “releases” of a busy channel, which has an intensity (as soon as the next request is served, the channel will either become free or decrease the number of applications in the queue).
Rice. 4. Single-channel QS with waiting
Shown in fig. 4 scheme is a scheme of reproduction and death. Let us write expressions for the limiting probabilities of states:
(5)
or using: :
(6)
The last line in (6) contains a geometric progression with the first term 1 and the denominator p, from which we get:
(7)
in connection with which the marginal probabilities take the form:
(8).
Expression (7) is valid only for< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Let us define the characteristics of the QS: the probability of failure, the relative throughput q, the absolute throughput A, the average queue length, the average number of applications associated with the system, the average waiting time in the queue, the average residence time of the application in the QS.
Failure probability. Obviously, the request is rejected only in the case when the channel is busy and all m-places in the queue are also:
(9).
Relative throughput:
(10).
Average queue length. Let's find the average number of -applications in the queue as the mathematical expectation of a discrete random variable R-number of applications in the queue:
With probability, there is one application in the queue, with probability - two applications, in general, with probability, there are k-1 applications in the queue, etc., whence:
(11).
Since , the sum in (11) can be treated as a derivative with respect to the sum of a geometric progression:
Substituting this expression into (11) and using from (8), we finally obtain:
(12).
The average number of claims in the system. Next, we obtain a formula for the average number of -requests associated with the system (both in the queue and in service). Since , where is the average number of applications under service, and k is known, it remains to determine . Since there is only one channel, the number of serviced requests can be 0 (with probability ) or 1 (with probability 1 - ), whence:
.
and the average number of applications associated with QS is:
(13).
Average waiting time for an application in the queue. Let's denote it; if a claim arrives in the system at some point in time, then with probability the service channel will not be busy and it will not have to queue (the waiting time is zero). With probability, it will come into the system during the service of some application, but there will be no queue in front of it, and the application will wait for the start of its service for a period of time (the average time for servicing one application). With probability, there will be one more in the queue before the considered application, and the average waiting time will be equal to , and so on.
If k=m+1, i.e. when a newly incoming customer finds the service channel busy and there are m-customers in the queue (probability of this is ), then in this case the customer does not queue (and is not served), so the waiting time is zero. The average waiting time will be:
if we substitute expressions for probabilities (8) here, we get:
(14).
Here relations (11), (12) (derivative of a geometric progression), as well as from (8) are used. Comparing this expression with (12), we notice that, in other words, the average waiting time is equal to the average number of applications in the queue, divided by the intensity of the flow of applications.
(15).
Average residence time of a request in the system. Let's denote - the expectation of a random variable - the time of the application's stay in the QS, which is the sum of the average waiting time in the queue and the average service time . If the system load is 100%, obviously, otherwise:
.
Example 1. A filling station (gas station) is a QS with one service channel (one column).
The site at the station allows no more than three cars to stay in the queue for refueling at the same time (m = 3). If there are already three cars in the queue, the next car that arrives at the station does not queue. The flow of cars arriving for refueling has an intensity = 1 (car per minute). The refueling process lasts an average of 1.25 minutes.
Define:
failure probability;
relative and absolute capacity of gas stations;
average number of cars waiting for refueling;
the average number of cars at the gas station (including serviced);
average waiting time for a car in the queue;
the average time the car stays at the gas station (including service).
In other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the flow of applications.
We first find the reduced intensity of the flow of applications: =1/1.25=0.8; =1/0.8=1.25.
According to formulas (8):
The probability of failure is 0.297.
Relative capacity of QS: q=1-=0.703.
The absolute throughput of the QS: A==0.703 cars per minute.
The average number of cars in the queue is found by the formula (12):
those. the average number of cars waiting in line for a gas station is 1.56.
Adding to this value the average number of cars under service:
we get the average number of cars associated with the gas station.
The average waiting time for a car in the queue according to the formula (15):
Adding to this value, we get the average time that the car spends at the gas station:
Systems with unlimited waiting. In such systems, the value of m is not limited and, therefore, the main characteristics can be obtained by passing to the limit in the previously obtained expressions (5), (6), etc.
Note that in this case the denominator in the last formula (6) is the sum of an infinite number of members of a geometric progression. This sum converges when the progression is infinitely decreasing, i.e. at<1.
It can be proven that<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
If, then relations (8) take the form:
(16).
If there are no restrictions on the length of the queue, each request that comes into the system will be serviced, therefore q=1, 
.
The average number of requests in the queue is obtained from (12) with :
The average number of applications in the system according to formula (13) for :
.
We obtain the average waiting time from formula (14) for:
.
Finally, the average residence time of an application in the QS is:
A system with a limited queue length. Consider a channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel) ; the number of seats in the queue.
The system states are numbered according to the number of requests connected by the system:
no queue:
All channels are free;
One channel is busy, the rest are free;
Busy -channels, the rest are not;
All channels are occupied, there are no free ones;
there is a queue:
All n-channels are occupied; one application is in the queue;
All n-channels are occupied, r-requests in the queue;
All n-channels are occupied, r-orders are in the queue.
GSP is shown in fig. 17. Each arrow has corresponding intensities of event streams. According to the arrows from left to right, the system is always transferred by the same flow of requests with intensity , according to the arrows from right to left, the system is transferred by a service flow, the intensity of which is equal to, multiplied by the number of busy channels.
Rice. 17. Multichannel QS with waiting
The graph is typical for the processes of reproduction and death, for which the solution was previously obtained. Let's write expressions for the limiting probabilities of states using the notation : (here we use the expression for the sum of a geometric progression with the denominator ).
Thus, all state probabilities are found.
Let us define the characteristics of the system efficiency.
Failure probability. An incoming request is rejected if all n-channels and all m-places in the queue are occupied:
(18)
The relative throughput complements the failure probability to one:
Absolute throughput of QS:
(19)
Average number of busy channels. For CMOs with failures, it coincided with the average number of applications in the system. For QS with a queue, the average number of busy channels does not coincide with the average number of requests in the system: the latter value differs from the first by the average number of requests in the queue.
Let us denote the average number of busy channels . Each busy channel serves on average - requests per unit of time, and the QS as a whole serves on average A - requests per unit of time. Dividing one by the other, we get:
The average number of requests in the queue can be calculated directly as the mathematical expectation of a discrete random variable:
(20)
Here again (expression in brackets) the derivative of the sum of a geometric progression occurs (see above (11), (12) - (14)), using the ratio for it, we get:
Average number of applications in the system:
Average waiting time for an application in the queue. Let us consider a number of situations that differ in the state in which a newly arrived request will find the system and how long it will have to wait for service.
If the entity does not find all channels busy, it will not have to wait at all (the corresponding terms in the mathematical expectation are equal to zero). If the request arrives at the moment when all n-channels are occupied, and there is no queue, it will have to wait on average for a time equal to (because the “release flow” of -channels has intensity ). If a customer finds all channels busy and one customer in front of it in the queue, it will have to wait on average for a period of time (for each customer in front), etc. time . If a newly arrived customer finds already m-customers in the queue, then it will not wait at all (but will not be served either). We find the average waiting time by multiplying each of these values by the corresponding probabilities:
(21)
Just as in the case of a single-channel QS with waiting, we note that this expression differs from the expression for the average queue length (20) only by the factor , i.e.
.
The average residence time of a request in the system, as well as for a single-channel QS, differs from the average waiting time by the average service time multiplied by the relative throughput:
.
Systems with unlimited queue length. We have considered a channel QS with waiting, when no more than m-customers can be in the queue at the same time.
Just as before, when analyzing systems without restrictions, it is necessary to consider the obtained relations for .
We obtain the probabilities of states from the formulas by passing to the limit (at ). Note that the sum of the corresponding geometric progression converges at and diverges at >1. Assuming that<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Probability of failure, relative and absolute throughput. Since each request will be served sooner or later, the QS throughput characteristics will be:
The average number of requests in the queue is obtained from (20):
,
and the average waiting time is from (21):
.
The average number of busy channels, as before, is determined in terms of the absolute throughput:
.
The average number of customers associated with the QS is defined as the average number of customers in the queue plus the average number of customers under service (the average number of busy channels):
Example 2. A gas station with two dispensers (n = 2) serves a flow of cars with a rate of =0.8 (cars per minute). Average service time per machine:
There is no other gas station in the area, so the queue of cars in front of the gas station can grow almost indefinitely. Find the characteristics of the QS.
Insofar as<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
etc.
We find the average number of occupied channels by dividing the absolute throughput of QS A==0.8 by the service intensity=0.5:
The probability of no queue at the gas station will be:
Average number of cars in the queue:
Average number of cars at filling stations:
Average waiting time in queue:
Average time a car stays at a gas station:
CMO with limited waiting time. Previously, we considered systems with waiting limited only by the queue length (the number of m-customers simultaneously in the queue). In such a QS, a claim that has grown into a queue does not leave it until it waits for service. In practice, there are QS of another type, in which the application, after waiting for some time, can leave the queue (the so-called "impatient" applications).
Consider a QS of this type, assuming that the waiting time constraint is a random variable.
Let us assume that there is an n-channel waiting QS in which the number of places in the queue is not limited, but the time spent in the queue by a customer is some random variable with an average value, so that each customer in the queue is subject to a kind of Poisson " care flow" with intensity:
If this flow is Poisson, then the process occurring in the QS will be Markov. Let us find the probabilities of states for it. The numbering of system states is associated with the number of requests in the system - both served and queued:
no queue:
All channels are free;
One channel is busy;
Two channels are busy;
All n-channels are occupied;
there is a queue:
All n-channels are occupied, one application is in the queue;
All n-channels are busy, r-requests are in the queue, etc.
The graph of states and transitions of the system is shown in fig. 23.
Rice. 23. QS with limited waiting time
Let's label this graph as before; all arrows leading from left to right will have the intensity of the flow of applications. For states without a queue, the arrows leading from them from right to left will, as before, have the total intensity of the service flow of all busy channels. As for the states with a queue, the arrows leading from them from right to left will have the total intensity of the service flow of all n-channels plus the corresponding intensity of the flow of departures from the queue. If there are r-orders in the queue, then the total intensity of the flow of departures will be equal to .
As can be seen from the graph, there is a pattern of reproduction and death; applying general expressions for the limiting probabilities of states in this scheme (using the abbreviated notation , we write:
(24)
Let us note some features of QS with limited waiting in comparison with the previously considered QS with “patient” requests.
If the queue length is not limited and the customers are “patient” (do not leave the queue), then the stationary limit mode exists only in the case (for , the corresponding infinite geometric progression diverges, which physically corresponds to the unlimited growth of the queue for ).
On the contrary, in a QS with "impatient" customers leaving the queue sooner or later, the steady-state service mode is always achieved, regardless of the reduced intensity of the customer flow . This follows from the fact that the series for in the denominator of formula (24) converges for any positive values of and .
For CMOs with "impatient" applications, the concept of "probability of failure" does not make sense - each application gets in line, but may not wait for service, leaving ahead of time.
Relative throughput, the average number of applications in the queue. The relative throughput q of such a QS can be calculated as follows. Obviously, all applications will be served, except for those that leave the queue ahead of schedule. Let us calculate the average number of requests that leave the queue ahead of schedule. To do this, we calculate the average number of applications in the queue:
For each of these requests, there is a “flux of exits” with an intensity of . This means that from the average number of -requests in the queue, on average, -requests will leave without waiting for service, -requests per unit of time and only -requests will be serviced on average per unit of time. The relative throughput of the QS will be:
The average number of busy channels is still obtained by dividing the absolute throughput A by:
(26)
The average number of applications in the queue. Relation (26) allows us to calculate the average number of requests in the queue without summing the infinite series (25). From (26) we get:
and the average number of busy channels included in this formula can be found as the mathematical expectation of a random variable Z, which takes the values 0, 1, 2,..., n with probabilities ,:
In conclusion, we note that if in formulas (24) we pass to the limit at (or, which is the same, at ), then formulas (22) will be obtained, i.e., “impatient” requests will become “patient”.
So far, we have considered systems in which the incoming flow is not connected in any way with the outgoing one. Such systems are called open. In some cases, the serviced requests, after a delay, again enter the input. Such QS are called closed. A polyclinic serving a given area, a team of workers assigned to a group of machines, are examples of closed systems.
In a closed QS, the same finite number of potential requirements circulate. Until a potential requirement has been realized as a service requirement, it is considered to be in a delay block. At the time of implementation, it enters the system itself. For example, workers service a group of machines. Each machine is a potential requirement, turning into a real one the moment it breaks down. While the machine is running, it is in the delay unit, and from the moment of breakdown until the end of the repair, it is in the system itself. Each worker is a service channel.
Let be n- number of service channels, s- number of potential applications, n <s , - the intensity of the flow of applications for each potential requirement, μ - the intensity of service:
The probability of system downtime is determined by the formula
R
0
= 
.
Final probabilities of system states:
P k= at k
These probabilities express the average number of busy channels
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+Ps) or
=P 1 + 2P 2 +…+(n- 1)Pn- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Through we find the absolute bandwidth of the system:
as well as the average number of applications in the system
M=s- =s- .
Example 1. The input of a three-channel QS with failures receives a flow of applications with an intensity \u003d 4 requests per minute, time for servicing an application by one channel t service =1/μ =0.5 min. Is it advantageous from the point of view of QS throughput to force all three channels to serve applications at once, and the average service time is reduced by a factor of three? How will this affect the average time an application spends in the CMO?
Solution. We find the downtime probability of a three-channel QS by the formula
ρ = /μ=4/2=2, n=3,
P 0 = = = 0,158.
The probability of failure is determined by the formula:
P otk \u003d P n ==
P otk = 0.21.
Relative throughput of the system:
P service = 1-R otk 1-0,21=0,79.
Absolute system bandwidth:
A= P service 3,16.
The average number of busy channels is determined by the formula:
1.58, the share of channels occupied by the service,
q = 0,53.
The average residence time of an application in the QS is found as the probability that the application is accepted for service, multiplied by the average service time: t QS 0.395 min.
Combining all three channels into one, we obtain a single-channel system with parameters μ= 6, ρ= 2/3. For a single-channel system, the downtime probability is:
R 0 = = =0,6,
failure probability:
P open =ρ P 0 = = 0,4,
relative throughput:
P service = 1-R otk =0,6,
absolute bandwidth:
A=P service = 2.4.
t CMO = R service= =0.1 min.
As a result of combining channels into one, the system throughput has decreased, since the probability of failure has increased. The average residence time of an application in the system has decreased.
Example 2. The input of a three-channel QS with an unlimited queue receives a flow of requests with intensity =4 requests per hour, average service time for one request t=1/μ=0.5 h. Find the performance indicators of the system.
For the considered system n =3, =4, μ=1/0.5=2, ρ= /µ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
The average number of applications in the queue is found by the formula:
L
=
.
L = = .
The average waiting time for an application in the queue is calculated by the formula:
t= = 0.22 h.
Average residence time of an application in the system:
T=t+ 0,22+0,5=0,72.
Example 3. There are 3 masters working in the hairdressing salon, and 3 chairs in the waiting room. The flow of customers has intensity =12 clients per hour. Average service time t service = 20 min. Determine the relative and absolute throughput of the system, the average number of occupied seats, the average length of the queue, the average time that the client spends in the hairdresser.
For this task n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. The probability of downtime is determined by the formula:
R
0
=
.
P
0
= 
0,012.
The probability of denial of service is determined by the formula
P otk \u003d P n + m \u003d .
P open =P n + m 0,307.
Relative throughput of the system, i.e. Service Probability:
P service =1-P open 1-0,307=0,693.
Absolute Bandwidth:
A= P service 12 .
Average number of busy channels:
.
The average queue length is determined by the formula:
L
=
L= 
1,56.
Average waiting time for service in queue:
t= h.
Average number of applications in CMO:
M=L + .
Average residence time of an application in the CMO:
T=M/ 0.36 h
Example 4. The worker serves 4 machines. Each machine fails with intensity =0.5 failures per hour, mean time to repair t rem\u003d 1 / μ \u003d 0.8 h. Determine the throughput of the system.
This problem considers a closed QS, μ =1.25, ρ=0.5/1.25=0.4. The probability of downtime for a worker is determined by the formula:
R
0
=
.
P
0
= 
.
Worker Employment Probability R zan = 1-P 0 . A=( 1-P 0 )μ =0.85μ machines per hour.
A task:
Two workers serve a group of four machines. Stops of a running machine occur on average after 30 minutes. The average setup time is 15 minutes. Operating time and setup time are distributed exponentially.
Find the average share of free time for each worker and the average time the machine is running.
Find the same characteristics for a system where:
a) two machines are assigned to each worker;
b) two workers always serve the machine together, and with double intensity;
c) the only faulty machine is served by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first describe the system in terms of the processes of death and birth).
Solution:
The following states of the system S are possible:
S 0 - all machines are operational;
S 1 - 1 machine is being repaired, the rest are serviceable;
S 2 - 2 the machine is being repaired, the rest are in good order;
S 3 - 3 the machine is being repaired, the rest are in good order;
S 4 - 4 the machine is being repaired, the rest are in good order;
S 5 - (1, 2) machines are being repaired, the rest are in good order;
S 6 - (1, 3) machines are being repaired, the rest are in good order;
S 7 - (1, 4) machines are being repaired, the rest are in good order;
S 8 - (2, 3) machines are being repaired, the rest are in good order;
S 9 - (2, 4) machines are being repaired, the rest are in good order;
S 10 - (3, 4) machines are being repaired, the rest are in good order;
S 11 - (1, 2, 3) machines are being repaired, 4 the machine is serviceable;
S 12 - (1, 2, 4) machines are being repaired, 3 the machine is serviceable;
S 13 - (1, 3, 4) machines are being repaired, 2 the machine is serviceable;
S 14 - (2, 3, 4) machines are being repaired, 1 machine is serviceable;
S 15 - all machines are repaired.
System State Graph…
This system S is an example of a closed system, since each machine is a potential requirement, turning into a real one at the moment of its breakdown. While the machine is running, it is in the delay unit, and from the moment of failure until the end of the repair, it is in the system itself. Each worker is a service channel.
If the worker is busy, he sets up μ-machines per unit of time, the throughput of the system:
Answer:
The average share of free time for each worker is ≈ 0.09.
Average running time of the machine ≈ 3.64.
a) Each worker is assigned two machines.
The probability of a worker downtime is determined by the formula:
Worker Employment Probability:
If the worker is busy, he sets up μ-machines per unit of time, the throughput of the system:
Answer:
The average share of free time for each worker is ≈ 0.62.
The average time of the machine ≈ 1.52.
b) Two workers always serve the machine together, and with double intensity.
c) The only faulty machine is served by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first, describe the system in terms of death and birth processes).
Comparison of 5 answers:
The most effective way to organize workers at the machines will be the initial version of the problem.
Above, examples of the simplest queuing systems (QS) were considered. The concept of "simple" does not mean "elementary". Mathematical models of these systems are applicable and successfully used in practical calculations.
The possibility of applying decision theory in queuing systems is determined by the following factors:
1. The number of applications in the system (which is considered as a QS) should be large enough (massively).
2. All applications entering the QS input must be of the same type.
3. For calculations using formulas, it is necessary to know the laws that determine the receipt of applications and the intensity of their processing. Moreover, the application flows must be Poisson.
4. Structure of QS, i.e. the set of incoming requirements and the sequence of processing the application must be rigidly fixed.
5. It is necessary to exclude subjects from the system or describe them as requirements with a constant processing intensity.
To the limitations listed above, one more can be added, which has a strong influence on the dimension and complexity of the mathematical model.
6. The number of priorities used should be kept to a minimum. Application priorities must be constant, i.e. they cannot change during processing within the QS.
In the course of the work, the main goal was achieved - the main material “QS with limited waiting time” and “Closed QS”, which was set by the teacher of the academic discipline, was studied. We also got acquainted with the application of the acquired knowledge in practice, i.e. consolidated the material covered.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolution..
5) Fomin G.P. Mathematical methods and models in commercial activity. M: Finance and statistics, 2001.
6) Gmurman V.E. Theory of Probability and Mathematical Statistics. M: Higher School, 2001.
7) Sovetov B.A., Yakovlev S.A. Systems Modeling. M: Higher School, 1985.
8) Lifshits A.L. Statistical modeling of QS. M., 1978.
9) Wentzel E.S. Operations research. M: Nauka, 1980.
10) Wentzel E.S., Ovcharov L.A. Probability theory and its engineering applications. M: Nauka, 1988.
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 QS with a queue also occupy a special place (most of the analytical formulas obtained so far for non-Markovian 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 applications with intensity X; the service flow has an intensity reciprocal to the average service time of the request. It is required to find the final probabilities of the QS states, as well as the characteristics of its efficiency:
The average number of applications in the system,
Average residence time of an application in the system,
The average number of applications in the queue,
The average time an application spends in the queue,
The probability that the channel is busy (the degree of load on the channel).
As for the absolute throughput A and relative Q, there is no need to calculate them: due to the fact that the queue is unlimited, each application will be served sooner or later, therefore, for the same reason
Solution. The states of the system, as before, will be numbered according to the number of applications in the QS:
The channel is free
The channel is busy (serving the request), there is no queue,
The channel is busy, one application is in the queue,
The channel is busy, applications are in the queue,
Theoretically, the number of states is not limited by anything (infinitely). 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. According to all arrows, the flow of requests with intensity A transfers the system from left to right, and from right to left - the flow of services with intensity
First of all, let us ask ourselves, are there final probabilities in this case? After all, the number of system states is infinite, and, in principle, the queue can increase indefinitely! Yes, it is true: the final probabilities for such a QS do not always exist, but only when the system is not overloaded. It can be proved that if strictly less than one, then the final probabilities exist, and for , the queue increases without limit. This fact seems especially “incomprehensible” when it would seem that there are no impossible requirements for the system: during the service of one application, on average, one application comes in, and everything should be in order, but in reality it is not.
With QS, it copes with the flow of applications only if this flow is regular, and the service time is also not random, equal to the interval between applications. In this "ideal" case, there will be no queue in the QS at all, the channel will be continuously busy and will regularly issue serviced requests. But as soon as the flow of requests or the flow of services become at least a little random, the queue will already 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 the replacement of random variables by their mathematical expectations can lead to!
But let's get back to our single-channel QS with an unlimited queue. Strictly speaking, the formulas for the final probabilities in the scheme of death and reproduction were derived by us only for the case of a finite number of states, but let's take liberties - we will use them for an infinite number of states. Let us calculate the final probabilities of states according to formulas (19.8), (19.7). In our case, the number of terms in formula (19.8) will be infinite. We get an expression for
The series in formula (20.11) is a geometric progression. We know that when the series converges - this is an infinitely decreasing geometric progression with a denominator. For , the series diverges (which is an indirect, though not rigorous, proof that the final state probabilities exist only for ). Now suppose that this condition is satisfied, and Summing up the progression in (20.11), we have
(20.12)
The probabilities are found by the formulas:
whence, taking into account (20.12), we finally find:
As you can see, the probabilities form a geometric progression with the denominator . Oddly enough, the maximum of them is the probability that the channel will be free at all. No matter how busy a queuing system is, if it can handle the flow of requests at all, the most likely number of requests in the system will be 0.
Let's find the average number of applications in QS . Here you have to tinker a little. Random variable Z - the number of applications in the system - has possible values with probabilities
Its mathematical expectation is
(20.14)
(the sum is taken not from 0 to but from 1 to, since the zero term is equal to zero).
We substitute into formula (20.14) the expression for
Now let's take it out of the sum sign:
Here we again apply the “little trick”: there is nothing more than the derivative of pores from the expression means,
By interchanging the operations of differentiation and summation, we get:
But the sum in the formula (20.15) is nothing but the sum of an infinitely decreasing geometric progression with the first member and denominator; this sum is equal to and its derivative . Substituting this expression into (20.15), we get:
(20.16)
Well, now let's apply Little's formula (19.12) and find the average residence time of an application in the system:
Let's find the average number of requests in the queue. We will argue as follows: the number of requests in the queue is equal to the number of requests in the system minus the number of requests under service. Hence (by the rule of addition of mathematical expectations), the average number of applications in the queue is equal to the average number of applications in the system minus the average number of applications 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 as ). Obviously, it is equal to one minus the probability that the channel is free;
Therefore, the average number of requests under service is equal to
The system receives a Poisson flow of requirements with intensity λ, the service flow has intensity μ, the maximum number of places in the queue is T. If a claim enters the system when all places in the queue are filled, it leaves the system unserved.
The final probabilities of the states of such a system always exist, since the number of states is finite:
S 0 - the system is free and is idle;
S 1 - one request is served, the channel is busy, there is no queue;
S 2 - one application is served, one is in the queue;
S m +1 - one application is served, T queue.
The state graph of such a system is shown in Figure 5:
S 0 S 1 S 2 S m+1
μ μ μ ………. μ μ
Figure 5: Single-channel QS with limited queue.
In the formula for R 0 find the sum of a finite number of members of a geometric progression:
(52)
Taking into account the formula for ρ, we obtain the expression:
There are (m+2) elements of a geometric progression in parentheses with the first member 1 and the denominator ρ. According to the formula for the sum (m + 2) of the members of the progression:
(54)
(55)
The formulas for the probabilities of limit states will look like:
Denial of Service Probability We define a request as the probability that when a request enters the system, its channel will be occupied and all places in the queue are also occupied:
(57)
Hence the service probability(as well as from carrier bandwidth) are equal to the probabilities of the opposite event:
Absolute Bandwidth is the number of requests served by the system per unit of time:
(59)
Average number of requests under service:
(60)
(61)
Average number of applications in the system:
(62)
A single-channel QS with a limited queue can be considered in Mathcad.
Example:
The parking lot serves 3 cars with a flow rate of 0.5 and an average service time of 2.5 minutes. Determine all indicators of the system.
6 Multi-channel smoo with unlimited queue
Let a system S be given that has P service channels that receive the simplest flow of requests with intensity λ. Let the service flow also be the simplest and have intensity μ. The queue for service is not limited.
By the number of applications in the system, we denote the states of the system: S 0 ,S 1 ,S 2 ,…,S k ,… S n , where S k – the state of the system when there are k requests in it (the maximum number of requests under service is n). The state graph of such a system is depicted as a diagram in Figure 6:
λ λ λ λ λ λ λ
……. …….
S 0 S 1 S 2 S m+1 S n
μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ
Figure 6: Multichannel QS with unlimited queue.
The intensity of the flow of services varies depending on the state of the system: kμ upon transition from the state S k to the state S k -1 since any of the k channels; after all channels are occupied with service, the intensity of the flow of services remains equal to pμ, upon receipt of the following applications in the system.
To find the final probabilities of states, we obtain formulas similar to how it was done for a single-channel system.
(63)
Hence the formulas for the final probabilities are expressed in terms of
For finding R 0 we get the equation:
For the terms in brackets, starting from the (n + 2)th, you can apply the formula for finding the sum of an infinitely decreasing geometric progression with the first term 
and denominator ρ/n:
(66)
Finally, we obtain the Erlang formula for finding the probability of system downtime:
(67)
Let us give formulas for calculating the main indicators of the efficiency of the system.
The system will cope with the flow of requests if
condition
,
(68)
which means that the number of requests received by the system per unit of time does not exceed the number of requests served by the system during the same time. Wherein probability of denial of service equals zero.
From here service probability(as well as relative throughput systems) are equal to the probabilities of the opposite event, that is, to unity:
(69)
Absolutethroughput- the number of applications served by the system per unit of time:
(70)
If the system copes with the flow of applications, then in stationary mode outflow rate is equal to the intensity of the flow of requests entering the system, since all requests are serviced:
ν=λ . (71)
Since each channel serves μ requests per unit of time, then average busy channels can be calculated:
(72)
The averagetimeservice one application channel ;
.
(73)
The probability that, upon entering the system, an order will end up in a queue is equal to the probability that there are more than P applications:
(74)
The number of applications under service, is equal to the number of busy channels:
(75)
Average number of applications in the queue:
(76)
Then the averagenumberapplicationsin system:
(77)
Average residence time of an application in the system (in the queue):
(78)
(79)
A multi-channel QS with an unlimited queue can be considered in the Mathcad system.
Example 1:
The hairdressing salon has 5 masters. At rush hour, the intensity of the flow of customers is 6 people. At one o'clock. Service of one client lasts an average of 40 minutes. Determine the average length of the queue, assuming it is unlimited.
Fragment of solving the problem in Mathcad.
Example 2:
The railway ticket office has 2 windows. Time to serve one passenger is 0.5 minutes. Passengers approach the ticket office in groups of 3. Determine all characteristics of the system.
Fragment of solving the problem in Mathcad.
Continuation of the solution of the problem in Mathcad.
For CMO with failures:
For CMO with unlimited waiting both absolute and relative throughput lose their meaning, since each incoming request will be served sooner or later. For such a QS, important indicators are:
For CMO mixed type both groups of indicators are used: both relative and absolute bandwidth, and expectation characteristics.
Depending on the purpose of the queuing operation, any of the above indicators (or a set of indicators) can be selected as a performance criterion.
analytical model QS is a set of equations or formulas that allow you to determine the probabilities of system states during its operation and calculate performance indicators based on known characteristics of the incoming flow and service channels.
There is no general analytical model for an arbitrary QS. Analytical models have been developed for a limited number of special cases of QS. Analytical models that more or less accurately represent real systems are, as a rule, complex and difficult to see.
Analytical modeling of the QS is greatly facilitated if the processes occurring in the QS are Markovian (the flows of requests are simple, the service times are exponentially distributed). In this case, all processes in the QS can be described by ordinary differential equations, and in the limiting case, for stationary states - by linear algebraic equations and, having solved them, determine the selected performance indicators.
Let's consider examples of some QS.
2.5.1. Multichannel QS with failures
Example 2.5. Three traffic inspectors check the waybills of truck drivers. If at least one inspector is free, the passing truck is stopped. If all the inspectors are busy, the truck passes without stopping. The flow of trucks is the simplest, the check time is random with an exponential distribution.
Such a situation can be simulated by a three-channel QS with failures (without a queue). The system is open, with homogeneous applications, single-phase, with absolutely reliable channels.
Description of states:
All inspectors are free;
One inspector is busy;
Two inspectors are busy;
Three inspectors are busy.
The graph of system states is shown in fig. 2.11.
Rice. 2.11.
On the graph: - the intensity of the flow of trucks; - the intensity of document checks by one traffic inspector.
The simulation is carried out in order to determine the part of the cars that will not be tested.
Solution
The desired part of the probability is the probability of employment of all three inspectors. Since the state graph represents a typical scheme of "death and reproduction", we will find using dependencies (2.2).
The throughput of this post of traffic inspectors can be characterized relative throughput:
Example 2.6. To receive and process reports from the reconnaissance group, a group of three officers was assigned to the reconnaissance department of the association. The expected rate of reporting is 15 reports per hour. The average processing time of one report by one officer is . Each officer can receive reports from any reconnaissance group. The released officer processes the last of the received reports. Incoming reports must be processed with a probability of at least 95%.
Determine if the assigned group of three officers is sufficient to complete the assigned task.
Solution
A group of officers works as a CMO with failures, consisting of three channels.
The flow of reports with intensity 
can be considered the simplest, since it is the total of several reconnaissance groups. Maintenance intensity 
. The distribution law is unknown, but this is not essential, since it is shown that for systems with failures it can be arbitrary.
The description of the states and the state graph of the QS will be similar to those given in Example 2.5.
Since the state graph is a "death and reproduction" scheme, there are ready-made expressions for the limiting state probabilities for it:
The relation is called the reduced intensity of the flow of applications. Its physical meaning is as follows: the value is the average number of requests coming to the QS for the average service time of one request.
In the example 
.
In the considered QS, failure occurs when all three channels are busy, that is, . Then:
Because failure probability in the processing of reports is more than 34% (), then it is necessary to increase the personnel of the group. Let us double the composition of the group, that is, the QS will now have six channels, and calculate:
Thus, only a group of six officers will be able to process incoming reports with a probability of 95%.
2.5.2. Multichannel QS with waiting
Example 2.7. There are 15 crossing facilities of the same type in the river forcing section. The flow of equipment arriving at the crossing averages 1 unit/min, the average time of crossing one unit of equipment is 10 minutes (taking into account the return of the crossing facility).
Evaluate the main characteristics of the crossing, including the likelihood of an immediate crossing immediately upon the arrival of a piece of equipment.
Solution
Absolute Bandwidth, i.e. everything that comes to the crossing is almost immediately crossed.
Average number of operating crossing facilities:
Crossing utilization and downtime ratios:
A program was also developed to solve the example. The time intervals for the arrival of equipment at the crossing, the time of the crossing are taken to be distributed according to an exponential law.
The ferry utilization rates after 50 runs are practically the same: 
.
The maximum length of the queue is 15 units, the average time spent in the queue is about 10 minutes.
Waiting Systems with Unlimited Input
The simplest flow of requests arrives on n identical channels with intensity λ . If at the time of receipt of the request all channels are busy, then this request is placed in a queue and waits for the start of service. The service time of each request is a random variable that obeys the exponential distribution law with the parameter μ .Calculation formulas
Probability that all channels are free
Probability of being busy k channels, provided that the total number of applications in service does not exceed the number of channels,
The probability that the system is k applications, in the case when their number is greater than the number of channels,
The probability that all channels are busy
Average waiting time for a request to start service in the system
Average queue length
Average number of idle channels
A gas station with two columns serves a Poisson flow of cars with an intensity of λ=0.8 cars per minute. The service time of one machine obeys an exponential law with an average value of 2 minutes. There is no other gas station in the area, so the queue in front of the gas station can grow almost indefinitely. Find:
1) the average number of busy columns;
2) the probability of no queue at the gas station;
3) the probability that you will have to wait for the start of the service;
4) the average number of cars in the queue;
5) average waiting time in the queue;
6) the average time spent by the car at the gas station;
7) the average number of cars at gas stations.
Solution. By the condition of the problem n=2, λ=0.8; μ=1/t service =0.5; ρ=λ/μ=1.6
Insofar as ρ /n=0,8<1, то очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы системы массового обслуживания.
We find the probabilities of QS states:
Average number of busy columns:
N zan \u003d n-N 0 \u003d 2- (2 p 0 +1 p 1) \u003d 2-2 0.1111 - 0.1778 \u003d 1.6
Probability of no queue at the gas station:
The probability of having to wait for service to start is equal to the probability that all columns are busy:
p0 +p1 +p2 = 0.1111+0.1778+0.1422 = 0.4311
Average number of cars in the queue:
Average waiting time in queue:
Average time a car stays at a gas station:
t preb \u003d t service + t cool \u003d 2 + 3.5556 \u003d 5.5556 min.
Average number of cars at filling stations:
N zan + L och = 1.6+2.8444 = 4.4444
Consider a single-channel QS with expectations, in which the number of channels is equal to one n= 1, the intensity of receipt of requests is λ, the intensity of service is equal to μ. A request that arrives at a time when the channel is busy gets queued and waits for service. The number of places in the queue is limited and equal to m. If all places in the queue are occupied, then the application leaves the queue unserved. Let's analyze the state of the system:
- S 0 – channel is free;
- S 1 – the channel is busy;
- S 2 – the channel is busy, one request is in the queue;
- Sk– the channel is busy, (k–1) requests in the queue;
- Sm+ 1 - the channel is busy, queued m applications.
Rice. 25
Using the Erlang formulas, we find the probabilities of events that the QS is in the state S 1 , S 2 , …, S m+1: 
(28)
In this case, the probability that a claim arriving in the system will find it free is equal to 
. (29)
The ratio of the intensity of receipt of requests λ to the intensity of servicing requests μ is the reduced intensity μ, i.e.
ρ=λ/μ
Let us replace the relation λ/&mu by ρ in formulas (28) and (29), then the expressions will take the form:
(30)
Probability R 0 will be calculated using the following formula:
p 0 = -1 . (31)
Expression for probability P 0 is a geometric progression, the sum of which will be equal to
.
Thus, formulas (30) and (31) make it possible to determine the probability of any event that can occur in the system, i.e., to determine the probability of the system being in any state.
Formula for P 0 is valid for the case when ρ ≠ 1 . In the case when ρ = 1, i.e., the intensity of receipt of requests is equal to the intensity of their service, another formula is used to calculate the probability that the system is free:
,
where m is the number of applications in the queue.
Let's define performance characteristics of a single-channel QS:
- the probability that the next request that arrived in the system will be rejected R open;
- absolute throughput BUT,
- relative throughput Q,
- number of busy channels k ,
- average number of requests in queue r ,
- average number of applications associated with QS, z .
The next request that enters the system is rejected when the channel is busy, i.e. another request is being serviced, and that’s it. m places in the queue are also occupied. then the probability of this event can be calculated by the following formula:
. (32)
The probability that an application will come into the system and either be served immediately or there will be places in the queue, i.e. the relative throughput, can be found by the formula
. (33)
The average number of applications that can be served per unit of time, i.e., the absolute throughput, is calculated as follows:
A=Q λ (34)
Thus, formulas (32), (33), (34) can be used to calculate the main performance indicators for any queuing system. now we derive expressions for calculating the characteristics inherent only to this QS.
The average number of requests in the queue r is defined as the mathematical expectation of a discrete random variable, where R- the number of applications in the queue.
♦ R 2 is the probability that there is one application in the service queue;
♦ R 3 is the probability that there are two applications in the queue;
♦ Rk is the probability that there is an application in the queue (k–1);
♦ Rm+ 1 is the probability that there are m requests in the queue.
Then the average number of requests in the queue can be calculated as follows:
r =1 P 2 +2 P 3 + ... +(k-1) P k + ... + m P m+1 . (35)
Let us substitute into formula (35) the previously found probabilities calculated in formula (30):
r =1 ρ 2 p 0 +2 ρ 3 p 0 + ... +(k-1) ρ k p 0 + ... +m ρ m+1 p 0 . (35)
Let's factor out the probability P 0 and R 2 , then we get the final formula for calculating the average number of applications in the service queue:
r =ρ 2 p 0 (1+2 ρ+ ... +(k-1) ρ k-2 + ... +m ρ m-1)
Let us derive a formula for the average number of applications associated with the QS, z , i.e., the number of applications in the queue that are being serviced. Consider the total number of requests associated with the QS, z, as the sum of two values of the average number of requests in the queue r and the number of busy channels k:
z = r + k .
Since there is only one channel, the number of busy channels k can take the values 0 or 1. The probability that k = 0, i.e. the system is free, corresponds to the probability P 0 , the value of which can be found by formula (31). If k = 1, i.e. the channel is busy servicing the request, but there are still places in the queue, then the probability of this event can be calculated by the formula
.
Therefore, z will be equal to:
. (37)
Single-channel QS with waiting
The queuing system has one channel. The incoming flow of service requests is the simplest flow with intensity l. The intensity of the service flow is equal to m (i.e., on average, a continuously busy channel will issue m. serviced requests). Service duration is a random variable subject to an exponential distribution law. The service flow is the simplest Poisson flow of events. A request that arrives at a time when the channel is busy is queued and awaits service.Suppose that no matter how many requests enter the input of the serving system, this system (queue + clients being served) cannot accommodate more than N-requirements (requests), i.e., clients that are not waiting are forced to be served elsewhere . Finally, the source that generates service requests has an unlimited (infinitely large) capacity.
The QS state graph in this case has the form shown in Fig. 3.2.
Graph of States of a Single-Channel Queuing System with Waiting (Death and Breeding Scheme)
QS states have the following interpretation:
S 0 - channel is free
S 1 - the channel is busy (there is no queue);
S 2 - the channel is busy (one request is in the queue);
………………………………
S n - the channel is busy (n - 1 requests are in the queue);
……………………………
S N - the channel is busy (N - 1 requests are in the queue).
The stationary sag in this system will be described by the following system of algebraic equations:
P - state number.
The solution of the above system of equations (3.10) for our QS model has the form
It should be noted that the fulfillment of the stationarity condition for this QS is not necessary, since the number of requests admitted to the serving system is controlled by introducing a restriction on the queue length (which cannot exceed N- 1), and not the ratio between the intensities of the input stream, i.e., not the ratio
l/m = p
Let's define characteristics of a single-channel QS with a wait and a limited queue length equal to (N - 1):
Consider an example of a single-channel QS with waiting.
Example 3.2. A specialized diagnostic post is a single-channel QS. The number of parking lots for cars waiting for diagnostics is limited and equal to 3 [(N- 1) = 3]. If all the parking lots are occupied, i.e. there are already three cars in the queue, then the next car that arrived for diagnostics does not get into the service queue. The flow of cars arriving for diagnostics is distributed according to the Poisson law and has an intensity l= 0.85 (vehicles per hour). The time of car diagnostics is distributed according to the exponential law and equals 1.05 hours on average.
Required to define probabilistic characteristics of the diagnostic post operating in stationary mode.
Solution
1. Car maintenance flow parameter:
2. The reduced intensity of the flow of cars is defined as the ratio of the intensities l and m, i.e.
3. Calculate the final probabilities of the system:
P 1 \u003d ρ P 0 \u003d 0.893 0.248 \u003d 0.221
P 2 \u003d ρ 2 P 0 \u003d 0.893 2 0.248 \u003d 0.198
P 3 \u003d ρ 3 P 0 \u003d 0.893 3 0.248 \u003d 0.177
P 4 \u003d ρ 4 P 0 \u003d 0.893 2 0.248 \u003d 0.158
4. The probability of refusal to service the car:
P open \u003d P 4 \u003d ρ 4 P 0 ≈ 0.158
5. Relative throughput of the diagnostic post:
q=1-P open = 1-0.158 = 0.842
6. Absolute throughput of the diagnostic post
A=λ q = 0.85 0.842 = 0.716 (vehicles per hour)
7. The average number of cars in service and in the queue (i.e. in the queuing system):
8. Average time spent by a car in the system:
9. Average length of stay of an application in the service queue:
W q \u003d W S -1 / μ \u003d 2.473-1 / 0.952 \u003d 1.423 hours
10. Average number of applications in the queue (queue length): L q= A, (1 - P N) W q= 0,85
L q \u003d λ (1-P N) W q \u003d 0.85 (1-0.158) 1.423 \u003d 1.02
The work of the considered diagnostic post can be considered satisfactory, since the diagnostic post does not service cars in an average of 15.8% of cases. (R otk= 0.158). As indicators of the effectiveness of the QS with expectation, in addition to the already known indicators - the absolute A and relative Q throughput, the probability of failure P otk. , average number of occupied channels (for a multichannel system), we will also consider the following: L syst. - average number of requests to the system; T sist. - average residence time of the application in the system; L - average number of applications in the queue (queue length); T och. - average time of stay of the application in the queue; Р zan .. - the probability that the channel is busy (the degree of channel load).
Single channel system with unlimited queue
In practice, one-channel QS with an unlimited queue is often encountered (for example, a pay phone with one booth).Let's consider the task.
There is a single-channel QS with a queue on which no restrictions are imposed (neither on the length of the queue, nor on the waiting time). The flow of requests arriving at the QS has an intensity λ, and the service flow has an intensity μ. It is necessary to find the limiting probabilities of states and indicators of QS efficiency.
The system can be in one of the states S 0 , S 1 , S 2 , …, S k , according to the number of applications in the QS: S 0 - the channel is free; S 1 - the channel is busy (serves the request), there is no queue, S 2 - the channel is busy, one request is in the queue; ... S k - the channel is busy, (k-1) requests are in the queue, etc.
The QS state graph is shown in fig. 8.
Rice. 8
This is a process of death and reproduction, but with an infinite number of states, in which the intensity of the flow of applications is equal to λ, and the intensity of the flow of service is μ.
Before writing down the formulas for the limiting probabilities, it is necessary to be sure of their existence, because in the case when the time t→∞, the queue can grow indefinitely. Proved that ifρ<1, those. the average number of incoming requests is less than the average number of serviced requests (per unit time), then there are marginal probabilities. Ifρ≥1, the queue grows to infinity.
To determine the limiting probabilities of states, we use formulas (16), (17) for the process of death and reproduction (here we allow a certain lack of strictness, since these formulas were previously obtained for the case of a finite number of system states). Get(32)
Since limiting probabilities exist only for ρ< 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
p 0 =1-ρ, (33)
and taking into account relations (17)
p 1 \u003d p p 0; p 2 \u003d p 2 p 0; ... ; p k =ρ k p 0 ; ...
find the limiting probabilities of other states
p 1 =ρ·(1-ρ); p 2 =ρ 2 (1-ρ); ... ; p k =ρ k ·(1-ρ); ... (34)
Limit probabilities p 0 , p 1 , p 2 , …, p k ,… form a decreasing geometric profession with denominator p< 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
The average number of applications in the system L sist. we define by the formula of mathematical expectation, which, taking into account (34), takes the form 
(35)
(summation from 1 to ∞, since the zero term 0·p 0 =0).
It can be shown that formula (35) is transformed (for ρ< 1) к виду
(36)
Find the average number of applications in the queue L och. It's obvious that
L Pts \u003d L syst -L about (37)
where L about. - the average number of applications under service.
The average number of requests under service is determined by the formula of the mathematical expectation of the number of requests under service, which takes the values 0 (if the channel is free) or 1 (if the channel is busy):
L Pts \u003d 0 p 0 +1 (1-p 0)
those. the average number of requests under service is equal to the probability that the channel is busy:
L och \u003d P zan \u003d 1-p 0, (38)
Force (33)
L och \u003d P zan ρ, (39)
Now, according to formula (37), taking into account (36) and (39),
(40)
Proved that for any nature of the flow of applications, for any distribution of service time, for any discipline of service, the average residence time of an application in the system (queue) is equal to the average number of applications in the system (in the queue) divided by the intensity of the flow of applications, those. 
(41)
(42)
Formulas (41) and (42) are called Little's formulas. They stem from the fact that in the limiting, stationary mode, the average number of customers arriving in the system is equal to the average number of customers leaving it: both streams of applications have the same intensity λ.
Based on formulas (41) and (42), taking into account (36) and (40), the average residence time of an application in the system is determined by the formula: 
(43)
and the average time an application spends in the queue
(44)
Single-channel QS with waiting without limitation on the capacity of the waiting block
The stationary mode of operation of this QS exists at t→∞ for any n=0,1,2,… and when l< m.Система алгебраических уравнений, описывающих работу СМО при t®¥ для любого n = 0, 1, 2...., имеет видThe solution of this system of equations has the form
P n =(1-ρ) ρ n , n=0,1,2,... (3.21)
where ρ=λ/μ< 1
The characteristics of a single-channel latency QS, with no limit on queue length, are as follows:
average number of customers (requests) in the system for service:
average length of stay of a client in the system:
Example 3.3. Let us recall the situation considered in Example 3.2, where we are talking about the functioning of the diagnostic post. Let the diagnostic post under consideration have an unlimited number of parking areas for cars arriving for service, i.e., the length of the queue is not limited.
It is required to determine the final values of the following probabilistic characteristics:
- probabilities of system states (diagnostic post);
- the average number of cars in the system (in service and in the queue);
- the average duration of the car's stay in the system (in service and in the queue);
- the average number of cars in the service queue;
- the average length of time a vehicle spends in a queue.
Solution
1. The service flow parameter m and the reduced car flow rate p are defined in example 3.2:
m = 0.952; p = 0.893.
2. Calculate the limiting probabilities of the system using the formulas
P 0 \u003d 1-ρ \u003d 1-0.893 \u003d 0.107
P 1 \u003d (1-ρ) ρ \u003d (1-0.893) 0.893 \u003d 0.096
P 2 \u003d (1-ρ) ρ 2 \u003d (1-0.893) 2 0.893 \u003d 0.085
P 3 \u003d (1-ρ) ρ 3 \u003d (1-0.893) 3 0.893 \u003d 0.076
P 4 \u003d (1-ρ) ρ 4 \u003d (1-0.893) 4 0.893 \u003d 0.068
P 5 \u003d (1-ρ) ρ 5 \u003d (1-0.893) 5 0.893 \u003d 0.061
etc.
It should be noted that R o determines the proportion of time during which the diagnostic post is forced to be inactive (idle). In our example, it is 10.7%, since R o= 0,107.
3. Average number of cars in the system (in service and in the queue):
4. Average length of stay of a client in the system:
6. The average length of stay of the car in the queue -
7. Relative throughput of the system:
i.e., each request that enters the system will be served.
8. Absolute bandwidth: BUT= l q= 0.85 1 = 0.85
It should be noted that an enterprise that performs car diagnostics is primarily interested in the number of customers that will visit the diagnostic post when the restriction on the queue length is removed.
Suppose in the original version the number of parking spaces for arriving cars was three (see example 3.2). The frequency m of occurrence of situations when a car arriving at the diagnostic post is not able to join the queue:
T= l P N
In our example, with N = 3 + 1 = 4 and p = 0.893,
m \u003d l P o p 4 \u003d 0.85 0.248 0.8934 0.134 cars per hour.
With a 12-hour operation mode of the diagnostic post, this is equivalent to the fact that the diagnostic post on average per shift (day) will lose 12 0.134 = 1.6 vehicles.
Removing the limit on the length of the queue makes it possible to increase the number of customers served in our example by an average of 1.6 vehicles per shift (12 hours of work) at the diagnostic post. It is clear that the decision to expand the parking area for cars arriving at the diagnostic site should be based on an assessment of the economic damage that is caused by the loss of customers with only three parking spaces for these cars.
Multi-channel QS with unlimited queue
Let's consider the problem. There is an n-channel QS with an unlimited queue. The flow of requests arriving at the QS has an intensity λ, and the service flow has an intensity μ. It is necessary to find the limiting probabilities of QS states and indicators of its efficiency.The system can be in one of the states S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - numbered according to the number of requests in the QS: S 0 - there are no requests in the system (all channels are free) ; S 1 - one channel is busy, the rest are free; S 2 - two channels are busy, the rest are free;..., S k - k channels are busy, the rest are free;..., S n - all n channels are busy (there is no queue); S n+1 - all n channels are occupied, there is one request in the queue;..., S n+r - all are occupied n channels, r Applications are queuing...
The system state graph is shown in fig. 9. Let's pay attention to the fact that, unlike the previous QS, the intensity of the service flow (transferring the system from one state to another from right to left) does not remain constant, but as the number of requests in the QS increases from 0 to n, it increases from m to nm , since the number of service channels increases accordingly. When the number of requests in the QS is greater than n, the intensity of the service flow remains equal to nm.
average number of applications in the queue 
, (50)
average number of applications in the system
L syst =L och +ρ, (51)
The average residence time of an application in the queue and the average residence time of an application in the system, as before, are found using the Little formulas (42) and (41).
Comment. For a QS with an unlimited queue for r< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q=1, and the absolute throughput is equal to the intensity of the incoming flow of applications, i.e. BUT=l.
QS with limited queue
QS with limited queue. QS with a bounded queue differ from the problems considered above only in that the number of applications in the queue is limited (cannot exceed some given T). If a new claim arrives at the moment when all places in the queue are occupied, it leaves the QS unserved, i.e. gets rejected.Obviously, to calculate the limiting probabilities of states and performance indicators of such QS, the same approach as above can be used, with the difference that it is necessary to summarize not an infinite progression (as, for example, we did when deriving formula (33)), but a finite .
The average residence time of an application in the queue and in the system, as before, is determined by Little's formulas (44) and (43).
CMO with limited waiting time. In practice, one often encounters CMOs with so-called "impatient" applications. Such requests may leave the queue if the waiting time exceeds a certain value. In particular, such applications arise in various technological systems, in which a delay in the start of service can lead to a loss in product quality, in operational management systems, when urgent messages lose value (or even meaning) if they do not arrive for service within a certain period of time. time.
In the simplest mathematical models of such systems, it is assumed that a request can be in the queue for a random time distributed according to an exponential law with some parameter υ, i.e. we can conditionally assume that each customer standing in the service queue can leave the system with the rate υ.
Appropriate indicators of the effectiveness of QS with a limited time are obtained on the basis of the results obtained for the process of death and reproduction.
In conclusion, we note that in practice there are often closed queuing systems , in which the incoming flow of requests depends significantly on the state of the QS itself. As an example, we can cite the situation when some machines come to the repair base from the places of operation: it is clear that the more machines are in a state of repair, the less they continue to be used and the less the intensity of the flow of new machines arriving for repair. Closed QS is characterized by a limited number of sources of requests, and each source is "blocked" for the duration of its request service (ie, it does not issue new requests). In such systems, with a finite number of QS states, limiting probabilities will exist for any values of the intensities of the flow of requests and service. They can be calculated if we turn again to the process of death and reproduction.
It might be useful to read:
- Radiation: impact on humans and its consequences;
- Arts and Crafts Download Presentation on Arts and Crafts;
- Presentation on the topic "Addition and subtraction of polynomials" Addition and subtraction of polynomials presentation;
- Radiation: impact on humans and its consequences;
- Open lesson "capacitors" Energy of a charged capacitor application of capacitors presentation;
- Presentation on the topic "Nikolai Nosov "Live Hat"";
- Presentation "globe" presentation for a lesson on the world around on the topic;
- Presentation on the topic: "A walk in kindergarten;