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

Multi-channel queuing system with limited queue

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

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

Figure 7 - State graph of a multichannel QS with a limited queue

All channels are free, there is no queue;

Busy l channels ( l \u003d 1, n), there is no queue;

All n channels are busy, there is i applications ( i \u003d 1, m).

Comparison of the graphs in Figure 2 and Figure 7 shows that the last system is a special case of the birth and death system, if the following changes 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). As a result, we get:

The formation of a queue occurs when at the moment the next request arrives at the QS, all channels are busy, i.e. the system contains either n, or (n + 1),…, or (n + m - 1) customers. Because these events are inconsistent, then the probability of queue formation 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 applications served in the QS can be written as:

Average number of applications in the CMO:

The average time spent by 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 for.

Figure 8 - The state graph 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 limited queue at. It should be borne in mind that for the probability p 0 \u003d p 1 \u003d ... \u003d p n \u003d 0, i.e. the queue grows indefinitely. Consequently, this case is of no practical interest, and only the case is considered below. For from (26) we get:

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

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

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

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 time spent in the QS and in the queue is determined by formulas (12) and (13).

Multichannel queuing system with limited queue and limited waiting time in the queue

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

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

The rest of the designations have the same meaning here as in the subsection.

Comparison of graphs in Fig. 3 and 9 shows that the last system is a special case of the birth and death system, if the following changes are made in it (the left-hand 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 queuing 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 bandwidth:

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 the CMO service... The online calculator is designed to calculate following indicators single-channel SMO:

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

Instruction. To solve similar problems in online mode select the CMO model. Please indicate the flow rate of requests λ and service flow rate μ... For a single-channel QS with a limited queue length, you can specify queue length m, and for a single-channel QS with an unlimited queue - the number of applications in the queue (to calculate the probability of finding these applications 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 λ \u003d 11 cars / h. The service time of the request is a random variable that obeys an exponential law with the parameter μ \u003d 14 cars / h. Determine the average number of vehicles 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 in each machine. On average, 328 cars are received for inspection per day. The flows of requests and services are the simplest. If a car arriving at the inspection point does not find a single channel free, it leaves the inspection point unattended. Determine the limiting probabilities of conditions and the characteristics of the maintenance of the preventive inspection point.
Decision. Here α \u003d 328/24 ≈ \u003d 13.67, t \u003d 0.4. These data must be entered into the calculator.

IN commercial activities more often there are CMOs with waiting (queue).

Consider a simple one-channel QS with a limited queue, in which the number of seats in the queue m is a fixed value. Consequently, a claim arriving at the moment when all the 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 "birth - death" process of a service, all intensities of service flows are equal

The states of the QS can be represented as follows:

S0 - the service channel is free,

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

S2 - the service channel is busy, there is one customer 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 customer is rejected.

To describe a random QS process, you can use the rules and formulas set forth earlier. Let's write expressions that determine the limiting probabilities of states:

In this case, the expression for p0 can be written more simply, using the fact that the denominator contains a geometric progression with respect to p, then after the appropriate transformations we get:

c \u003d (1- s)

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

If we assume m \u003d 0, then we move from considering a single-channel QS with waiting to the already considered single-channel QS with denial of service.

Indeed, the expression for the limiting probability p0 in the case m \u003d 0 has the form:

po \u003d m / (l + m)

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

Let us determine the main characteristics of a single-channel queuing system 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.

A request is rejected if it arrives at the time when the QS is already in the state Sm + 1 and, therefore, all the places in the queue yes are occupied and one channel serves

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

States Sm + 1:

Potk \u003d pm + 1 \u003d сm + 1 * p0

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

Q \u003d 1- potk \u003d 1- сm + 1 * p0

the absolute bandwidth is:

The average number of requests L standing in the queue for service is determined by the mathematical expectation of a random variable k - the number of requests 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-in the queue all seats are occupied

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

Table 1. The law of distribution of a discrete random variable

The mathematical expectation of this random variable is:

Loch \u003d 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:

Lp \u003d p2 * 1- pm * (m-m * p + 1)* p0

In the special case for p \u003d 1, when all the probabilities pk are equal, one can use the expression for the sum of the terms of the numerical series

1 + 2 + 3 + m \u003d m (m + 1)

Then we get the formula

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

Applying similar reasoning and transformations, we can show that the average waiting time for servicing a claim on the queue is determined by the Little formulas

Pt \u003d Lp / A (at p? 1) and T1p \u003d L "pt / A (at p \u003d 1).

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

An application received by the QS at the time when all channels are busy is rejected, and, therefore, the time for its "waiting" in the QS is zero. This leads in the general case (at p ≥ 1) to a decrease in Tochrostom l, since the share of such requests increases with increasing l.

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

When k is large enough, the probability pk tends to zero. Therefore, the relative throughput will be Q \u003d 1, and the absolute throughput will be equal to A - l Q - l, therefore, all incoming requests are served, and the average queue length will be equal to:

Lp \u003d p21-p

and the average waiting time according to Little's formula

Point \u003d Loch / A

In the limit p<< 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t > ?). The limiting probabilities of states therefore cannot be determined: for Q \u003d 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 applications and the absolute throughput, respectively, are on average s and m, however, an unlimited increase in the queue, and hence the waiting time in it, leads to the fact that after a while, applications begin to accumulate in the queue for an unlimited time.

As one of the characteristics of the QS, the average time Tcmo of the request staying in the QS is used, which includes the average time spent in the queue and the average service time. This value is calculated according to Little's formulas: if the queue length is limited, the average number of applications in the queue is:

Lсmo \u003d m + 1;2

Tsmo \u003d Lсmo;for p? 1

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

Tsmo \u003d m + 1at 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 customers 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 t.

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

S 0 - idle state;

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

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

S n + t -queue tapplications.

Since the flows of requests and services are ordinary, the state graph is depicted as a death and reproduction scheme. The only difference from a similar scheme for an unlimited queue is 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's compose a system of algebraic equations for finding the final state probabilities:

Where do we get erlang formulasfor a multi-channel system with limited queue:

Recent tthe terms in parentheses represent the sum tthe first members of a 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 limiting states will be as follows:

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

Number of channelswhich necessaryto have the system to cope with the flow of requests, we define from the condition

In this case, the relation ρ< 1.

Denial of service probabilitywe define claims as the probability that when a claim enters the system, all of its channels will be occupied, and all m places in the queue are occupied:

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

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

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

Average service timechannel of one request :

Average number of applications in the queue:

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

Average number of requests in the system(under service and in queue) equals:

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

Example:

The gas station site can accommodate no more than 3 cars at a time, and if it is busy, then the next car arriving at the station does not queue. Service flow rate λ \u003d 0.5 cars per minute. Service flow rate μ \u003d 0.4 cars per minute. Determine all the characteristics of the CMO.

Fragment of solving the problem in Mathcad.

Continuation of the problem in Mathcad.

Multichannel CMO with unlimited queue

Let's consider the problem. There isn-channel QS with unlimited queue. The flow of applications arriving in 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 the indicators of its efficiency.

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

The system state graph is shown in Figure 7. Note 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, and as the number of requests in the QS increases from 0 to n increases from the value m to n ??, since the number of service channels increases accordingly. When the number of requests in the QS is greater than n, the intensity of the service flow remains equal to nm.

Figure 7 - State graph of a 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 techniques, you can find:

average number of busy channels

average number of requests 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 by Little's formulas (48) and (49).

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

QS with limited queue

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