Multichannel smo with waiting and limited queue. Single channel smo with waiting. Single channel system with unlimited queue

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

Let there be a single-channel QS with a queue on which no restrictions are imposed (neither on the length of the queue, nor on the waiting time). This QS receives a flow of applications with intensity X; the service flow has an intensity reciprocal to the average service time of the request. It is required to find the final probabilities of the QS states, as well as the characteristics of its efficiency:

The average number of applications in the system,

Average residence time of an application in the system,

The average number of applications in the queue,

The average time an application spends in the queue,

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

As for the absolute throughput A and relative Q, there is no need to calculate them: due to the fact that the queue is unlimited, each application will be served sooner or later, therefore, for the same reason

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

The channel is free

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

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

The channel is busy, applications are in the queue,

Theoretically, the number of states is not limited by anything (infinitely). The state graph has the form shown in Fig. 20.2. This is a scheme of death and reproduction, but with an infinite number of states. For all arrows, the flow of requests with intensity A transfers the system from left to right, and from right to left - the flow of services with intensity

First of all, let us ask ourselves, are there final probabilities in this case? After all, the number of system states is infinite, and, in principle, the queue can increase indefinitely! Yes, it is true: the final probabilities for such a QS do not always exist, but only when the system is not overloaded. It can be proved that if strictly less than one, then the final probabilities exist, and for , the queue increases without limit. This fact seems especially “incomprehensible” when it would seem that there are no impossible requirements for the system: during the service of one application, on average, one application comes in, and everything should be in order, but in reality it is not.

With QS, it copes with the flow of applications only if this flow is regular, and the service time is also not random, equal to the interval between applications. In this "ideal" case, there will be no queue in the QS at all, the channel will be continuously busy and will regularly issue serviced requests. But as soon as the flow of requests or the flow of services become at least a little random, the queue will already grow indefinitely. In practice, this does not happen only because "an infinite number of applications in the queue" is an abstraction. These are the gross errors that the replacement of random variables by their mathematical expectations can lead to!

But let's return to our single-channel QS with no limited queue. Strictly speaking, the formulas for the final probabilities in the scheme of death and reproduction were derived by us only for the case of a finite number of states, but let's take liberties - we will use them for an infinite number of states. Let us calculate the final probabilities of states according to formulas (19.8), (19.7). In our case, the number of terms in formula (19.8) will be infinite. We get an expression for

The series in formula (20.11) is a geometric progression. We know that when the series converges - this is an infinitely decreasing geometric progression with a denominator. For , the series diverges (which is an indirect, though not rigorous, proof that the final state probabilities exist only for ). Now suppose that this condition is satisfied, and Summing up the progression in (20.11), we have

(20.12)

The probabilities are found by the formulas:

whence, taking into account (20.12), we finally find:

As you can see, the probabilities form a geometric progression with the denominator . Oddly enough, the maximum of them is the probability that the channel will be free at all. No matter how busy a queuing system is, if it can handle the flow of requests at all, the most likely number of requests in the system will be 0.

Let's find the average number of applications in QS . Here you have to tinker a little. Random variable Z - the number of applications in the system - has possible values ​​with probabilities

Its mathematical expectation is

(20.14)

(the sum is taken not from 0 to but from 1 to, since the zero term is equal to zero).

We substitute into formula (20.14) the expression for

Now let's take it out of the sum sign:

Here we again apply the “little trick”: there is nothing more than the derivative of pores from the expression means,

By interchanging the operations of differentiation and summation, we get:

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

(20.16)

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

Let's find the average number of requests in the queue. We will argue as follows: the number of requests in the queue is equal to the number of requests in the system minus the number of requests under service. Hence (by the rule of addition of mathematical expectations), the average number of applications in the queue is equal to the average number of applications in the system minus the average number of applications under service. The number of requests under service can be either zero (if the channel is free) or one (if it is busy). The mathematical expectation of such a random variable is equal to the probability that the channel is busy (we denoted it as ). Obviously, it is equal to one minus the probability that the channel is free;

Therefore, the average number of requests under service is equal to

operation or efficiency of the queuing system are as follows.

For CMO with failures:

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

For CMO mixed type both groups of indicators are used: both relative and absolute bandwidth, and expectation characteristics.

Depending on the purpose of the queuing operation, any of the above indicators (or a set of indicators) can be chosen as a performance criterion.

analytical model QS is a set of equations or formulas that allow you to determine the probabilities of system states during its operation and calculate performance indicators based on known characteristics of the incoming flow and service channels.

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

Analytical modeling of the QS is greatly facilitated if the processes occurring in the QS are Markovian (the flows of requests are simple, the service times are 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 drivers' waybills trucks. If at least one inspector is free, the passing truck is stopped. If all the inspectors are busy, the truck passes without stopping. The flow of trucks is the simplest, the check time is random with an exponential distribution.

Such a situation can be simulated by a three-channel QS with failures (without a queue). The system is open, with homogeneous applications, single-phase, with absolutely reliable channels.

Description of states:

All inspectors are free;

One inspector is busy;

Two inspectors are busy;

Three inspectors are busy.

The graph of system states is shown in fig. 2.11.


Rice. 2.11.

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

The simulation is carried out in order to determine the part of the cars that will not be tested.

Solution

The desired part of the probability is the probability of employment of all three inspectors. Since the state graph represents a typical scheme of "death and reproduction", we will find using dependencies (2.2).

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

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

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

Solution

A group of officers works as a CMO with failures, consisting of three channels.

The flow of reports with intensity can be considered the simplest, since it is the total of several reconnaissance groups. Maintenance intensity . The distribution law is unknown, but this is not essential, since it is shown that for systems with failures it can be arbitrary.

The description of the states and the state graph of the QS will be similar to those given in Example 2.5.

Since the state graph is a "death and reproduction" scheme, there are ready-made expressions for the limiting state probabilities for it:

The relation is called the reduced intensity of the flow of applications. Its physical meaning is as follows: the value is the average number of requests coming to the QS for the average service time of one request.

In the example .

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

Because failure probability in the processing of reports is more than 34% (), then it is necessary to increase the personnel of the group. Let us double the composition of the group, that is, the QS will now have six channels, and calculate:

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

2.5.2. Multichannel QS with waiting

Example 2.7. There are 15 crossing facilities of the same type in the river forcing section. The flow of equipment arriving at the crossing averages 1 unit/min, the average time of crossing one unit of equipment is 10 minutes (taking into account the return of the crossing facility).

Evaluate the main characteristics of the crossing, including the likelihood of an immediate crossing immediately upon the arrival of a piece of equipment.

Solution

Absolute throughput , i.e. everything that comes to the crossing is almost immediately crossed.

Average number of operating crossing facilities:

Crossing utilization and downtime ratios:

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

The ferry utilization rates after 50 runs are practically the same: .

The maximum length of the queue is 15 units, the average time spent in the queue is about 10 minutes.

Consider a single-channel queuing system with waiting.

We will assume that the incoming flow of service requests is the simplest flow with intensity λ.

The intensity of the service flow is equal to μ. Service duration is a random variable subject to an exponential distribution law. Service flow is the simplest Poisson flow of events.

A request that arrives at a time when the channel is busy is queued and awaits service. We will assume that the size of the queue is limited and cannot accommodate more than m applications, i.e. an application that made at the time of its arrival in the CMO m +1 requests (m waiting in line and one in service) leaves the QS.

The system of equations describing the process in this system has a solution:

(0‑1)

The denominator of the first expression is a geometric progression with the first term 1 and the denominator ρ, whence we obtain

For ρ = 1 you can resort to direct calculation

(0‑8)

The average number of tickets in the system.

Since the average number of applications in the system

(0‑9)

where is the average number of applications under service, then knowing it remains to find. Because there is only one channel, then the number of serviced requests can be either 0 or 1 with probabilities P 0 and P 1=1- P 0 respectively, from where

(0‑10)

and the average number of applications in the system is equal to

(0‑11)

Average waiting time for an application in the queue.

(0‑12)

i.e., the average waiting time for a ticket in the queue is equal to the average number of tickets in the queue, divided by the intensity of the flow of requests.

Average residence time of a request in the system.

The residence time of an application in the system is the sum of the waiting time for an application in the queue and the service time. If the system load is 100%, then =1/μ, otherwise = q/μ. From here

(0‑13)

The content of the work.

Preparation of experiment tools .

It is carried out similarly in accordance with the general rules.

Calculation on an analytical model.

1. IN Microsoft application Excel, prepare the following table.

2. In the columns for the QS parameters of the table, write down the initial data, which are determined by the rule:

m=1,2,3

(maximum queue length).

For every value m it is necessary to find theoretical and experimental values ​​of QS indicators for such pairs of values:

= <порядковый номер в списке группы>

3. In the columns with indicators of the analytical model, enter the appropriate formulas.

Experiment on a simulation model.

1. Set the launch mode to exponentially distributed service time by setting the value of the corresponding parameter to 1.

2. For every combination m , and run the model.

3. Enter the results of the launches in the table.

4. Enter formulas in the corresponding columns of the table to calculate the average value of the indicator P otk , q and A.


Analysis of results .

1. Analyze the results obtained by theoretical and experimental methods, comparing the results with each other.

2. For m=3 plot dependency graphs on one diagram P open from the theoretically and experimentally obtained data.

Optimization of QS parameters .

Solve the problem of optimizing the size of the number of places in the queue m for a device with an average service time = from the point of view of maximizing profit. As the conditions of the problem, take:

- income from servicing one application equal to 80 USD/hour,

- the cost of maintaining one device equal to 1 c.u./hour.

1. For calculations, it is advisable to create a table:

The first column is filled with the values ​​of the numbers of the natural series (1,2,3…).

All cells of the second and third columns are filled with and values.

In the cells of columns from the fourth to the ninth, the formulas for the columns of the section 0 table are transferred.

Enter the values ​​in the columns with the initial data of the Income, Expense, Profit sections (see above).

In the columns with the calculated values ​​of the sections Income, Expense, Profit, write down the calculation formulas:

- number of applications per unit of time

N r =A

- total income per unit of time

I S = I r *N r

- total consumption per unit of time

E S = E s + E q *(n-1)

- profit per unit of time

P = I S - E S

where

I r - income from one application,

E s - the cost of operating one device,

E q - the cost of operating one place in the queue.

Graphs for P otk ,

- table with data to find the best m and value m opt,

- graph of profit per unit time from m .


test questions :

1) Give short description single-channel QS model with a limited queue.

2) What indicators characterize the functioning of a single-channel QS with failures?

3) How is the probability p calculated 0 ?

4) How are the probabilities p i?

5) How to find the probability of refusal to service an application?

6) How to find relative bandwidth?

7) What is the absolute throughput?

8) How is the average number of requests in the system calculated?

9) Give examples of a QS with a limited queue.

Tasks .

1) The port has one cargo berth for unloading ships. The flow rate is 0.5 visits per day. The average time of unloading one vessel is 2 days. If there are 3 vessels in the queue for unloading, then the incoming vessel is sent for unloading to another berth. Find the performance indicators of the berth.

2) The information desk of the railway station receives telephone inquiries with an intensity of 80 applications per hour. The help desk operator answers an incoming call in an average of 0.7 minutes. If the operator is busy, the client is given a message "Waiting for a response", the request is placed in a queue, the length of which does not exceed 4 requests. Give an assessment of the work of the help desk and the option of its reorganization

Topic. Theory of queuing systems.

Each QS consists of a certain number of service units, which are calledservice channels (these are machine tools, transport carts, robots, communication lines, cashiers, sellers, etc.). Every QS is designed to serve someapplication flow (requirements) arriving at some random time.

QS classification according to the method of processing the input flow of applications.

Queuing systems

With rejections

(no queue)

With a queue

Unlimited queue

limited queue

with priority

In order of arrival

Relative Priority

Absolute priority

By service time

By queue length

Classification by way of functioning:

    open, i.e. the flow of requests does not depend on the internal state of the QS;

    closed, i.e. the input flow depends on the state of the QS (one maintenance worker services all channels as they fail).

Multichannel QS with waiting

A system with a limited queue length. Consider channel QS with waiting, which receives a flow of requests with intensity ; service intensity (for one channel) ; number of places in line

The system states are numbered according to the number of applications, system-related:

no queue:

- all channels are free;

- one channel is occupied, the rest are free;

- busy -channels, the rest are not;

- everyone is busy - no free channels;

there is a queue:

- all n-channels are occupied; one application is in the queue;

- all n-channels are occupied, r-requests in the queue;

- all n-channels are occupied, r-requests in the queue.

GSP is shown in fig. 9. Each arrow has corresponding intensities of event flows. According to the arrows from left to right, the system is always transferred by the same flow of applications with intensity , according to the arrows from right to left, the system is transferred by the service flow, the intensity of which is equal to multiplied by the number of busy channels.

Rice. 9. Multichannel QS with waiting

Failure probability.

(29)

The relative throughput complements the failure probability to one:

Absolute throughput of QS:

(30)

Average number of busy channels.

The average number of requests in the queue can be calculated directly as the mathematical expectation of a discrete random variable:

(31)

where .

Here again (expression in brackets) the derivative of the sum of a geometric progression occurs (see above (23), (24) - (26)), using the ratio for it, we get:

Average number of applications in the system:

Average waiting time for an application in the queue.

(32)

Just as in the case of a single-channel waiting QS, we note that this expression differs from the expression for the average queue length only by the factor , i.e.

.

Average residence time of an application in the system, the same as for a single-channel QS .

Systems with unlimited queue length. We have reviewed channel QS with waiting, when no more than m-requests can be in the queue at the same time.

Just as before, when analyzing systems without restrictions, it is necessary to consider the relations obtained for .

Failure Probability

The average number of applications in the queue will be obtained at from (31):

,

and the average waiting time is from (32): .

Average number of applications .

Example 2 A gas station with two dispensers (n = 2) serves a flow of cars with intensity =0.8 (cars per minute). Average service time per machine:

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

CMO with limited waiting time. Previously, we considered systems with waiting limited only by the queue length (the number of m-customers simultaneously in the queue). In such a QS, a claim that has grown into a queue does not leave it until it waits for service. In practice, there are QS of a different type, in which the application, after waiting for some time, can leave the queue (the so-called "impatient" applications).

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

Poisson "flow of escapes" with intensity:

If this flow is Poisson, then the process occurring in the QS will be Markov. Let us find the probabilities of states for it. The numbering of system states is associated with the number of requests in the system - both served and queued:

no queue:

- all channels are free;

- one channel is busy;

- two channels are occupied;

- all n-channels are occupied;

there is a queue:

- all n-channels are occupied, one request is in the queue;

- all n-channels are occupied, r-requests are in the queue, etc.

The graph of states and transitions of the system is shown in fig. 10.

Rice. 10. CMO with limited waiting time

Let's label this graph as before; all arrows leading from left to right will have the intensity of the flow of applications . For states without a queue, the arrows leading from them from right to left will, as before, have the total intensity of the service flow of all busy channels. As for the states with a queue, the arrows leading from them from right to left will have the total intensity of the service flow of all n-channels plus the corresponding intensity of the dequeue flow. If there are r-entries in the queue, then the total intensity of the flow of departures will be equal to .

Average number of applications in the queue: (35)

For each of these requests, there is an “exit flow” with an intensity . So from the average - applications in the queue will leave on average without waiting for service, -applications per unit of time and total per unit of time will be served on average - applications. The relative throughput of the QS will be:

Average Busy Channels is still obtained by dividing the absolute throughput of A by Closed QS

So far, we have considered systems in which the incoming flow is not connected in any way with the outgoing one. Such systems are called open. In some cases, the serviced requests, after a delay, again enter the input. Such QS are called closed. A polyclinic serving a given area, a team of workers assigned to a group of machines, are examples of closed systems.

In a closed QS, the same finite number of potential requirements circulate. Until a potential requirement has been realized as a service requirement, it is considered to be in a delay block. At the time of implementation, it enters the system itself. For example, workers service a group of machines. Each machine is a potential requirement, turning into a real one the moment it breaks down. While the machine is running, it is in the delay unit, and from the moment of breakdown until the end of the repair, it is in the system itself. Each worker is a service channel. = =P 1 + 2 P 2 +…+(n- 1 )P n- 1 +n( 1 -P The input of a three-channel QS with failures receives a flow of applications with an intensity \u003d 4 requests per minute, time for servicing an application by one channelt service=1/μ =0.5 min. Is it advantageous from the point of view of QS throughput to force all three channels to serve applications at once, and the average service time is reduced by a factor of three? How will this affect the average time an application spends in the CMO?

Example 2 . /µ=2, ρ/n =2/3<1.

Task 3:

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

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

Find the same characteristics for a system where:

a) two machines are assigned to each worker;

b) two workers always serve the machine together, and with double intensity;

c) the only faulty machine is served by both workers at once (with double intensity), and when at least one more faulty machine appears, they begin to work separately, each serving one machine (first describe the system in terms of the processes of death and birth).

In commercial activities, QS with waiting (queue) are more common.

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 the 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 Tochrostom 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

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

tsmo= m+1 at p ?1 2m

 

It might be useful to read: