Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок
The author considers a GI/G/1 retrial queueing system in which delaed customers are directed to the "orbit" to be returned in a constant time T. Let a be the mean inter-arrival time, τ be the service time. Then, under the condition (T + τ) / a < 1 a steady-state regime o...
Saved in:
| Date: | 2019 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2019
|
| Online Access: | https://journal.iasa.kpi.ua/article/view/171346 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | System research and information technologies |
| Download file: |  |
Institution
System research and information technologies| _version_ | 1867334365347840000 |
|---|---|
| author | Koba, E. V. |
| author_facet | Koba, E. V. |
| author_institution_txt_mv | [
{
"author": "E. V. Koba",
"institution": null
}
] |
| author_sort | Koba, E. V. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2019-06-24T16:34:27Z |
| description | The author considers a GI/G/1 retrial queueing system in which delaed customers are directed to the "orbit" to be returned in a constant time T. Let a be the mean inter-arrival time, τ be the service time. Then, under the condition (T + τ) / a < 1 a steady-state regime of the system is proved to exist. It is shown that the stated condition cannot be essentially improved. |
| first_indexed | 2025-07-17T10:25:15Z |
| format | Article |
| fulltext |
© О.В. Коба, 2005
Системні дослідження та інформаційні технології, 2005, № 1 39
TIДC
ПРОГРЕСИВНІ ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ,
ВИСОКОПРОДУКТИВНІ КОМП’ЮТЕРНІ
СИСТЕМИ
УДК 519.872
УМОВА СТІЙКОСТІ СИСТЕМИ ОБСЛУГОВУВАННЯ 1/G/GI
З T -ПОВЕРНЕННЯМ ЗАЯВОК
О.В. КОБА
Розглянуто систему обслуговування 1// GGI , в якій у випадку зайнятості ка-
налу заявка спрямовується на орбіту, з якої повертається через сталий час T .
Нехай a — середній інтервал між заявками, τ — середній час обслуговуван-
ня. Тоді за умови 1/)( <+ aT τ існує стаціонарний режим системи. Доведено,
що цю умову неможливо істотно покращити.
1. Вступні зауваження. Розв’язувана в даній статті задача належить до ана-
лізу систем обслуговування з повторенням заявок (з повторними викликами)
[1, 2]. У випадку, що розглядається, час, через який заявки повторюються,
дорівнює сталому T із ймовірністю 1. Нашим завданням буде встановлення
достатньої умови стійкості системи, якщо відомі значення T , середнього
часу τ обслуговування заявки та середнього часу a між надходженням за-
явок.
Слід зазначити, що фактично всю теорію систем з поверненням заявок
розвинено для випадку, коли час перебування заявки на орбіті має експоне-
нціальну щільність розподілу. В цьому разі важливо знати тільки загальне
число цих заявок, що і пояснює розвинення теорії систем саме з марковсь-
ким поверненням.
Між тим, у задачах прикладного характеру, особливо у задачах з авто-
матизацією, марковська модель не є адекватною. Час перебування заявки на
орбіті в таких системах часто є детермінованим [3] або має загальний розпо-
діл.
Це і спричинило появу деяких інших робіт автора, наприклад, [4, 5].
2. Достатня умова стійкості системи. Розглянемо систему з повер-
ненням заявок типу 1//GGI з T -поверненням. Моменти надходження за-
явок в систему 0,0, 0 =≥ tntn . Інтервали між надходженням заявок
1,1 ≥−= − ntt nnnξ . Позначимо )(xA функцію розподілу довжини інтервалу
nξ між надходженням заявок, )(xB — функцію розподілу часу обслугову-
вання n -ї заявки. Нехай
∫ ∫
∞ ∞
==
0 0
),(),( xdBxxdAxa τ
О.В. Коба
ISSN 1681–6048 System Research & Information Technologies, 2005, № 1 40
T — сталий час перебування заявки на орбіті, nW — час чекання n -ї заяв-
ки. Вважатимемо, що в початковий момент часу система вільна від заявок.
Теорема 1. За умови
1<+
a
T τ
випадкова величина nW має граничний розподіл, тобто
),(}{ xFxW
n
n
∞→
→≤Ρ
де )(xF — деяка функція розподілу.
Доведення. Теорему буде доведено за допомогою порівняння даної си-
стеми з поверненням заявок з системою 1// GGI з чеканням, у якої nξ —
те ж саме, що і у вихідної системи, а час обслуговування nn YT +=η .
Відомо [6], що за умови
1
}{
}{
<
Ε
Ε
=
n
n
ξ
η
ρ
математичне сподівання числа заявок, які обслужені за період зайнятості
системи 1// GGI , скінченне.
Без обмеження загальності покладемо, що період зайнятості системи
1// GGI починається в момент 0t надходження першої заявки. Якщо QN —
число заявок, що обслужені за цей період зайнятості, то для будь-якого
0≥n маємо
}..........,,{}{ 11010 nnQ nN ξξηηξη ++≥++≥Ρ=>Ρ −
Повернемося тепер до системи обслуговування з поверненням заявок.
Нехай RQN — число заявок, які обслужені за період зайнятості, що почався
в момент 0t . Цей період складається з часу обслуговування kY та інтервалів
між ними довжиною kU . Очевидно,
...,,{}{ 2111010 ξξξ +≥++≥Ρ=>Ρ YUYYnN RQ
}......,... 2111110 nnn YUYUY ξξξ +++≥+++++ −− . (1)
Розглянемо стан системи з поверненням заявок в момент закінчення
деякого обслуговування. Якщо до цього моменту період зайнятості не закін-
чився, то деяке число заявок знаходиться на орбіті, тому повернення з орбі-
ти відбудеться раніше, ніж через час T . Таким чином, .TU k ≤ Тоді з (1)
випливає, що
=++≥++++≥+Ρ≤>Ρ − }...)(...)(,...,){(}{ 11010 nnRQ TYTYTYnN ξξξ
}.{}......,...,{ 11010 nNQnn >Ρ=++≥++≥Ρ= − ξξηηξη
Підсумовуючи по n , знайдемо
Умова стійкості системи обслуговування 1// GGI з T -поверненням заявок
Системні дослідження та інформаційні технології, 2005, № 1 41
∑ ∑
∞
=
∞
=
∞<Ε=>Ρ≤>Ρ=Ε
0 0
}{}{}{}{
n n
QQRQRQ NnNnNN . (2)
Якщо в моменти nt заявка, що надходить, застає систему вільною, то
відбувається деяка рекурентна подія. З (2) випливає, що вона додатна.
Оцінимо умовну ймовірність q події })({ 1 вільнасистемаtмоментв n −+
при умові })({ вільнасистемаtмоментв n− .
Маємо
}.{ 1 nnYq ξ≤Ρ= −
Якщо припустити, що 0=q , то
0)...(1)...(1
110 =
⎭
⎬
⎫
⎩
⎨
⎧ ++≤++Ρ − nn n
YY
n
ξξ
для будь-якого n , що неможливо, оскільки за законом великих чисел
τ
∞→
− →++
n
nYY
n
)...(1
10 ,
a
n n
n
∞→
→++ )...(1
1 ξξ (за ймовірністю)
і a<τ . Таким чином, 0>q , а тому рекурентна подія аперіодична. Оскільки
вона також додатна, то є ергодичною. Існування граничного розподілу nW
виводиться з теорії рекурентних подій [7].
Теорему доведено.
3. Неможливість поліпшення отриманої оцінки.
Теорема 2. Для будь-якого 0>ε існує така система RQ з T -
поверненням, для якої
ετ
+=
+ 1
a
T
і час чекання ∞→
∞→n
nW за ймовірністю.
Доведення. Візьмемо довільне )1,0(∈p і припустимо, що 1=T ,
,}1{ pn ==Ρ ξ .1}0{ pqn −===Ρ ξ Відносно nY припустимо лише, що вони
додатні, з математичним сподіванням ∞<τ .
У будь-який момент nt = в систему надходить група nS заявок (при-
пустимо, що nS незалежні випадкові величини), де
,1,}{ 1 ≥==Ρ − kqpkS k
n
звідки
p
Sn
1}{ =Ε .
Позначимо nL число заявок на орбіті в момент ).( +n Для цієї величини
виконується рекурентна нерівність
О.В. Коба
ISSN 1681–6048 System Research & Information Technologies, 2005, № 1 42
,)1( 1 +− −+≥ nnn SLL (3)
оскільки в момент n повертаються всі заявки, відправлені на орбіту в мо-
мент 1−n і до них приєднується нова група nS заявок, за виключенням од-
нієї, що вже обслуговується, якщо 01 >+− nn SL і попереднє обслуговування
закінчено. (Якщо 1≤nY з ймовірністю 1, то (3) буде рівністю.)
Рівняння
+− −+= )1( 1 nnn SLL
можна інтерпретувати як співвідношення для величини черги в системі
1// DGI , в якій час обслуговування дорівнює 1, і в будь-який момент nt =
надходить геометрично розподілена група заявок. Оскільки навантаження
такої системи
11
1
1)/1(
}{
}{}{
>==
Ε
ΕΕ
=
p
p
пучкамиміжінтервал
YS nnρ ,
то [7]
∞→
∞→n
nL (4)
з ймовірністю 1. (Перехід від рівності до нерівності (3) лише підсилює твер-
дження.)
Позначимо nQ число заявок на орбіті в момент )( nt . Тоді 1−≥
ntn LQ .
Очевидно, ∞→nt при ∞→n з ймовірністю 1. Звідси і з (4)
∞→
∞→n
nQ (5)
з ймовірністю 1. Якщо KQn ≥ , то також iKQ in −≥+ , 0>i , а тому ймовір-
ність того, що n -а заявка не буде взята на обслуговування за час k ,
K
kKkWn
1}{ −−
≥>Ρ . (6)
Внаслідок (5) права частина (6) прямує до 1 при ∞→n при будь-якому
k , тобто ∞→nW , ∞→n за ймовірністю.
Оскільки в даному прикладі 1=T , pan ==Ε }{ξ , то
pa
T ττ +
=
+ 1 .
Щоб задовольнити умову теореми, достатньо взяти ετ < і покласти
ε
τ
+
+
=
1
1p .
Теорему доведено.
4. Умова, за якої кожна заявка буде обслужена. У п. 2 було виведено
достатню умову стійкості системи обслуговування з T -поверненням типу
1// GGI , яку в загальному випадку покращити неможливо (теорема 2). Про-
те у випадку конкретних розподілів потоку та обслуговування, напевне, мо-
жливі й точніші оцінки, але ця задача складна. Так, точна умова стійкості
системи 1// DM з T -поверненням авторові невідома.
Умова стійкості системи обслуговування 1// GGI з T -поверненням заявок
Системні дослідження та інформаційні технології, 2005, № 1 43
У цьому параграфі доведемо, що у випадку системи 1// DM за умови
1<= λτρ і будь-якого τ≥T кожна заявка буде обслужена із ймовірністю 1.
Нехай nt — момент надходження n -ї заявки. Введемо подію
nCnk {: -та заявка не взята на обслуговування до моменту tkm + включно}.
Якщо ця подія наступила, то в кожний з моментів kTtTtt nnn ++ ,...,, обслу-
говується або яка-небудь з перших 1−n заявок, або заявка, що надійшла в
деякому інтервалі
kjjTtjTt nn ≤≤+− 1),,( τ .
Загальне число таких заявок — пуассонівська випадкова величина nkN з
параметром ρk .
Таким чином, маємо
}.{}{ nkNC nknk −>Ρ≤Ρ
Оскільки математичне сподівання
ρkNnk =Ε }{
і дисперсія
ρσ kNnk =}{2 ,
то за нерівністю Чебишева при )1/( ρ−> nk
.0
))1((
})1(}{{}{ 2
∞→
→
−−
≤−−>Ε−Ρ=−>Ρ
k
nknknk nk
knkNNnkN
ρ
ρρ
За аксіомою неперервності знаходимо, що із ймовірністю 1 знайдеться
таке nk , при якому n -та заявка обслужиться в інтервалі Tkt nn +( ,
)τ++ Tkt nn , що і треба було довести.
ЛІТЕРАТУРА
1. Yang T., Templeton J.G.C. A survey on retrial queues // Queueing Systems. —
1987. — № 2. — P. 201–233.
2. Falin G.I., Templeton J.G.C. Retrial Queues. — London: Chapman & Hall, 1997. —
328 p.
3. Lakatos L. A probability model connected with landing of airplanes // Safety and Re-
liability. — A.A.Balkema / Rotterdam / Brookfield. — 1999. — 1. — P. 151–154.
4. Коба О.В. Достаточное условие эргодичности системы M/D/1 с Т-возвраще-
нием и приоритетом задержанных заявок // Доповіді НАН України.— 2003.
— № 5. — С.17–20.
5. Коба О.В. Стаціонарні характеристики системи масового обслуговування
GI/G/1 із Т-поверненням при обслуговуванні в порядку черги // Вісник на-
ціонального авіаційного ун-ту. — 2003. — № 1. — С. 122–125.
6. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. —
М.: Наука, 1987. — 336 с.
7. Феллер В. Введение в теорию вероятностей и ее приложения. 1. — М.: Мир,
1984. — 528 с.
Надійшла 05.04.2004
О.В. Коба
ISSN 1681–6048 System Research & Information Technologies, 2005, № 1 44
|
| id | journaliasakpiua-article-171346 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:25:15Z |
| publishDate | 2019 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/52/607f0338cfed455f444f64d89ab80352.pdf |
| spelling | journaliasakpiua-article-1713462019-06-24T16:34:27Z A stability condition for the GI/G/1 retrial queueing system with T-returns Условие устойчивости системы обслуживания GI/G/1 з T-повторением заявок Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок Koba, E. V. The author considers a GI/G/1 retrial queueing system in which delaed customers are directed to the "orbit" to be returned in a constant time T. Let a be the mean inter-arrival time, τ be the service time. Then, under the condition (T + τ) / a &lt; 1 a steady-state regime of the system is proved to exist. It is shown that the stated condition cannot be essentially improved. Рассматривается система массового обслуживания GI/G/1, в которой в случае занятости всех каналов заявка отправляется на "орбиту", с которой возвращается через постоянное время T. Пусть a — средний интервал между заявками, τ — среднее время обслуживания. Тогда при условии (T + τ) / a &lt; 1 существует стационарный режим системы. Доказано, что это условие невозможно существенно улучшить. Розглянуто систему обслуговування GI/G/1, в якій у випадку зайнятості каналу заявка спрямовується на орбіту, з якої повертається через сталий час T. Нехай a — середній інтервал між заявками, τ — середній час обслуговування. Тоді за умови (T + τ) / a &lt; 1 існує стаціонарний режим системи. Доведено, що цю умову неможливо істотно покращити. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2019-06-24 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/171346 System research and information technologies; No. 1 (2005); 39-43 Системные исследования и информационные технологии; № 1 (2005); 39-43 Системні дослідження та інформаційні технології; № 1 (2005); 39-43 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/171346/171002 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Koba, E. V. Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок |
| title | Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок |
| title_alt | A stability condition for the GI/G/1 retrial queueing system with T-returns Условие устойчивости системы обслуживания GI/G/1 з T-повторением заявок |
| title_full | Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок |
| title_fullStr | Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок |
| title_full_unstemmed | Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок |
| title_short | Умова стійкості системи обслуговування GI/G/1 з T-поверненням заявок |
| title_sort | умова стійкості системи обслуговування gi/g/1 з t-поверненням заявок |
| url | https://journal.iasa.kpi.ua/article/view/171346 |
| work_keys_str_mv | AT kobaev astabilityconditionforthegig1retrialqueueingsystemwithtreturns AT kobaev uslovieustojčivostisistemyobsluživaniâgig1ztpovtoreniemzaâvok AT kobaev umovastíjkostísistemiobslugovuvannâgig1ztpovernennâmzaâvok AT kobaev stabilityconditionforthegig1retrialqueueingsystemwithtreturns |