Smo with failures and partial mutual assistance. QS with failures and full mutual assistance for mass 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 multi-channel queuing system 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 service of an application by two channels, is described. 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 of the model
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 of Kolmogorov differential equations, which can be written in general form 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 the 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(r-2)(.-r) ().
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 time 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 at the final stage to 15 minutes. 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 further 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: [email protected].ru. Area of research: optimization and simulation of a hub airport transportation service system.
System of equations
QS with failures for a random number of serving flows is a vector model for Poisson flows. Graph, system of equations.
Let us represent QS 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.
If the request is accepted for service and the system goes into a state with intensity λ m.
Upon completion of servicing one of the requests, 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.
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 μ.
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 characteristics are determined.
QS with an infinite queue for Poisson flows. Graph, system of equations, calculated ratios.
System Graph
System of equations
Where n– number of service channels, l– number of mutually assisting channels
QS with an infinite queue and partial mutual assistance for arbitrary flows. Graph, system of equations, calculated ratios.
System Graph
System of equations
–λ R 0 + nμ R 1 =0,
.………………
–(λ + nμ) P k+ λ P k –1 + nμ P k +1 =0 (k = 1,2, ... , n–1),
……………....
-(λ+ nμ) P n+ λ P n –1 + nμ P n+1=0,
……………….
-(λ+ nμ) Pn+j+ λ Р n+j –1 + nμ Р n+j+1=0, j=(1,2,….,∞)
QS with an infinite queue and complete mutual assistance for arbitrary flows. Graph, system of equations, calculated ratios.
System Graph
|
System of equations
QS with a finite queue for Poisson flows. Graph, system of equations, calculated ratios.
System Graph
System of equations
Design ratios:
,
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 a random variable governed by an 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 stream;
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.
| 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. | |||||||||||
| Queue | 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 | No 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.
IN 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.
IN 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 mainly depend 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 objectives of the study, can be characterized by a large number of different 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 of economic efficiency of 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 V
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 .
