SMO with unlimited queue. CMO with waiting (queue). Multi-channel SMO with unlimited queue

Federal agency RF education

FGOU SPO "Perevozsky Construction College"

Course work

in the discipline "Mathematical methods"

on the topic “CMO with limited waiting time. Closed SMO "

Introduction ................................................. .................................................. ....... 2

1. Foundations of the theory queuing.................................................. 3

1.1 The concept of a random process .............................................. .................... 3

1.2 Markov random process .............................................. ................ 4

1.3 Streams of events ............................................... .......................................... 6

1.4 Kolmogorov equations for state probabilities. Final probabilities of states ............................................... .................................................. ........ nine

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 Multichannel QS with waiting ............................................. ......... 25

3. Closed CMO .............................................. .......................................... 37

The solution of the problem................................................ ............................................. 45

Conclusion ................................................. .................................................. . fifty

Bibliography................................................ ....................................... 51

In this course, we will consider various queuing systems (QS) and queuing networks (QS).

A queuing system (QS) is understood as a dynamic system designed to efficiently service the flow of requests (service requests) under constraints on the resources of the system.

QS models are convenient for describing individual subsystems of modern computing systems, such as the processor subsystem - 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 the solution of a certain problem arriving in a computer system goes through a sequence of stages of counting, accessing external storage devices and input-output devices. After performing a certain sequence of such stages, the number and duration of which depends on the complexity of the program, the application is considered served 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 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 theory of QS, then move on to acquaintance in detailed content with 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, assesses the future from the standpoint of the probability of certain events.

Those. here, as, for example, in game theory problems are considered in conditions uncertainties .

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. This 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 the clock (it seems to be a rigorous verified work - "works like a clock") is subject to random changes (moving forward, lagging behind, stopping). But as long as these perturbations are insignificant, have little effect on the parameters of interest to us, we can neglect them and consider the process as deterministic, not random.

Let there be some system S (a 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 flows random process , if it changes its state over time (passes from one state to another), and, moreover, in a randomly unknown way.

Examples:

1. System S - technological system (machine tool section). The machines break down from time to time and are repaired. The process in this system is random.

2. System S - an airplane flying at a specified altitude along a specified route. Disturbing factors - meteorological conditions, crew errors, etc., consequences - “bumpiness”, violation of the flight schedule, etc.

A 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 entered this state.

Let at the moment t 0 the system is in a certain state 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 with t >t 0? Exactly - no, but some probabilistic characteristics of the process can be found in the future. For example, the probability that after a while the system S will be able to S 1 or will remain in state S 0, etc.

Example ... System S - a group of aircraft participating in air combat. Let 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 advantage will be on the side of the “red”. This probability depends on the state of the system at the time t 0, and not on when and in what sequence the 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 in the study of such processes, Markov models can be applied (in the queuing theory, not Markov queuing systems are considered, but the mathematical apparatus describing them is much more complicated).

In the study of operations, 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 "jumpwise", 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 moment.

Example ... Technological system (site) S consists of two machines, each of which at a random moment of time may fail (fail), after which the repair of the unit immediately begins, also continuing in a previously unknown, random time. The following system states are possible:

S 0 - both machines are in good working order;

S 1 - the first machine is being repaired, the second is operational;

S 2 - the second machine is being repaired, the first is operational;

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 end of the repair.

When analyzing random processes with discrete states, it is convenient to use the 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.

Figure: 1. System state graph

Note. State transition 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 probability of simultaneous failure of both machines.

Stream of events - a sequence of homogeneous events following one after another at some random moments in time.

In the previous example, this is a failure flow and a recovery flow. 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 - fig. 2.

Figure: 2. Display of the stream of events on the time axis

The position of each point is random, and only one implementation of the stream 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 the stationary flow is constant. The flow of events inevitably has thickening 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 disjoint time segments 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 stream appear at certain points in time. independently of each other and each is caused by its own reasons.

The stream of events is called ordinary if the events appear in it one by one, 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 simplest mathematical description. It plays the same special role among streams as does the law of normal distribution among other distribution laws. Namely, when a sufficiently large number of independent, stationary and ordinary flows (comparable in intensity) are superimposed, a flow close to the simplest is obtained.

For the simplest flow with an intensity interval T between adjacent events has the so-called exponential (exponential) distribution with density:

where is the parameter of the exponential law.

For a random variable T having an exponential distribution, the mathematical expectation is the reciprocal of the parameter, and the mean square 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 action of the simplest streams of events (call streams, failure streams, recovery streams, etc.). If all streams of events transferring the system S from the state to the elementary state, then the process in the system will be Markov.

So, the system in the state is affected by simplest flow 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 the states of the system, for each arc, the intensities of that stream of events are put down, which transfers the system along a given arc (arrow). - the 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.

Figure: 3. Labeled system state graph

This figure shows the rate of failure flow; - the intensity of the flow of recoveries.

We assume that the average time to repair a machine does not depend on whether one machine is being repaired or both. Those. a separate specialist is engaged in the repair of each machine.

Let the system be in a state S 0. In the state S 1 it is translated by the flow of failures of the first machine. Its intensity is equal to:

where is the average uptime of the first machine.

From the state S 1 in S 0, the system transfers the flow of "completion of repairs" of the first machine. Its intensity is equal to:

where is the average repair time for the first machine.

The intensities of the streams of events that transfer the system along all graph arcs are calculated in a similar way. Having at its disposal a labeled graph of system states, we construct mathematical model this process.

Let the system under consideration S has -possible states. The probability of the th state is the probability that at the moment in time, the system will be in the state. Obviously, 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, we compose and solve kolmogorov equations - a special kind of equation in which the unknown functions are the probabilities of states. The rule for composing these equations is given here without proof. But before citing it, let's explain the concept final state probability .

What will happen with 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 a finite number of states of the system.

Final probabilities of states - these are no longer variable quantities (functions of time), but constant numbers. It's obvious that:

Final condition probability Is essentially the average relative time the system is 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 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 to 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 this state, multiplied by the total intensity of all flows, leading out of 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 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 (do not have a free term), and, therefore, 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 values \u200b\u200bof the flow intensities be equal:.

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 able to S 0 (both machines are in good working order), 20% - in a state S 1 (the first machine is being repaired, the second is working), 27% - in a state S 2 (the second machine is being repaired, the first is working), 13% - in a state S 3 (both machines are being repaired). Knowing these final probabilities can help estimate the average system performance and repair tool utilization.

Let the system S capable of S 0 (fully operational) brings income of 8 conventional units per unit of time, in a state S 1 - income 3 conventional units, in a state S 2 - income of 5 conventional units, in a state 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 ... Suppose we can reduce the average repair time of the first or second machine (or both), but it will cost us a certain amount... The question is, will the increased income associated with the acceleration of repairs pay off 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 bureaus, machine tools and others technological systems, flexible control systems production systems etc.

Each QS consists of a number of service units, which are called service channels (these are machines, transport carts, robots, communication lines, cashiers, salespeople, etc.). Any CMO is intended to serve some flow of applications (requirements) arriving at some random moments in time.

Service of the claim continues for some, generally speaking, random time, after which the channel is released and is ready to receive the next claim. The random nature of the flow of claims and the service time leads to the fact that at some time periods at the input of the QS, an unnecessarily large number of requests accumulates (they either enter the queue or leave the QS unserved). In other periods, the SMO will work with underload or even be 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 the appearance of some events (the arrival of a new request, the end of service, the moment when the request, tired of waiting, leaves the queue).

The subject of queuing theory - construction of mathematical models connecting the given operating conditions of the QS (the number of channels, their performance, rules of operation, the nature of the flow of applications) with the characteristics of interest to us - indicators of the QS efficiency. These metrics describe the QS's ability to handle the flow of applications. They can be: the average number of requests 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.

The mathematical analysis of the work of the QS is greatly facilitated if the process of this work is Markovsky, 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 approximated to Markov processes. The following mathematical apparatus describes Markov processes.

First division (by the presence of queues):

1. CMO with failures;

2. CMO with a queue.

In CMO with refusals a request arriving at a time when all channels are busy receives a refusal, leaves the QS and is not serviced in the future.

In the SMO with a queue a request arriving at the moment when all channels are busy does not leave, but enters the queue and waits for the opportunity to be served.

Queuing systems are subdivided on different types depending on how the queue is organized - limited or not limited ... Restrictions can relate to both the queue length and the waiting time, "service discipline".

So, for example, the following QSs are considered:

· QS with impatient requests (queue length and service time are limited);

· CMO with service with priority, i.e. some applications are served out of turn, etc.

In addition, QS are divided into open QS and closed QS.

In an 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 serves a group of machines that occasionally require adjustment, then the intensity of the flow of "requirements" from the machine tools depends on how many of them are already working properly and waiting for adjustment.

The classification of the CMO is far from limited to the listed varieties, but this is enough.

Consider the simplest queuing system with waiting - a one-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 claims per unit (time). A claim arriving at the moment when the channel is busy becomes queued and waits for service.

System with limited queue length. First, suppose that the number of seats in the queue is limited to the number m, i.e. if a customer arrives at the moment when there are already m-customers in the queue, it leaves the system unused. Further, letting m tend to infinity, we 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 claims in the system (both served 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 customers are in the queue;

The channel is busy, t-applications are in the queue.

The GSP is shown in Fig. 4. All intensities of streams of events transferring into the system along the arrows from left to right are equal, and from right to left -. Indeed, along the arrows from left to right, the system transfers the flow of customers (as soon as a customer arrives, the system goes to the next state), and from right to left, the flow of “releases” of the busy channel, which has intensity (as soon as the next customer is served, the channel will either be free or decrease number of applications in the queue).

Figure: 4. Single-channel CMO with waiting

Shown in fig. 4 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 denominator p, whence we get:

(7)

in this connection, the limiting 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 refusal, 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 time of stay of the application in the QS.

Probability of failure. Obviously, the application is rejected only if the channel is busy and all the m-places in the queue are also:

(9).

Relative throughput:

(10).

Average queue length. Let us 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 customer in the queue, with probability two customers, in general, with probability there are k-1 customers in the queue, etc., whence:

(11).

Since the sum in (11) can be interpreted as a derivative with respect to the sum of a geometric progression:

Substituting this expression in (11) and using from (8), we finally get:

(12).

Average number of orders in the system. Next, we obtain a formula for the average number of applications associated with the system (both queued and being serviced). Since, where is the average number of customers under service, and k is known, it remains to determine. Since there is only one channel, the number of serviced claims can be 0 (with probability) or 1 (with probability 1 -), whence:

.

and the average number of applications related to the QS is equal to:

(13).

Average waiting time for a request in the queue. Let's designate it; if a customer arrives at 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). Most likely, it will come to the system while servicing some request, but there will be no queue in front of it, and the request will wait for the start of its servicing for a period of time (the average time of servicing one request). With probability, there will be another one in the queue before the considered application, and the waiting time on average will be equal, etc.

If k \u003d m + 1, i.e. when a newly arriving customer finds the service channel busy and m-customers are in the queue (the probability of this), 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 here the expressions for the probabilities (8), we get:

(14).

Here we used 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 customers in the queue divided by the intensity of the flow of applications.

(15).

Average time spent by a request in the system. Let us denote the expectation of a random variable as the residence time of an application 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 petrol station (petrol station) is an SMO with one service channel (one dispenser).

The site at the station allows no more than three cars to be queued for refueling at the same time (m \u003d 3). If there are already three cars in the queue, the next car arriving at the station does not get into the queue. The flow of cars arriving for refueling has an intensity \u003d 1 (car per minute). The filling process takes an average of 1.25 minutes.

Define:

probability of failure;

relative and absolute throughput of gas stations;

the average number of cars waiting to be refueled;

the average number of cars at the filling station (including serviced cars);

average waiting time for a car in a queue;

average time spent by a car at a gas station (including service).

In other words, the average waiting time is equal to the average number of customers in the queue divided by the intensity of the flow of applications.

First, we find the reduced intensity of the flow of applications: \u003d 1 / 1.25 \u003d 0.8; \u003d 1 / 0.8 \u003d 1.25.

According to the formulas (8):

The probability of failure is 0.297.

Relative throughput of the QS: q \u003d 1- \u003d 0.703.

Absolute throughput of CMO: A \u003d\u003d 0.703 cars per minute.

We find the average number of cars in the queue by the formula (12):

those. the average number of cars waiting in line for refueling 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.

Average waiting time for a car in a 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 terms 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 customer entering the system will be served, therefore q \u003d 1, .

We obtain the average number of requests in the queue from (12) for:

The average number of requests in the system according to formula (13) at:

.

We obtain the average waiting time from formula (14) for:

.

Finally, the average residence time of an application in the CMO is:

System with limited queue length. Consider a channel queuing system with an expectation, which receives a flow of requests with an intensity; service intensity (for one channel); the number of places in the queue.

The states of the system 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 busy, no free;

there is a queue:

All n-channels are busy; one application is in the queue;

All n-channels, r-requests in the queue are busy;

All n-channels, r-requests in the queue are busy.

The GSP is shown in Fig. 17. Each arrow has the corresponding intensity of the streams of events. Along the arrows from left to right, the system is always transferred by the same flow of requests with intensity, along the arrows from right to left, the system is transferred to the service flow, the intensity of which is multiplied by the number of busy channels.

Figure: 17. Multichannel QS with waiting

The graph is typical for the processes of reproduction and death, for which a solution was previously obtained. Let us write expressions for the limiting probabilities of states using the notation: (here an expression is used for the sum of a geometric progression with a denominator).

Thus, all state probabilities are found.

Let's define the characteristics of the system efficiency.

Probability of failure. An incoming customer is rejected if all n-channels and all m-places in the queue are busy:

(18)

The relative throughput complements the probability of failure to one:

Absolute throughput of the CMO:

(19)

Average number of busy channels. For QS with refusals, 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 applications in the system: the latter value differs from the first by the average number of applications in the queue.

Let's 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 (the expression in brackets) the derivative of the sum of a 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 a request in the queue. Let us consider a number of situations that differ in the state in which the newly arrived claim will find the system and how long it will have to wait for service.

If the request finds not all channels busy, it will not have to wait at all (the corresponding terms in the mathematical expectation are equal to zero). If a claim arrives at a time when all n-channels are busy, but there is no queue, it will have to wait an average time equal to (because the "release flow" -channels has an intensity). If an application finds all channels busy and one application is in front of itself in the queue, it will have to wait on average for a period of time (for each application in front of it), etc. time. If a newly arrived claim finds itself in the queue of m-claims, then it will not wait at all (but it will not be served either). We find the average waiting time by multiplying each of these values \u200b\u200bby 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 a factor, i.e.

.

The average residence time of a claim in the system, 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 queuing system with waiting, when no more than m-claims can be in the queue simultaneously.

As before, when analyzing systems without restrictions, it is necessary to consider the relations obtained at.

We obtain the probabilities of the states from the formulas by passing to the limit (at). Note that the sum of the corresponding geometric progression converges for and diverges for\u003e 1. Assuming that<1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:

(22)

Failure probability, relative and absolute throughput. Since each application will sooner or later be served, the characteristics of the QS throughput will be:

We obtain the average number of requests in the queue for from (20):

,

and the average waiting time is from (21):

.

The average number of busy channels, as before, is determined through the absolute bandwidth:

.

The average number of applications associated with the QS is determined 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 dispensers (n \u003d 2) serves a flow of cars with an intensity \u003d 0.8 (cars per minute). Average service time for one machine:

There is no other gas station in this area, so the queue of cars in front of the gas station can grow almost indefinitely. Find the characteristics of the CMO.

Because the<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:

etc.

We find the average number of occupied channels by dividing the absolute throughput of the QS A \u003d 0.8 by the service rate \u003d 0.5:

The probability of not queuing at a gas station will be:

Average number of cars in the queue:

Average number of cars at a gas station:

Average waiting time in queue:

Average time spent by a car 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-customers simultaneously in the queue). In such a queue, a request that has grown into a queue does not leave it until it waits for service. In practice, there are QSs of a different type, in which an application, after waiting for a while, can leave the queue (the so-called "impatient" applications).

Consider a QS of this type, assuming that the waiting time limit is a random variable.

Suppose that there is an n-channel queuing system in which the number of places in the queue is not limited, but the time that an application is in the queue is some random variable with an average value, thus, a kind of Poisson “ flow of departures "with intensity:

If this flow is Poisson, then the process 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 serviced and queued:

no queue:

All channels are free;

One channel is busy;

Two channels are occupied;

All n-channels are busy;

there is a queue:

All n-channels are busy, one request is in the queue;

All n-channels are busy, r-customers are in the queue, and so on.

The graph of system states and transitions is shown in Fig. 23.

Figure: 23. CMO with limited waiting time

We mark this graph as before; all arrows leading from left to right will have the intensity of the flow of applications. For out-of-order states, the arrows leading from them from right to left will, as before, have the total flow rate for servicing 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 leaving the queue. If there are r-customers in the queue, then the total intensity of the exit flow 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 abbreviated notation, we write:

(24)

Let us note some features of the 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 limiting regime exists only if (for, the corresponding infinite geometric progression diverges, which physically corresponds to an unlimited growth of the queue for).

On the contrary, in the QS with “impatient” customers leaving the queue sooner or later, the established service mode at is always achieved, regardless of the reduced intensity of the flow of customers. This follows from the fact that the series for in the denominator of formula (24) converges for any positive values \u200b\u200bof and.

For QS with "impatient" requests, the concept of "probability of failure" does not make sense - each request enters the queue, but it 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 early. Let's calculate the average number of applications that leave the queue ahead of schedule. To do this, we calculate the average number of requests in the queue:

Each of these applications is subject to a “flow of exits” with intensity. This means that from the average number of - applications in the queue, on average, it will leave without waiting for service, - applications per unit of time, and on average, - applications will be serviced per unit of time. The relative throughput of the CMO will be:

The average number of busy channels is still obtained by dividing the absolute bandwidth A by:

(26)

Average number of applications in the queue. Relation (26) allows calculating the average number of customers in the queue without summing the infinite series (25). From (26) we get:

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 \u200b\u200b0, 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 at will result formulas (22), ie, "impatient" applications will become "patient".

Until now, we have considered systems in which the incoming stream is not connected in any way with the outgoing one. Such systems are called open-loop. In some cases, after a delay, serviced requests are returned to the entrance. Such QSs are called closed. The polyclinic serving this area, the team of workers assigned to the group of machines are examples of closed systems.

The same finite number of potential requirements circulates in a closed QS. Until a potential requirement has been realized as a service requirement, it is considered to be in a delay block. At the moment of implementation, it enters the system itself. For example, workers are serving a group of machines. Each machine is a potential requirement, becoming a reality 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 - in the system itself. Every worker is a service channel.

Let n - number of service channels, s - the number of potential applications, n <s , is the flow rate of requests for each potential requirement, μ is the service rate:

The system downtime probability is determined by the formula

R 0 = .

Final probabilities of system states:

P k \u003d at k \u003d at.

These probabilities are used to express the average number of occupied channels

=P 1 + 2P 2 +… + N (P n + P n + 1 +… + P s) or

\u003d P 1 + 2P 2 + ... + (n- 1) P n- 1 + n ( 1-P 0 -P 1 -… -P n-1 ).

Through we find the absolute throughput of the system:

as well as the average number of requests in the system

M \u003d s- \u003d s-.

Example 1 ... The input of a three-channel QS with refusals receives a flow of applications with an intensity \u003d 4 requests per minute, service time for one channel t service \u003d 1 / μ \u003d 0.5 min. Is it beneficial from the point of view of the QS throughput to force all three channels to serve requests at once, and the average service time is reduced by three times? How will this affect the average residence time of an application in the CMO?

Decision. We find the downtime probability of a three-channel QS by the formula

ρ = / μ \u003d 4/2 \u003d 2, n \u003d 3,

P 0 = = = 0,158.

The probability of failure is determined by the formula:

P open \u003d P n ==

P open \u003d 0.21.

Relative system capacity:

P obsl \u003d 1-R open 1-0,21=0,79.

Absolute system capacity:

A \u003d P obsl 3,16.

The average number of occupied channels is determined by the formula:

1.58, the proportion of channels occupied by service,

q = 0,53.

We find the average residence time of an application in the QS as the probability that the application is accepted for service, multiplied by the average service time: t CMO 0.395 minutes

Combining all three channels into one, we obtain a one-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 \u003d ρ P 0 = = 0,4,

relative bandwidth:

P obsl \u003d 1-R open =0,6,

absolute bandwidth:

A \u003d P obsl \u003d 2.4.

t SMO \u003d P obsl \u003d \u003d 0.1 min.

As a result of combining channels into one, the throughput of the system has decreased, since the probability of failure has increased. The average time spent by a request in the system has decreased.

Example 2 ... At the input of a three-channel QS with an unlimited queue, a flow of applications with an intensity \u003d 4 requests per hour, average service time for one request t \u003d 1 / μ \u003d 0.5 h. Find indicators of the efficiency of the system.

For the considered system n =3, \u003d 4, μ \u003d 1 / 0.5 \u003d 2, ρ \u003d / μ \u003d 2, ρ / n =2/3<1. Определяем вероятность простоя по формуле:

P \u003d .

P 0 = =1/9.

We find the average number of applications in the queue by the formula:

L =.

L = = .

We calculate the average waiting time for an application in the queue using the formula:

t \u003d \u003d 0.22 h.

Average time spent by a request in the system:

T \u003d t + 0,22+0,5=0,72.

Example 3 ... The hairdresser has 3 masters and there are 3 chairs in the waiting room. The flow of customers has an intensity \u003d 12 clients per hour. Average service time t service \u003d 20 min. Determine the relative and absolute throughput of the system, the average number of occupied seats, the average queue length, the average time that the client spends at the hairdresser.

For this task n =3, m =3, =12, μ =3, ρ =4, ρ / n \u003d 4/3. The downtime probability is determined by the formula:

R 0 =.

P 0 = 0,012.

The probability of denial of service is determined by the formula

P open \u003d P n + m \u003d .

P open =P n + m 0,307.

The relative throughput of the system, i.e. service probability:

P service =1-P open 1-0,307=0,693.

Absolute bandwidth:

A \u003d P obsl 12 .

Average number of busy channels:

.

The average queue length is determined by the formula:

L =

L \u003d 1,56.

Average waiting time for service in the queue:

t \u003d h.

Average number of applications in CMO:

M \u003d L + .

Average time spent by an application in the CMO:

T \u003d M / 0.36 hrs

Example 4 ... The worker operates 4 machines. Each machine fails with intensity \u003d 0.5 failures per hour, mean repair time t rem \u003d 1 / μ \u003d 0.8 h. Determine the throughput of the system.

This problem considers a closed QS, μ \u003d 1.25, ρ \u003d 0.5 / 1.25 \u003d 0.4. The probability of a worker's downtime is determined by the formula:

R 0 =.

P 0 = .

Worker employment probability P zan \u003d 1-R 0 . A \u003d ( 1-P 0 )μ \u003d 0.85μ machines per hour.

A task:

Two workers serve a group of four machines. Stops of a working machine occur on average after 30 minutes. The average setup time is 15 minutes. Runtime and setup time are exponentially distributed.

Find the average share of free time for each worker and the average operating time of the machine.

Find the same specifications for a system in which:

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 death and birth processes).

Decision:

The following states of the S system are possible:

S 0 - all machines are in good working order;

S 1 - 1 machine is being repaired, the rest are in good order;

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 serviceable;

S 11 - (1, 2, 3) the machines are being repaired, 4 the machine is operational;

S 12 - (1, 2, 4) the machines are being repaired, 3 the machine is operational;

S 13 - (1, 3, 4) machines are being repaired, 2 machine is working properly;

S 14 - (2, 3, 4) machines are being repaired, 1 machine is operational;

S 15 - all machines are being repaired.

System state graph ...

This S system is an example of a closed system, since each machine is a potential requirement, turning into a real one at the time 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 - in the system itself. Every worker is a service channel.

If a worker is busy, he adjusts μ-machines per unit of time, the throughput of the system:

Answer:

The average share of free time for each worker is ≈ 0.09.

Average operating time of the machine ≈ 3.64.

a) Two machines are assigned to each worker.

The probability of a worker downtime is determined by the formula:

Probability of a worker being employed:

If a worker is busy, he adjusts μ-machines per unit of time, the throughput of the system:

Answer:

The average share of free time for each worker is ≈ 0.62.

Average operating time of the machine ≈ 1.52.

b) Two workers always operate 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.

The examples of the simplest queuing systems (QS) were considered above. Protozoa does not mean elementary. The mathematical models of these systems are applicable and successfully used in practical calculations.

The possibility of using decision theory in queuing systems is determined by the following factors:

1. The number of applications in the system (which is considered as QS) must be large enough (in large quantities).

2. All applications entering the QS entrance must be of the same type.

3. For calculations by formulas, it is necessary to know the laws that determine the receipt of applications and the intensity of their processing. Moreover, the flows of applications must be Poisson.

4. The structure of the QS, i.e. the set of incoming requests 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 constant processing intensity.

One more constraint can be added to the above constraints, 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 "CMO with limited waiting time" and "Closed CMO" were studied, which was supplied by the teacher of the discipline. We also got acquainted with the application of the acquired knowledge in practice, i.e. consolidated the passed material.

1) http://www.5ballov.ru.

2) http://www.studentport.ru.

3) http://vse5ki.ru.

4) http: // revolution ..

5) Fomin G.P. Mathematical methods and models in commercial activities. M: Finance and Statistics, 2001.

6) Gmurman V.E. Theory of Probability and Mathematical Statistics. M: Higher School, 2001.

7) B.A. Soviets, S.A. Yakovlev. System modeling. M: Higher School, 1985.

8) Lifshits A.L. Statistical modeling of the QS. M., 1978.

9) Wentzel E.S. Operations research. M: Science, 1980.

10) Wentzel E.S., Ovcharov L.A. Probability theory and its engineering applications. M: Science, 1988.

In practice, one-channel CMOs with a queue are quite common (a doctor serving patients; a pay phone with one booth; a computer that fulfills user orders). In the theory of queuing, single-channel queuing systems also occupy a special place (it is to such queuing systems that most of the analytical formulas for non-Markov systems obtained so far belong). Therefore, we will pay special attention to a single-channel QS with a queue.

Let there be a single-channel QS with a queue that is not subject to any restrictions (neither in the length of the queue, nor in the waiting time). This QS receives a stream of applications with intensity X; the service flow has an intensity inverse to the average service time of a claim.It is required to find the final probabilities of the states of the QS, as well as the characteristics of its efficiency:

Average number of requests in the system,

Average time spent by a request in the system,

Average number of applications in the queue,

Average time spent by an application in the queue,

The probability that the channel is busy (the degree of channel loading).

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 served, therefore, for the same reason

Decision. The states of the system, as before, will be numbered according to the number of requests in the QS:

The channel is free

The channel is busy (serving a request), there is no queue,

The channel is busy, one request is in the queue,

The channel is busy, applications are in the queue,

Theoretically, the number of states is unlimited (infinite). The state graph has the form shown in Fig. 20.2. This is a scheme of death and reproduction, but with an infinite number of states. Along all arrows, the flow of requests with intensity 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 any final probabilities in this case? After all, the number of states of the system is infinite, and, in principle, the queue can grow infinitely! Yes, it is so: 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 for grows indefinitely. This fact seems to be especially "incomprehensible" when It would seem that the system does not have unrealizable requirements: during the service of one request, on average, one request arrives, and everything should be in order, but in reality it is not.

With the QS, it copes with the flow of requests only if this flow is regular, and the service time is also not random, equal to the interval between requests. In this “ideal” case, there will be no queue 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 grow indefinitely. In practice, this does not happen just because "an infinite number of applications in the queue" is an abstraction. These are the gross errors that can result from replacing random variables with their mathematical expectations!

But 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 us take liberty - we will use them for an infinite number of states. Let's calculate the final probabilities of states using formulas (19.8), (19.7). In our case, the number of terms in formula (19.8) will be infinite. Let's get an expression for

The series in formula (20.11) is a geometric progression. We know that the at series converges - it is an infinitely decreasing geometric progression with a denominator. For, the series diverges (which is an indirect, albeit not rigorous, proof that the final probabilities of states exist only for). Now we assume that this condition is satisfied, and Summing 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 loaded the system with the queue, if only it can cope with the flow of requests at all, the most probable number of requests in the system will be 0.

Let's find the average number of applications in the QS. Here you have to tinker a little. Random variable Z - the number of applications in the system - has possible values \u200b\u200bwith 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).

Let us substitute into formula (20.14) the expression for

Now we take out the sign of the sum:

Here again we will apply a "little trick": there is nothing else but a derivative of pore from the expression means,

Reversing the operations of differentiation and summation, we get:

But the sum in formula (20.15) is nothing but the sum of an infinitely decreasing geometric progression with the first term and denominator; this sum is equal to and its derivative. Substituting this expression in (20.15), we get:

(20.16)

Well, now let's apply Little's formula (19.12) and take the average residence time of an application in the system:

Find the average number of customers in the queue Let us reason as follows: the number of customers in the queue is equal to the number of customers in the system minus the number of customers under service. This means (according to the rule of addition of mathematical expectations), the average number of requests in the queue is equal to the average number of requests in the system minus the average number of requests under service. The number of claims 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 designated it). Obviously equal to one minus the probability that the channel is free;

Therefore, the average number of claims under service is

The system receives a Poisson flow of customers with intensity λ, the service flow has intensity μ, the maximum number of seats in the queue is t.If a claim enters the system when all the places in the queue are occupied, 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 idle;

S 1 - one request is served, the channel is busy, there is no queue;

S 2 - one request is served, one is in the queue;

S m +1 - one request is served, tqueue.

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 queuing system 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:

The brackets contain (m + 2) elements of a geometric progression with the first term 1 and the denominator ρ. According to the formula for the sum (m + 2) members of the progression:

(54)

(55)

The formulas for the probabilities of limiting states will be as follows:

Denial of service probabilitywe define requests as the probability that when a request enters the system, its channel will be busy and all the places in the queue are also occupied:

(57)

Hence the service probability(as well as from wearable bandwidth) are equal to the probabilities of the opposite event:

Absolute bandwidthIs the number of requests served by the system per unit of time:

(59)

Average number of service calls:

(60)

(61)

Average number of applications in the system:

(62)

Single-channel QS with limited queue can be viewed in Mathcad.

Example:

The parking lot is serviced by 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 SMO with unlimited queue

Let there be given a system S with pservice channels that receive the simplest flow of customers with intensity λ. Let the service flow be also the simplest and have intensity μ. The service queue is not limited.

According to the number of customers in the system, we denote the system states: 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 service flow intensity 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 busy with service, the service flow rate remains equal пμ,upon receipt of the following applications in the system.

To find the final state probabilities, we obtain formulas similar to how it was done for a single-channel system.

(63)

Hence the formulas for the final probabilities are expressed through

To find r 0 we get the equation:

For the terms in brackets, starting with the (n + 2) th, we can apply the formula for finding the sum of an infinitely decreasing geometric progression with the first term and the denominator ρ / n:

(66)

Finally, we get the Erlang formula for finding the probability of system downtime:

(67)

Here are the formulas for calculating the main indicators of the efficiency of the system.

The system will cope with the flow of applications if

condition is satisfied

, (68)

which means that the number of claims entered into the system per unit of time does not exceed the number of claims served by the system during the same time. Wherein denial of service probabilityis zero.

From here service probability(and also relative bandwidthsystems) are equal to the probability of the opposite event, that is, to one:

(69)

Absolutethroughputis the number of requests served by the system per unit of time:

(70)

If the system copes with the flow of applications, then in stationary mode outflow rateis equal to the intensity of the flow of claims entering the system, since all claims are serviced:

ν=λ . (71)

Since each channel serves μ claims per unit time, then average number of busy channelsyou can calculate:

(72)

Averagetimeservicechannel of one request ;

. (73)

The probability that, upon entering the system, an application will be in the queue is equal to the probability that there are more than papplications:

(74)

The number of applications under service,equal to the number of busy channels:

(75)

Average number of applications in the queue:

(76)

Then averagenumberapplicationsin system:

(77)

Average time spent by an application in the system (in the queue):

(78)

(79)

A multichannel QS with an unlimited queue can be viewed in the Mathcad system.

Example 1:

The hairdressing salon has 5 masters. During rush hour, the intensity of the flow of customers is 6 people. In hour. Serving one client lasts an average of 40 minutes. Determine the average queue length, assuming it is unlimited.

Fragment of the problem solution in Mathcad.

Example 2:

There are 2 windows at the railway ticket office. Time for servicing one passenger is 0.5 minutes. Passengers come to the ticket office for 3 people. Determine all characteristics of the system.

Fragment of the problem solution in Mathcad.

Continuation of solving the problem in Mathcad.

the operation or efficiency of the queuing system are as follows.

For CMO with rejections:

For CMO with unlimited waiting both the absolute and the relative throughput lose their meaning, since each incoming claim will sooner or later be served. For such a QS, important indicators are:

For CMO mixed type both groups of indicators are used: as relative and absolute bandwidthand the characteristics of the expectation.

Depending on the purpose of the queuing operation, any of the above 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 the states of a system in the course of its operation and to calculate performance indicators based on the known characteristics of the incoming stream and service channels.

There is no general analytical model for an arbitrary QS... Analytical models are developed for a limited number of special cases of QS. Analytical models that more or less accurately represent real systems are usually complex and difficult to visualize.

Analytical modeling of the QS is greatly facilitated if the processes occurring in the QS are Markov (the flows of applications are the simplest, the 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, 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 drives by without delay. The flow of trucks is the simplest, the check time is random with an exponential distribution.

This situation can be simulated by a three-channel QS with failures (out of turn). The system is open-loop, with homogeneous applications, single-phase, with absolutely reliable channels.

Description of states:

All inspectors are free;

One inspector is busy;

Two inspectors are occupied;

Three inspectors are busy.

The system state graph is shown in Fig. 2.11.

Figure: 2.11.

On the graph: - the intensity of the flow of trucks; - the intensity of document checks by one car inspector.

Simulations are carried out to identify the part of the vehicles that will not be tested.

Decision

The sought-after part of the probability is the probability that all three inspectors will be employed. Since the state graph represents a typical scheme of "death and reproduction", we will find it using dependencies (2.2).

The throughput of this post of traffic inspectors can be characterized by relative throughput:

Example 2.6... A group of three officers was assigned to receive and process reports from the reconnaissance group in the intelligence department of the association. The expected intensity of the flow of reports is 15 reports per hour. Average processing time of one report by one officer -. Each officer can receive reports from any reconnaissance group. The released officer processes the last of the reports received. Incoming reports must be processed with a probability of at least 95%.

Determine if the assigned team of three officers is sufficient to complete the assigned task.

Decision

The group of officers works as a refusal system consisting of three channels.

Stream of reports with intensity can be considered the simplest, since it is a total of several reconnaissance groups. Service intensity ... The distribution law is unknown, but this is insignificant, since it has been 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 attitude is called reduced intensity of the flow of applications... Its physical meaning is as follows: the value is the average number of claims arriving at the QS during the average service time of one claim.

In the example .

In the considered QS, a failure occurs when all three channels are busy, that is. Then:

As probability of failure in the processing of reports is more than 34% (), 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 we will calculate:

Thus, only a group of six officers will be able to process incoming reports with a 95% probability.

2.5.2. Multichannel CMO with waiting

Example 2.7... There are 15 crossing means of the same type on the river crossing section. 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 (taking into account the return of the crossing means).

Assess the main characteristics of the crossing, including the probability of an immediate crossing immediately upon the arrival of a vehicle.

Decision

Absolute bandwidth , that is, everything that approaches the ferry is almost immediately ferried.

Average number of crossing facilities in operation:

Ferry utilization and downtime rates:

A program was also developed to solve the example. The time intervals for the arrival of equipment at the crossing, the crossing time are taken to be distributed according to the exponential law.

The utilization rates of the crossing 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 incoming traffic

N identical channels receive the simplest flow of requests with intensity λ ... If at the moment of receipt of a request all channels are busy, then this request enters the queue and waits for the start of servicing. The service time of each customer is a random variable that obeys an exponential distribution law with the parameter μ .

Calculation formulas
The probability that all channels are free

The probability of being busy kchannels, provided that the total number of customers in service does not exceed the number of channels,

The probability that the system is k applications, in the case when their number is more than the number of channels,

The probability that all channels are busy

Average waiting time for an application to start service in the system

Average queue length

Average number of free channels

Example
A petrol station with two dispensers serves Poisson traffic at a rate of λ \u003d 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 petrol station in this area, so the queue in front of the petrol station can grow almost indefinitely. Find:
1) the average number of occupied columns;
2) the likelihood of no queue at the gas station;
3) the likelihood that you will have to wait for the start of 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 the filling station.
Decision... By the condition of the problem, n \u003d 2, λ \u003d 0.8; μ \u003d 1 / t obsl \u003d 0.5; ρ \u003d λ / μ \u003d 1.6
Because the ρ /n=0,8<1, то очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы системы массового обслуживания.
We find the probabilities of the states of the QS:

Average number of occupied 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 not queuing at a gas station:

The probability that you will have to wait for the start of service is equal to the probability that all columns are busy:
p 0 + p 1 + p 2 \u003d 0.1111 + 0.1778 + 0.1422 \u003d 0.4311
Average number of cars in the queue:

Average waiting time in queue:
Average time spent by a car at a gas station:
t preb \u003d t service + t standby \u003d 2 + 3.5556 \u003d 5.5556 min.
Average number of cars at a gas station:
N zan + L och \u003d 1.6 + 2.8444 \u003d 4.4444
Consider a single-channel queuing system with expectations, in which the number of channels is equal to one n \u003d 1, the arrival rate of claims is λ, the service rate is equal to μ. A claim arriving at the time when the channel is busy enters the queue and waits for service. The number of places in the queue is limited and equal m... If all the places in the queue are occupied, then the request leaves the queue not served. Let's analyze the state of the system:

• S 0 - the channel is free;
• S 1 - the channel is busy;
• S 2 - the channel is busy, one request is in the queue;
• S k - the channel is busy, (k – 1) customers in the queue;
• S m + 1 - the channel is busy, in the queue m applications.

Let's draw a graph of states of such a QS (Fig. 25).

Figure: 25
Using Erlang's formulas, we find the probabilities of events that the QS is in the state S 1 , S 2 , …, S m + 1:
(28)

Moreover, the probability that a customer arriving at the system will find it free is
. (29)
The ratio of the arrival rate λ of the claims to the rate of servicing the claims μ is the reduced rate μ, i.e.

ρ=λ/μ
Let us replace the ratio λ / µm to ρ in formulas (28) and (29), then the expressions take the form:

(30)
Probability R 0 will be calculated using the following formula:
p 0 \u003d -1. (31)
Expression for probability P 0 is a geometric progression, the sum of which will be

.
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 finding the system in any state.
Formula for P 0 is valid for the case when ρ ≠ 1. In the case when ρ \u003d 1, i.e., the arrival rate of claims is equal to the rate of their servicing, another formula is used to calculate the probability that the system is free:

,
where m is the number of customers in the queue.

We define performance characteristics of a single-channel QS:

• the probability that the next application arriving in the system will be rejected R open;
• absolute throughput A,
• relative bandwidth Q,
• number of busy channels k,
• the average number of customers in the queue r,
• average number of applications related to QS, z.

The next customer entering the system is rejected if the channel is busy, i.e., another customer is being serviced, and all m places in the queue are also occupied. then the probability of this event can be calculated using the following formula:

. (32)
The probability that a claim will arrive in the system and either will 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 claims that can be serviced per unit of time, i.e., the absolute throughput, is calculated as follows:

A \u003d Q λ (34)
Thus, using formulas (32), (33), (34), one can calculate the main performance indicators for any queuing system. now we will derive expressions for calculating the characteristics inherent only in this QS.
The average number of customers 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 customer in the service queue;
♦ R 3 - the probability that there are two applications in the queue;
♦ R k - the probability that there is (k – 1) customer in the queue;
♦ R m + 1 is the probability that there are m customers in the queue.
Then the average number of applications in the queue can be calculated as follows:
r \u003d 1 P 2 + 2 P 3 + ... + (k-1) P k + ... + m P m + 1. (35)
Substitute into formula (35) the previously found values \u200b\u200bof the probabilities calculated in formula (30):
r \u003d 1 ρ 2 p 0 + 2 ρ 3 p 0 + ... + (k-1) ρ k p 0 + ... + m ρ m + 1 p 0. (35)
Let's take out the probability P 0 and R 2, then we get the final formula for calculating the average number of requests in the service queue:
r \u003d ρ 2 p 0 (1 + 2 ρ + ... + (k-1) ρ k-2 + ... + m ρ m-1)
Let us derive a formula for the average number of requests associated with the QS, z, i.e., the number of requests in the queue that are being serviced. Consider the total number of requests associated with the QS, z as the sum of two values \u200b\u200bof the average number of requests in the queue r and the number of busy channels k:

z \u003d r + k.
Since there is only one channel, the number of occupied channels k can take on the values \u200b\u200b0 or 1. The probability that k \u003d 0, i.e. the system is free, corresponds to the probability P 0, the value of which can be found by the formula (31). If k \u003d 1, i.e. the channel is busy serving 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 CMO with waiting

The queuing system has one channel. The incoming flow of service requests is the simplest flow with intensity l. The service flow intensity is equal to m (i.e., on average, a continuously busy channel will issue m. Serviced claims). Service duration is a random variable subject to an exponential distribution law. Service flow is the simplest Poisson flow of events. A claim arriving at a time when the channel is busy enters the queue and awaits service.
Suppose that no matter how many requests arrive at the input of the serving system, the given system (queue + serviced clients) cannot accommodate more than N-requests (requests), i.e., clients that have not been expected are forced to be serviced elsewhere ... Finally, the source generating service requests has an unlimited (infinitely large) capacity.
The state graph of the QS in this case has the form shown in Fig. 3.2.


State graph of a single-channel QS with waiting (scheme of death and reproduction)
The states of the QS 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).
Stationary sag in this system will be described by the following system of algebraic equations:

p -status 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 optional, since the number of applications admitted to the serving system is controlled by introducing a limit on the queue length (which cannot exceed N- 1), and not the ratio between the intensities of the input flow, i.e., not the ratio
l / m \u003d p
We define characteristics of a single-channel systemwith waiting and limited queue length equal to (N -1):

Consider an example of a single-channel queuing system with waiting.
Example 3.2. A specialized diagnostic post is a single-channel system. The number of parking lots awaiting diagnostics is limited to 3 [(N- 1) \u003d 3]. If all the parking lots are occupied, that is, there are already three cars in the queue, then the next car arriving for diagnostics does not get into the service queue. The flow of cars arriving for diagnostics is distributed according to Poisson's law and has an intensity l\u003d 0.85 (car per hour). The time of car diagnostics is distributed according to the exponential law and is on average 1.05 hours.
It is required to define probabilistic characteristics of a stationary diagnostic station.
Decision
1. Parameter of car maintenance flow:

2. The reduced intensity of the flow of cars is defined as the ratio of the intensities l and m, i.e.

3. Let's 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 likelihood of refusal to service the car:
P open \u003d P 4 \u003d ρ 4 P 0 ≈ 0.158
5. Relative throughput of the diagnostic station:
q \u003d 1-P open \u003d 1-0.158 \u003d 0.842
6. Absolute throughput of the diagnostic station
A \u003d λ q \u003d 0.85 0.842 \u003d 0.716 (car per hour)
7. Average number of cars being serviced and queued (ie in the queuing system):

8. Average time of car stay in the system:
9. Average length of time an application is in the queue for service:
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\u003d 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 on average in 15.8% of cases (P open\u003d 0.158). As indicators of the efficiency of the QS with the expectation, in addition to the already known indicators - absolute A and relative Q throughput, the probability of failure P open. , the average number of occupied channels (for a multichannel system) we will also consider the following: L system. - the average number of requests to the system; T sist. - the average time spent by the application in the system; L pts. - the average number of applications in the queue (queue length); T och. - the average time of a request being in the queue; R busy .. - the probability that the channel is busy (the degree of channel loading).

Single channel system with unlimited queue

In practice, one-channel CMOs with an unlimited queue are often encountered (for example, a payphone with one booth).
Let's consider the problem.
There is a single-channel QS with a queue, on which no restrictions are imposed (neither on the length of the queue, nor on the waiting time). The flow of claims arriving at the QS has intensity λ, and the flow of service has intensity μ. It is necessary to find the limiting probabilities of states and indicators of the effectiveness of the QS.
The system can be in one of the states S 0, S 1, S 2, ..., S k, according to the number of requests in the QS: S 0 - the channel is free; S 1 - the channel is busy (serving 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) customers are in the queue, etc.
The QS state graph is shown in Fig. 8.

Figure: 8
This is a process of death and multiplication, but with an infinite number of states, in which the flow rate of claims is λ, and the rate of service flow is μ.
Before writing down the formulas for the limiting probabilities, you need to be sure of their existence, because in the case when the time t → ∞, the queue can grow indefinitely. It has been proven that ifρ<1, those. the average number of incoming claims is less than the average number of serviced claims (per unit time), then the limiting probabilities exist. Ifρ≥1, the queue grows indefinitely.

To determine the limiting probabilities of states, we will use formulas (16), (17) for the process of death and reproduction (here we assume a certain laxity, since these formulas were previously obtained for the case of a finite number of system states). We get (32)
Since the limiting probabilities exist only for ρ< 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
p 0 \u003d 1-ρ, (33)
and taking into account relations (17)
p 1 \u003d ρ · p 0; p 2 \u003d ρ 2 · p 0; ...; p k \u003d ρ k p 0; ...
find the limiting probabilities of other states
p 1 \u003d ρ · (1-ρ); p 2 \u003d ρ 2 · (1-ρ); ...; p k \u003d ρ k (1-ρ); ... (34)
The limiting probabilities p 0, p 1, p 2,…, p k,… form a decreasing geometric profession with the denominator p< 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
The average number of applications in the system L system. will be determined by the mathematical expectation formula, which, taking into account (34), takes the form
(35)
(summation from 1 to ∞, since the zero term is 0 · p 0 \u003d 0).
It can be shown that formula (35) transforms (for ρ< 1) к виду
(36)
Find the average number of applications in the queue L och. It's obvious that
L och \u003d L system -L about (37)
where L vol. is the average number of applications being serviced.
The average number of claims under service is determined by the formula for the mathematical expectation of the number of claims under service, which takes the values \u200b\u200b0 (if the channel is free) or 1 (if the channel is busy):
L och \u003d 0 p 0 + 1 (1-p 0)
those. the average number of claims under service is equal to the probability that the channel is busy:
L och \u003d P zan \u003d 1-p 0, (38)
By virtue of (33)
L och \u003d P zan ρ, (39)
Now, according to formula (37), taking into account (36) and (39)
(40)
It has been proven that for any nature of the flow of requests, for any distribution of the service time, for any discipline of service, the average time of a request in the system (queue) is equal to the average number of requests in the system (in the queue) divided by the intensity of the flow of requests,those.
(41)
(42)
Formulas (41) and (42) are called little's formulas.They follow 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 requests 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 is in the queue
(44)

Single-channel CMO with waiting without limitation on the capacity of the waiting unit

The stationary mode of operation of this QS exists as t → ∞ for any n \u003d 0,1,2, ... and when l< m.Система алгебраических уравнений, описывающих работу СМО при t®¥ для любого n = 0, 1, 2...., имеет вид
The solution to this system of equations has the form
P n \u003d (1-ρ) ρ n, n \u003d 0,1,2, ... (3.21)
where ρ \u003d λ / μ< 1
The characteristics of a single-channel QS with waiting, without restrictions on the queue length, are as follows:
average number of clients (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, ie, the queue length is not limited.
It is required to determine the final values \u200b\u200bof the following probabilistic characteristics:

• probabilities of system states (diagnostic post);
• the average number of cars in the system (at service and in the queue);
• the average length of time a car has been in the system (for service and in queue);
• the average number of cars in the queue for service;
• the average length of time a car is in line.

Decision
1. The service flow parameter m and the reduced vehicle flow rate p are defined in Example 3.2:
m \u003d 0.952; p \u003d 0.893.
2. Let us calculate the limiting probabilities of the system by 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 P about determines the proportion of time during which the diagnostic post is forced to be idle (idle). In our example, it is 10.7%, since P about= 0,107.
3. Average number of cars in the system (at service and in queue):
4. Average length of stay of a client in the system:

6. The average duration of the car's stay in the queue
7. Relative system capacity:
that is, every request entering the system will be served.
8. Absolute bandwidth: A\u003d l q\u003d 0.85 1 \u003d 0.85
It should be noted that the company that performs vehicle diagnostics is primarily interested in the number of customers who will visit the diagnostic post when the queue length restriction is lifted.
Suppose, in the original version, the number of parking spaces for arriving cars was equal to three (see example 3.2). The frequency m of situations when a vehicle arriving at the diagnostic post is unable to join the queue:

t\u003d l P N

In our example, with N \u003d 3 + 1 \u003d 4 and p \u003d 0.893,
m \u003d l P about{!LANG-cb4aa236aa89b58df4407f405af28756!}
{!LANG-42b6e9c438ce97a892709129307ea5ff!}
{!LANG-e1a465ef819f62e50d5f8fa99688adc6!}

{!LANG-f29e72c28ee4de896662e531ced3f30a!}

{!LANG-540dfa1d51fc20c469896ad85d5ae1c9!}

{!LANG-2f2ead958ab8e9478eec16b4b96cc53a!} n{!LANG-1b56c3aeeb2497de45224595d1f756bb!} {!LANG-72cfd272ace172fa35026445fbef9b03!}{!LANG-cac4efb1c2bcc6038b72cd286467f2b3!}

{!LANG-c7e2a57328d1ff4b177aaf57e70f0eaf!}

{!LANG-169dc186ac190361a2ec34afd20f5f53!}
, (50)
{!LANG-ab0a0e1a62abcf25964ca6b1fa505672!}
{!LANG-4f0a9620bf98d209ada06af6caa606d2!}
{!LANG-0bd2a5f86f56c870a840f16fcd5eebcc!}
{!LANG-3d7bf2c69366a4450734b95291bc4e65!}{!LANG-81dd27550e657dc416d8fb1447efd16a!}< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q{!LANG-297ac3be7474f70d0432bb0a0fc311d7!} A{!LANG-2d5d96dc3abc538c95fe2a2972c4f680!}

{!LANG-28c6101dd187c0f916d01f2078a2d2e1!}

{!LANG-14f92f53115cc5c4f97b8bd48bf597bb!}{!LANG-1d6a9fed3bd7cf3cf853ee0d99c73316!} {!LANG-11194a930d666cf255acbc5ee04f50c7!}{!LANG-b050fd18d747dfd62889ab8a4c08d7f9!}
{!LANG-5ae7e4ae94d385450b9cb52b73bbd9ed!}
{!LANG-3989607ddb0044f642257d2d7ddb6262!}
{!LANG-315fb4c811a5d090a76bea28f6574ba2!}{!LANG-f51fe39f1e915bbb0ea6fa8a23904d27!}

{!LANG-9652893c989c3bfdf84f1340cdd4cd1c!}
{!LANG-535ea4ce44d55ec1012ebb7c5309da59!}

{!LANG-0a0c1078c2ed6cb0b4fbc7d56b4a579b!}

 

{!LANG-1b75b6e50e1a24775b05d59b0041a55c!}

• {!LANG-1696a098947b92b35780785d1c6fc3e0!};
• {!LANG-61b958d457922e1604cebc5286dea1f9!};
• {!LANG-ebf78d94d37e58bddcc386bec56a8c4f!};
• {!LANG-4d2c9923961d56aae4998dec3a32fbb5!};
• {!LANG-751b335275e275633dfcd83128c5bc5b!};
• {!LANG-3d2e84f350165f01bdc1e89bf2424fd9!};
• {!LANG-b6a6f4c2057349d9dae65f468aebab75!};
• {!LANG-8cd0cfb4bcf3a0a88383d4978183efba!};