Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$
For finite capacity queueing systems of the type M θ/G/1, the convenient formulas for the ergodic distribution of a queue length are obtained. An estimate of a rate of convergence of the distribution of queue length in the trasient regime to the ergodic distribution is obtained and computational al...
Gespeichert in:
| Datum: | 2007 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2007
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/3380 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509460024262656 |
|---|---|
| author | Bratiychuk, A. M. Братійчук, А. М. |
| author_facet | Bratiychuk, A. M. Братійчук, А. М. |
| author_sort | Bratiychuk, A. M. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:52:51Z |
| description | For finite capacity queueing systems of the type M θ/G/1, the convenient formulas for the ergodic distribution of a queue length are obtained.
An estimate of a rate of convergence of the distribution of queue length in the trasient regime to the ergodic distribution is obtained and computational algorithms for finding the convergence rate are presented.
|
| first_indexed | 2026-03-24T02:41:27Z |
| format | Article |
| fulltext |
UDK 519.21
A. M. Bratijçuk (Ky]v. nac. un-t im. T.�Íevçenka)
ÍVYDKIST| ZBIÛNOSTI DO ERHODYÇNOHO ROZPODILU
DOVÛYNY ÇERHY V SYSTEMAX TYPU M G Nθθ/ / /1
For finite capacity queueing systems of the type M Gθ / /1, the convenient formulas for the ergodic
distribution of a queue length are obtained. An estimate of a rate of convergence of the distribution of
queue length in the trasient regime to the ergodic distribution is obtained and computational algorithms
for finding the convergence rate are presented.
Dlq system obsluΩyvanyq typa M Gθ / /1 s ohranyçennoj oçered\g najden¥ udobn¥e formu-
l¥ dlq πrhodyçeskoho raspredelenyq dlyn¥ oçeredy, poluçena ocenka skorosty sxodymosty
raspredelenyq dlyn¥ oçeredy v perexodnom reΩyme k πrhodyçeskomu, a takΩe pryveden¥ v¥-
çyslytel\n¥e alhorytm¥ dlq naxoΩdenyq skorosty sxodymosty.
1. Vstup. U statti rozhlqdagt\sq systemy obsluhovuvannq typu M Gθ / /1 z
obmeΩenog çerhog, qki formal\no moΩna opysaty takym çynom. Zamovlennq
nadxodqt\ hrupamy zhidno z puassonivs\kym procesom z parametrom λ , rozmir
n-] hrupy θn ne zaleΩyt\ vid momentu nadxodΩennq i P{ }θn i= = ai , i = 1,
2, … . Zamovlennq obsluhovugt\sq po çerzi, i obsluhovane zamovlennq zalyßa[
systemu, a obsluhovugçyj prystrij vidrazu rozpoçyna[ obsluhovuvannq z çerhy,
qkwo vona [, v protyvnomu razi çeka[ na nadxodΩennq çerhovo] hrupy zamovlen\.
Dyscyplina obsluhovuvannq [ FIFO, i çerha vseredyni odni[] hrupy zamovlen\
moΩe buty orhanizovana dovil\nym sposobom, oskil\ky xarakterystyky, qki my
vyvça[mo v cij roboti (dovΩyna çerhy ta period zajnqtosti), ne budut\ zaleΩaty
vid sposobu ]] orhanizaci].
Nexaj ξ ( t ) — kil\kist\ zamovlen\ u systemi v moment çasu t ; τ1 — dovΩyna
perßoho periodu zajnqtosti.
Neskladno dovesty fakt isnuvannq πk
df
= lim ( ){ }t t k→∞ =P ξ , 0 ≤ k ≤ N ,
qkyj, faktyçno, [ naslidkom skinçennosti çerhy. V bil\ßosti robit, prysvqçe-
nyx takym systemam, holovnu uvahu zoseredΩeno na alhorytmax obçyslennq er-
hodyçnoho rozpodilu πk , k = 0, … , N. Taki alhorytmy moΩna znajty v [1]. Na
dumku avtora, holovnym nedolikom cyx alhorytmiv [ ta obstavyna, wo koly, na-
pryklad, obçyslyvßy erhodyçnyj rozpodil dlq deqkoho N, namahagt\sq
obçyslyty joho dlq N + 1 (a taka neobxidnist\ vynyka[, qkwo vyvçagt\sq prob-
lemy optymizaci] i dovΩyna çerhy [ parametrom keruvannq), to, po-perße, bahato
z parametriv alhorytmu potribno pereobçyslyty zanovo, oskil\ky vony [
funkci[g N, a po-druhe, dlq obçyslennq, skaΩimo, π1 potribno znaty πk , 1 <
< k ≤ N + 1 (u vsqkomu razi v alhorytmax, qki navedeno v [1]). Ce vymaha[ vely-
ko] kil\kosti obçyslen\ navit\ dlq vidnosno nevelykyx N. Taki alhorytmy bu-
demo nazyvaty „nezruçnymy”. Pryklad takoho alhorytmu z [1] my navedemo nyΩ-
çe. Isnu[ we odna problema, pov’qzana z rozpodilom πk , k = 1, … , N. Na prak-
tyci nas çasto cikavyt\ qk ßvydko myna[ perexidnyj reΩym systemy z tym, wob
korystuvatys\ erhodyçnym rozpodilom πk , k = 1, … , N . Ocinky typu
π ξk t k− =P{ }( ) = O t( )−α
z deqkym α > 0, qki moΩna otrymaty dosyt\ leh-
ko, [ maloprydatnymy, oskil\ky ne dagt\ vidpovidi na postavlene pytannq. Nam
potribna ocinka typu π ξk t k− =P{ }( ) ≤ Ct−α
z toçnym znaçennqm stalo] C,
obçyslennq qko] vymahalo b lyße informaci] pro parametry systemy. Taki
ocinky budemo nazyvaty „toçnymy”. Nam nevidomi taki ocinky. Tomu pytannq, na
qki my xoçemo daty vidpovid\ u statti, moΩna sformulgvaty tak.
1. Znajty „zruçni” alhorytmy dlq obçyslennq erhodyçnoho rozpodilu.
© A. M. BRATIJÇUK, 2007
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9 1169
1170 A. M. BRATIJÇUK
2. Znajty „toçni” ocinky dlq ßvydkosti zbiΩnosti do erhodyçnoho rozpo-
dilu.
Stattq pobudovana takym çynom. U p.�2 navedeno deqki dopomiΩni rezul\ta-
ty, dovedennq qkyx moΩna znajty v [2, 3]. U p.�3 dovedeno erhodyçnu teoremu i
otrymano „zruçni” formuly dlq erhodyçnoho rozpodilu dovΩyny çerhy, a v na-
stupnomu punkti vstanovleno „toçni” ocinky dlq ßvydkosti zbiΩnosti v cij teo-
remi. V ostann\omu punkti navedeno alhorytmy dlq obçyslennq velyçyn, qki
vykorystovugt\sq pry ocinci ßvydkosti zbiΩnosti v erhodyçnij teoremi.
2. Poznaçennq. DopomiΩni rezul\taty. Dlq Re s > 0 , z ≤ 1 poznaçymo
f ( s ) = e dF xsx−
∞
∫ ( )
0
, θ ( z ) =
l
l
lz a
=
∞
∑
1
, an =
i n
ia
=
∞
∑ , mi = x dF xi ( )
0
∞
∫ .
Symvoly En , Pn poznaçagt\ vidpovidno umovne matematyçne spodivannq ta
umovnu jmovirnist\ pry umovi ξ ( 0 ) = n , a bi
k∗, i = 0, 1, 2, … , — k-kratna
zhortka poslidovnosti bi, i = 0, 1, 2, … .
Nexaj poslidovnosti p si( ) , q si( ) , Re s ≥ 0 , zadagt\sq spivvidnoßennqmy
i
i
iz p s
= −
∞
∑
1
( ) =
f s z
z f s
+ −( )λ θ( ( ))
( )
1
,
i
i
iz q s
=
∞
∑
0
( ) =
1 1
1
− + −( )
+ −( )
f s z
f s s z
λ θ
λ θ
( ( ))
( ) ( ( ))
.
Oçevydno, wo p si( ) , s ≥ 0 , moΩna interpretuvaty qk rozpodil strybkiv deqko-
ho neperervnoho znyzu vypadkovoho blukannq. Nexaj R sk ( ), k = 1, 2, … , [ re-
zol\ventog c\oho blukannq, qka zada[t\sq spivvidnoßennqm
k
k
kz R s
=
∞
∑
1
( ) = z f s f s z z( ) ( ( ))+ −( ) −( )−λ θ1 1 (1)
dlq dostatn\o malyx z .
Poznaçymo
gn ( s, k, N )
df
= I n k N q s I k N q sk n
i N n
i{ } { }( ) ( )≤ < + =−
= −
∞
∑ ,
Qn ( N, s ) =
f s f s R s
f s f s R s
ll
N n
ll
N
( ) ( ( )) ( )
( ) ( ( )) ( )
+ −
+ −
=
− −
=
−
∑
∑
1
1
1
1
1
1 ,
a operator Q ( µ, ν, f ) dlq poslidovnosti fl , l = 0, 1, … , oznaçymo tak:
Q ( µ, ν, f ) =
l
N
l l
l
N
i
l i
N
l i lR f a R f
=
−
=
−
= +
−
−∑ ∑ ∑−
1
1
0
1
1
1
( ) ( )µ ν µ .
U roboti [3] dlq sumisnoho rozpodilu dovΩyny çerhy ta perßoho periodu zajnq-
tosti otrymano zobraΩennq
0
∞
−∫ = >e t k t dtst
nP { }( ) ,ξ τ =
= Q N s R s g s k N R s g s k Nn
l
N
l l
l n
N
l n l( , ) ( ) ( , , ) ( ) ( , , )
=
−
= +
−
−∑ ∑−
1
1
1
1
(2)
dlq 1 ≤ n ≤ N – 1 i
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
ÍVYDKIST| ZBIÛNOSTI DO ERHODYÇNOHO ROZPODILU DOVÛYNY ÇERHY … 1171
0
∞
−∫ = ≥e t k t dtst
NP { }( ) ,ξ τ =
=
f s R s g s k N
f s f s R s
I k N
f s
s
l ll
N
ll
N
2
1
1
1
1
1
1( ) ( ) ( , , )
( ) ( ( )) ( )
( ){ }=
−
=
−
∑
∑+ −
+ = −
. (3)
Zvidsy otrymu[mo takyj rezul\tat.
Naslidok11. Dlq periodu zajnqtosti spravedlyvymy [ zobraΩennq
En
se− τ =
f s f s R s
f s f s R s
ll
N n
ll
N
( ) ( ( )) ( )
( ) ( ( )) ( )
+ −
+ −
=
− −
=
−
∑
∑
1
1
1
1
1
1 (4)
dlq 1 ≤ n ≤ N – 1 i
EN
se− τ =
f s
f s f s R sll
N
2
1
1
1
( )
( ) ( ( )) ( )+ − =
−∑
. (5)
Dlq dovΩyny çerhy v dovil\nyj moment çasu ma[mo
0
∞
−∫ =e t k dtst
NP { }( )ξ =
=
( ) ( , , ) ( ( ))
( ( )) ( ) ( , , ) ( ) ( )
{ } { }λ θ λ
λ θ λ
+ + = − + =
− + +( ) +
−s Q s g I k N a f s s I k
f s s Q s f s a sf s
N
N
1 0
1 1
1
×
× f s f s R s R s g s k Nl
l
N n
l n
N
l n l( ) ( ( )) ( ) ( ) ( , , )+ −
−
=
− −
= +
−
−∑ ∑1
1
1
1
1
, (6)
de θ = λ λ( )+ −s 1, a 1 poznaça[ poslidovnist\, totoΩno rivnu 1.
3. Erhodyçnyj rozpodil dovΩyny çerhy. Rozhlqnemo pytannq pro erho-
dyçnyj rozpodil dovΩyny çerhy. Isnuvannq c\oho rozpodilu vyplyva[ z faktu
obmeΩenosti çerhy, ale my dovedemo ce, vykorystovugçy teorig vidnovlennq,
oskil\ky ce dozvolyt\ otrymaty deqki zobraΩennq, potribni v podal\ßomu. Ot-
Ωe, nexaj systema poçyna[ pracgvaty v moment nadxodΩennq perßo] hrupy za-
movlen\. Vid c\oho momentu rozpoçyna[t\sq vidlik çasu. Perßyj period zajnq-
tosti tako] systemy my poznaçyly τ1 . Todi z formul (4), (5) otrymu[mo
Ee s− τ1 =
f s a f s a R s f s a
f s f s R s
nn
N
nn
N
ll
N n
N
ll
N
( )) ( ( )) ( ) ( )
( ) ( ( )) ( )
=
−
=
−
=
− −
=
−
∑ ∑ ∑
∑
+ − +
+ −
1
1
1
1
1
1 2
1
1
1
1
. (7)
Poznaçymo çerez τi , i = 1, 2, … , momenty zvil\nennq systemy vid zamovlen\, a
çerez ξi intervaly prostog systemy pislq momentiv τi do nadxodΩennq çerho-
vo] hrupy zamovlen\. Zrozumilo, wo ξ i — pokaznykovo rozpodileni vypadkovi
velyçyny z parametrom λ i momenty ξ τi i+ utvorggt\ proces vidnovlennq.
Poznaçymo çerez H ( x ) funkcig vidnovlennq, qka vidpovida[ c\omu procesu,
tobto H ( x ) = Φ∗
=
∞∑ i
i
x( )
0
, de Φ ( x ) = P{ }τ ξ1 1+ < x . Ma[mo
P{ }( )ξ t k= = P P{ } ( )( ) , ( ) ( )ξ τ ξt k t t u k d u
t
= ≥ + − =∫1
0
Φ , 0 < k ≤ N .
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
1172 A. M. BRATIJÇUK
Zvidsy
P{ }( )ξ t k= =
0
1
t
t u k t u d H u∫ − = ≥ −P{ }( ) , ( )ξ τ , 0 < k ≤ N . (8)
Analohiçno
P{ }( )ξ t = 0 =
0
1 1 1
t
t u t u d H u∫ < − + ≥ −P{ }, ( )τ τ ξ . (9)
Z (8), (9) ta teoremy vidnovlennq otrymu[mo taku teoremu.
Teorema11. Magt\ misce spivvidnoßennq
πk = lim ( ){ }
t
t k
→∞
=P ξ =
λ
λ τ
ξ τ
E
P
1 0
11+
= ≥
∞
∫ { }( ) ,v v vk d , 0 < k ≤ N , (10)
π0 = lim ( ){ }
t
t
→∞
=P ξ 0 = λ
λ τ
τ τ ξ
E
P
1 0
1 1 11+
< + ≥
∞
∫ { },v v vd . (11)
Z formul (2), (3) otrymu[mo
0
1
∞
∫ = ≥P{ }( ) ,ξ τv v vk d = R g k N a R g k Nl l
l
N
n
n
N
l n l
l n
N
( , ) ( , )
=
−
=
−
−
= +
−
∑ ∑ ∑−
1
1
1
1
1
1
+
+ a m I k NN 1 { }= ,
de
gn ( k , N ) = I n k N q I k N qk n
i N n
i{ } { }≤ < + =−
= −
∞
∑ ,
a poslidovnist\ gl zada[t\sq spivvidnoßennqm
z qi
i
i =
∞
∑
0
=
1 1
1
− −( )
−
f z
z
λ θ
λ θ
( ( ))
( ( ))
. (12)
Poslidovnist\ Rl = lim ( )s lR s→0 , l = 1, 2, … , dlq dostatn\o malyx z zada[t\-
sq rivnistg
z Rk
k
k =
∞
∑
1
= z f z zλ θ( ( ))1 1−( ) −( )− . (13)
Cg poslidovnist\ budemo interpretuvaty (za terminolohi[g monohrafi] [2]) qk
potencial deqkoho reßitçastoho blukannq, neperervnoho znyzu. Ce blukannq
vyznaça[t\sq tvirnog funkci[g
f z
z
λ θ( ( ))1 −( )
= z pi
i
i
( )λ
= −
∞
∑
1
, (14)
de, qk lehko zrozumity,
p i( )λ =
k
t
k
i
ke
t
k
a dF t
=
∞ ∞
−
+
∗∑ ∫
0 0
1
λ λ( )
!
( ) , i ≥ – 1.
Z formuly (7) otrymu[mo
E τ1 = m R a R an
n
N
n
n
N
l
l
N n
N
=
−
=
−
=
− −
∑ ∑ ∑− −
1
1
1
1
1
1
,
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
ÍVYDKIST| ZBIÛNOSTI DO ERHODYÇNOHO ROZPODILU DOVÛYNY ÇERHY … 1173
i tomu z (10), (11) ta rivnosti
0
1 1 1
∞
∫ < + >P{ },τ τ ξv v vd = 1/ λ ,
qka [ naslidkom toho, wo pokaznykovyj rozklad ma[ vlastyvist\ vidsutnosti
pam’qti, oderΩu[mo takyj rezul\tat.
Teorema12. Dlq erhodyçnoho rozpodilu dovΩyny çerhy v systemi M G Nθ / / /1
spravedlyvymy [ nastupni zobraΩennq:
πk =
R g k N a R g k N a mI k N
m R a R a
l ll
N
nn
N
l n ll n
N
N
nn
N
nn
N
ll
N n
N
( , ) ( , ) { }=
−
=
−
−= +
−
=
−
=
−
=
− −
∑ ∑ ∑
∑ ∑ ∑
− + =
+ − −( )
1
1
1
1
1
1
1
1
1
1
1
1
1 λ
(15)
dlq 0 < k ≤ N i
π0 = 1
1
1
1
1
1
1
1+ − +( )=
−
=
−
=
− −∑ ∑ ∑λm R a R ann
N
nn
N
ll
N n
N
. (16)
Ci Ω sami formuly moΩna otrymaty z (6), vykorystavßy tauberovu teoremu.
Formuly, navedeni vywe, moΩna efektyvno vykorystaty dlq znaxodΩennq
erhodyçnoho rozpodilu. Dlq toho wob poqsnyty, wo my rozumi[mo pid efektyv-
nistg, navedemo odyn rezul\tat z [1] wodo erhodyçnoho rozkladu dovΩyny çer-
hy, ale v systemi typu M G N/ / /1 (tobto bez hrupovyx nadxodΩen\ zamovlen\),
a same alhorytm dlq obçyslennq erhodyçnoho rozpodilu.
Poznaçymo
ak =
0
∞
−∫ ( )
!
( )
λ λx
k
e dF x
k
x , ak =
j k
ja
=
∞
∑
i vyznaçymo ′γ k , 0 ≤ k ≤ N – 1 , za dopomohog rekurentnyx spivvidnoßen\
′γ 0 = 1,
(17)
′ +γ k 1 = a a ak
j
k
j k j k0
1
1
1
−
=
− +′ − ′ −
∑γ γ , 0 ≤ k ≤ N – 2 .
Nexaj
γ k = ′ ′
=
−
∑γ γk
j
N
j
0
1
, ρ =
k
ka
=
∞
∑
1
, ρ′ =
ρ
γ ρ0 +
.
Todi
π0 =
γ
γ ρ
0
0 +
, πk =
′ +
=
− +∑ρ
ρ
γ γ0
1
1a ak
j
k
j k j , 1 ≤ k ≤ N – 1 ,
πN =
′ +
=
∞
=
−
= − +
∑ ∑ ∑ρ
ρ
γ γ0
1
1
1k N
k
j
N
j
k N j
k
ka a .
Z navedenyx formul vyplyva[, wo koly my zming[mo parametr N (maksymal\na
[mnist\ çerhy), to koΩen raz povynni povtoryty alhorytm (17), oskil\ky dopo-
miΩni velyçyny ′γ k [ funkci[g N. Krim toho, wob znajty, napryklad, π 1 pry
N = 100, neobxidno znajty vsi ′γ k , 0 ≤ k ≤ 99 . Ce pryvodyt\ do velyko] kil\-
kosti obçyslen\. My pokaΩemo qk z formul (15), (16) moΩna otrymaty alho-
rytm, pozbavlenyj cyx nedolikiv.
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
1174 A. M. BRATIJÇUK
Nasampered zapyßemo alhorytmy dlq obçyslennq poslidovnostej Ri
, qi , i ≥
≥ 1. ZauvaΩymo, wo ci alhorytmy ne zaleΩat\ vid parametra N i, otΩe, mo-
Ωut\ buty obçysleni lyße na pidstavi informaci] pro vxidnyj potik ta rozpodil
çasu obsluhovuvannq.
Rekurentne spivvidnoßennq
Rk+1 = p I k R p Rk
n
k
n k n1
1
0
0−
=
−= + −
∑{ } , R0 = 0, k ≥ 0,
bezposeredn\o otrymu[mo z rivnostej (13), (14). Z rivnosti (12) ma[mo
qk = 1
0 0
1
0λ
λ
i
k
i
j
k
j
i
k j
ia p a
=
∞
∗
=
−
=
∞
−
∗∑ ∑ ∑−
( ) , k ≥ 1.
4. Ocinky dlq ßvydkosti zbiΩnosti. Dlq ocinky ßvydkosti zbiΩnosti v
teoremi�2 potribnyj rezul\tat z [4]. Wob joho sformulgvaty, rozhlqnemo riv-
nqnnq vidnovlennq
x ( t ) = y t x t u dQ u
t
( ) ( ) ( )+ −∫
0
, (18)
de Q ( u ) — funkciq rozpodilu na [ 0, ∞ ) , a funkciq y ( t ) [ bezposeredn\o
intehrovnog za Rimanom na [ 0, ∞ ) . Qkwo H ( t ) — funkciq vidnovlennq, wo po-
rodΩena Q ( u ) , to rivnqnnq (18) ma[ [dynyj obmeΩenyj rozv’qzok, qkyj moΩna
zapysaty u vyhlqdi
x ( t ) =
0
t
y t u dH u∫ −( ) ( ),
i qkwo q = t dQ t( )
0
∞
∫ , to
x
df= lim ( )
t
x t
→∞
= q y t dt−
∞
∫1
0
( ) .
Prypustymo, wo rozpodil Q ( u ) ma[ vyhlqd
Q ( t ) =
0
1
t
t ue dL u∫ −( )− +λ( ) ( ), (19)
de L ( u ) — deqkyj rozpodil na [ 0, ∞ ) , λ > 0. Spivvidnoßennq (19) [ ekvi-
valentnym tomu, wo O ( t ) ma[ nezaleΩnu pokaznykovu komponentu z paramet-
rom λ . Poznaçymo
R ( t ) = λ( ( )) ( )1 − −Q t q t , µ =
0
2
∞
∫ t dQ t( ) ,
de q ( t ) — wil\nist\ rozpodilu Q ( t ) . Z (19) vyplyva[, wo R ( t ) ≥ 0, t ≥ 0.
Teorema13 [4]. Nexaj:
1) t dQ tα+∞
∫ 1
0
( ) < ∞ dlq deqkoho α > 1;
2) sup ( ) ( )t t y t≥
++0
11 α < ∞ .
Todi dlq vsix t ≥ ( )αε0
1−
ma[mo
x t x( ) − <
C
t
( )
( )
ε
ε α
0
01 +
,
de
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
ÍVYDKIST| ZBIÛNOSTI DO ERHODYÇNOHO ROZPODILU DOVÛYNY ÇERHY … 1175
C( )ε0 =
2 1
1 10
0 0
0
1( ) ( )
sup ( ) ( ) ( ( ))
+ + + − −
≥
+α ε α λ
λµαε
ε
λµ
αe
t y t x Q t
t
,
a ε0 — [dynyj korin\ rivnqnnq
0 0
1
∞
∫ ∫+ −
( ) ( ) exp ( )ε αt R t R u du dt
t
= 1.
Vykorysta[mo cg teoremu dlq toho, wob ocinyty ßvydkist\ zbiΩnosti v teo-
remi�1.
Poznaçymo
D ( t ) = λ( ( )) ( )1 − −Φ t b t , W ( t ) = D t D s ds
t
( ) exp ( )−
∫
0
,
de b ( t ) — wil\nist\ rozpodilu Φ ( t ) , i nexaj η1 = τ ξ1 1+ , de, nahada[mo, τ1
— perßyj period zajnqtosti, a ξ1 — perßyj period prostog systemy. NevaΩ-
ko perekonatys\, wo dlq dovil\noho natural\noho n vykonu[t\sq rivnist\
E η1
n =
i
n
n i
ii i n
n i=
−∑ + + …
−0
1
1 2( )( )
( )λ
τE .
Spravedlyvog [ nastupna teorema.
Teorema14. Nexaj t dF tp +∞
∫ 1
0
( ) < ∞ dlq deqkoho natural\noho p > 1.
Todi dlq vsix t ≥ ( )2 0
1ε −
i 0 ≤ k ≤ N vykonu[t\sq nerivnist\
P{ }( )ξ πt k k= − ≤
2 1 1 1
1
2
0 0
1
2
0 0
1
2p p p
p
p p e
p t
+ + +
+
( )( ) max( , )
( )
ε λ ε η
λ η ε ε
λ ηE E
E
, (20)
de ε0 — [dynyj korin\ rivnqnnq
i
p
i
p
i iC t W t dt e
=
∞
−∑ ∫ −
1 0
1ε λ τ( ) E = 0. (21)
Dovedennq. U danomu vypadku zamist\ Q ( t ) , y ( t ) my ma[mo vidpovidno
Φ ( t ) ta P{ }( ) ,ξ τt k t= ≥1 abo P{ },τ η1 1< ≥t t . Toj fakt, wo rozpodil
Φ ( t ) ma[ nezaleΩnu pokaznykovu komponentu z parametrom λ , [ oçevydnym,
oskil\ky momenty nadxodΩennq zamovlen\ utvorggt\ puassonivs\kyj proces.
U c\omu vypadku velyçyna τ1 ma[ vsi momenty ≤ p + 1. Cej fakt bezposeredn\o
vyplyva[ iz zobraΩennq (10) i [ naslidkom toho, wo çerha v systemi obmeΩena.
Vypadkova velyçyna ξ1 (pokaznykovo rozpodilena) ma[ vsi momenty. Tomu, vy-
korystovugçy nerivnist\ Çebyßova, nevaΩko pokazaty, wo vykonugt\sq umovy
teoremy�3. Ma[mo
sup ( ) ,{ } { }
t
p
kt t t t
≥
+ < ≥ − ≥
0
1 1 11 ε τ η π ηP P ≤ 2 1
0
1sup ( ) { }
t
pt t
≥
+ ≥ε ηP ≤
≤ 2 1 1
0 1 1
1max sup ( ) , sup ( ) { }
≤ ≤ ≥
+ + ≥
t
p
t
pt t t
ε ε
ε ε ηP ≤
≤ 2 2 11
1
1max , sup ( ( ) )p p p
t
ptε η ε
ε
E
≥
−+
≤ 2 11
1
p p p+ ( )max , ε ηE .
Cq rivnist\, teorema��3 ta formula (8) dagt\ ocinku (20) dlq 0 < k ≤ N . Dlq
k = 0 dovedennq [ analohiçnym, lyße zamist\ (8) potribno vykorystaty (9).
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
1176 A. M. BRATIJÇUK
Dlq toho wob znajty ε0 z (21), faktyçno, potribno znajty funkcig Φ ( x ) ,
vykorystavßy (7). Cq zadaça [ dosyt\ skladnog, i tomu baΩano znajty bil\ß
zruçnyj alhorytm dlq obçyslennq pravo] çastyny nerivnosti (20). Prypustymo,
wo my znajßly promiΩok [ ε1, ε2 ] takyj, wo 0 < ε1 ≤ ε0 ≤ ε2 < ∞ , i dlq ε1, ε2
vdalosq znajty zruçnißi obçyslgval\ni alhorytmy. Todi, zaminyvßy v znamen-
nyku (20) ε0 na ε1
, a v çysel\nyku ε0 na ε2
, my dosqhnemo postavleno] mety.
Dlq realizaci] ci[] ide] zauvaΩymo, wo oskil\ky koefici[nty pry ε
i
v (21) [ do-
datnymy, to dodatnyj korin\ rivnqnnq (21) znaxodyt\sq miΩ dodatnymy korenq-
my dvox rivnqn\
i
p
i
p
i iC t D t dt
=
∞
∑ ∫
1 0
ε ( ) = e−λ τE 1 ,
i
p
i
p
i iC t D t dt
=
∞
∑ ∫
1 0
ε ( ) = 1. (22)
NevaΩko perekonatys\, wo
0
∞
∫ t D t dti ( ) =
λ τE 1
1
1
i
i
+
+
.
Tomu rivnqnnq (22) moΩemo perepysaty takym çynom:
i
p
i
p
i iC
=
+
+ +∑
1
1
1
1
1ε τE = λ λ τ− −+1 1 1( )p e E , (23)
i
p
i
p
i iC
=
+
+ +∑
1
1
1
1
1ε τE = λ− +1 1( )p . (24)
OtΩe, my ma[mo nastupnyj rezul\tat.
Teorema15. Nexaj t dF tp +∞
∫ 1
0
( ) < ∞ dlq deqkoho natural\noho p > 1.
Todi dlq vsix t ≥ ( )2 1
1ε −
i 0 ≤ k ≤ N vykonu[t\sq nerivnist\
P{ }( )ξ πt k k= − ≤
2 1 1 1
1
2
2 2
1
2
1 1
1
2p p p
p
p p e
p t
+ + +
+
( )( ) max( , )
( )
ε λ ε η
λ η ε ε
λ ηE E
E
,
de ε1 ta ε2 [ [dynymy dodatnymy korenqmy vidpovidno rivnqn\ (23) ta (24).
Dlq vypadku p = 2 ma[mo takyj rezul\tat.
Naslidok12. Nexaj t dF t3
0
( )
∞
∫ < ∞ . Todi dlq vsix t ≥ ( )2 1
1ε −
i 0 ≤ k ≤
≤ N ma[ misce nerivnist\
P{ }( )ξ πt k k= − ≤
48 2 1 1
1
1
2
2 2
3 3
1
2
1 1
2
e
t
λ η ε λ ε η
λ η ε ε
E E
E
( ) max( , )
( )
+
+
,
de
ε1 =
9 12 3
2
1
2 2 1
1
3
1 1
2
1
3
( ) exp( )E E E E
E
τ λ τ λ τ τ
τ
+ − −−
,
ε2 =
9 12 3
2
1
2 2 1
1
3
1
2
1
3
( )E E E
E
τ λ τ τ
τ
+ −−
,
Eη1
3 = E E Eτ λ τ λ τ λ1
3 1
1
2 2
1
33 3 2+ + +− − − ,
Eη1
2 = E Eτ λ τ λ1
2 1
1
22+ +− − .
U nastupnomu punkti my navedemo alhorytm dlq obçyslennq momentiv per-
ßoho periodu zajnqtosti.
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
ÍVYDKIST| ZBIÛNOSTI DO ERHODYÇNOHO ROZPODILU DOVÛYNY ÇERHY … 1177
5. Momenty dlq periodu zajnqtosti. Dlq toho wob otrymaty zobraΩennq
dlq E τ1
n
, potribno zdyferencigvaty (7) po s vidpovidnu kil\kist\ raziv, a
potim perejty do hranyci pry s → 0 . Ale takyj pidxid pryzvede do duΩe
hromizdkyx formul, i tomu my skorysta[mos\ inßym metodom. Dlq c\oho
perepyßemo (7) u vyhlqdi
f s f s R s e
l
N
l
s( ) ( ( )) ( )+ −
=
−
−∑1
1
1
1E τ =
= f s a f s a f s a R s
n
N
n N
n
N
n
l
N n
l( ) ( ) ( ( )) ( )
=
−
=
−
=
− −
∑ ∑ ∑+ + −
1
1
2
1
1
1
1
1 .
Zdyferencigvavßy cg formulu k raziv po s, otryma[mo
i
k
i
k
i i s k i
k j
j
j
k i
j
l
k i j
l
N
C e f s C f s R s
=
− −
−
=
−
− −
=
−
∑ ∑ ∑− −
0
1
1 1
1
1 1( ) ( ) ( ) ( )( ) ( ) ( )E τ τ +
+ ( ( )) ( )( )1
1
1
−
=
−
−∑f s R s
l
N
l
k i =
= f s a C f s a R sk
n
N
n k
i
i
k
i
n
N
n
l
N n
l
k i( ) ( ) ( )( ) ( ) ( )
=
−
= =
−
=
− −
−∑ ∑ ∑ ∑−
1
1
1 1
1
1
1
+
+ ( ( )) ( ) ( ) ( )( ) ( ) ( )1
1
1
1
1
0
− +
=
−
=
+ −
=
−∑ ∑ ∑f s a R s C f s f s a
n
N
n
l
N n
l
k
k
i
i
k
i k i
N .
Oskil\ky f i( )( )0 = ( )−1 i
im = ( ) ( )−
∞
∫1
0
i ix dF x , to, pidstavyvßy v cg formulu
s = 0 , budemo maty
i
k
i
k
i i k i
k i k j
j
j
k i
j
j l
k i j
l
N
C m C m R
=
−
− −
=
−
− −
=
−
∑ ∑ ∑− − − −
0
1
1 1
1
1 1 1 0( ) ( ) ( ) ( )( )E τ =
= ( ) ( ) ( )( )− − −
=
−
= =
−
−
=
− −
∑ ∑ ∑ ∑1 1 0
1
1
1 1
1
1
1
k
k n
n
N
i
k
k
i i
i n
n
N
l
k i
l
N n
m a C m a R +
+ ( )−
=
−∑1
0
k
N
i
k
k
i
i k ia C m m .
Zvidsy oderΩu[mo formulu dlq rekurentnoho obçyslennq momentiv periodu
zajnqtosti
E τ1
k =
i
k
k
i i j k
k j
j
j
k i
j l
k i j
k i
l
N
C C m R m
=
−
+
−
=
−
− −
−
=
−
∑ ∑ ∑− −
0
1
1
1 1
1
1 0E τ ( ) ( )( )
+
+ m a C m a Rk n
n
N
i
k
k
i i k
i n
n
N
l
k i
l
N n
=
−
=
+
=
−
−
=
− −
∑ ∑ ∑ ∑− −
1
1
1 1
1
1
1
1 0( ) ( )( )
+
+ a C m mN k
i
i
k
i k i
=
−∑
0
.
Nam we potribno znajty zruçni formuly dlq obçyslennq Rk
i( )( )0 . Dlq c\oho
perepyßemo spivvidnoßennq (1) u vyhlqdi
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
1178 A. M. BRATIJÇUK
f s z z z R sk
k
k
( ( ( ))) ( )+ − −( )
=
∞
∑λ θ1
1
= z f s( ).
Zdyferencigvavßy cg rivnist\ po s i raziv, otryma[mo
C f s z z R si
j
j
i
j k
k
i j
k=
−
=
∞
∑ ∑+ −
1 1
1( ) ( )( ( ( ))) ( )λ θ +
+ f s z z z R sk
k
i
k
( ( ( ))) ( )( )+ − −( )
=
∞
∑λ θ1
1
= z f si( )( ),
zvidky, poklavßy s = 0, budemo maty
C f z z Ri
j
j
i
j k
k
i j
k=
−
=
∞
∑ ∑−
1 1
1 0( ) ( )( ( ( ))) ( )λ θ +
+ f z z z Rk
k
i
k
( ( ( ))) ( )( )λ θ1 0
1
− −( )
=
∞
∑ = z mi
i( )−1 , (25)
de
f zj( )( ( ( )))λ θ1 − = z p jk
k
k
−
=
∞
∑ 1
1
( , )λ ,
p ji( , )λ =
k
j t j
k
i
ke t
t
k
a dF t
=
∞ ∞
−
+
∗∑ ∫ −
0 0
11( )
( )
!
( )λ λ
, i ≥ – 1. (26)
Perepyßemo teper (25) u vyhlqdi
C
f z
f z z
z R z Ri
j
j
i j
k
k
i j
k
k
k
i
k=
−
=
∞
=
∞
∑ ∑ ∑−
− −
+
1 1 1
1
1
0 0
( )
( ) ( )( ( ( )))
( ( ( )))
( ) ( )
λ θ
λ θ
=
( )
( ( ( )))
−
− −
1
1
i
izm
f z zλ θ
. (27)
Todi
z f z
f z z
j( )( ( ( )))
( ( ( )))
λ θ
λ θ
1
1
−
− −
= z p z Rk
k
j
k
k
k
k
−
=
∞
=
∞
∑ ∑1
1 1
( ) = z R p jk
k
k i
i
k
i
=
∞
−
=
−
−∑ ∑
1 0
1
10( ) ( , )λ .
Teper z (27) oderΩu[mo
Rk
i( )( )0 = ( ) ( ) ( , )( )− −
=
− +
−
=
−
=
−
−∑ ∑ ∑1 0
1
1
0 0
1
1
i
i k i
j
j
i
k l
i j
l
k
l p
p
l
lm R C R R p j λ , (28)
de p jl( , )λ znaxodymo z (26). Rivnist\ (28) da[ nam ßukane rekurentne spivvid-
noßennq dlq Rk
i( )( )0 .
1. Takagi H. Queueing analysis. – North-Holland, 1993. – Vol. 2. – 546 p.
2. Korolgk V. S. Hranyçn¥e zadaçy dlq sloΩn¥x puassonovskyx processov. – Kyev: Nauk.
dumka, 1975. – 138 s.
3. Bratijçuk M. S. Toçni formuly dlq systemy obsluhovuvannq typu E Gθ / /1 // Ukr. mat.
Ωurn. – 2000. – 52, # 7. – S.�1034 – 1044.
4. Kartaßov N. R. Stepenn¥e ocenky skorosty sxodymosty v teoreme vosstanovlenyq // Teo-
ryq veroqtnostej y ee prymenenyq. – 1979. – 25. – S.�600 – 607.
OderΩano 18.11.2005
ISSN 1027-3190. Ukr. mat. Ωurn., 2007, t. 59, # 9
|
| id | umjimathkievua-article-3380 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:41:27Z |
| publishDate | 2007 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/72/3ad12c07cd8aab7b651430b803644872.pdf |
| spelling | umjimathkievua-article-33802020-03-18T19:52:51Z Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ Швидкість збіжності до ергодичного розподілу довжини черги в системах типу $M^{θ}/G/1/N$ Bratiychuk, A. M. Братійчук, А. М. For finite capacity queueing systems of the type M θ/G/1, the convenient formulas for the ergodic distribution of a queue length are obtained. An estimate of a rate of convergence of the distribution of queue length in the trasient regime to the ergodic distribution is obtained and computational algorithms for finding the convergence rate are presented. Для систем обслуживания типа M θ/G/1 с ограниченной очередью найдены удобные формулы для эргодического распределения длины очереди, получена оценка скорости сходимости распределения длины очереди в переходном режиме к эргодическому, а также приведены вычислительные алгоритмы для нахождения скорости сходимости. Institute of Mathematics, NAS of Ukraine 2007-09-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3380 Ukrains’kyi Matematychnyi Zhurnal; Vol. 59 No. 9 (2007); 1169–1178 Український математичний журнал; Том 59 № 9 (2007); 1169–1178 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/3380/3503 https://umj.imath.kiev.ua/index.php/umj/article/view/3380/3504 Copyright (c) 2007 Bratiychuk A. M. |
| spellingShingle | Bratiychuk, A. M. Братійчук, А. М. Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ |
| title | Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ |
| title_alt | Швидкість збіжності до ергодичного розподілу довжини черги в системах типу $M^{θ}/G/1/N$ |
| title_full | Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ |
| title_fullStr | Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ |
| title_full_unstemmed | Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ |
| title_short | Rate of convergence to ergodic distribution for queue length in systems of the $M^{θ}/G/1/N$ |
| title_sort | rate of convergence to ergodic distribution for queue length in systems of the $m^{θ}/g/1/n$ |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3380 |
| work_keys_str_mv | AT bratiychukam rateofconvergencetoergodicdistributionforqueuelengthinsystemsofthemthg1n AT bratíjčukam rateofconvergencetoergodicdistributionforqueuelengthinsystemsofthemthg1n AT bratiychukam švidkístʹzbížnostídoergodičnogorozpodíludovžiničergivsistemahtipumthg1n AT bratíjčukam švidkístʹzbížnostídoergodičnogorozpodíludovžiničergivsistemahtipumthg1n |