Залишковий час обслуговування в системі GI/G/1/∞
For a GI/G/1/∞-type queueing system, the remaining service time at time t is under consideration. Its distribution as t → ∞ is considered as well.
Gespeichert in:
| Datum: | 2008 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/7497 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Залишковий час обслуговування в системі GI/G/1/∞ / M. С. Братiйчук // Доп. НАН України. — 2008. — № 12. — С. 7-12. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-7497 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-74972010-04-01T12:01:28Z Залишковий час обслуговування в системі GI/G/1/∞ Братійчук, M.С. Математика For a GI/G/1/∞-type queueing system, the remaining service time at time t is under consideration. Its distribution as t → ∞ is considered as well. 2008 Article Залишковий час обслуговування в системі GI/G/1/∞ / M. С. Братiйчук // Доп. НАН України. — 2008. — № 12. — С. 7-12. — Бібліогр.: 5 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/7497 519.21 uk Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Математика Математика |
| spellingShingle |
Математика Математика Братійчук, M.С. Залишковий час обслуговування в системі GI/G/1/∞ |
| description |
For a GI/G/1/∞-type queueing system, the remaining service time at time t is under consideration. Its distribution as t → ∞ is considered as well. |
| format |
Article |
| author |
Братійчук, M.С. |
| author_facet |
Братійчук, M.С. |
| author_sort |
Братійчук, M.С. |
| title |
Залишковий час обслуговування в системі GI/G/1/∞ |
| title_short |
Залишковий час обслуговування в системі GI/G/1/∞ |
| title_full |
Залишковий час обслуговування в системі GI/G/1/∞ |
| title_fullStr |
Залишковий час обслуговування в системі GI/G/1/∞ |
| title_full_unstemmed |
Залишковий час обслуговування в системі GI/G/1/∞ |
| title_sort |
залишковий час обслуговування в системі gi/g/1/∞ |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2008 |
| topic_facet |
Математика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/7497 |
| citation_txt |
Залишковий час обслуговування в системі GI/G/1/∞ / M. С. Братiйчук // Доп. НАН України. — 2008. — № 12. — С. 7-12. — Бібліогр.: 5 назв. — укр. |
| work_keys_str_mv |
AT bratíjčukms zališkovijčasobslugovuvannâvsistemígig1 |
| first_indexed |
2025-07-02T10:20:56Z |
| last_indexed |
2025-07-02T10:20:56Z |
| _version_ |
1836530172170338304 |
| fulltext |
оповiдi
НАЦIОНАЛЬНОЇ
АКАДЕМIЇ НАУК
УКРАЇНИ
12 • 2008
МАТЕМАТИКА
УДК 519.21
© 2008
M. С. Братiйчук
Залишковий час обслуговування в системi GI/G/1/∞
(Представлено академiком НАН України В. С. Королюком)
For a GI/G/1/∞-type queueing system, the remaining service time at time t is under consi-
deration. Its distribution as t → ∞ is considered as well.
Розглядається стандартна система обслуговування типу GI/G/1/∞, яка описується за до-
помогою послiдовностей {α(i)
n }, n > 1, i = 1, 2, випадкових величин, де α(1)
n — промiжок часу
мiж надходженням n−1-ї та n-ї вимоги, а α(2)
n — час обслуговування n-ї вимоги. Дисциплiна
обслуговування є типу FIFO — “перший прийшов — перший обслужився”.
Нехай ξ(t) — число вимог у системi в момент часу t. Вважаємо, що траєкторiї проце-
су ξ(t) є неперервними справа. Покладемо T (t) = inf{s > t : ξ(s) = ξ(t) − 1} − t, якщо
ξ(t) > 1, i T (t) = 0, якщо ξ(t) = 0. Тобто T (t) є залишковий час обслуговування в мо-
мент t. Нас цiкавить формула для перетворення Лапласа–Стiльтьєса функцiї P{T (t) < x},
а також формула для розподiлу T (∞). Якщо вхiдний потiк вимог є пуассонiвським, то
можна застосувати метод вкладеного ланцюга Маркова, як це було зроблено в [1] для до-
слiдження подiбної задачi. Випадок системи GI/G/1 розглядався в [2], де було отримано
формулу для середнього залишкового часу обслуговування в момент надходження чергової
вимоги при умовi, що вiдома кiлькiсть вимог у системi в цей момент. У випадку системи
GI/G/1 процес ξ(t) не має зручних марковських моментiв, i тому для вивчення розподiлу
функцiонала T (t) ми використовуємо метод, який вперше був запропонований В.С. Коро-
люком у [3]. Ми опишемо лише головнi iдеї цього методу, а бiльш детальну iнформацiю
можна знайти в [4].
Введемо такi позначення:
Fi(x) = P{α(i)
n < x},
fi(s) =
∞∫
0
e−sxdFi(x), Re s > 0.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №12 7
Для функцiї f(x) такої, що
∞∫
−∞
exp(−ax)|f(x)|dx < ∞, ми означимо проектори I± таким
чином:
I+
[ ∞∫
−∞
e−sxf(x) dx
]
=
∞∫
0
e−sxf(x) dx, I− = I − I+, Re s = a,
де I означає тотожний оператор. Нехай також mi =
∞∫
0
xdFi(x) < ∞.
1. Результати. Має мiсце тотожнiсть (див., напр., [5])
1 − f1(s)f2(λ− s) = f+(s, λ)f−(s, λ), Re s = 0, (1)
де функцiї f±(s, λ) є регулярними та обмеженими у напiвплощинах ±Re s > 0 вiдповiдно, не
мають там нулiв та f±(∞, λ) = 1. Розклад [1], який називається факторизацiйний, є єдиним,
i в [5] можна знайти ряд властивостей функцiй f±(s, λ). Тут нам буде потрiбна лише така:
якщо m2 −m1 < 0 (умова ергодичностi для системи), то f+(0, 0) = 0 i f−(0, 0) > 0.
Теорема 1. Для Reλ > 0, Reµ > 0 справедлива формула
∞∫
0
e−λt
E{e−µT (t)/ξ(0) = 1}dt =
1
λ
+
f+(0, λ)
(µ− λ)f+(λ, λ)
(
1 − f2(µ)
1 − f2(λ)
−
µ
λ
)
.
Наслiдок 1. Нехай m2/m1 = ρ < 1, тодi
lim
t→∞
P{T (t) < x1} = I{x > 0}(1 − ρ) +
ρ
m2
x∫
0
(1 − F2(y)) dy. (2)
Цей наслiдок має просту ймовiрнiсну iнтерпретацiю. Якщо вимога надходить до системи,
яка перебуває в ергодичному станi, то можливi двi ситуацiї:
1) з iмовiрнiстю 1 − ρ вимога застає систему вiльною, i тодi T (∞) = 0;
2) з iмовiрнiстю ρ вимога застає систему зайнятою, i тодi процес обслуговування, розгля-
нутий на перiодi зайнятостi, є процесом вiдновлення, який породжується розподiлом F2(x).
Вираз m−1
2
∫ x
0 (1−F2(y)) dy якраз i є розподiлом ергодичного залишкового часу очiкування
для такого процесу.
2. Доведення результатiв. Покладемо µi(t) = max
{
n :
n∑
k=1
α
(i)
k 6 t
}
i означимо про-
цеси ξ∗(t) таким чином: ξ∗(t) = ξ(0) + µ1(t) − µ2(t), ξ(0) > 0. Вiдомо, що ξ(t) = ξ∗(t) −
− inf
06u6t
(ξ∗(u), 0).
Нехай ρn, n = 0, 1, . . ., ρ0 = 0 позначають послiдовнi моменти стрибкiв процесу ξ∗(t),
i ми скажемо, що ρn, n > 1, має тип “1”, якщо ρn є моментом стрибка процесу µ1(t), i вiн
має тип “2”, якщо це є моментом стрибка процесу µ2(t).
Нехай подiя An, n > 0, означає, що момент ρn має тип “1”. Покладемо κn = 2 − I{An},
ν(n) = min{k > 0: κn 6= κn+k}, де I{An} = 1 чи 0 вiдповiдно до того вiдбулась подiя An
чи нi. Означимо процеси β(t) = ρn+ν(n) − t та κ(t) = κn, ρn 6 t < ρn+ν(n), n > 0. Нехай
8 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №12
ξ∗n = ξ∗(ρn), βn = β(ρn). Процес (ξ∗(t),κ(t), β(t)) не є марковським, але з його конструк-
цiї випливає, що послiдовнiсть (ξ∗n,κn, βn), n > 0, є його вкладеним ланцюгом Маркова.
Нижченаведенi спiввiдношення задають його перехiднi ймовiрностi:
P{ξ∗n+1 = i+ 1,κn+1 = 1, βn+1 ∈ [z, z + dz)/ξ∗n = i,κn = k, βn = x} =
=
{
−dzF1(x− z), якщо k = 1, x > z;
dzF2(x+ z), якщо k = 2,
(3)
P{ξ∗n+1 = i− 1,κn+1 = 2, βn+1 ∈ [z, z + dz)/ξ∗n = i,κn = k, βn = x} =
=
{
dzF1(x+ z), якщо k = 1;
−dzF2(x− z), якщо k = 2, x > z.
(4)
Введемо подiю Ai(n, x) = {ξ(0) = n,κ(0) = i, β(0) = x}, i = 1, 2, i для n > 0, µ > 0,
x > 0 покладемо
ψi(n, t, x) = E{e−µT (t)/Ai(n, x)}.
Неважко зрозумiти, що
ψ1(n, t, x) = e−µ(x−t), ψ2(n, t, x) = 1 − f(n, t, µ), x > t,
де
f(n, t, µ) = µ
n−1∑
k=0
∞∫
0
e−µy
t∫
0
F 2(y + t− v) dF k∗
2 (v) dy.
Для x > 0, n > 1 з формули повної ймовiрностi та (3), (4) отримуємо
ψ1(n, t, x) = I{x 6 t}
( x∫
0
ψ1(n + 1, t− y, x− y) dF1(y) +
+
∞∫
x
ψ2(n− 1, t− x, y − x) dF1(y)
)
+ I{x > t}e−µ(x−t),
ψ2(n, t, x) = I{x 6 t}
( x∫
0
ψ2(n − 1, t− y, x− y) dF2(y) +
+
t∫
x
ψ1(n+ 1, t− x, y − x) dF2(y) +
∞∫
t
e−µ(y−t)dF2(y)
)
+ I{x > t}(1 − f(n, t, µ)).
(5)
Цi рiвняння мають бути ще доповненi такою граничною умовою:
ψ2(0, t, x) = I{x 6 t}
( t−x∫
0
ψ1(1, t − x, y) dF2(y) +
∞∫
t−x
e−µ(y−t+x)dF2(y)
)
+ I{x > t}. (6)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №12 9
Нехай ψ̂i(n, λ, x) =
∞∫
x
e−λtψi(n, t, x) dt, i = 1, 2, λ > 0.
З (6) отримуємо
ψ̂2(0, λ, x) = e−λx
( ∞∫
0
ψ̂1(1, λ, y) dF2(y) +
f2(λ) − f2(µ)
µ− λ
)
= e−λxC.
Зауважимо, що
C = ψ̂2(0, λ,+0) =
∞∫
0
e−λt
E{e−µT (t)/ξ(0) = 1}dt = ψ̂1(2, λ,+0). (7)
Зробимо в (5) такi перетворення. Спочатку перейдемо до перетворення Лапласа за t
з параметром λ > 0, пiсля чого введемо новi функцiї
V1(n, x) = eλxψ̂1(n+ 1, λ, x), V2(n, x) = ψ̂2(n+ 1, λ, x) − e−λxC.
У результатi цього отримаємо систему iнтегральних рiвнянь
V1(n, x) −
x∫
0
V1(n+ 1, x− y) dF1(y) −
∞∫
x
V2(n − 1, y − x) dF1(y) =
= ϕ1(n, x) + Cψ1(x),
V2(n, x) −
x∫
0
e−λyV2(n− 1, x− y) dF2(y) −
∞∫
x
e−λyV1(n+1, y−x) dF2(y) =
= ϕ2(x) + Cψ2(x), n > 0, x > 0,
(8)
з граничною умовою V2(−1, x) = 0. Тут ми позначили
ϕ1(n, x) =
∞∫
0
e−λt(1 − f(n, t, µ))F 1(t+ x) dt, ψ1(x) =
∞∫
x
e−λ(y−x)dF1(y),
ϕ2(x) =
1
µ− λ
∞∫
x
e−λy(1 − e−(µ−λ)(y−x)) dF2(y), ψ2(x) = −e−λxF 2(x).
Система (8) дослiджувалась у роботах [3, 4], i в останнiй з них були отриманi форму-
ли для загального розв’язку такої системи. Тут ми сформулюємо результат з цiєї роботи
у випадку системи (8) для функцiї V1(1, x), оскiльки лише вiн буде використовуватися далi.
∞∫
0
e−sxV1(1, x) dx =
∞∫
0
e−(s−λ)x
∞∫
x
e−λt
E{e−µT (t)/A1(2, x)}dtdx =
=
1
f+(s, λ)
I+
[
Φ(s, λ)
f−(s, λ)
]
+
C
f+(s, λ)
I+
[
Ψ(s, λ)
f−(s, λ)
]
+
C(f1(s) − f1(λ))
(λ− s)(1 − f1(s))
+
+
∞∑
k=0
fk
1 (s)ϕ+(k + 1, s), (9)
10 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №12
де
Φ(s, λ) =
I+[ϕ−(s)f1(s)]
1 − f1(s)
+
∞∑
k=1
fk
1 (s)I−[ϕ+(k, s)f2(λ− s)],
Ψ(s, λ) =
I+[ψ−(s)f1(s)] + I−[ψ+(s)f2(λ− s)]
1 − f1(s)
.
Тут
ϕ+(n, s) =
∞∫
0
e−sxϕ1(n, x) dx, ψ+(s) =
∞∫
0
e−sxψ1(x) dx,
ϕ−(s) =
∞∫
0
esxϕ2(x) dx, ψ−(s) =
∞∫
0
esxψ2(x) dx.
Надалi доведення базується на двох технiчних результатах, якi ми подамо у виглядi
леми.
Лема 1. Для 0 < Re s < λ маємо
I+
[
Ψ(s, λ)
f−(s, λ)
]
=
1 − f1(λ)
λ− s
(
f+(λ, λ)
1 − f1(λ)
−
f+(s, λ)
1 − f1(s)
)
,
I+
[
Φ(s, λ)
f−(s, λ)
]
=
1
sf−(0, λ)
(
f2(λ) − f2(µ)
µ− λ
−
1 − f2(λ)
λ
)
+
+
1 − f1(λ)
λ(λ− s)
(
f+(s, λ)
1 − f1(s)
−
f+(λ, λ)
1 − f1(λ)
)
+ f+(s, λ)
∞∑
k=1
fk
1 (s)ϕ̂+(k + 1, s),
де
ϕ̂+(n, s) =
∞∫
0
e−sx
∞∫
0
e−λtf(n, t, µ)F 1(x+ t) dtdx.
Лема 1 та формула (9) дають
∞∫
0
e−(s−λ)x
∞∫
x
e−λt
E{e−µT (t)/A1(2, x)}dtdx =
= −
C
λ− s
(
1 −
f+(λ, λ)
f+(s, λ)
)
+
1 − f1(λ)
λ(λ− s)f+(s, λ)
(
f+(s, λ)
1 − f1(s)
−
f+(λ, λ)
1 − f1(λ)
)
+
+
1
sf−(0, λ)
(
f2(λ)−f2(µ)
µ− λ
−
1−f2(λ)
λ
)
+
1
λ− s
(
1−f1(s)
s
−
1−f1(λ)
λ
)
. (10)
З (7), (10) та тауберової теореми маємо
C = lim
x→0+
ψ̂1(2, λ, x) = lim
s→+∞
s
∞∫
0
e−(s−λ)x
∞∫
x
e−λt
E{e−µT (t)/A1(2, x)}dtdx =
= C(1 − f+(λ, λ)) +
f+(λ, λ)
λ
+
1
f−(0, λ)
(
f2(λ) − f2(µ)
µ− λ
−
1 − f2(λ)
λ
)
,
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2008, №12 11
що дає
C =
1
λ
+
f+(0, λ)
(µ− λ)f+(λ, λ)
(
1 − f2(µ)
1 − f2(λ)
−
µ
λ
)
.
Це та (7) завершує доведення теореми 1.
Щоб довести наслiдок 1, зауважимо, що в умовах цього наслiдку система є ергодичною,
а lim
t→∞
P{T (t) < x} iснує та не залежить вiд початкового стану. Маємо
lim
λ→0
f+(0, λ)
f+(λ, λ)
= lim
λ→0
f−(0, λ)(1 − f2(λ))
f−(λ, λ)(1 − f1(λ))
=
m2
m1
= ρ.
Це та теорема 1 дають
Ee−µT (∞) = lim
λ→0
λ
∞∫
0
e−λt
E{e−µT (t)/ξ(0) = 1}dt = 1 − ρ+
ρ
m2
1 − f2(µ)
µ
,
звiдки випливає (2).
Робота виконана за пiдтримки Мiнiстерства наукових дослiджень та iнформацiйних техно-
логiй Польської Народної Республiки (грант No. 3 T11C 014 26.)
1. Chydzinski A. On the remaininig service time upon reaching a given level in M/G/1 queue // Queueing
Systems. – 2004. – 47. – P. 71–80.
2. Fakinos D. The expected remaining service time in a single-server queue // Oper. Res. – 1982. – 30. –
P. 1014–1018.
3. Королюк В.С., Пирлиев В. Случайное блуждание на полуоси на суперпозиции двух процессов вос-
становления // Укр. мат. журн. – 1984. – 36, № 4. – С. 433–436.
4. Bratiychuk M. S., Kempa W. Application of the superposition of renewal processes to the study of batch
arrival queues // Queueing Systems. – 2003. – 44. – P. 51–67.
5. Боровков А. A. Вероятностные процессы в теории массового обслуживания. – Mосква: Наука, 1972. –
368 с.
Надiйшло до редакцiї 13.05.2008Шльонський технiчний унiверситет, Глiвiце, Польща
12 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2008, №12
|