You get a bonus - 1 coin for daily activity. Now you have 1 coin

19.8. Queuing system with failures. Erlang equations

Lecture



Queuing systems are divided into two main types: a) systems with failures, b) systems with waiting.

In systems with refusals, an application that arrived at the moment when all service channels are busy immediately receives a refusal, leaves the system and does not participate in the further maintenance process.

In systems with waiting, an application that has made all channels busy does not leave the system, but becomes in a queue and waits until a channel becomes free. Present   19.8.  Queuing system with failures.  Erlang equations we will consider the system with failures as the simplest.

Let there be   19.8.  Queuing system with failures.  Erlang equations -channel queuing system with failures. Consider it as a physical system.   19.8.  Queuing system with failures.  Erlang equations with a finite set of states:

  19.8.  Queuing system with failures.  Erlang equations - all channels are free,

  19.8.  Queuing system with failures.  Erlang equations - exactly one channel is busy,

……………

  19.8.  Queuing system with failures.  Erlang equations - busy exactly   19.8.  Queuing system with failures.  Erlang equations channels,

……………

  19.8.  Queuing system with failures.  Erlang equations - all busy   19.8.  Queuing system with failures.  Erlang equations channels.

The scheme of possible transitions is given in fig. 19.8.1.

  19.8.  Queuing system with failures.  Erlang equations

Fig. 19.8.1.

We set the task: to determine the probabilities of the system states   19.8.  Queuing system with failures.  Erlang equations   19.8.  Queuing system with failures.  Erlang equations for any point in time   19.8.  Queuing system with failures.  Erlang equations . The task will be solved under the following assumptions:

1) the flow of applications - the simplest, with a density

2) service time   19.8.  Queuing system with failures.  Erlang equations - indicative, with parameter   19.8.  Queuing system with failures.  Erlang equations

  19.8.  Queuing system with failures.  Erlang equations .   19.8.  Queuing system with failures.  Erlang equations . (19.8.1)

Note that the parameter   19.8.  Queuing system with failures.  Erlang equations in the formula (19.8.1) is completely analogous to the parameter   19.8.  Queuing system with failures.  Erlang equations exponential law of distribution of the gap   19.8.  Queuing system with failures.  Erlang equations between neighboring events of the simplest flow:

  19.8.  Queuing system with failures.  Erlang equations   19.8.  Queuing system with failures.  Erlang equations . (19.8.2)

Parameter   19.8.  Queuing system with failures.  Erlang equations makes sense of "flow density applications." Similarly, the value   19.8.  Queuing system with failures.  Erlang equations can be interpreted as the “release flux density” of a busy channel. Indeed, let us imagine a channel that is continuously occupied (uninterruptedly supplied with applications); then, obviously, in this channel there will be a simple stream of releases with a density   19.8.  Queuing system with failures.  Erlang equations .

Since both flows — applications and exemptions — are the simplest, the process going on in the system will be Markov.

Consider the possible system states and their probabilities.

  19.8.  Queuing system with failures.  Erlang equations . (19.8.3)

Obviously for any point in time

  19.8.  Queuing system with failures.  Erlang equations . (19.8.4)

Create differential equations for all probabilities (19.8.3), starting with   19.8.  Queuing system with failures.  Erlang equations . Fix a point in time   19.8.  Queuing system with failures.  Erlang equations and find the probability   19.8.  Queuing system with failures.  Erlang equations that at the moment   19.8.  Queuing system with failures.  Erlang equations the system will be able to   19.8.  Queuing system with failures.  Erlang equations (all channels are free). This can happen in two ways (Fig. 19.8.2):

  19.8.  Queuing system with failures.  Erlang equations

Fig. 19.8.2.

  19.8.  Queuing system with failures.  Erlang equations - in the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations and in time   19.8.  Queuing system with failures.  Erlang equations did not pass from it to   19.8.  Queuing system with failures.  Erlang equations (not a single application has arrived)

  19.8.  Queuing system with failures.  Erlang equations - in the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations and in time   19.8.  Queuing system with failures.  Erlang equations the channel was released, and the system went into a state   19.8.  Queuing system with failures.  Erlang equations .

The ability to "jump" the system through the state (for example, from   19.8.  Queuing system with failures.  Erlang equations at   19.8.  Queuing system with failures.  Erlang equations through   19.8.  Queuing system with failures.  Erlang equations ) for a small period of time can be neglected, as the value of a higher order of smallness compared with   19.8.  Queuing system with failures.  Erlang equations and   19.8.  Queuing system with failures.  Erlang equations .

By the addition theorem, we have

  19.8.  Queuing system with failures.  Erlang equations . (19.8.5)

Find the probability of the event   19.8.  Queuing system with failures.  Erlang equations by the multiplication theorem. Probability that at the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations equal to   19.8.  Queuing system with failures.  Erlang equations . Probability that for time   19.8.  Queuing system with failures.  Erlang equations will not come any application equal   19.8.  Queuing system with failures.  Erlang equations . Up to values ​​of the highest order of smallness

  19.8.  Queuing system with failures.  Erlang equations . (19.8.6)

Consequently,

  19.8.  Queuing system with failures.  Erlang equations .

We find   19.8.  Queuing system with failures.  Erlang equations . Probability that at the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations equal to   19.8.  Queuing system with failures.  Erlang equations . Probability that for time   19.8.  Queuing system with failures.  Erlang equations the channel is free, equal to   19.8.  Queuing system with failures.  Erlang equations up to low order values

  19.8.  Queuing system with failures.  Erlang equations .

Consequently,

  19.8.  Queuing system with failures.  Erlang equations .

From here

  19.8.  Queuing system with failures.  Erlang equations .

Shifting   19.8.  Queuing system with failures.  Erlang equations to the left by dividing by   19.8.  Queuing system with failures.  Erlang equations and going to the limit at   19.8.  Queuing system with failures.  Erlang equations , we obtain the differential equation for   19.8.  Queuing system with failures.  Erlang equations :

  19.8.  Queuing system with failures.  Erlang equations . (19.8.7)

Similar differential equations can be compiled for other probabilities of states.

Take any   19.8.  Queuing system with failures.  Erlang equations and find the probability   19.8.  Queuing system with failures.  Erlang equations that at the moment   19.8.  Queuing system with failures.  Erlang equations the system will be able to   19.8.  Queuing system with failures.  Erlang equations (fig. 19.8.3).

  19.8.  Queuing system with failures.  Erlang equations

Fig. 19.8.3.

This probability is calculated as the probability of the sum of not two, but three events (according to the number of arrows directed to   19.8.  Queuing system with failures.  Erlang equations ):

  19.8.  Queuing system with failures.  Erlang equations - in the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations (busy)   19.8.  Queuing system with failures.  Erlang equations channels), and in time   19.8.  Queuing system with failures.  Erlang equations did not pass from him to any   19.8.  Queuing system with failures.  Erlang equations nor in   19.8.  Queuing system with failures.  Erlang equations (not a single application has been received, not a single channel has been released);

  19.8.  Queuing system with failures.  Erlang equations - in the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations (busy)   19.8.  Queuing system with failures.  Erlang equations channels), and in time   19.8.  Queuing system with failures.  Erlang equations moved to   19.8.  Queuing system with failures.  Erlang equations (one application has arrived);

  19.8.  Queuing system with failures.  Erlang equations - in the moment   19.8.  Queuing system with failures.  Erlang equations the system was able to   19.8.  Queuing system with failures.  Erlang equations (busy)   19.8.  Queuing system with failures.  Erlang equations channels), and in time   19.8.  Queuing system with failures.  Erlang equations one of the channels is free.

We find   19.8.  Queuing system with failures.  Erlang equations . We first calculate the probability that in time   19.8.  Queuing system with failures.  Erlang equations No application will come and none of the channels will be released:

  19.8.  Queuing system with failures.  Erlang equations .

Neglecting small values ​​of higher orders, we have

  19.8.  Queuing system with failures.  Erlang equations ,

from where

  19.8.  Queuing system with failures.  Erlang equations .

Similarly

  19.8.  Queuing system with failures.  Erlang equations ,

  19.8.  Queuing system with failures.  Erlang equations

and

  19.8.  Queuing system with failures.  Erlang equations .

From here we get the differential equation for   19.8.  Queuing system with failures.  Erlang equations   19.8.  Queuing system with failures.  Erlang equations :

  19.8.  Queuing system with failures.  Erlang equations .

Let's make the equation for the last probability   19.8.  Queuing system with failures.  Erlang equations (fig. 19.8.4).

  19.8.  Queuing system with failures.  Erlang equations

Fig. 19.8.4.

We have

  19.8.  Queuing system with failures.  Erlang equations ,

Where   19.8.  Queuing system with failures.  Erlang equations - the probability that in time   19.8.  Queuing system with failures.  Erlang equations no channel is free;   19.8.  Queuing system with failures.  Erlang equations - the probability that in time   19.8.  Queuing system with failures.  Erlang equations one application will come. We obtain the differential equation for   19.8.  Queuing system with failures.  Erlang equations :

  19.8.  Queuing system with failures.  Erlang equations .

Thus, the obtained system of differential equations for probabilities   19.8.  Queuing system with failures.  Erlang equations :

  19.8.  Queuing system with failures.  Erlang equations (19.8.8)

Equations (19.8.8) are called Erlang equations. Integration of the system of equations (19.8.8) with initial conditions

  19.8.  Queuing system with failures.  Erlang equations ;   19.8.  Queuing system with failures.  Erlang equations

(at the initial moment all channels are free) gives dependence   19.8.  Queuing system with failures.  Erlang equations for anyone   19.8.  Queuing system with failures.  Erlang equations . Probabilities   19.8.  Queuing system with failures.  Erlang equations characterize the average load of the system and its change over time. In particular,   19.8.  Queuing system with failures.  Erlang equations there is a possibility that the application that came at the moment   19.8.  Queuing system with failures.  Erlang equations , will find all channels busy (will be rejected):

  19.8.  Queuing system with failures.  Erlang equations .

Magnitude   19.8.  Queuing system with failures.  Erlang equations called relative system bandwidth. For the moment   19.8.  Queuing system with failures.  Erlang equations this is the ratio of the average number of applications served per unit of time to the average number of applications submitted.

The system of linear differential equations (19.8.8) can be relatively easily integrated with any particular number of channels.   19.8.  Queuing system with failures.  Erlang equations .

Note that in the derivation of equations (19.8.8) we never used the assumption that   19.8.  Queuing system with failures.  Erlang equations and   19.8.  Queuing system with failures.  Erlang equations (density of application flow and release flow) are constant. Therefore, equations (19.8.8) remain valid for time-dependent   19.8.  Queuing system with failures.  Erlang equations ,   19.8.  Queuing system with failures.  Erlang equations as long as the streams of events that translate the system from state to state remain Poissonian (without this, the process will not be Markovian).


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Queuing theory

Terms: Queuing theory