Let's consider a single-channel queuing system with waiting.
We will assume that the incoming flow of requests for service is the simplest flow with intensity λ.
The service flow intensity is μ. The duration of service is a random variable subject to the exponential distribution law. The service flow is the simplest Poisson flow of events.
A request received when the channel is busy is queued and awaits service. We will assume that the queue size is limited and cannot accommodate more than m applications, i.e. an application that found itself at the moment of its arrival at the CMO m +1 requests (m waiting in line and one being serviced) leaves the CMO.
The system of equations describing the process in this system has a solution:
(0‑1)
The denominator of the first expression is a geometric progression with the first term 1 and the denominator ρ, whence we get
At ρ = 1 you can resort to direct calculation
(0‑8)
The average number of applications in the system.
Since the average number of applications in the system
(0‑9)
where is the average number of applications under service, then knowing it remains to find. Because there is only one channel, then the number of serviced requests can be either 0 or 1 with the probabilities P 0 and P 1=1- P 0 accordingly, where from
(0‑10)
and the average number of applications in the system is
(0‑11)
Average waiting time for an application in queue.
i.e., the average waiting time for an application in the queue is equal to the average number of applications in the queue divided by the intensity of the application flow.
Average time an application stays in the system.
The time an application stays in the system is the sum of the application’s waiting time in the queue and the service time. If the system load is 100%, then =1/μ, otherwise = q/μ. From here
(0‑13)
Contents of the work.
Preparation of experimental instruments .
It is performed similarly in accordance with the general rules.
Calculation using an analytical model.
1. Prepare the following table in Microsoft Excel.
2. In the columns for the QS parameters of the table, write down the initial data that is determined according to the rule:
m=1,2,3
(maximum queue length).
For each value m it is necessary to find theoretical and experimental values of QS indicators for the following pairs of values:
= <порядковый номер в списке группы>
3. Enter the appropriate formulas in the columns with the analytical model indicators.
Experiment on a simulation model.
1. Set the launch mode with exponentially distributed service time by setting the value of the corresponding parameter to 1.
2. For every combination m , and run the model.
3. Enter the results of the runs into the table.
4. Enter formulas to calculate the average value of the indicator in the appropriate columns of the table P open, q and A.
Analysis of results .
1. Analyze the results obtained by theoretical and experimental methods, comparing the results with each other.
2. For m=3, plot the dependencies on one diagram P open from theoretically and experimentally obtained data.
Optimization of QS parameters .
Solve the problem of optimizing the size of the number of places in a queue m for a device with an average service time = from the point of view of obtaining maximum profit. As the conditions of the problem, take:
- income from servicing one application equal to 80 USD/hour,
- the cost of maintaining one device is equal to 1cu/hour.
1. For calculations, it is advisable to create a table:
The first column is filled with the values of the numbers in the natural series (1,2,3...).
All cells in the second and third columns are filled with and values.
The formulas for the columns of the table in section 0 are transferred to the cells of columns from the fourth to the ninth.
In the columns with the initial data of the Income, Expense, Profit sections, enter the values (see above).
In the columns with calculated values of the Income, Expense, Profit sections, write down the calculation formulas:
- number of applications per unit of time
N r =A
- total income per unit of time
I S = I r *N r
- total consumption per unit of time
E S =E s + E q *(n-1)
- profit per unit of time
P = I S - E S
Where
Ir - income from one application,
E s - operating cost of one device,
Eq - cost of operating one place in the queue.
Graphs for P open,
- table with data to find the best m and the value of m opt,
- graph of profit per unit of time versus m.
Security questions :
1) Give a brief description of the single-channel limited queue QS model.
2) What indicators characterize the functioning of a single-channel QS with failures?
3) How is the probability p calculated 0 ?
4) How are probabilities p calculated i?
5) How to find the probability of failure to service an application?
6) How to find relative bandwidth?
7) What is the absolute throughput?
8) How is the average number of applications in the system calculated?
9) Give examples of QS with a limited queue.
Tasks.
1) The port has one cargo berth for unloading ships. The flow rate is 0.5 visits per day. The average unloading time for one vessel is 2 days. If there are 3 vessels in the queue for unloading, then the arriving vessel is sent to another berth for unloading. Find berth performance indicators.
2) The railway station information desk receives telephone requests at an intensity of 80 requests per hour. The help desk operator answers an incoming call in an average of 0.7 minutes. If the operator is busy, the client receives the message “Wait for a response”; the request is placed in a queue, the length of which does not exceed 4 requests. Give an assessment of the work of the help desk and an option for its reorganization
Federal Agency for Education of the Russian Federation
FGOU SPO "Perevozsky Construction College"
Coursework
in the discipline "Mathematical methods"
on the topic “SMO with limited waiting time. Closed QS"
Introduction........................................................ ........................................................ ....... 2
1. Fundamentals of queuing theory.................................................... ...... 3
1.1 The concept of a random process.................................................... .................... 3
1.2 Markov random process.................................................... ................ 4
1.3 Event streams................................................................... ........................................... 6
1.4 Kolmogorov equations for state probabilities. Final probabilities of states.................................................. ........................................................ ........ 9
1.5 Problems of queuing theory.................................................... .. 13
1.6 Classification of queuing systems.................................................. 15
2. Queuing systems with waiting.................................................... 16
2.1 Single-channel QS with waiting.................................................... .......... 16
2.2 Multi-channel QS with waiting.................................................... ......... 25
3. Closed QS.................................................... ............................................... 37
Solution to the problem................................................... ........................................... 45
Conclusion................................................. ........................................................ .50
References........................................................ ..................................... 51
In this course we will look at various queuing systems (QS) and queuing networks (Queuing).
The queuing system (QS) is understood as a dynamic system designed to efficiently service the flow of requests (service requirements) under restrictions on system resources.
QS models are convenient for describing individual subsystems of modern computing systems, such as the processor subsystem - main memory, input-output channel, etc. A computing system as a whole is a collection of interconnected subsystems, the interaction of which is probabilistic. An application for solving a certain problem entering a computing system goes through a sequence of stages of counting, accessing external storage devices and input-output devices. After completing a certain sequence of such stages, the number and duration of which depends on the complexity of the program, the request is considered serviced and leaves the computer system. Thus, the computing system as a whole can be represented by a set of QS, each of which reflects the process of functioning of an individual device or a group of similar devices that are part of the system.
A set of interconnected QSs is called a queuing network (stochastic network).
To begin with, we will look at the basics of the theory of QS, then we will move on to familiarize ourselves in detailed content with QS with expectation and closed QS. The course also includes a practical part, in which we will learn in detail how to apply theory in practice.
Queuing theory is one of the branches of probability theory. This theory considers probabilistic problems and mathematical models (before this we considered deterministic mathematical models). Let us remind you that:
Deterministic mathematical model reflects the behavior of an object (system, process) from the perspective full certainty in the present and future.
Probabilistic mathematical model takes into account the influence of random factors on the behavior of an object (system, process) and, therefore, evaluates the future from the standpoint of the probability of certain events.
Those. here, as, for example, in game theory problems are considered in conditions uncertainty .
Let us first consider some concepts that characterize “stochastic uncertainty,” when the uncertain factors included in the problem are random variables (or random functions), the probabilistic characteristics of which are either known or can be obtained from experience. Such uncertainty is also called “favorable”, “benign”.
Strictly speaking, random disturbances are inherent in any process. It is easier to give examples of a random process than a “non-random” process. Even, for example, the process of running a clock (it seems to be a strictly calibrated work - “works like a clock”) is subject to random changes (moving forward, lagging behind, stopping). But as long as these disturbances are insignificant and have little effect on the parameters of interest to us, we can neglect them and consider the process as deterministic, non-random.
Let there be some system S(technical device, group of such devices, technological system - machine, site, workshop, enterprise, industry, etc.). In the system S leaks random process, if it changes its state over time (passes from one state to another), moreover, in a previously unknown random manner.
Examples:
1. System S– technological system (machine section). Machines break down from time to time and are repaired. The process taking place in this system is random.
2. System S- an aircraft flying at a given altitude along a specific route. Disturbing factors - weather conditions, crew errors, etc., consequences - bumpiness, violation of the flight schedule, etc.
A random process occurring in a system is called Markovsky, if for any moment of time t 0 probabilistic characteristics of a process in the future depend only on its state at the moment t 0 and do not depend on when and how the system reached this state.
Let the system be in a certain state at the moment t 0 S 0 . We know the characteristics of the state of the system in the present and everything that happened during t <t 0 (process history). Can we predict (predict) the future, i.e. what will happen when t >t 0 ? Not exactly, but some probabilistic characteristics of the process can be found in the future. For example, the probability that after some time the system S will be able S 1 or will remain in state S 0, etc.
Example. System S- a group of aircraft participating in air combat. Let x– number of “red” planes, y– number of “blue” aircraft. By the time t 0 number of surviving (not shot down) aircraft, respectively – x 0 , y 0 . We are interested in the probability that at a moment in time the numerical superiority will be on the side of the “reds”. This probability depends on what state the system was in at the time t 0, and not on when and in what sequence those shot down died until the moment t 0 planes.
In practice, Markov processes in their pure form are usually not encountered. But there are processes for which the influence of “prehistory” can be neglected. And when studying such processes, Markov models can be used (queuing theory does not consider Markov queuing systems, but the mathematical apparatus that describes them is much more complex).
In operations research, Markov random processes with discrete states and continuous time are of great importance.
The process is called discrete state process, if its possible states S 1 , S 2, ... can be determined in advance, and the transition of the system from state to state occurs “in a jump,” almost instantly.
The process is called continuous time process, if the moments of possible transitions from state to state are not fixed in advance, but are uncertain, random and can occur at any moment.
Example. Technological system (section) S consists of two machines, each of which can fail (fail) at a random moment in time, after which the repair of the unit immediately begins, which also continues for an unknown, random time. The following system states are possible:
S 0 - both machines are working;
S 1 - the first machine is being repaired, the second is working;
S 2 - the second machine is being repaired, the first one is working;
S 3 - both machines are being repaired.
System transitions S from state to state occur almost instantly, at random moments when a particular machine fails or a repair is completed.
When analyzing random processes with discrete states, it is convenient to use a geometric scheme - state graph. The vertices of the graph are the states of the system. The arcs of the graph are possible transitions from state to state. For our example, the state graph is shown in Fig. 1.
Rice. 1. System state graph
Note. Transition from state S 0 in S 3 is not indicated in the figure, because it is assumed that the machines fail independently of each other. We neglect the possibility of simultaneous failure of both machines.
Event stream– a sequence of homogeneous events following one after another at some random moments in time.
In the previous example, this is a flow of failures and a flow of restorations. Other examples: the flow of calls at a telephone exchange, the flow of customers in a store, etc.
The flow of events can be visually represented by a series of points on the time axis O t- rice. 2.
Rice. 2. Image of the flow of events on the time axis
The position of each point is random, and only one implementation of the flow is depicted here.
Event flow intensity ( ) is the average number of events per unit of time.
Let's look at some properties (types) of event streams.
The stream of events is called stationary, if its probabilistic characteristics do not depend on time.
In particular, the intensity of the stationary flow is constant. The flow of events inevitably has condensations or rarefactions, but they are not of a regular nature, and the average number of events per unit of time is constant and does not depend on time.
The stream of events is called flow without consequences, if for any two non-overlapping sections of time and (see Fig. 2) the number of events falling on one of them does not depend on how many events fall on the other. In other words, this means that the events that form the flow appear at certain points in time independently of each other and are each caused by its own causes.
The stream of events is called ordinary, if events appear in it one by one, and not in groups of several at once.
The stream of events is called simplest (or stationary Poisson), if it has three properties at once:
1) stationary;
2) ordinary;
3) has no consequences.
The simplest flow has the simplest mathematical description. It plays the same special role among flows as the law of normal distribution does among other distribution laws. Namely, when superimposing a sufficiently large number of independent, stationary and ordinary flows (comparable to each other in intensity), a flow close to the simplest is obtained.
For the simplest flow with intensity interval T between neighboring events has a so-called exponential distribution with density:
where is the parameter of the exponential law.
For a random variable T, which has an exponential distribution, the mathematical expectation is the reciprocal of the parameter, and the standard deviation is equal to the mathematical expectation:
Considering Markov processes with discrete states and continuous time, it is assumed that all transitions of the system S from state to state occur under the influence of simple event flows (call flows, failure flows, recovery flows, etc.). If all event streams transferring the system S from state to state of the simplest, then the process occurring in the system will be Markovian.
So, a system in state is affected by a simple flow of events. As soon as the first event of this flow appears, the system “jumps” from state to state (on the state graph along the arrow).
For clarity, on the system state graph, for each arc, the intensity of the flow of events that moves the system along this arc (arrow) is indicated. - intensity of the flow of events that transfers the system from state to . Such a graph is called marked. For our example, the labeled graph is shown in Fig. 3.
Rice. 3. Labeled system state graph
In this figure - the intensity of the failure flow; - intensity of recovery flow.
We assume that the average time to repair a machine does not depend on whether one machine is repaired or both at once. Those. Each machine is repaired by a separate specialist.
Let the system be in the state S 0 . In state S 1 it is translated by the flow of failures of the first machine. Its intensity is equal to:
where is the average failure-free operation time of the first machine.
From the state S 1 in S 0 the system is transferred by the flow of “repair completions” of the first machine. Its intensity is equal to:
where is the average repair time for the first machine.
The intensities of event flows that transfer the system along all arcs of the graph are calculated in a similar way. Having at our disposal a labeled graph of system states, we construct mathematical model of this process.
Let the system under consideration S has -possible states. The probability of the th state is the probability that at the moment of time, the system will be in the state. It is obvious that for any moment in time the sum of all state probabilities is equal to one:
To find all probabilities of states as functions of time, compose and solve Kolmogorov equations– a special type of equation in which the unknown functions are the probabilities of states. The rule for composing these equations is presented here without proof. But before introducing it, let’s explain the concept final probability of state .
What will happen to the state probabilities at ? Will they strive for any limits? If these limits exist and do not depend on the initial state of the system, then they are called final state probabilities .
where is the finite number of system states.
Final state probabilities– these are no longer variable quantities (functions of time), but constant numbers. It is obvious that:
Final state probability is essentially the average relative time the system remains in this state.
For example, the system S has three states S 1 , S 2 and S 3. Their final probabilities are respectively 0.2; 0.3 and 0.5. This means that a system in a limiting stationary state spends on average 2/10 of its time in the state S 1, 3/10 – able S 2 and 5/10 – able S 3 .
The rule for composing the Kolmogorov system of equations: in each equation of the system on the left side is the final probability of a given state, multiplied by the total intensity of all flows, leading from this state, A in his right parts– the sum of the products of the intensities of all flows, included in -th state, on the probabilities of the states from which these flows come.
Using this rule, we write a system of equations for our example :
.
This system of four equations with four unknowns, it would seem, can be completely solved. But these equations are homogeneous (they do not have a free term), and, therefore, they determine the unknowns only up to an arbitrary factor. However, you can use the normalization condition: 
and use it to solve the system. In this case, one (any) of the equations can be discarded (it follows as a consequence of the others).
Continuation of the example. Let the flow intensities be equal to: .
We discard the fourth equation and add a normalization condition instead:
.
Those. in the limiting, stationary mode the system S on average 40% of the time will be spent in a state of S 0 (both machines are operational), 20% - in good condition S 1 (the first machine is being repaired, the second is working), 27% - in condition S 2 (the second machine is being repaired, the first one is working), 13% - in condition S 3 (both machines are being repaired). Knowing these final probabilities can help estimate the average efficiency of the system and the workload of repair organs.
Let the system S able S 0 (fully operational) brings in an income of 8 conventional units per unit of time, able S 1 – income 3 conventional units, able S 2 – income 5 conventional units, able S 3 – does not generate income. Then, in the limiting, stationary mode, the average income per unit of time will be equal to: conventional units.
Machine 1 is repaired in a fraction of the time equal to: . Machine 2 is repaired in a fraction of the time equal to: . Arises optimization problem. Even though we can reduce the average repair time of the first or second machine (or both), it will cost us a certain amount. The question is, will the increased revenue associated with faster repairs pay for the increased repair costs? You will need to solve a system of four equations with four unknowns.
Examples of queuing systems (QS): telephone exchanges, repair shops, ticket offices, information desks, machine tools and other technological systems, control systems of flexible production systems, etc.
Each QS consists of a certain number of service units, which are called service channels(these are machines, transport carts, robots, communication lines, cashiers, salespeople, etc.). Every QS is designed to serve some kind of flow of applications(requirements) arriving at some random moments in time.
Service of the request continues for some, generally speaking, random time, after which the channel is freed and ready to receive the next request. The random nature of the flow of applications and service time leads to the fact that at some periods of time an excessively large number of applications accumulate at the input of the QS (they either queue up or leave the QS unserved). In other periods, the system will work with underload or be completely idle.
The QS operation process is a random process with discrete states and continuous time. The state of the QS changes abruptly when certain events occur (the arrival of a new application, the end of service, the moment when an application that is tired of waiting leaves the queue).
Subject of queuing theory– construction of mathematical models that connect the given operating conditions of the QS (number of channels, their productivity, operating rules, nature of the flow of requests) with the characteristics of interest to us - indicators of the effectiveness of the QS. These indicators describe the ability of the CMO to cope with the flow of applications. They can be: the average number of applications served by the QS per unit of time; average number of busy channels; average number of applications in queue; average waiting time for service, etc.
Mathematical analysis of the work of a QS is greatly facilitated if the process of this work is Markovian, i.e. streams of events that transfer the system from state to state are the simplest. Otherwise, the mathematical description of the process becomes very complicated and it is rarely possible to bring it to specific analytical dependencies. In practice, non-Markov processes are reduced to Markov processes with approximation. The following mathematical apparatus describes Markov processes.
First division (based on the presence of queues):
1. QS with failures;
2. Queue with a queue.
In QS with failures an application received at a time when all channels are busy is rejected, leaves the QS and is not serviced in the future.
In SMO with a queue an application that arrives at a time when all channels are busy does not leave, but gets in a queue and waits for the opportunity to be served.
QS with queues are subdivided into different types depending on how the queue is organized - limited or unlimited. Restrictions may concern both the length of the queue and the waiting time, “service discipline”.
So, for example, the following QSs are considered:
· CMO with impatient requests (queue length and service time are limited);
· QS with priority service, i.e. some applications are processed out of turn, etc.
In addition, QSs are divided into open QSs and closed QSs.
In an open QS the characteristics of the flow of requests do not depend on the state of the QS itself (how many channels are occupied). In a closed QS– depend. For example, if one worker services a group of machines that require adjustment from time to time, then the intensity of the flow of “demands” from the machines depends on how many of them are already operational and awaiting adjustment.
The classification of SMO is far from limited to the above varieties, but this is enough.
Let's consider the simplest QS with waiting - a single-channel system (n - 1), which receives a flow of requests with intensity ; service intensity (i.e., on average, a continuously busy channel will issue serviced requests per unit (of time). A request received at a time when the channel is busy is queued and awaits service.
System with limited queue length. Let us first assume that the number of places in the queue is limited by the number m, i.e. if an application arrives at a time when there are already m-applications in the queue, it leaves the system unserved. In the future, by directing m to infinity, we will obtain the characteristics of a single-channel QS without restrictions on the queue length.
We will number the states of the QS according to the number of applications in the system (both being serviced and awaiting service):
The channel is free;
The channel is busy, there is no queue;
The channel is busy, one request is in the queue;
The channel is busy, k-1 applications are in queue;
The channel is busy, applications are in queue.
The GSP is shown in Fig. 4. All intensities of event flows moving into the system along arrows from left to right are equal to , and from right to left - . Indeed, the flow of requests moves the system along the arrows from left to right (as soon as a request arrives, the system goes to the next state), from right to left - the flow of “releases” of a busy channel, which has an intensity (as soon as the next request is serviced, the channel will either become free or decrease number of applications in queue).
Rice. 4. Single-channel QS with waiting
Shown in Fig. 4 diagram is a diagram of reproduction and death. Let us write expressions for the limiting probabilities of states:
(5)
or using: :
(6)
The last line in (6) contains a geometric progression with the first term 1 and the denominator p, from which we obtain:
(7)
in connection with which the limiting probabilities take the form:
(8).
Expression (7) is valid only for< 1 (при = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем = 1 равна m+2, и в этом случае:
Let us determine the characteristics of the QS: probability of failure, relative throughput q, absolute throughput A, average queue length, average number of applications associated with the system, average waiting time in the queue, average time spent by an application in the QS.
Probability of failure. Obviously, the application is rejected only if the channel is busy and all t-places in the queue are also busy:
(9).
Relative Bandwidth:
(10).
Average queue length. Let's find the average number of applications in the queue as the mathematical expectation of a discrete random variable R-number of applications in the queue:
With probability there is one application in the queue, with probability there are two applications, in general with probability there are k-1 applications in the queue, etc., from which:
(11).
Since , the sum in (11) can be interpreted as a derivative of the sum of the geometric progression:
Substituting this expression into (11) and using from (8), we finally obtain:
(12).
The average number of applications in the system. Next, we obtain a formula for the average number of -requests associated with the system (both standing in the queue and being serviced). Since , where is the average number of applications under service, and k is known, it remains to determine . Since there is only one channel, the number of serviced requests can be 0 (with probability ) or 1 (with probability 1 - ), from which:
.
and the average number of applications associated with the QS is:
(13).
Average waiting time for an application in the queue. Let's denote it ; if a request comes into the system at some point in time, then with probability the service channel will not be busy, and it will not have to wait in line (the waiting time is zero). Most likely, she will come into the system while some request is being served, but there will be no queue in front of her, and the request will wait for the start of its servicing for a period of time (the average time of servicing one request). There is a probability that there will be another application in the queue before the application being considered, and the average waiting time will be equal to , etc.
If k=m+1, i.e. when a newly arriving request finds the service channel busy and m-requests in the queue (probability of this), then in this case the request does not queue (and is not served), so the waiting time is zero. The average waiting time will be:
if we substitute expressions for probabilities (8) here, we get:
(14).
Here we use relations (11), (12) (derivative of a geometric progression), as well as from (8). Comparing this expression with (12), we note that in other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the application flow.
(15).
Average time an application stays in the system. Let us denote the mathematical expectation of a random variable as the time a request stays in the QS, which is the sum of the average waiting time in the queue and the average service time. If the system load is 100%, obviously, otherwise:
.
Example 1. A gas station (gas station) is a service station with one service channel (one pump).
The area at the station allows no more than three cars to be in line for refueling at the same time (m = 3). If there are already three cars in the queue, the next car arriving at the station does not join the queue. The flow of cars arriving for refueling has an intensity = 1 (car per minute). The refueling process lasts an average of 1.25 minutes.
Define:
probability of failure;
relative and absolute capacity of gas stations;
average number of cars waiting to refuel;
average number of cars at a gas station (including those being serviced);
average waiting time for a car in line;
average time a car spends at a gas station (including service).
In other words, the average waiting time is equal to the average number of applications in the queue divided by the intensity of the application flow.
We first find the reduced intensity of the flow of applications: =1/1.25=0.8; =1/0.8=1.25.
According to formulas (8):
Probability of failure is 0.297.
Relative capacity of the QS: q=1-=0.703.
Absolute throughput of QS: A==0.703 cars per minute.
We find the average number of cars in the queue using formula (12):
those. The average number of cars waiting in line to fill the gas station is 1.56.
Adding to this value the average number of vehicles under service:
we get the average number of cars associated with a gas station.
Average waiting time for a car in queue according to formula (15):
Adding to this value, we get the average time that a car spends at a gas station:
Systems with unlimited waiting. In such systems, the value of m is not limited and, therefore, the main characteristics can be obtained by passing to the limit in previously obtained expressions (5), (6), etc.
Note that the denominator in the last formula (6) is the sum of an infinite number of terms of the geometric progression. This sum converges when the progression is infinitely decreasing, i.e. at<1.
It can be proven that<1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что <1.
If, then relations (8) take the form:
(16).
If there are no restrictions on the length of the queue, each application that comes into the system will be serviced, therefore q=1, 
.
We obtain the average number of applications in the queue from (12) at:
The average number of applications in the system according to formula (13) at:
.
The average waiting time is obtained from formula (14) with:
.
Finally, the average time an application stays in the QS is:
System with limited queue length. Let's consider a channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel); number of places in the queue.
System states are numbered according to the number of requests associated with the system:
no queue:
All channels are free;
One channel is occupied, the rest are free;
-channels are occupied, the rest are not;
All channels are occupied, there are no free channels;
there is a queue:
All n-channels are occupied; one application is in the queue;
All n-channels, r-requests in the queue are occupied;
All n-channels, r-requests in the queue are occupied.
GSP is shown in Fig. 17. Each arrow is marked with the corresponding intensities of event flows. Along the arrows from left to right, the system is always transferred by the same flow of requests with an intensity of
Rice. 17. Multi-channel QS with waiting
The graph is typical for the processes of reproduction and death, for which the solution was previously obtained. Let's write expressions for the limiting probabilities of states using the notation: (here we use the expression for the sum of a geometric progression with a denominator).
Thus, all state probabilities have been found.
Let us determine the characteristics of the system efficiency.
Probability of failure. An incoming request is rejected if all n-channels and all m-places in the queue are occupied:
(18)
The relative throughput complements the probability of failure to one:
Absolute throughput of QS:
(19)
Average number of busy channels. For QS with refusals, it coincided with the average number of applications in the system. For a QS with a queue, the average number of busy channels does not coincide with the average number of applications in the system: the latter value differs from the first by the average number of applications in the queue.
Let us denote the average number of occupied channels by . Each busy channel serves on average A-claims per unit of time, and the QS as a whole serves on average A-claims per unit of time. Dividing one by the other, we get:
The average number of requests in the queue can be calculated directly as the mathematical expectation of a discrete random variable:
(20)
Here again (the expression in brackets) the derivative of the sum of the geometric progression occurs (see above (11), (12) - (14)), using the relation for it, we obtain:
Average number of applications in the system:
Average waiting time for an application in the queue. Let's consider a number of situations that differ in the state in which a newly arrived request will find the system and how long it will have to wait for service.
If a request does not find all channels busy, it will not have to wait at all (the corresponding terms in the mathematical expectation are equal to zero). If a request arrives at a time when all n-channels are busy and there is no queue, it will have to wait on average for a time equal to (because the “release flow” of -channels has an intensity of ). If a request finds all channels busy and one request in front of it in the queue, it will have to wait on average for an amount of time (for each request in front), etc. If a request finds itself in a queue of -requests, it will have to wait on average for time If a newly arrived request finds m-requests already in the queue, then it will not wait at all (but will not be served). We find the average waiting time by multiplying each of these values by the corresponding probabilities:
(21)
Just as in the case of a single-channel QS with waiting, we note that this expression differs from the expression for the average queue length (20) only by the factor , i.e.
.
The average residence time of a request in the system, as well as for a single-channel QS, differs from the average waiting time by the average service time multiplied by the relative throughput:
.
Systems with unlimited queue length. We considered a channel QS with waiting, when no more than m-requests can be in the queue at the same time.
Just as before, when analyzing systems without restrictions, it is necessary to consider the obtained relations for .
We obtain the probabilities of states from the formulas by passing to the limit (at ). Note that the sum of the corresponding geometric progression converges at and diverges at >1. Assuming that<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Probability of failure, relative and absolute throughput. Since each request will sooner or later be serviced, the characteristics of the QS throughput will be:
The average number of applications in the queue is obtained from (20):
,
and the average waiting time is from (21):
.
The average number of occupied channels, as before, is determined through the absolute throughput:
.
The average number of applications associated with the QS is defined as the average number of applications in the queue plus the average number of applications under service (average number of busy channels):
Example 2. A gas station with two pumps (n = 2) serves a flow of cars with an intensity of =0.8 (cars per minute). Average service time per machine:
There is no other gas station in the area, so the line of cars in front of the gas station can grow almost unlimitedly. Find the characteristics of the QS.
Because<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
etc.
We will find the average number of busy channels by dividing the absolute capacity of the QS A = = 0.8 by the service intensity = 0.5:
The probability of no queue at a gas station will be:
Average number of cars in queue:
Average number of cars at gas stations:
Average waiting time in queue:
Average time a car spends at a gas station:
QS with limited waiting time. Previously, we considered systems with waiting limited only by the queue length (the number of m-requests simultaneously in the queue). In such a QS, an application that has grown in a queue does not leave it until it waits for service. In practice, there are other types of QS in which an application, after waiting for some time, can leave the queue (so-called “impatient” applications).
Let's consider a QS of this type, assuming that the waiting time constraint is a random variable.
Let us assume that there is an n-channel waiting QS in which the number of places in the queue is unlimited, but the time a request stays in the queue is some random variable with a mean value, thus, each request in the queue is subject to a kind of Poisson " flow of care” with intensity:
If this flow is Poisson, then the process occurring in the QS will be Markovian. Let us find the state probabilities for it. The numbering of system states is associated with the number of applications in the system - both being served and standing in queue:
no queue:
All channels are free;
One channel is busy;
Two channels are busy;
All n-channels are occupied;
there is a queue:
All n-channels are occupied, one request is in the queue;
All n-channels are occupied, r-requests are in queue, etc.
The graph of states and transitions of the system is shown in Fig. 23.
Rice. 23. QS with limited waiting time
Let's mark this graph as before; all arrows leading from left to right will indicate the intensity of the flow of applications. For states without a queue, the arrows leading from them from right to left will, as before, indicate the total intensity of the flow servicing all occupied channels. As for states with a queue, the arrows leading from them from right to left will have the total intensity of the service flow of all n-channels plus the corresponding intensity of the flow of departures from the queue. If there are r-applications in the queue, then the total intensity of the flow of departures will be equal to .
As can be seen from the graph, there is a pattern of reproduction and death; using general expressions for the limiting probabilities of states in this scheme (using abbreviated notations, we write:
(24)
Let us note some features of a QS with limited waiting compared to the previously considered QS with “patient” requests.
If the length of the queue is not limited and the requests are “patient” (do not leave the queue), then the stationary limit regime exists only in the case (at the corresponding infinite geometric progression diverges, which physically corresponds to the unlimited growth of the queue at ).
On the contrary, in a QS with “impatient” requests leaving the queue sooner or later, the established service mode at is always achieved, regardless of the reduced intensity of the flow of requests. This follows from the fact that the series for in the denominator of formula (24) converges for any positive values of and .
For a QS with “impatient” requests, the concept of “probability of failure” does not make sense - each request gets in line, but may not wait for service, leaving ahead of time.
Relative throughput, the average number of requests in the queue. The relative capacity q of such a QS can be calculated as follows. Obviously, all applications will be serviced, except those that leave the queue ahead of schedule. Let's calculate the average number of applications that leave the queue early. To do this, we calculate the average number of applications in the queue:
Each of these applications is subject to a “flow of departures” with an intensity of . This means that out of the average number of -applications in the queue, on average, -applications will leave without waiting for service, -applications per unit of time and in total per unit of time, on average -applications will be served. The relative capacity of the QS will be:
We still obtain the average number of occupied channels by dividing the absolute bandwidth A by:
(26)
Average number of applications in queue. Relation (26) allows you to calculate the average number of applications in the queue without summing the infinite series (25). From (26) we obtain:
and the average number of occupied channels included in this formula can be found as the mathematical expectation of a random variable Z, taking values 0, 1, 2,..., n with probabilities ,:
In conclusion, we note that if in formulas (24) we go to the limit at (or, what is the same, at ), then formulas (22) will be obtained, i.e., “impatient” applications will become “patient”.
So far we have considered systems in which the incoming flow is in no way connected with the outgoing flow. Such systems are called open-loop. In some cases, serviced requests are again received at the input after a delay. Such QSs are called closed. A clinic serving a given area, a team of workers assigned to a group of machines, are examples of closed systems.
In a closed QS, the same finite number of potential requirements circulates. Until a potential requirement has been realized as a service request, it is considered to be in a delay block. At the moment of implementation, it enters the system itself. For example, workers maintain a group of machines. Each machine is a potential requirement, turning into a real one at the moment of its breakdown. While the machine is working, it is in the delay block, and from the moment of breakdown until the end of the repair, it is in the system itself. Each worker is a service channel.
Let n- number of service channels, s- number of potential applications, n <s , - the intensity of the flow of applications for each potential requirement, μ - the intensity of service:
The probability of system downtime is determined by the formula
R
0
= 
.
Final probabilities of system states:
Pk= at k
The average number of occupied channels is expressed through these probabilities
=P 1 + 2P 2 +…+n(P n +P n+ 1 +…+P s) or
=P 1 + 2P 2 +…+(n- 1)P n- 1 +n( 1-P 0 -P 1 -…-P n-1 ).
Using this we find the absolute throughput of the system:
as well as the average number of applications in the system
M=s- =s- .
Example 1. The input of a three-channel QS with failures receives a flow of requests with an intensity =4 requests per minute, time for servicing a request by one channel t obs =1/μ =0.5 min. From the point of view of QS capacity, is it profitable to force all three channels to service requests at once, and the average service time is reduced by three times? How will this affect the average time an application spends in the CMO?
Solution. We find the probability of downtime of a three-channel QS using the formula
ρ = /μ =4/2=2, n=3,
P 0 = = = 0,158.
The probability of failure is determined by the formula:
P open = P n ==
P open = 0.21.
Relative system throughput:
R obsl = 1-R open 1-0,21=0,79.
Absolute system throughput:
A= P obsl 3,16.
The average number of occupied channels is determined by the formula:
1.58, share of channels occupied by servicing,
q = 0,53.
The average time an application stays in the QS is found as the probability that the application is accepted for service, multiplied by the average service time: t SMO 0.395 min.
Combining all three channels into one, we get a single-channel system with parameters μ= 6, ρ= 2/3. For a single-channel system, the probability of downtime is:
R 0 = = =0,6,
probability of failure:
P open =ρ P 0 = = 0,4,
relative throughput:
R obsl = 1-R open =0,6,
absolute throughput:
A=P obs =2.4.
t SMO =P obsl= =0.1 min.
As a result of combining the channels into one, the system throughput decreased as the probability of failure increased. The average time an application spends in the system has decreased.
Example 2. The input of a three-channel QS with an unlimited queue receives a flow of requests with an intensity =4 applications per hour, average time to service one application t=1/μ=0.5 h. Find the system performance indicators.
For the system under consideration n =3, =4, μ=1/0.5=2, ρ= /μ=2, ρ/ n =2/3<1. Определяем вероятность простоя по формуле:
P= 
.
P
0
= 
=1/9.
We find the average number of applications in the queue using the formula:
L
=
.
L = = .
We calculate the average waiting time for an application in the queue using the formula:
t= = 0.22 hours.
Average time an application stays in the system:
T=t+ 0,22+0,5=0,72.
Example 3. There are 3 hairdressers working in the hairdressing salon, and there are 3 chairs in the waiting room. The flow of clients has intensity =12 clients per hour. Average service time t obsl =20 min. Determine the relative and absolute throughput of the system, the average number of occupied chairs, the average length of the queue, the average time that the client spends in the hairdresser.
For this task n =3, m =3, =12, μ =3, ρ =4, ρ/n=4/3. The probability of downtime is determined by the formula:
R
0
=
.
P
0
= 
0,012.
The probability of denial of service is determined by the formula
P open =P n+m = .
P open =Pn + m 0,307.
Relative system capacity, i.e. service probability:
P obsl =1-P open 1-0,307=0,693.
Absolute throughput:
A= P obsl 12 .
Average number of busy channels:
.
The average queue length is determined by the formula:
L
=
L= 
1,56.
Average waiting time for service in queue:
t= h.
Average number of applications to the CMO:
M=L + .
Average time an application stays in the CMO:
T=M/ 0.36 hours
Example 4. A worker operates 4 machines. Each machine fails with intensity =0.5 failures per hour, average repair time t rem=1/μ=0.8 h. Determine the throughput of the system.
This problem considers a closed QS, μ =1.25, ρ=0.5/1.25=0.4. The probability of worker downtime is determined by the formula:
R
0
=
.
P
0
= 
.
Probability of worker employment R zan = 1-P 0 . A=( 1-P 0 )μ =0.85μ machines per hour.
Task:
Two workers operate a group of four machines. Stops of a working machine occur on average after 30 minutes. The average setup time is 15 minutes. Operating and setup time are distributed according to an exponential law.
Find the average share of free time for each worker and the average operating time of the machine.
Find the same characteristics for a system in which:
a) each worker is assigned two machines;
b) two workers always service the machine together, and with double intensity;
c) the only faulty machine is serviced by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first describe the system in terms of the processes of death and birth).
Solution:
The following states of system S are possible:
S 0 – all machines are operational;
S 1 – 1 machine is being repaired, the rest are in good working order;
S 2 – 2 machine is being repaired, the rest are in working order;
S 3 – 3 machine is being repaired, the rest are in working order;
S 4 – 4 machine is being repaired, the rest are in good working order;
S 5 – (1, 2) machines are being repaired, the rest are in good working order;
S 6 – (1, 3) machines are being repaired, the rest are in good working order;
S 7 – (1, 4) machines are being repaired, the rest are in good working order;
S 8 – (2, 3) machines are being repaired, the rest are in good working order;
S 9 – (2, 4) machines are being repaired, the rest are in working order;
S 10 – (3, 4) machines are being repaired, the rest are in good working order;
S 11 – (1, 2, 3) machines are being repaired, 4 machine is operational;
S 12 – (1, 2, 4) machines are being repaired, 3 machine is operational;
S 13 – (1, 3, 4) machines are being repaired, machine 2 is operational;
S 14 – (2, 3, 4) machines are being repaired, 1 machine is operational;
S 15 – all machines are repaired.
System state graph...
This system S is an example of a closed system, since each machine is a potential requirement, turning into a real one at the moment of its breakdown. While the machine is working, it is in the delay block, and from the moment of breakdown until the end of the repair, it is in the system itself. Each worker is a service channel.
If a worker is busy, he sets up μ-machines per unit time, system capacity:
Answer:
The average share of free time for each worker is ≈ 0.09.
Average machine operating time ≈ 3.64.
a) Each worker is assigned two machines.
The probability of worker downtime is determined by the formula:
Probability of worker employment:
If a worker is busy, he sets up μ-machines per unit time, system capacity:
Answer:
The average share of free time for each worker is ≈ 0.62.
Average machine operating time ≈ 1.52.
b) Two workers always service the machine together, and with double intensity.
c) The only faulty machine is serviced by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first describe the system in terms of the processes of death and birth).
Comparison of 5 answers:
The most effective way to organize workers at machines will be the initial version of the task.
Examples of the simplest queuing systems (QS) were discussed above. The term “protozoa” does not mean “elementary”. Mathematical models of these systems are applicable and successfully used in practical calculations.
The possibility of applying decision theory in queuing systems is determined by the following factors:
1. The number of applications in the system (which is considered as a QS) must be quite large (massively).
2. All applications received at the input of the QS must be of the same type.
3. To calculate using formulas, you need to know the laws that determine the receipt of applications and the intensity of their processing. Moreover, the order flows must be Poisson.
4. Structure of the QS, i.e. the set of incoming requirements and the sequence of application processing must be strictly fixed.
5. It is necessary to exclude subjects from the system or describe them as requirements with a constant processing intensity.
To the restrictions listed above, we can add one more, which has a strong impact on the dimension and complexity of the mathematical model.
6. The number of priorities used should be minimal. The priorities of applications must be constant, i.e. they cannot change during processing within the QS.
In the course of the work, the main goal was achieved - the main material of “QS with limited waiting time” and “Closed QS” was studied, which was set by the teacher of the academic discipline. We also got acquainted with the application of the acquired knowledge in practice, i.e. consolidated the material covered.
1) http://www.5ballov.ru.
2) http://www.studentport.ru.
3) http://vse5ki.ru.
4) http://revolution..
5) Fomin G.P. Mathematical methods and models in commercial activities. M: Finance and Statistics, 2001.
6) Gmurman V.E. Probability theory and mathematical statistics. M: Higher School, 2001.
7) Sovetov B.A., Yakovlev S.A. Systems modeling. M: Higher School, 1985.
8) Lifshits A.L. Statistical modeling of QS. M., 1978.
9) Ventzel E.S. Operations Research. M: Nauka, 1980.
10) Ventzel E.S., Ovcharov L.A. Probability theory and its engineering applications. M: Nauka, 1988.
The operations or efficiency of the queuing system are as follows.For QS with failures:
For SMO with unlimited waiting both absolute and relative throughput lose their meaning, since every incoming request will sooner or later be serviced. For such a QS, the important indicators are:
For Mixed type QS both groups of indicators are used: both relative and absolute throughput, and characteristics of expectation.
Depending on the purpose of the queuing operation, any of the given indicators (or a set of indicators) can be selected as an efficiency criterion.
Analytical model A QS is a set of equations or formulas that allow one to determine the probabilities of system states during its operation and calculate performance indicators based on the 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 reflect real systems are usually complex and difficult to visualize.
Analytical modeling of a QS is greatly facilitated if the processes occurring in the QS are Markovian (the flows of requests are simple, service times are distributed exponentially). 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, the selected efficiency indicators can be determined.
Let's look at 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 by without stopping. The flow of trucks is simple, the check time is random with an exponential distribution.
This situation can be modeled by a three-channel QS with failures (no queue). The system is open-loop, with homogeneous requests, 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 system state graph is shown in Fig. 2.11.
Rice. 2.11.
On the graph: - intensity of truck flow; - intensity of document checks by one traffic inspector.
Simulation is carried out to determine the portion of vehicles that will not be tested.
Solution
The required part of the probability is the probability of employment of all three inspectors. Since the state graph represents a typical “death and reproduction” scheme, we will find using dependencies (2.2).
The throughput capacity of this traffic inspector post can be characterized relative throughput:
Example 2.6. To receive and process reports from the reconnaissance group, a group of three officers was appointed in the intelligence department of the association. The expected intensity of the flow of reports is 15 reports per hour. The average time for processing 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 whether the assigned team of three officers is sufficient to complete the assigned task.
Solution
A group of officers operates as a CMO with failures, consisting of three channels.
Flow of reports with intensity 
can be considered the simplest, since it is the total of several reconnaissance groups. Service intensity 
. The distribution law is unknown, but this is unimportant, since it has been shown that for systems with failures it can be arbitrary.
The description of 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 it for the limiting probabilities of the state:
The attitude is called given intensity of the flow of applications. Its physical meaning is as follows: the value represents the average number of requests arriving at the QS during the average time of servicing one request.
In the example 
.
In the QS under consideration, a failure occurs when all three channels are busy, that is. Then:
Because probability of failure in the processing of reports is more than 34% (), then it is necessary to increase the personnel of the group. Let's double the composition of the group, that is, the CMO will now have six channels, and calculate:
Thus, only a group of six officers will be able to process incoming reports with a 95% probability.
2.5.2. Multi-channel QS with waiting
Example 2.7. At the river crossing section there are 15 similar crossing facilities. The flow of equipment arriving at the crossing is on average 1 unit/min, the average time for crossing one unit of equipment is 10 minutes (including the return of the crossing vehicle).
Assess the main characteristics of the crossing, including the likelihood of immediate crossing immediately upon the arrival of the unit of equipment.
Solution
Absolute throughput, i.e. everything that approaches the crossing is practically crossed immediately.
Average number of operating crossing facilities:
Ferry utilization and downtime rates:
A program was also developed to solve the example. The time intervals for equipment to arrive at the crossing and the crossing time are assumed to be distributed according to an exponential law.
The utilization rates of the crossing after 50 runs are almost the same: 
.
The maximum queue length is 15 units, the average time spent in the queue is about 10 minutes.
Purpose of the QS service. The online calculator is designed to calculate the following indicators of single-channel QS:- probability of channel failure, probability of a free channel, absolute throughput;
- relative throughput, average service time, average channel downtime.
Instructions. To solve such problems online, select the QS model. Specify demand flow intensity λ And service flow intensity μ. For a single-channel QS with a limited queue length, you can specify queue length m, and for a single-channel QS with an unlimited queue - the number of applications in the queue (to calculate the probability of these applications being in the queue). see example solution. . The resulting solution is saved in a Word file.
Classification of single-channel queuing systems
Example No. 1. Auto gas station has one gas station. It is assumed that the simplest flow of cars enters the station with an intensity of λ=11 cars/hour. The request servicing time is a random variable that obeys an exponential law with the parameter μ=14 vehicles/hour. Determine the average number of cars at the station.
Example No. 2. There is a point for carrying out preventive inspection of machines with one inspection group. It takes an average of 0.4 hours to inspect and identify defects in each machine. On average, 328 cars per day are received for inspection. The flows of requests and services are the simplest. If a car arriving at the inspection point does not find a single channel free, it leaves the inspection point unserviced. Determine the limiting probabilities of conditions and maintenance characteristics of a preventive inspection point.
Solution. Here α = 328/24 ≈ = 13.67, t = 0.4. This data must be entered into the calculator.
In practice, single-channel QSs with a queue (a doctor serving patients, a processor executing machine commands) are quite common. Therefore, it is necessary to consider single-channel QS with a queue in more detail.
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 l; the service flow has an intensity m inverse to the average request service 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 requests in the system;
W SYST– average time a request stays in the system;
L VERY– average number of applications in the queue;
W VERY– average time an application stays in the queue;
P ZAN- the probability that the channel is busy (the degree of channel load).
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 request will sooner or later be serviced, therefore, for the same reason.
Solution. The state of the system, as before, will be numbered according to the number of applications in the QS:
-S 0 – channel is free;
-S 1 – channel is busy (serving a request), there is no queue;
-S 2 – channel is busy, one request is in queue;
-S k – channel is busy, k-1 applications are in queue.
Theoretically, the number of states is unlimited (infinite). Formulas for the final probabilities in the scheme of death and reproduction were derived only for the case of a finite number of states, but we will make the assumption that we will use them for an infinite number of states. Then the number of terms in the formula will be infinite. We obtain an expression for p o:
The series in formula (17) is a geometric progression. We know that the series converges - it is an infinitely decreasing progression with a denominator r. When the series diverges (which is an indirect, although not strict, proof that the final probabilities of states p o, p 1, …, p k,...exist only when ). Then:
Let's find the average number of applications to the CMO L SYST. Random variable Z - the number of applications in the system - has possible values 0, 1, 2, ..., k, ... with probabilities p o, p 1, …, p k,... Its mathematical expectation is equal to:
Using Little's formula (9), we find the average time a request stays in the system:
Let's find the average number of applications in the queue. 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 VERY equal to the average number of applications in the system L SYST 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 P ZAN. It is obvious that:
Therefore, the average number of requests under service is:
Using Little's formula (9), we find the average time an application stays in the queue.
Loading...
