Formulation of the problem. At the entrance n-channel QS receives the simplest flow of requests with density λ. The density of the simplest service flow of each channel is equal to μ. If the request received for service finds all channels free, then it is accepted for service and serviced simultaneously l channels ( l < n). In this case, the service flow of one request will have an intensity l.
If a request received for servicing finds one request in the system, then n ≥ 2l newly arrived application will be accepted for service and will be serviced simultaneously l channels.
If an application received for servicing finds in the system i applications ( i= 0,1, ...), while ( i+ 1)l≤ n, then the received request will be serviced l channels with a total capacity l. If a newly received application finds in the system j requests, and two inequalities are simultaneously satisfied: ( j + 1)l > n and j < n, then the application will be accepted for service. In this case, some applications can be served l channels, the other part smaller than l, number of channels, but all n channels that are randomly distributed among the applications. If a newly received application is found in the system n applications, it is rejected and will not be served. An application that has been serviced is serviced to the end (applications are "patient").
The state graph of such a system is shown in Fig. 3.8.
Rice. 3.8. QS state graph with failures and partial
mutual assistance between channels
Note that the state graph of the system up to the state x h coincides with the state graph of the classical queuing system with failures, shown in Fig. 2, up to the notation of the flow parameters. 3.6.
Consequently,
(i
= 0, 1, ..., h).
Graph of system states, starting from the state x h and ending with the state x n, coincides up to notation with the state graph of QS with full mutual assistance, shown in Fig. 3.7. In this way,
.
We introduce the notation λ / lμ = ρ l ; λ / nμ = χ, then
Taking into account the normalized condition, we obtain
To shorten further notation, we introduce the notation
Find the characteristics of the system.
Application Service Probability
The average number of applications in the system,
Average Busy Channels
.
Probability that a particular channel will be busy
.
The probability of occupancy of all channels of the system
3.4.4. Queuing systems with failures and inhomogeneous flows
Formulation of the problem. At the entrance n-channel QS receives an inhomogeneous elementary flow with a total intensity λ Σ , and
λ Σ
=
,
where λ i- the intensity of applications in i-m source.
Since the flow of requests is considered as a superposition of requirements from various sources, the combined flow with sufficient accuracy for practice can be considered Poisson for N = 5...20 and λ i ≈ λ i +1 (i1,N). The service intensity of one device is distributed according to the exponential law and is equal to μ = 1/ t. Servicing devices for servicing an application are connected in series, which is equivalent to increasing the service time by as many times as many devices are combined for servicing:
t obs = kt, μ obs = 1 / kt = μ/ k,
where t obs – request service time; k- the number of service devices; μ obs - the intensity of the application service.
Within the framework of the assumptions made in Chapter 2, we represent the QS state as a vector , where k m is the number of requests in the system, each of which is serviced m appliances; L = q max- q min +1 is the number of input streams.
Then the number of occupied and free devices ( n zan ( 
),n sv ( 
)) able 
is defined as follows:
Out of state 
the system can go to any other state 
. Since the system has L input streams, then from each state it is potentially possible L direct transitions. However, due to the limited resources of the system, not all of these transitions are feasible. Let the QS be in the state 
and an application arrives requiring m appliances. If a m≤ n sv ( 
), then the request is accepted for service and the system goes into a state with intensity λ m. If the application requires more devices than there are free ones, then it will receive a denial of service, and the QS will remain in the state 
. If able 
there are applications requiring m devices, then each of them is serviced with intensity m, and the total intensity of servicing such requests (μ m) is defined as μ m
= k m μ
/ m. When the service of one of the requests is completed, the system will go into a state in which the corresponding coordinate has a value one less than in the state 
,
=, i.e. reverse transition will occur. On fig. 3.9 shows an example of a QS vector model for n
= 3, L
= 3, q min = 1, q max=3, P(m) = 1/3, λ Σ = λ, the intensity of instrument maintenance is μ.
Rice. 3.9. An example of a QS vector model graph with denial of service
So every state 
characterized by the number of serviced requests of a certain type. For example, in a state 
one claim is serviced by one device and one claim by two devices. In this state, all devices are busy, therefore, only reverse transitions are possible (the arrival of any customer in this state leads to a denial of service). If the service of the request of the first type ended earlier, the system will switch to the state 
(0,1,0) with intensity μ, but if the service of the second type of request ended earlier, then the system will go into the state 
(0,1,0) with intensity μ/2.
A system of linear algebraic equations is compiled from the graph of states with applied transition intensities. From the solution of these equations, the probabilities are found R(
), by which the QS characteristic is determined.
Consider finding R otk (probability of denial of service).
,
where S is the number of graph states of the QS vector model; R(
) is the probability of the system being in the state 
.
The number of states according to is defined as follows:
,
(3.22)
;
Let us determine the number of states of the QS vector model according to (3.22) for the example shown in Fig. 3.9.
.
Consequently, S = 1 + 5 + 1 = 7.
To implement real requirements for service devices, a sufficiently large number of n
(40, ..., 50), and requests for the number of service devices of the application in practice lie in the range of 8–16. With such a ratio of instruments and requests, the proposed way of finding the probabilities becomes extremely cumbersome, since QS vector model has a large number of states S(50)
= 1790, S(60)
= 4676, S(70) = 11075, and the size of the matrix of coefficients of the system of algebraic equations is proportional to the square S, which requires a large amount of computer memory and a significant amount of computer time. The desire to reduce the amount of computation stimulated the search for recurrent computational possibilities R(
) based on multiplicative forms of representation of state probabilities. The paper presents an approach to the calculation R(
):
(3.23)
The use of the criterion of equivalence of the global and detailed balances of Markov chains proposed in the paper makes it possible to reduce the dimension of the problem and perform calculations on a computer of medium power using the recurrence of calculations. In addition, there is the possibility:
– calculate for any values n;
– speed up the calculation and reduce the cost of machine time.
Other characteristics of the system can be defined similarly.
So far, we have considered only those QSs in which each claim can be serviced by only one channel; idle channels cannot "help" a busy one in service.
In general, this is not always the case: there are systems queuing, where the same request can be served simultaneously by two or more channels. For example, the same failed machine can serve two workers at once. Such "mutual assistance" between channels can take place both in open and closed QS.
When considering CMOs with mutual assistance between channels, two factors need to be taken into account:
1. How much faster is the service of an application when not one, but several channels work on it at once?
2. What is the “discipline of mutual aid”, i.e. when and how do several channels take over the service of the same request?
Let's consider the first question first. It is natural to assume that if more than one channel, but several channels, work on servicing a request, the intensity of the service flow will not decrease with increasing k, i.e., it will be a certain non-decreasing function of the number k of working channels. Let's denote this function. The possible form of the function is shown in fig. 5.11.
Obviously, an unlimited increase in the number of simultaneously operating channels does not always lead to a proportional increase in the service rate; it is more natural to assume that, at a certain critical value, a further increase in the number of busy channels no longer increases the service intensity.
In order to analyze the operation of a QS with mutual assistance between channels, it is necessary, first of all, to set the type of function
The simplest case for investigation will be the case when the function increases proportionally to k when a remains constant and equal when a (see Fig. 5.12). If, in addition, the total number of channels that can help each other does not exceed
Let us now turn to the second question: the discipline of mutual aid. The simplest case of this discipline we will conditionally designate as “all as one”. This means that when one request appears, all channels start serving it at once and remain busy until the service of this request ends; then all channels switch to servicing another request (if it exists) or wait for it to appear if it does not exist, etc. Obviously, in this case, all channels work as one, the QS becomes single-channel, but with a higher service intensity.
The question arises: is it beneficial or disadvantageous to introduce such mutual assistance between channels? The answer to this question depends on the intensity of the flow of applications, what type of function, what type of QS (with failures, with a queue), what value is chosen as a characteristic of service efficiency.
Example 1. There is a three-channel QS with failures: the intensity of the flow of applications (applications per minute), the average service time of one application by one channel (min), the function "? Is it beneficial from the point of view of reducing the average residence time of an application in the system?
Solution a. Without mutual help
By the Erlang formulas (see § 4) we have:
Relative throughput CMO;
Absolute Bandwidth:
The average residence time of an application in the QS is found as the probability that the application will be accepted for service, multiplied by the average service time:
Gist (min).
It should not be forgotten that this average time applies to all requests - both serviced and unserved. We may be interested in the average time that a serviced request will stay in the system. This time is:
6. With mutual assistance.
Average residence time of an application in the CMO:
Average residence time of a serviced request in the QS:
Thus, in the presence of mutual assistance “all as one”, the throughput of the SMO has noticeably decreased. This is explained by an increase in the probability of failure: while all channels are busy serving one application, other applications may come and, naturally, be refused. As for the average residence time of an application in the CMO, it, as expected, decreased. If, for some reason, we are striving to reduce the time that the application spends in the QS in every possible way (for example, if staying in the QS is dangerous for the application), it may turn out that, despite the decrease in throughput, it will still be beneficial to combine three channels into one.
Let us now consider the impact of “all as one” mutual assistance on the work of CMOs with expectation. For simplicity, we take only the case of an unbounded queue. Naturally, there will be no influence of mutual assistance on the throughput of the QS in this case, since under any conditions all incoming applications will be served. The question arises about the influence of mutual assistance on the characteristics of waiting: the average length of the queue, the average waiting time, the average time spent in the QS.
By virtue of formulas (6.13), (6.14) § 6 for service without mutual assistance, the average number of customers in the queue will be
average waiting time:
and the average time spent in the system:
If mutual assistance of the “all as one” type is used, then the system will work as a single-channel system with parameters
and its characteristics are determined by formulas (5.14), (5.15) § 5:
Example 2. There is a three-channel QS with an unlimited queue; intensity of the flow of applications (applications per min.), average service time Function Beneficial in view of:
Average queue length
Average waiting time for service,
Average residence time of an application in the CMO
introduce mutual assistance between channels like "all as one"?
Solution a. No mutual help.
By formulas (9.1) - (9.4) we have
(3-2)
b. With mutual assistance
By formulas (9.5) - (9.7) we find;
Thus, the average length of the queue and the average waiting time in the queue in the case of mutual assistance is greater, but the average time the application spends in the system is less.
From the considered examples it is clear that mutual assistance between k? "all as one" type of cash, as a rule, does not contribute to improving the efficiency of service: the time spent by an application in the QS decreases, but other characteristics of the service worsen.
Therefore, it is desirable to change the service discipline so that mutual assistance between channels does not interfere with accepting new requests for service if they appear during the time when all channels are busy.
Let us conditionally call "uniform mutual assistance" the following type of mutual assistance. If the request arrives at the moment when all channels are free, then all channels are accepted for its service; if, at the time of servicing the request, another one arrives, some of the channels switch to servicing it; if, while these two requests are being served, another one arrives, some of the channels are switched to serve it, and so on, until all channels are occupied; if so, the newly arrived claim is rejected (in a QS with denials) or placed in a queue (in a QS with waiting).
With this discipline of mutual assistance, the application is rejected or queued only when it is not possible to serve it. As for the “downtime” of channels, it is minimal under these conditions: if there is at least one application in the system, all channels work.
We mentioned above that when a new request appears, some of the busy channels are released and switched to servicing the newly arrived request. What part? It depends on the type of function. If it has the form of a linear relationship, as shown in fig. 5.12, and it doesn't matter which part of the channels to allocate for servicing a newly received request, as long as all channels are occupied (then the total intensity of services for any distribution of channels by requests will be equal to ). It can be proved that if the curve is convex upward, as shown in Fig. 5.11, then you need to distribute the channels among the applications as evenly as possible.
Let us consider the work of -channel QS with "uniform" mutual assistance between channels.
Let us consider a multi-channel queuing system (there are n channels in total), in which requests arrive at a rate of λ and are serviced at a rate of μ. A request that has arrived in the system is serviced if at least one channel is free. If all channels are busy, then the next request that enters the system is rejected and leaves the QS. We number the system states by the number of busy channels:
- S 0 – all channels are free;
- S 1 – one channel is occupied;
- S 2 – two channels are occupied;
- Sk– busy k channels;
- Sn– all channels are busy.
Rice. 7.24
Figure 6.24 shows a state graph in which Si– channel number; λ is the intensity of receipt of applications; μ
- respectively, the intensity of servicing requests. Applications enter the queuing system with a constant intensity and gradually occupy channels one after another; when all channels are occupied, the next request that arrives at the QS will be rejected and leave the system.
Let us determine the intensities of the event flows that transfer the system from state to state when moving both from left to right and from right to left along the state graph.
For example, let the system be in the state S 1 , i.e., one channel is busy, since there is a request at its input. As soon as the request is processed, the system will switch to the state S 0 .
For example, if two channels are busy, then the service flow that transfers the system from the state S 2 per state S 1 will be twice as intense: 2-μ; respectively, if busy k channels, the intensity is equal to k-μ.
The service process is a process of death and reproduction. The Kolmogorov equations for this particular case will have the following form:
(7.25)
Equations (7.25) are called Erlang equations
.
In order to find the values of the probabilities of the states R 0 , R 1 , …, Rn, it is necessary to determine the initial conditions:
– R 0 (0) = 1, i.e. there is a request at the system input;
– R 1 (0) = R 2 (0) = … = Rn(0) = 0, i.e., in initial moment time the system is free.
After integrating the system of differential equations (7.25), we obtain the values of the state probabilities R 0 (t), R 1 (t), … Rn(t).
But we are much more interested in the limiting probabilities of states. As t → ∞ and using the formula obtained when considering the process of death and reproduction, we obtain the solution of the system of equations (7.25):
(7.26)
In these formulas, the intensity ratio λ / μ
to the flow of applications it is convenient to designate ρ
.This value is called the reduced intensity of the flow of applications, that is, the average number of applications arriving in the QS for the average service time of one application.
Taking into account the above notation, the system of equations (7.26) takes the following form:
(7.27)
These formulas for calculating marginal probabilities are called Erlang formulas
.
Knowing all the probabilities of the QS states, we find the QS efficiency characteristics, i.e., the absolute throughput BUT, relative throughput Q and probability of failure R open
A request that enters the system will be rejected if it finds all channels busy:
.
The probability that the application will be accepted for service:
Q = 1 – R otk,
where Q is the average share of received requests serviced by the system, or the average number of requests served by the QS per unit of time, divided by the average number of requests received during this time:
A=λ Q=λ (1-P open)
In addition, one of the most important characteristics QS with failures is average busy channels. AT n-channel QS with failures, this number coincides with the average number of applications in the QS.
The average number of applications k can be calculated directly in terms of the probabilities of the states Р 0 , Р 1 , … , Р n:
,
i.e. we find the mathematical expectation of a discrete random variable that takes a value from 0 to n with probabilities R 0 , R 1 , …, Rn.
It is even easier to express the value of k in terms of the absolute throughput of the QS, i.e. A. The value of A is the average number of applications that are serviced by the system per unit of time. One busy channel serves μ requests per time unit, then the average number of busy channels
| Classification features | Varieties of queuing systems | |||||||||||
| Incoming demand flow | Limited requirements | Closed | open | |||||||||
| distribution law | Systems with a specific law of distribution of the incoming flow: exponential, Erlang k order, palm, normal, etc. | |||||||||||
| Turn | Queue discipline | With ordered queue | With an unordered queue | Service Priority | ||||||||
| Waiting Service Limits | With rejections | With unlimited waiting | Restricted (mixed) | |||||||||
| By queue length | Waiting time in queue | By time of stay in SMO | Combined | |||||||||
| Service discipline | Service stages | single phase | Polyphase | |||||||||
| Number of service channels | single channel | Multichannel | ||||||||||
| With equal channels | With unequal channels | |||||||||||
| Reliability of service channels | With absolutely reliable channels | With unreliable channels | ||||||||||
| No recovery | With recovery | |||||||||||
| Mutual Aid Channels | without mutual aid | With mutual help | ||||||||||
| Service reliability | With mistakes | Without mistakes | ||||||||||
| Service Time Distribution | Systems with a specific service time distribution law: deterministic, exponential, normal, etc. | |||||||||||
If the service is performed in stages by some sequence of channels, then such a QS is called multiphase.
AT CMO with "mutual assistance" between channels, the same request can be served simultaneously by two or more channels. For example, the same failed machine can serve two workers at once. Such "mutual assistance" between channels can take place both in open and closed QS.
AT CMO with errors an application accepted for service in the system is serviced not with full probability, but with some probability ; in other words, there may be errors in service, the result of which is that some applications that went to the QS and supposedly "served" actually remain unserved due to "marriage" in the work of the QS.
Examples of such systems are: information desks, sometimes giving incorrect information and instructions; a corrector that can miss an error or correct it incorrectly; telephone exchange, sometimes connecting the subscriber to the wrong number; trading and intermediary firms that do not always fulfill their obligations with high quality and on time, etc.
To analyze the process occurring in a QS, it is essential to know basic system parameters: the number of channels, the intensity of the flow of applications, the performance of each channel (the average number of applications served per unit time by the channel), the conditions for the formation of the queue, the intensity of the departure of applications from the queue or system.
The relation is called system load factor. Often only such systems are considered in which .
Service time in QS can be both random and non-random. In practice, this time is most often taken as distributed according to the exponential law, .
The main characteristics of the QS depend relatively little on the type of service time distribution law, but depend mainly on the average value . Therefore, it is often assumed that the service time is distributed according to an exponential law.
The assumptions about the Poisson nature of the flow of requests and the exponential distribution of service time (which we will assume from now on) are valuable because they allow us to apply the apparatus of the so-called Markov random processes in the theory of queuing.
The effectiveness of service systems, depending on the conditions of the tasks and the objectives of the study, can be characterized a large number various quantitative indicators.
The most commonly used are the following indicators:
1. The probability that the channels are busy with the service is .
A special case is the probability that all channels are free.
2. The probability of refusal of the application in service.
3. The average number of busy channels characterizes the degree of system load.
4. Average number of channels free of service:
5. Coefficient (probability) of idle channels.
6. Equipment load factor (probability of busy channels)
7. Relative throughput - the average share of incoming requests served by the system, i.e. the ratio of the average number of requests serviced by the system per unit of time to the average number of requests received during this time.
8. Absolute throughput, i.e. the number of applications (requirements) that the system can serve per unit of time:
9. Average channel idle time
For systems with expectation additional features are used:
10. Average waiting time for requests in the queue.
11. Average residence time of an application in the CMO.
12. Average queue length.
13. Average number of applications in the service sector (in CMOs)
14. Probability that the time the application stays in the queue will not last more than a certain time.
15. The probability that the number of requests in the queue waiting to start service is greater than some number.
In addition to the listed criteria, when evaluating the effectiveness of systems, cost indicators:
– the cost of servicing each requirement in the system;
– the cost of losses associated with waiting per unit of time;
– the cost of losses associated with the departure of requirements from the system;
is the cost of operating the system channel per unit of time;
is the cost per unit of downtime for the channel.
When choosing the optimal system parameters for economic indicators, you can use the following loss cost function:
a) for systems with unlimited waiting
Where is the time interval;
b) for systems with failures ;
c) for mixed systems.
Options that provide for the construction (commissioning) of new elements of the system (for example, service channels) are usually compared at reduced costs.
The reduced costs for each option are the sum of current costs (cost) and capital investments, reduced to the same dimension in accordance with the efficiency standard, for example:
(given costs per year);
(given costs for the payback period),
where - current costs (cost) for each option, p.;
– industry normative coefficient economic efficiency capital investments (usually = 0.15 - 0.25);
– capital investments for each option, p.;
is the standard payback period for capital investments, years.
The expression is the sum of current and capital costs for a certain period. They are called given, since they refer to a fixed period of time (in this case, to the standard payback period).
Indicators and can be used both in the form of the sum of capital investments and the cost of finished products, and in the form specific capital investments per unit of production and unit cost of production.
To describe a random process occurring in a system with discrete states , state probabilities are often used , where is the probability that at the moment the system will be in the state .
It's obvious that .
If a process occurring in a system with discrete states and continuous time is Markovian, then for the probabilities of states it is possible to compose a system of linear Kolmogorov differential equations.
If there is a labeled graph of states (Fig. 4.3) (here, above each arrow leading from state to state, the intensity of the flow of events is indicated, transferring the system from state to state along this arrow), then the system of differential equations for probabilities can be immediately written using the following simple rule.
On the left side of each equation there is a derivative, and on the right side there are as many terms as the arrows are directly related to this state; if the arrow points in
If all flows of events that transfer the system from state to state are stationary, the total number of states is finite and there are no states without exit, then the limit mode exists and is characterized by marginal probabilities .
