Queuing system with limited queue. Single channel smoo with unlimited queue. Work order

Multi-channel queuing system with limited queue

Let the input of a QS with service channels receive Poisson flow applications with intensity. The intensity of servicing the request by each channel is equal, and the maximum number of places in the queue is equal.

The graph of such a system is shown in Figure 7.

Figure 7 - Graph of states of a multi-channel QS with a limited queue

All channels are free, there is no queue;

busy l channels ( l= 1, n), there is no queue;

All n channels are busy, there is a queue i applications ( i= 1, m).

Comparison of the graphs in Figure 2 and Figure 7 shows that the latter system is a special case of the birth and death system, if the following substitutions are made in it (left notations refer to the birth and death system):

Expressions for the final probabilities are easy to find from formulas (4) and (5). As a result, we get:

The formation of a queue occurs when, at the moment of receipt of the next request in the QS, all channels are busy, i.e. there are either n, or (n+1),…, or (n + m - 1) customers in the system. Because these events are incompatible, then the probability of forming a queue p och is equal to the sum of the corresponding probabilities:

A request is denied service when all m places in the queue are occupied, i.e.:

Relative throughput is equal to:

The average number of applications in the queue is determined by formula (11) and can be written as:

The average number of requests served in the QS can be written as:

Average number of applications in the CMO:

The average residence time of an application in the QS and in the queue is determined by formulas (12) and (13).

Multi-channel queuing system with unlimited queue

The graph of such a QS is shown in Figure 8 and is obtained from the graph in Figure 7 with.

Figure 8 - Graph of states of a multichannel QS with unlimited queue

The formulas for the final probabilities can be obtained from the formulas for the n-channel QS with a bounded queue at. It should be borne in mind that when the probability p 0 = p 1 =…= p n = 0, i.e. the queue grows indefinitely. Therefore, this case is of no practical interest, and only the case is considered below. When from (26) we get:

The formulas for the remaining probabilities have the same form as for QS with a limited queue:

From (27) we obtain an expression for the probability of the formation of a queue of applications:

Since the queue is not limited, the probability of refusal to service the request is:

Absolute Bandwidth:

From formula (28) at , we obtain an expression for the average number of requests in the queue:

The average number of serviced requests is determined by the formula:

The average residence time in the QS and in the queue is determined by formulas (12) and (13).

Multi-channel queuing system with limited queue and limited waiting time in queue

The difference between such a QS and the QS considered in Subsection 5.5 is that the service waiting time when the application is in the queue is considered to be a random variable distributed according to an exponential law with the parameter, where is the average waiting time of the application in the queue, and - makes sense intensity of the flow of requests leaving the queue. The graph of such a QS is shown in Figure 9.

Figure 9 - Graph of a multi-channel QS with a limited queue and a limited waiting time in the queue

The remaining designations here have the same meaning as in the subsection.

Comparison of graphs in fig. 3 and 9 shows that the latter system is a special case of the birth and death system if the following substitutions are made in it (the left notation refers to the birth and death system):

Expressions for the final probabilities are easy to find from formulas (4) and (5) taking into account (29). As a result, we get:

where. The probability of forming a queue is determined by the formula:

A request is denied service when all m places in the queue are occupied, i.e. denial of service probability:

Relative throughput:

Absolute Bandwidth:

The average number of applications in the queue is found by formula (11) and is equal to:

The average number of applications served in the QS is found by formula (10) and is equal to:

Purpose of QS service. The online calculator is designed to calculate the following indicators single-channel QS:

channel failure probability, free channel probability, absolute throughput;
relative throughput, average service time, average channel idle time.

Instruction. To solve such problems in online mode select the QS model. Specify application 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 requests in the queue (to calculate the probability of finding these requests in the queue). see solution example. . The resulting solution is saved in a Word file.

Classification of single-channel queuing systems

Example #1. Auto Gas station It has one gas station. It is assumed that the simplest flow of cars arrives at the station with an intensity of λ=11 cars/h. Application service time is a random variable that obeys an exponential law with the parameter μ=14 vehicles/h. Determine the average number of cars at the station.

Example #2. There is a point for preventive inspection of machines with one inspection group. It takes an average of 0.4 hours to inspect and identify defects for each machine. An average of 328 cars per day are received for inspection. The flows of requests and services are the simplest. If the car that arrived at the inspection point does not find a single channel free, it leaves the inspection point unserved. Determine the limiting probabilities of the states and the characteristics of the maintenance of the preventive inspection point.
Solution. Here α = 328/24 ≈ = 13.67, t = 0.4. These data must be entered into the calculator.

IN commercial activities more common QS with waiting (queue).

Consider a simple single-channel QS with a limited queue, in which the number of places in the queue m is a fixed value. Consequently, an application that arrives at the moment when all places in the queue are occupied is not accepted for service, does not enter the queue, and leaves the system.

The graph of this QS is shown in Fig. 3.4 and coincides with the graph in Fig. 2.1 describing the process of "birth - death", with the difference that in the presence of only one channel.

The labeled graph of the process of "birth - death" of service, all intensities of service flows are equal

QS states can be represented as follows:

S0 - service channel is free,

S, - the service channel is busy, but there is no queue,

S2 - the service channel is busy, there is one request in the queue,

S3 - the service channel is busy, there are two requests in the queue,

Sm+1 - the service channel is busy, all m places in the queue are occupied, any next request is rejected.

To describe a random QS process, you can use the rules and formulas outlined earlier. Let us write the expressions defining the limiting probabilities of the states:

The expression for p0 can be written in this case in a simpler way, using the fact that the denominator is a geometric progression with respect to p, then after the appropriate transformations we get:

c= (1-s)

This formula is valid for all p other than 1, but if p = 1, then p0 = 1/(m + 2), and all other probabilities are also equal to 1/(m + 2).

If we assume m = 0, then we pass from consideration of a single-channel QS with waiting to the already considered single-channel QS with denials of service.

Indeed, the expression for the marginal probability p0 in the case m = 0 has the form:

po \u003d m / (l + m)

And in the case of l \u003d m, it has the value p0 \u003d 1 / 2.

Let us define the main characteristics of a single-channel QS with waiting: the relative and absolute throughput, the probability of failure, as well as the average queue length and the average waiting time for an application in the queue.

The application is rejected if it arrives at the moment when the QS is already in the state Sm + 1 and, therefore, all places in the queue are occupied and one channel serves

Therefore, the probability of failure is determined by the probability of occurrence

Sm+1 states:

Potc = pm+1 = cm+1 * p0

The relative throughput, or the proportion of serviced requests arriving per unit of time, is determined by the expression

Q \u003d 1- potk \u003d 1- cm + 1 * p0

the absolute bandwidth is:

The average number of applications L standing in the service queue is determined by the mathematical expectation of the random variable k - the number of applications standing in the queue

the random variable k takes the following only integer values:

1 - there is one application in the queue,
2 - there are two applications in the queue,

t-all places in the queue are occupied

The probabilities of these values are determined by the corresponding state probabilities, starting from the state S2. The distribution law of a discrete random variable k is depicted as follows:

Table 1. Law of distribution of a discrete random variable

The mathematical expectation of this random variable is:

Loch = 1* p2 +2* p3 +...+ m* pm+1

IN general case for p ? 1, this sum can be transformed using geometric progression models to a more convenient form:

Loch = p2 * 1-pm * (m-m*p+1)*p0

In the particular case at p = 1, when all probabilities pk turn out to be equal, one can use the expression for the sum of the terms of the numerical series

1+2+3+ m = m(m+1)

Then we get the formula

L "och \u003d m(m+1)* p0 = m(m+1)(p=1).

Applying similar reasoning and transformations, it can be shown that the average waiting time for servicing a request and a queue is determined by Little's formulas

Point \u003d Loch / A (at p? 1) and T1och \u003d L "och / A (at p \u003d 1).

Such a result, when it turns out that Tox ~ 1/l, may seem strange: with an increase in the intensity of the flow of requests, it seems that the queue length should increase and the average waiting time should decrease. However, it should be borne in mind that, firstly, the value of Loch is a function of l and m and, secondly, the QS under consideration has a limited queue length of no more than m applications.

A request that arrives at the QS at a time when all channels are busy is rejected, and, therefore, its “waiting” time in the QS is zero. This leads in the general case (for p? 1) to a decrease in Tochrost l, since the proportion of such applications increases with the growth of l.

If we abandon the restriction on the length of the queue, i.e. aspire m--> >?, then cases p< 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

For sufficiently large k, the probability pk tends to zero. Therefore, the relative throughput will be Q = 1, and the absolute throughput will be equal to A - l Q - l, therefore, all incoming requests are serviced, and the average queue length will be equal to:

Loch = p2 1-p

and the average waiting time according to Little's formula

Point \u003d Loch / A

In the limit p<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t >?). Therefore, the limiting probabilities of states cannot be determined: for Q= 1 they are equal to zero. In fact, the CMO does not fulfill its functions, since it is not able to service all incoming applications.

It is easy to determine that the share of serviced requests and the absolute throughput, respectively, average c and m, however, an unlimited increase in the queue, and, consequently, the waiting time in it, leads to the fact that after a while, requests begin to accumulate in the queue for an unlimited time.

As one of the characteristics of the QS, the average time Tsmo of the stay of an application in the QS is used, including the average time spent in the queue and the average service time. This value is calculated by Little's formulas: if the queue length is limited, the average number of applications in the queue is equal to:

Lmo= m+1;2

tsmo= Lcmo; at p?1

A then the average residence time of the request in the system queuing(both in queue and under service) is equal to:

tsmo= m+1 at p ?1 2m

Calculations of the main indicators of the functioning of a system with n service channels, with limited places in the queue, are carried out similarly to those that were made for a system with an unlimited queue. A feature of the functioning of systems with limited queue length is a finite number of system states.

Let the service channels receive the simplest flow of requirements with intensity λ . The service flow coming from one channel is also the simplest and has intensity μ. The number of places in the queue is limited and equal to T.

By the number of requests in the system, we denote the states of the system:

S0- idle state;

S p- the state of the system when all channels are busy with service;

S p+1 - all channels are busy, one request is in the queue;

S p+t - queue T applications.

Since the flows of requests and services are ordinary, the state graph is depicted as a scheme of death and reproduction. The difference from a similar scheme for an unlimited queue is only that the number of states is finite. The state graph of such a system is depicted as a diagram in Figure 7:

λ λ λ λ λ λ

……. …….

S 0 S 1 S 2 S n S n+m

μ 2μ 3μ ………. nμ nμ …… nμ

Figure 7: Multichannel QS with limited queue.

Let us compose a system of algebraic equations for finding the final probabilities of states:

Where do we get Erlang formulas for a multichannel system with limited queue:

Latest T terms in parentheses are the sum T the first terms of the geometric progression with the denominator ρ/n which is equal to:

Thus, to calculate p 0 we get the formula:

The formulas for the probabilities of limit states will look like:

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

Number of channels which necessary to have the system cope with the flow of applications, we determine from the condition

In this case, the relation ρ< 1.

Denial of Service Probability We define requests as the probability that when a request enters the system, all n channels will be occupied, and all m places in the queue will be occupied:

From here service probability(as well as relative throughput systems) are equal to the probabilities of the opposite event:

Absolute bandwidth - the number of applications served by the system per unit of time:

Since each channel serves μ requests per unit of time, then average busy channels can be calculated:

Average service time one application channel :

Average number of applications in the queue:

Average number of requests under service is equal to the average number of busy channels:

Average number of applications in the system(under service and in queue) is equal to:

A multi-channel QS with a limited queue can be considered in Mathcad.

Example:

The gas station site can accommodate no more than 3 cars at the same time, and if it is busy, then the next car that arrives at the station does not queue. Service flow intensity λ=0.5 cars per minute. Service flow intensity μ=0.4 cars per minute. Determine all the characteristics of the QS.

Fragment of solving the problem in Mathcad.

Continuation of the problem in Mathcad.

Multi-channel QS with unlimited queue

Let's consider the task. Available n-channel QS with unlimited queue. The flow of applications entering the QS has an intensity l, and the flow of services has an intensity m. It is necessary to find the limiting probabilities of the states of the QS and indicators of its efficiency.

The system can be in one of the states S0, S1, S2, ..., Sk .., Sn, ..., numbered according to the number of requests in the QS: S0 - there are no requests in the system (all channels are free); S -- one channel is occupied, the rest are free; S2-- two channels are occupied, the rest are free; Sk -- k channels are occupied, the rest are free; Sn -- all n channels are busy (there is no queue); Sn+1 -- all n channels are occupied, there is one request in the queue; Sn+r -- all n channels are busy, r requests are in the queue.

The state graph of the system is shown in Figure 7. Let us pay attention to the fact that, unlike the previous QS, the intensity of the service flow (transferring the system from one state to another from right to left) does not remain constant, but as the number of requests in the QS increases from 0 to n increases from m to n??, as the number of service channels increases accordingly. When the number of requests in the QS is greater than n, the intensity of the service flow remains equal to nm.

Figure 7 - Graph of states of multichannel QS

It can be shown that for c/n< 1 предельные вероятности существуют. Если с/n ? 1, очередь растет до бесконечности. Используя формулы (20) и (21) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью

The probability that the application will be in the queue,

For an n-channel QS with an unlimited queue, using the previous tricks, one can find:

average busy channels

average number of applications in the system

The average residence time of an application in the queue and the average residence time of an application in the system, as before, are found using the Little formulas (48) and (49).

Comment. For a QS with an unlimited queue for s< 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа Ротк = 0, Q=1, а равна интенсивности входящего потока заявок, т.е. А = л.

QS with limited queue

QS with a bounded queue differ only in that the number of requests in the queue is limited (cannot exceed some given m). If a new claim arrives at the moment when all places in the queue are occupied, it leaves the QS unserved, i.e. gets rejected.