Multichannel smo with failures. QS with failures and full mutual assistance for arbitrary flows
UDC 519.248:656.71
MODEL OF A QUEUING SYSTEM WITH NON-STATIONARY FLOWS AND PARTIAL MUTUAL ASSISTANCE BETWEEN CHANNELS
© 2011 V. A. Romanenko
Samara State Aerospace University named after academician S.P. Korolev (national research university)
A dynamic model of a multichannel system is described queuing with non-stationary flows, waiting in a queue of limited length and partial mutual assistance of channels, which is expressed in the possibility of simultaneous servicing of an application by two channels. Expressions for the main probabilistic-temporal characteristics of the system are given. The results of modeling the functioning of the hub airport are described as an example of the system under consideration.
Queuing system, non-stationary flow, mutual assistance between channels, hub airport.
Introduction
A multi-channel queuing system (QS) with waiting in a queue of limited length is considered. A feature of the QS under consideration is partial mutual assistance between channels, which is expressed in the possibility of using two channels simultaneously to service one application. Combining the efforts of the channels leads in the general case to a reduction in the average service time. It is assumed that the QS receives a nonstationary Poisson flow of requests. The duration of the application service depends on the time.
A typical example of a QS with the listed features is the airport transportation service system. The simultaneous use of several (usually two) facilities (check-in counters, aircraft refuelers, special vehicles, etc.) for servicing one flight is provided for by the technological schedules of airport servicing of large aircraft (AC). At the same time, the need to improve the quality and reduce the duration of ground handling of transportation, which is especially relevant for large airports, leads to the fact that the share of operations performed not by one, but by several (two) means is increasing.
no with the increase in the scale of the airport. The model described in the article was developed to solve the problems of analyzing and optimizing the functioning of industrial complexes of hub airports (hubs), characterized by the saturation of ground handling facilities for transportation with a pronounced non-stationarity of the flow of passengers, aircraft and cargo and fluctuations in the intensity of their service.
general description models
The model is designed to determine the time dependences of the probabilistic characteristics of a QS containing N serving channels. The number of applications in the CMO should not exceed K, which may be due to technical restrictions on the number of aircraft parking spaces equipped at the airport, the capacity of the air terminal or cargo complex, etc. The number of channels allocated for servicing one request a can be either 1 or 2. If there are at least two free channels, the incoming request with a given probability takes to service
one of them and - with probability y2 = 1 - y1 - both channels. If, at the time of receipt of a request for servicing, the QS has only one free channel, then this request in any case occupies the available channel.
the only channel. If there are no idle channels, the newly received request “gets into the queue” and waits for service. If the number of claims in the queue is K-N, then the newly arrived claim leaves the QS unserved. The probability of such an event should be small.
The QS input receives a Poisson (not necessarily stationary) flow of requests
with intensity l(t). It is assumed that the duration of the request service both by one channel Tobsl1 (t) and by two -
Tobsl 2 (t) are exponentially distributed random functions of time (stochastic processes).
Application service intensity
one channel ^ (t) and simultaneously two channels m 2 (t) are defined as
mi (t) = [Tobsl1 (t)]-1 , m2 (t) = [Tobsl2 (t)]-1,
where Tobsl1 (t) = M [Tobsl1 (t)] , Tobsl 2 (t)= M[Tobsl 2 (t)]
Average service time for a request by one channel and two channels, respectively.
The connection between the values m1 (t) and m 2 (t) is given by the relation
m2 (t) = ^m1 (t) ,
where 9 is a coefficient that takes into account the relative increase in service intensity when using two channels.
In practice, the relationship between the number of funds raised and the intensity of service is quite complex, determined by the characteristics of the service operation under consideration. For operations, the duration of which is related to the volume of work performed (for example, refueling aircraft with aviation fuel using aircraft fuel tankers, boarding or disembarking passengers from the aircraft, etc.), the dependence of the intensity of service on the number of channels approaches a directly proportional one, however, being not strictly proportional. due to the time spent on preparing
but-final operations, which are not affected by the number of means. For such operations £2.
screening of passengers). In this case, in "1.
At an arbitrary moment of time I, the QS under consideration can be in one of b + 1 discrete states - B0, ...,
b. The transition from state to state can be carried out at any time. The probability that at time I the QS will be in the state
the normalization condition 2 p () =1
The calculation of the probabilities P0 (/), PX (t),..., Pb (t) makes it possible to determine such important virtual (instantaneous) QS characteristics as the average queue length, the average number of busy channels, the average number of customers in the QS, and others
The probabilities of states p(t) are found by solving the system differential equations Kolmogorov, in general view written as
=Ё jp(t)P /(t)-P,(t)Z (t).,
r = 0,1,...,b,
Where<р^ ^) - плотности (интенсивности) вероятностей перехода из состояния с порядковым номером г в состояние с порядковым номером ]. Величины фу (t) определяются по формуле
where P(/; At) is the probability that the QS, which was at the moment t in the state B., after
time At will pass from it to the state
To compose the Kolmogorov equations, a labeled graph of QS states is used. In it, above the arrows leading from B. to B., the corresponding intensities of f. .
To compose the graph, a three-index notation is introduced, in which the state of the considered QS at an arbitrary moment of time is characterized by three parameters: the number of busy channels n (n = 0,1,...,t), 0,1,...,^) and awaiting service m (m = 0,1,...,^ - N).
On fig. Figure 1 shows a labeled state graph, compiled using the rules described above and the notation introduced, for a QS chosen as a simple example.
On the graph and in the corresponding system of Kolmogorov equations given below, in order to save space, the designations of the functional time dependence of the intensities 1, m1, m2 and state probabilities are omitted.
^000 /L \u003d - (^1 ^ + ^2 ^) P000 + mp10 + m2P210,
\u003d - (m + Y-11 + Y21) psh + ^Rp000 +
2t1R220 + t2 R320,
LR210 IL \u003d - (t2 + ^11 + ^21) P210 + V2Rp000 +
T1P320 + 2 ^2P420,
LR220/L = -(2^1 + ^1^ + ^21) P220 + ^1Rio +
3 m1P330 + ^2P430,
LR32<:)1Л = - (т2 + т1 + ^11 + ^21)р320 +
+ ^ 11P210 + V2ЯP110 + 2t 1P430 +
LR4u1L (1 + 2 ^2) P420 + ^21P210 + m p30, LR330 /L = -(3m1 + ^1^+ ^21) P330 + ^11P220 + +4^1P440 + r2p40,
^430 /L = - (2^1 + ^2 + 1) P430 + ^11P320 +
+ ^ 2 ^ P220 + 3m 1p40 + 2 ^ 2p31,
LR530 / l \u003d - (t + 2m2 + i) p^30 + 1P420 +
+ ^2R320 + m1R531,
LR440 IL (4t1 + I) r40 + R330 +
5^1p50 + t2p41,
LR540 / l \u003d - (t2 + 3t + i) p540 + yar430 +
+ "^ 2R330 + 3 m1R541 + 2 m2R532,
LR531/L = - (^1 + 2^2 + R) R^31 + R530 +
LR550 IL \u003d - (5t1 + I) R550 + YAR440 +
5t1R551 + t2R542,
LR541/ l \u003d - (t2 + 3m + i) p^41 + rr^40 +
LR532 / l \u003d - (t1 + 2t2) R532 + i p531,
LR5511L \u003d - (5t1 + I) r51 + YAR550 + 5t1R552,
lr542 / l \u003d - (3 t + t2) p542 + i p541,
Rp5^ ^ = 5 m1P552 + i p51.
If at the moment t = 0 there are no requests in the QS, then initial conditions will be written in the form
P10(0)=P210(0)=P220(0)=...=P552(0)=0.
The solution of systems of large dimensions, similar to (1), (2), with variables 1(t, mDO, m2(0) is possible only by numerical methods using a computer.
Rice. 1. QS state graph
Building a QS Model
In accordance with the algorithmic approach, let us consider a method for transforming a system of Kolmogorov equations of arbitrary dimension into a form suitable for computer calculations. In order to simplify the notation, instead of triple, we use a double system of notation for the states of the QS, in which r is the number of channels occupied by servicing plus the length of the queue,] is the number of applications in the QS. The relationship between notation systems express dependencies:
r = n + m, r = 0.1,...,K;
] = k + m, ] = 0,1,...,K.
Not any state from the formal set may be implemented
B. (r = 0.1,...,K; ] = 0.1,...,K). In particular,
within the framework of the described model, states are impossible in which two or more requests are simultaneously serviced by one
channel, i.e. R. (t) = 0 if ] > r. Let 8 denote the set of admissible states of the QS. B.'s condition exists, and
the corresponding probability P. ^)
may be non-zero if one of the following conditions is met:
1)] <г< 2], если 2] < N,
2)] <г< ] + Ч - 1 если \ .
y] + H - 1< К,
3)] < г < К, если ] + ч - 1 ^ К,
r = 0.1,...,K; ] = 0,1,...,K,
where N is the maximum number of states with a different number of serving channels for a given number of requests, determined by the formula
Here the brackets denote the operation of discarding the fractional part. For example,
According to the state graph shown in Fig. 1, two customers can be served by two, three or four channels. Therefore, in the above example
H \u003d 5 - \u003d 5 - 2 \u003d 3.
To implement computer calculations using the Kolmogorov system of equations of arbitrary dimension, its equations must be reduced to some universal form that allows writing any equation. In order to develop such a form, we consider a fragment of the state graph that displays one arbitrary state B] with leading from it
intensity arrows. Let us denote by Roman numerals the neighboring states directly connected with B., as shown in Fig. 2.
For each state of B. (r = 0.1,...,K; ] = 0.1,...,K), such that B. e 8 , at time t the values
p^), p(t), p.^), p(t) take
various values (including those equal to zero). However, the structure of the equation
(3) remains unchanged, which makes it possible to use it for the computer implementation of the Kolmogorov system of equations of arbitrary dimension.
The intensities fr (t) , (p. (t), tending to transfer the QS to states with large values of r and ], if the presence of such states is possible, are determined based on a number of conditions as follows:
o.. u or
°(,-+1)0"+1) ї 8 ’
0(,-+2)(.+1) - 8 i £ N - 2,
o(i+1)(.+1)- 8 or
°(.+2)a+1)ї 8
O(.+1)(V+1) - 8’
Rice. 2. Fragment of the QS state graph
Taking into account the presence of neighboring states with respect to B., the equation for B. can be written as follows:
-£ = -[P () + P () + P. () +
Pp (tJ Pr, (t) + Pp+1)(.+1) (t) P(r+1)(.+1) () +
P(H(1-1)^)P(-1)(1-1)^) +
Р 2)()+1)() Р(r+2)()-+1)() +
RC2)(.-1) (t)P(g-2)(.-g) ().
O(.+1)(.+1)ї 8 or i > N - 2
Y2X(i), if
I(i+1)(.+1) - 8>
O(i+2)(.+1) - 8 'i £ N - 2,
O(i+1)(.+1)ї 8’
O(i+2)(.+1) - 8’
r = 0,1,...,k, . = 0,1,...,k.
Intensity r. (), p..11 (), transferring QS from the state B-. into states
with smaller values of r and. (if the presence of such states is possible) are directly proportional to the number of channels involved, serving applications of various types located in the QS (occupying one or two channels for servicing). A group of two channels occupied by servicing one request of the corresponding type can be considered as one channel. Therefore, in the general case
p () = cdM1 () , p. () = ku2^2 () ,
where k.1 is the number of applications occupying one channel, served by the QS in state B.; k is the number of applications occupying two channels served by the QS in state B. .
Through g and these quantities are defined as follows:
G2. - r if r< N,
y1 [ N - 2 (r - .), if r > N, (4)
To! 2 = g - . .
Taking into account the restrictions on the possibility of existence of states of the expression for
p(), p.() have the form
^B(r-1)(L) e 8,
QS performance indicators
The described model makes it possible to determine the time dependences of the following performance indicators for the functioning of the considered QS.
Average queue length:
can ()=22(g-n) R ().
Average number of busy channels:
Average number of applications in CMO:
m, ()=22 .R. ().
Denial of Service Probability:
Р„, ()= 2 Р- ().
The distribution of the virtual waiting time by the ticket can be obtained
service W (x, t) = P ^exp ()< х) , позволяющее характеризовать качество обслуживания рассматриваемой СМО. Поступившая в систему заявка вынуждена ожидать обслуживания в случае, если все каналы заняты обслуживанием заявок, поступивших
previously. There is a probability Рк=0 (t) of immediate servicing of the incoming request in the presence of a free channel (or several free channels)
B(g-1)(.-1) £ 8,
r = 0,1,...,K, . = 0.1, ..., K.
R. () ° 0 if B. £ 8 .
Taking into account the possibility of failure, the desired value of the distribution function W(x^) is determined as
F (x-‘) \u003d (--o (t)
EEZH M (,)) ()
Ru ()° 0 if °y. ї 8 .
Here W (x, m| (i,./)) is a conditional function
the distribution of the waiting time of a certain claim, provided that at the time of its arrival T it caught the QS in the state y.
In the QS under consideration, the waiting time for service by an incoming claim depends not only on the number of claims already in the QS, but also on the distribution of channels between group and individual servicing of existing claims. If there were no mutual assistance between channels, then the QS under consideration would be a traditional QS with waiting in a queue of limited length, for which the total waiting time for the start of service by a claim that found m other claims in the queue at the time of arrival would have the Erlang distribution (X) .
Here, the superscript contains the intensity of servicing requests by all N channels operating in the presence of a queue; the subscript is the distribution order according to the Erlang law. In the QS considered here, the described law is valid only for requests that entered the QS in states when all channels are busy, and all of them serve one request. For these states, one can write
X (x, m | ^ + m, N + m)) = ^ + 1() (x).
Let us denote by E^"^1 (x) the distribution function of the generalized Erlan-
ha, having the order of 2 "g - 1, where ag is the number
lo random variables distributed over
exponential law with the parameter yi. WITH
Using the introduced notation, we write expressions for the distribution function of the waiting time in other states. Compared to (5), these expressions have a more complex form, which does not interfere with their software implementation. Further, as an example, they are given only for the first three full-busy states of the channels using the previously introduced three-character indexing:
W (x, m | (n, k, m)) = W (x, m | (N, N - g, 0)) =
= (x), 0 £ g £ q,
where i. \u003d kіLt (t) + ku 2M2 (t);
W (x, m | (n, k, m)) = W (x, m | (N, N - g, l)) =
H ^ ^ - g) Km (T)
W (x, m | - g, 2))
H ^). (N - g) Km (t)
E/^(t),(t-g) ■i(t),(t-g+l)
(N),(N - g) kM(T)
EI-) (t-g) (x) +
^).(N - g) eH^) (x)
The average virtual waiting time for a claim Itoj () is defined numerically as
Identity (T) = | ^ W (x, T) .
The distribution of the virtual service time for an arbitrarily chosen request Tobcl ^) can also be determined.
Since the change Tobsl(t) in the considered QS is a random process, which is a mixture of two exponentially distributed random processes Tobcl1 (t) and Tobcl2 ^), the distribution
V (x^) \u003d P (Tobsl (t)< х) не будет показательным. С учётом возможности отказа выражение для функции распределения V (х^) запишется в виде
EEU M k,.YR (t)
R.. ^) ° 0 if 8. £ 8 .
Here V (x^| (r,.)) is the conditional distribution function of the service time of a certain request, provided that at the moment of its arrival it caught the QS in the state ..
If, at the moment of the beginning of servicing a request, the QS is in a state in which both group and individual servicing is possible, then the service time is a mixture of two pro-
transition to group service - in the presence of the possibility of the state (Fig. 2). Thus, we have:
U (M (i--/")) =
y (1 - e-m(t)x) + +y (1 - e^2(t)x),
I O(i+2)(]+1) ї 8, O(i+1)(.+1) - 8,
"2\* ^ I' I ^ +2)(.+1)
i = 0.1,...,N -1, i = 0.1,...,N -1.
Since in the absence of two free channels, any request is serviced by one channel, then the actual probability (t) of allocating one channel will be
det is greater than the given V The function φ ^) is defined as
EEU O", "p (t)
R. (t) ° 0 if I. ї 8 .
Here y1 (r,. is the probability of allocating one device to service an application received by the QS in the state .:
O(i+1)(.+1) - 8, O(i
2)(}+1) -2)(!+1)
durations: Tobsl1 (t) and Tobsl2 (t), ras- i \u003d 0.1 ..., K -1, . \u003d 0.1 ..., K -1.
exponentially limited with parameters ^1 (t) and ^2 (t) , respectively. If in
At this point, there is no possibility of selecting two channels, then the service time of the request is distributed exponentially with the parameter
t(t). When a request approaches the servicing channels in state B, the transition to individual servicing is admissible when
the presence of the possibility of the state I (
The average duration of service of an application that entered the QS at the moment
T, can be defined in terms of uv(T) as
Tbl (t) \u003d UV (t) Tm (t) + Tbs 2 (t).
Distribution of the virtual residence time of the application in the QS
u (x, m) \u003d P (Tpreb (t)< х)
is determined using the previously obtained expressions for the distribution functions of waiting time and service time
vanations as I,
2^2 (m) Em^^(m)^^) (x) +
ЕЕi М)) рї (t)
and (x, m | (^ .)) =
1 - e-M1(t)x
y (1 - e-t (t) x) - + y2 (1 - e
(1 - e ^m(t)x),
O(i+1)(.+1) - 8, O(i+ 2)(.+1) ї 8’
О(і+1)(.+1) - 8’ О(і+2)(.+1) - 8,
r = 0.1,...^-1, . = 0'l'...'N-1.
For other states, the formulas of the conditional distribution function are written by analogy with the formulas for
W (x^| (n, k, m)) using three-character indexing. Below they are given for the first three states of full employment of channels:
By the time the request enters, there is no queue, but all channels are busy:
u (x^| (n, k, m)) = u (x^ | (NN - g, 0)) =
(x), 0 £ g £ q;
By the time the application enters, there is one application in the queue:
R. (t) ° 0 if I. ї 8 .
Here u (x^| (r,.)) is the conditional distribution function of the time spent in the QS of a certain request, provided that at the moment of its arrival t it caught the system in the state ..
For states with free channels, the residence time in the QS coincides with the service time:
By the time the application enters, there are two applications in the queue:
and (x, m | (m, m - ^2))
(m)(m^)H (m)(m^+1)
(t)(t - g) ccm (t)
(t)(t - g) CCM (t)
The average virtual residence time of an application in the QS is defined as
Tpreb ^) \u003d Tobsl (t) + Identity (t) .
An example of using the QS model
The functioning of the production complex of one of the Eastern European regional hub airports during the day is simulated when performing a separate technological operation for servicing arriving aircraft. As the initial data for modeling, the time dependences of the average intensity of the flow of aircraft arriving
per service, i(t) and intensity
maintenance of the aircraft by one means t1 (t) .
As follows from the data
airport website dependency graph i(t)
(Fig. 3a), the arrival of VS is characterized by a significant non-uniformity: during the day, four intensity maxima are observed, corresponding to four “waves”
us» arrival-departure flights. Peak values 1(t) for the main "waves" reach 25-30 VS/h.
On fig. 3 and a plot of dependence t (t) is also displayed. It is assumed that not
only the intensity of the flow of aircraft, but also the intensity of their service is a function of time and depends on the phase of the "wave". The fact is that in order to reduce the average time of passenger transfer, the schedule of the hub airport is constructed in such a way that the “wave” is initiated by the arrivals of large passenger aircraft, the maintenance of which requires a lot of time, and completed by the arrivals of small aircraft. In the example, it is assumed that the average duration of the operation by one tool, which is 20 minutes for most of the day, at the initial stage of the “wave” increases to 25 minutes. and is reduced to final stage up to 15 min. Thus, four intervals with
lower level t(t) in fig. 3a correspond to the initial phases of the "waves" when the arrivals of large planes predominate. In turn, four increase intervals
level m ^) fall on the final
phases of "waves" with a predominance of small aircraft.
The simulation results are described below, which allow evaluating the efficiency of the system. On fig. 3b-3d shows the time dependences of the average values of the number of occupied channels Nz ^),
the total number of applications in the MOH system ^) and
queue lengths Moj (7) obtained for two limit values of probability n1 = 0 and n1 = 1 with the following design characteristics: N = 10; K = 40; at = 1.75 . Judging by the dependence graph Nz (t)
(Fig. 3b), during most of the daily time interval, the occupancy of the serving channels of the system remains low, which is a consequence of the non-stationarity of the input
flow of aircraft. High load (60-80%) is achieved only during the second “wave” of arrivals and departures, and the option n1 = 0 for large values of 1(t) causes a greater load on the system, and for small values of 1(t) - less
compared with the variant n1 = 1. At the same time, as
simulation showed that the probability of failure in the system under consideration for both options is negligible.
Comparison of dependency graphs
M3 ^) and Mozh ^) (Fig. 3c and 3d, respectively) allows us to conclude that in QS at n1 = 0 there are fewer requests on average, and more requests are expected to be serviced than at n1 = 1. This contradiction is explained by the fact , that each claim received by the QS, which in the case of n1 = 0 occupies two
channel, leaves fewer free channels for the following customers, forcing them to create a larger queue than in the case
n1 = 1. At the same time, the group use of channels, reducing the service time, causes a decrease in the total number of serviced and pending requests. So, in the example under consideration, the daily average service time
for option n1 = 1 is 20 min., and for
option n1 = 0 - 11.7 min.
The model considered above makes it possible to solve problems related to the search for optimal management of the quality of transportation service. On fig. 3e, 3f show some results of solving this kind of problem, the meaning of which is explained below on the example of the considered airport.
Even during peak loads, the average queue length, which does not exceed 0.6 aircraft in the considered example (Fig. 3d), does not guarantee that the waiting time in the queue will be acceptable for the vast majority of aircraft. A small average waiting time with a satisfactory average time for performing a service operation
It also does not exclude the possibility of unacceptably long downtime for maintenance of individual aircraft. Consider an example when the quality of airport service is subject to requirements both in terms of ensuring satisfactory values of the service waiting time and in terms of the time spent in the system. We will assume that more than 90% of the aircraft should be idle for maintenance for less than 40 minutes, and the waiting time for maintenance for the same proportion of aircraft should be less than 5 minutes. Using the notation introduced above, these requirements for the quality of airport service can be written as inequalities:
P (Tpreb (t)< 40мин)>09, P (Iden (t)< 5мин)> 09
On fig. 3e, 3f show the time dependences of the probabilities P (Tpreb (/)< 40мин)
and P (also (")< 5 мин) для интервала времени
460-640 min. from the beginning of the model day corresponding to the second “wave” of arrivals.
As can be seen from the figures, the option n1 = 1 is not
provides the estimated service time reliability: the service time requirement given by the condition
P (Tpreb (t)< 40мин)>09 , is carried out only during a short period of 530560 minutes, corresponding to the arrivals of small
Sun. In turn, the option n1 = 0 does not provide the calculated reliability in terms of waiting time in the queue: during the interval of large aircraft arrivals (500-510 min.)
Rice. 3. Simulation results 262
the condition P is satisfied (Tozh (t)< 5мин) > 0.9.
As the simulation showed, the way out of this situation can be the choice
compromise option у1 » 0.2. In practice, this option means that the airport services should allocate two funds for servicing not all aircraft, but only those selected on a certain basis, for example,
passenger capacity. Here y1 plays a role
a parameter that allows you to control the performance of the QS: the waiting time for an application in the queue and the time the application stays in the QS or service time.
Thus, the system under consideration, which uses one or two channels simultaneously to service a request, is a particular, but practically significant, case of a QS with
mutual assistance of channels. The use of a dynamic model of such a QS allows one to set and solve various optimization, including multicriteria, tasks related to managing not only the total number of funds, but also their mutual assistance. Such tasks are especially relevant for hub airports, which are saturated with facilities, with their non-stationary flight flows and fluctuating service intensity. Thus, the model of the considered QS is a tool for analyzing and optimizing the parameters of such a promising class of airports as hubs.
Bibliographic list
1. Bocharov, P.P. Queuing theory [Text] / P.P. Bocharov, A.V. Pechinkin. - M.: Publishing House of RUDN University, 1995. - 529 p.
MODEL OF A QUEUEING SYSTEM WITH NON-STATIONARY STREAMS AND PARTIAL MUTUAL ASSISTANCE BETWEEN CHANNELS
© 2011 V. A. Romanenko
Samara State Aerospace University named after academician S. P. Korolyov (National Research University)
A dynamic model of multichannel queuing system with non-stationary streams, waiting in a limited-length queue and partial mutual assistance of channels expressed in the opportunity of simultaneous service of a customer by two channels is described. Expressions for the basic probability-time characteristics of the system are given. The results of modeling the functioning of a hub airport as an example of the system discussed are described.
Queueing system, non-stationary flow, mutual assistance between channels, hub airport.
Information about the author Romanenko Vladimir Alekseevich, Ph.D. Email: [email protected]. Research interests: optimization and modeling of the transportation service system of the hub airport.
Romanenko Vladimir Alexeevitch, candidate of technical sciences, associate professor, doctor's degree at the department of transportation organization and management, Samara State Aerospace University named after academician S. P Korolyov (National Research University). E-mail: vla_rom@mail . en. Area of research: optimization and simulation of a hub airport transportation service system.
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 queuing systems 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 application appears, all channels begin to serve it at once and remain busy until the service of this application 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 capacity of QS;
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 an increase in service efficiency: the time spent by an application in the QS decreases, but other service characteristics deteriorate.
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.
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.
Hence,
(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. Thus,
.
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 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.
.
Hence, 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 average 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.
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 claim 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., at the initial 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 A, 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 of QS with failures is average busy channels. IN 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
In the vast majority of cases, in practice, the queuing system is multichannel, that is, several applications can be served in parallel, and, therefore, ,
service channel models(where the number of service channels n>1) are of undoubted interest.
The queuing process described by this model is characterized by the intensity of the input flow λ, while no more than n clients (applications). The average duration of service of one application is equal to 1/μ. The mode of operation of one or another service channel does not affect the mode of operation of other service channels of the system, and the duration of the service procedure for each of the channels is random variable, fixed to the exponential distribution law. The ultimate goal of using service channels connected in parallel is to increase (compared to a single-channel system) the speed of servicing requirements by servicing simultaneously n clients.
The stationary solution of the system has the form:
;
Where, .
Formulas for calculating probabilities are called Erlang formulas.
Let us determine the probabilistic characteristics of the functioning of a multichannel QS with failures in a stationary mode:
failure probability:
.
since the application is rejected if it arrives at a time when all channels are busy. Value R otk characterizes the completeness of service of the incoming flow;
the probability that the application will be accepted for service(it is also the relative throughput of the system) complements R otk up to one:
.
absolute bandwidth
average number of channels occupied by service() the following:
The value characterizes the degree of loading of the QS.
Example. Let n-channel QS is a computer center (CC) with three ( n=3) interchangeable PCs for solving incoming tasks. The flow of tasks arriving at the CC has an intensity of λ=1 task per hour. The average duration of service t about =1.8 hours.
It is required to calculate the values:
- probabilities of the number of busy CC channels;
- the probability of refusal to service the application;
- relative capacity of the CC;
- absolute capacity of CC;
- the average number of employed PCs at the CC.
Determine how much additional PC you need to purchase in order to increase the throughput of the computer center by 2 times.
Solution.
Let us define the parameter μ of the service flow:
.
The reduced intensity of the flow of applications
.
We find the limiting probabilities of states using the Erlang formulas:
The probability of refusal to service the application
.
Relative throughput of VC
.
Absolute throughput of CC:
.
Average number of busy channels - PC
Thus, in the established mode of operation of the QS, on average, 1.5 computers out of three will be occupied - the remaining one and a half will be idle. The work of the considered CC can hardly be considered satisfactory, since the center does not serve applications on average in 18% of cases (Р 3 = 0.180). It is obvious that the capacity of the computer center for given λ and μ can only be increased by increasing the number of PCs.
Let us determine how much it is necessary to use a PC in order to reduce the number of unserved requests arriving at the CC by 10 times, i.e. so that the probability of failure in solving problems does not exceed 0.0180. To do this, we use the formula for the probability of failure:
Let's make the following table:
| n | ||||||
| P 0 | 0,357 | 0,226 | 0,186 | 0,172 | 0,167 | 0,166 |
| P open | 0,673 | 0,367 | 0,18 | 0,075 | 0,026 | 0,0078 |
Analyzing the data in the table, it should be noted that the expansion of the number of CC channels for the given values of λ and μ to 6 PC units will ensure the satisfaction of applications for solving problems by 99.22%, since with n= 6 probability of denial of service ( R otk) is 0.0078.