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

19.10. Queuing system with waiting

Lecture



A queuing system is called a system with a wait, if an application that has made all channels busy becomes in a queue and waits until a channel becomes free.

If the waiting time for an application in the queue is not limited by anything, then the system is called a “clean system with waiting”. If it is limited by some conditions, then the system is called a “mixed type system”. This is an intermediate case between a clean system with failures and a clean system with a wait.

For practice, the most interesting are systems of mixed type.

The restrictions imposed on waiting can be of various types. It often happens that the restriction is imposed on the waiting time of the application in the queue; it is considered to be restricted from above for a period of time.   19.10.  Queuing system with waiting which can be either strictly defined or random. At the same time, only the waiting time in the queue is limited, and the started service is completed, regardless of how long the waiting lasted (for example, the client at the barbershop sitting in the chair usually does not go to the end of the service). In other tasks it is more natural to impose a restriction not on the waiting time in the queue, but on the total time the application is in the system (for example, an air target can stay in the firing zone only for a limited time and leave it regardless of whether the shelling is over or not). Finally, it is possible to consider such a mixed system (it is closest to the type of commercial enterprises selling non-essential items), when an application is placed in a queue only if the queue length is not too long. Here the limit is imposed on the number of applications in the queue.

In systems with anticipation, the so-called “queue discipline” plays a significant role. Pending applications can be called up for service both in the order of the queue (earlier arrived earlier and serviced), and in a random, unorganized order. There are queuing systems "with benefits", where some applications are served preferentially over others ("generals and colonels out of turn").

Each type of system with expectation has its own characteristics and its own mathematical theory. Many of them are described, for example, in V. V. Gnedenko’s book Lectures on the Theory of Queuing Theory.

Here we dwell only on the simplest case of a mixed system, which is a natural generalization of the Erlang problem for a system with refusals. For this case, we derive differential equations similar to the Erlang equations, and formulas for the probabilities of states in the steady state, similar to the Erlang formulas.

Consider a mixed queuing system   19.10.  Queuing system with waiting with   19.10.  Queuing system with waiting channels under the following conditions. At the input of the system comes the simplest flow of applications with a density   19.10.  Queuing system with waiting . Service time for one application   19.10.  Queuing system with waiting - indicative, with parameter   19.10.  Queuing system with waiting . An application that has made all channels busy is queued and is waiting for service; waiting time is limited to some time   19.10.  Queuing system with waiting ; if the application is not accepted for servicing before the expiration of this period, it leaves the queue and remains unattended. Waiting time   19.10.  Queuing system with waiting we will be considered random and distributed according to the exponential law

  19.10.  Queuing system with waiting   19.10.  Queuing system with waiting ,

where is the parameter   19.10.  Queuing system with waiting - the reciprocal of the average waiting time:

  19.10.  Queuing system with waiting ;   19.10.  Queuing system with waiting .

Parameter   19.10.  Queuing system with waiting completely analogous to the parameters   19.10.  Queuing system with waiting and   19.10.  Queuing system with waiting application flow and release flow. It can be interpreted as the density of the "flow of departures" of the application, standing in line. Indeed, let us imagine an application that only does what becomes in the queue and waits in it until the waiting period ends.   19.10.  Queuing system with waiting , then leaves and immediately queued up again. Then the “flow of withdrawals” of such an application from the queue will have a density   19.10.  Queuing system with waiting .

Obviously when   19.10.  Queuing system with waiting the mixed type system becomes a clean system with failures; at   19.10.  Queuing system with waiting it turns into a clean system with anticipation.

Note that with the exponential law of waiting time distribution, the system capacity does not depend on whether requests are serviced in a queue or in a random order: for each application, the law of distribution of the remaining waiting time does not depend on how long the request was already in the queue.

Due to the assumption of the Poisson character of all event flows that lead to changes in the states of the system, the process proceeding in it will be Markovian. We write the equations for the probabilities of the states of the system. To do this, first of all, we list these states. We will number them not by the number of channels occupied, but by the number of requests related to the system. The application will be called "system-related" if it is either in a state of service or waiting in line. Possible system states will be:

  19.10.  Queuing system with waiting - no channel is busy (no queue),

  19.10.  Queuing system with waiting - exactly one channel is busy (no queue),

………

  19.10.  Queuing system with waiting - busy exactly   19.10.  Queuing system with waiting channels (no queue)

………

  19.10.  Queuing system with waiting - all busy   19.10.  Queuing system with waiting channels (no queue)

  19.10.  Queuing system with waiting - all busy   19.10.  Queuing system with waiting channels, one application is in the queue,

………

  19.10.  Queuing system with waiting - all busy   19.10.  Queuing system with waiting channels,   19.10.  Queuing system with waiting applications are waiting in line

………

Number of applications   19.10.  Queuing system with waiting standing in line in our conditions can be arbitrarily large. Thus, the system   19.10.  Queuing system with waiting has an infinite (albeit countable) set of states. Accordingly, the number of differential equations describing it will also be infinite.

Obviously, the first   19.10.  Queuing system with waiting differential equations will not differ from the corresponding Erlang equations:

  19.10.  Queuing system with waiting

The difference between the new equations and the Erlang equations will begin when   19.10.  Queuing system with waiting . Indeed, in the state   19.10.  Queuing system with waiting system with failures can only go from the state   19.10.  Queuing system with waiting ; as for the system with the expectation, it can go into a state   19.10.  Queuing system with waiting not only from   19.10.  Queuing system with waiting but also from   19.10.  Queuing system with waiting (all channels are busy, one application is in the queue).

Let's make the differential equation for   19.10.  Queuing system with waiting . Fix the moment   19.10.  Queuing system with waiting and find   19.10.  Queuing system with waiting - the probability that the system is at the moment   19.10.  Queuing system with waiting will be able to   19.10.  Queuing system with waiting . This can be done in three ways:

1) at the moment   19.10.  Queuing system with waiting the system was already able   19.10.  Queuing system with waiting and in time   19.10.  Queuing system with waiting did not come out of it (not a single application came and not a single channel was released);

2) at the moment   19.10.  Queuing system with waiting the system was able to   19.10.  Queuing system with waiting and in time   19.10.  Queuing system with waiting moved to state   19.10.  Queuing system with waiting (one application has arrived);

3) at the moment   19.10.  Queuing system with waiting the system was able to   19.10.  Queuing system with waiting (all channels are busy, one application is in the queue), and during   19.10.  Queuing system with waiting moved to   19.10.  Queuing system with waiting (either one channel was released and the queued application occupied it, or the queued application went away due to the expiration of the term).

We have:

  19.10.  Queuing system with waiting ,

from where

  19.10.  Queuing system with waiting .

Calculate now   19.10.  Queuing system with waiting at any   19.10.  Queuing system with waiting - the probability that at the moment   19.10.  Queuing system with waiting everything   19.10.  Queuing system with waiting channels will be busy and smooth   19.10.  Queuing system with waiting applications will stand in line. This event can again be realized in three ways:

1) at the moment   19.10.  Queuing system with waiting the system was already able   19.10.  Queuing system with waiting and in time   19.10.  Queuing system with waiting this state has not changed (it means that not a single application has arrived, not a single drop has been released and not a single one   19.10.  Queuing system with waiting queued applications did not go away);

2) at the moment   19.10.  Queuing system with waiting the system was able to   19.10.  Queuing system with waiting and in time   19.10.  Queuing system with waiting moved to state   19.10.  Queuing system with waiting (i.e. one application has arrived);

3) at the moment   19.10.  Queuing system with waiting the system was able to   19.10.  Queuing system with waiting and in time   19.10.  Queuing system with waiting moved to state   19.10.  Queuing system with waiting (for this, either one of the channels must be freed, and then one of   19.10.  Queuing system with waiting queuing applications will occupy it, or one of the queuing applications must leave due to the expiration).

Consequently:

  19.10.  Queuing system with waiting ,

from where

  19.10.  Queuing system with waiting .

Thus, for the state probabilities, we have obtained a system of infinite number of differential equations:

  19.10.  Queuing system with waiting (19.10.1)

Equations (10/19/1) are a natural generalization of the Erlang equations to the case of a mixed-type system with a limited waiting time. Options   19.10.  Queuing system with waiting in these equations can be both constant and variable. When integrating system (19.10.1), it must be taken into account that although theoretically the number of possible states of the system is infinite, in practice the probabilities   19.10.  Queuing system with waiting with increasing   19.10.  Queuing system with waiting become negligible, and the corresponding equations can be discarded.

We derive formulas similar to the Erlang formulas for the probabilities of the system states at the steady state of service (with   19.10.  Queuing system with waiting ). From equations (10/19/1), assuming all   19.10.  Queuing system with waiting   19.10.  Queuing system with waiting constant, and all derivatives - equal to zero, we get a system of algebraic equations:

  19.10.  Queuing system with waiting (19.10.2)

They need to attach the condition:

  19.10.  Queuing system with waiting . (19.10.3)

Let us find the solution of the system (19.10.2).

For this, we apply the same technique that we used in the case of a system with failures: solve the first equation with respect to   19.10.  Queuing system with waiting we will substitute in the second, etc. For any   19.10.  Queuing system with waiting as in the case of a system with failures, we get:

  19.10.  Queuing system with waiting . (19.10.4)

We turn to the equations for   19.10.  Queuing system with waiting   19.10.  Queuing system with waiting . In the same way we get:

  19.10.  Queuing system with waiting ,

  19.10.  Queuing system with waiting ,

and generally for any   19.10.  Queuing system with waiting

  19.10.  Queuing system with waiting . (19.10.5)

In both formulas (19.10.4) and (19.10.5), the probability   19.10.  Queuing system with waiting . We define it from the condition (19.10.3). Substituting into it the expressions (19.10.4) and (19.10.5) for   19.10.  Queuing system with waiting and   19.10.  Queuing system with waiting , we get:

  19.10.  Queuing system with waiting ,

from where

  19.10.  Queuing system with waiting . (19.10.6)

Let's transform expressions (19.10.4), (19.10.5) and (19.10.6), entering in them instead of densities   19.10.  Queuing system with waiting and   19.10.  Queuing system with waiting "Reduced" density:

  19.10.  Queuing system with waiting (19.10.7)

Options   19.10.  Queuing system with waiting and   19.10.  Queuing system with waiting express, respectively, the average number of applications and the average number of requests left in a queue, falling on the average service time of a single application.

In the new notation of the formula (19.10.4), (19.10.5) and (19.10.6) will take the form:

  19.10.  Queuing system with waiting   19.10.  Queuing system with waiting ; (19.10.8)

  19.10.  Queuing system with waiting   19.10.  Queuing system with waiting ; (19.10.9)

  19.10.  Queuing system with waiting . (10/19/10)

Substituting (19.10.10) into (19.10.8) and (19.10.9), we obtain the final expressions for the probabilities of the system states:

  19.10.  Queuing system with waiting   19.10.  Queuing system with waiting ; (10/19/11)

  19.10.  Queuing system with waiting   19.10.  Queuing system with waiting . (10/19/12)

Knowing the probabilities of all system states, one can easily determine other characteristics of interest to us, in particular, the probability   19.10.  Queuing system with waiting that the application leaves the system unattended. We define it from the following considerations: at steady state, the probability   19.10.  Queuing system with waiting the fact that an application leaves the unserved system is nothing but the ratio of the average number of applications leaving the queue per unit of time to the average number of applications received per unit of time. Find the average number of applications leaving the queue per unit of time. To do this, we first calculate the expectation   19.10.  Queuing system with waiting the number of applications in the queue:

  19.10.  Queuing system with waiting . (10/19/13)

To obtain   19.10.  Queuing system with waiting , need to   19.10.  Queuing system with waiting multiply by the average "density of departures" of one application   19.10.  Queuing system with waiting and divided by the average density of applications   19.10.  Queuing system with waiting i.e. multiply by a factor

  19.10.  Queuing system with waiting .

We get:

  19.10.  Queuing system with waiting . (10/19/14)

The relative capacity of the system is characterized by the probability that an application that has entered the system will be served:

  19.10.  Queuing system with waiting .

Obviously, the system bandwidth with the expectation, with the same   19.10.  Queuing system with waiting and   19.10.  Queuing system with waiting , будет всегда выше, чем пропускная способность системы с отказами: в случае наличия ожидания необслуженными уходят не все заявки, заставшие   19.10.  Queuing system with waiting каналов занятыми, а только некоторые. Пропускная способность увеличивается при увеличении среднего времени ожидания   19.10.  Queuing system with waiting .

Непосредственное пользование формулами (19.10.11), (19.10.12) и (19.10.14) несколько затруднено тем, что в них входят бесконечные суммы. Однако члены этих сумм быстро убывают.

Посмотрим, во что превратятся формулы (19.10.11) и (19.10.12) при   19.10.  Queuing system with waiting and   19.10.  Queuing system with waiting . Obviously, when   19.10.  Queuing system with waiting система с ожиданием должна превратиться в систему с отказами (заявка мгновенно уходит из очереди). Indeed, with   19.10.  Queuing system with waiting формулы (19.10.12) дадут нули, а формулы (19.10.11) превратятся в формулы Эрланга для системы с отказами.

Рассмотрим другой крайний случай: чистую систему с ожиданием   19.10.  Queuing system with waiting .In such a system, applications do not leave the queue at all, and therefore   19.10.  Queuing system with waiting : each application will wait for service sooner or later. But in a clean system with waiting, there is not always a limit stationary mode when  19.10.  Queuing system with waiting .It can be proved that such a regime exists only if   19.10.  Queuing system with waiting , that is, when the average number of requests per service time of one application does not go beyond the limits of the   19.10.  Queuing system with waiting -channel system. If   19.10.  Queuing system with waiting , the number of applications in the queue will increase unlimitedly over time.

Let's pretend that   19.10.  Queuing system with waiting , and find the limit probabilities   19.10.  Queuing system with waiting   19.10.  Queuing system with waiting for a pure system with expectation. To do this, we put in formulas (19.9.10), (19.9.11) and (19.9.12)  19.10.  Queuing system with waiting . We get:

  19.10.  Queuing system with waiting ,

or, summing up the progression (which is only possible with   19.10.  Queuing system with waiting ),

  19.10.  Queuing system with waiting . (10/19/15)

From here, using the formulas (10/19/08) and (10/19/9), we find

  19.10.  Queuing system with waiting   19.10.  Queuing system with waiting (10/19/16)

and likewise for   19.10.  Queuing system with waiting   19.10.  Queuing system with waiting

  19.10.  Queuing system with waiting . (10/19/17)

The average number of applications in the queue is determined from the formula (10/19/13) with   19.10.  Queuing system with waiting :

  19.10.  Queuing system with waiting . (10/19/18)

Example 1. At the input of a three-channel system with an unlimited waiting time comes the simplest flow of applications with density   19.10.  Queuing system with waiting (applications per hour). Average service time for one application  19.10.  Queuing system with waiting minDetermine if steady state maintenance exists; if yes, then find the probabilities   19.10.  Queuing system with waiting , the probability of having a queue and the average queue length  19.10.  Queuing system with waiting .

Decision. We have   19.10.  Queuing system with waiting ;   19.10.  Queuing system with waiting . Because   19.10.  Queuing system with waiting , steady state exists. By the formula (10/19/16) we find

  19.10.  Queuing system with waiting ;   19.10.  Queuing system with waiting ;   19.10.  Queuing system with waiting ;   19.10.  Queuing system with waiting .

The likelihood of a queue:

  19.10.  Queuing system with waiting .

The average queue length by the formula (10/19/18) will be

  19.10.  Queuing system with waiting (application).


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