Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів
Розглядається двовимірний марковський процес {X(t), t≥0}, фазовий простір якого являє собою решітку в напівсмузі S(X) = {0,1,…, c +m}×Z₊. Процес {X(t), t≥0} описує обслуговування вимог у багатоканальній системі з повторними викликами та інтенсивністю повторів, яка не залежить від числа повторних в...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2020
|
| Schriftenreihe: | Доповіді НАН України |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/173048 |
| 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: | Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів / Є.О. Лебєдєв, В.Д. Пономарьов // Доповіді Національної академії наук України. — 2020. — № 7. — С. 22-31. — Бібліогр.: 13 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-173048 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1730482020-11-20T01:25:46Z Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів Лебєдєв, Є.О. Пономарьов, В.Д. Інформатика та кібернетика Розглядається двовимірний марковський процес {X(t), t≥0}, фазовий простір якого являє собою решітку в напівсмузі S(X) = {0,1,…, c +m}×Z₊. Процес {X(t), t≥0} описує обслуговування вимог у багатоканальній системі з повторними викликами та інтенсивністю повторів, яка не залежить від числа повторних викликів. Спочатку для моделі, що розглядається, знайдена умова ергодичності. Потім отримано матрич новекторне подання стаціонарного розподілу через параметри системи. Метод дослідження базується на апроксимації вихідної моделі за допомогою урізаної з подальшим переходом до границі. Застосування отриманих результатів продемонстровано на числових прикладах, у яких наведена залежність блокуючої ймовірності та середньої величини черги в стаціонарному режимі від параметрів системи. A bivariate Markov process {Х(t)=(X₁(t), X₂(t))^T, t≥0} whose phase space is a lattice semistrip S(X)={0,1,…, c+m, }xZ₊ is considered. The first component X₁(t) ∈{0,1,..., c +m} indicates the summarized number of busy servers and calls in the queue at the instant t ≥0, whereas the second one X₂(t)∈{0,1,...} is the number of retrial sources. Parameter c∈Z₊ is a number of servers and m∈Z is a maximal size of the queue. Local rates of X(t) are defined in such a way that X(t) describes the service policy of a multi-server retrial queue in which the rate of repeated flow does not depend on the number of sources of repeated calls. First, using tools of the theory for the QBD-processes (quasi-birth-and-death processes), we study the ergodicity conditions. Then, under these conditions, we consider a problem of finding the steady state probabilities for X(t). A vector-matrix representation of the probabilities via the model parameters is obtained. The applied technique uses an approximation of the initial model by a truncated one and the direct passage to the limit. The obtained formulae are the adequate method to calculate the steady state probabilities. An application of the main result is demonstrated via numerical examples in which we can see relation graphs of the blocking probability and the average number of retrials versus system parameters. 2020 Article Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів / Є.О. Лебєдєв, В.Д. Пономарьов // Доповіді Національної академії наук України. — 2020. — № 7. — С. 22-31. — Бібліогр.: 13 назв. — укр. 1025-6415 DOI: doi.org/10.15407/dopovidi2020.07.022 http://dspace.nbuv.gov.ua/handle/123456789/173048 519.21 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Лебєдєв, Є.О. Пономарьов, В.Д. Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів Доповіді НАН України |
| description |
Розглядається двовимірний марковський процес {X(t), t≥0}, фазовий простір якого являє собою решітку в
напівсмузі S(X) = {0,1,…, c +m}×Z₊. Процес {X(t), t≥0} описує обслуговування вимог у багатоканальній
системі з повторними викликами та інтенсивністю повторів, яка не залежить від числа повторних викликів. Спочатку для моделі, що розглядається, знайдена умова ергодичності. Потім отримано матрич новекторне подання стаціонарного розподілу через параметри системи. Метод дослідження базується на
апроксимації вихідної моделі за допомогою урізаної з подальшим переходом до границі.
Застосування отриманих результатів продемонстровано на числових прикладах, у яких наведена залежність блокуючої ймовірності та середньої величини черги в стаціонарному режимі від параметрів
системи. |
| format |
Article |
| author |
Лебєдєв, Є.О. Пономарьов, В.Д. |
| author_facet |
Лебєдєв, Є.О. Пономарьов, В.Д. |
| author_sort |
Лебєдєв, Є.О. |
| title |
Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів |
| title_short |
Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів |
| title_full |
Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів |
| title_fullStr |
Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів |
| title_full_unstemmed |
Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів |
| title_sort |
стаціонарний режим для системи масового обслуговування типу m | m | c | c + m із сталою інтенсивністю повторів |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2020 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/173048 |
| citation_txt |
Стаціонарний режим для системи масового обслуговування типу M | M | c | c + m із сталою інтенсивністю повторів / Є.О. Лебєдєв, В.Д. Пономарьов // Доповіді Національної академії наук України. — 2020. — № 7. — С. 22-31. — Бібліогр.: 13 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT lebêdêvêo stacíonarnijrežimdlâsistemimasovogoobslugovuvannâtipummccmízstaloûíntensivnístûpovtorív AT ponomarʹovvd stacíonarnijrežimdlâsistemimasovogoobslugovuvannâtipummccmízstaloûíntensivnístûpovtorív |
| first_indexed |
2025-07-15T09:35:02Z |
| last_indexed |
2025-07-15T09:35:02Z |
| _version_ |
1837705045519368192 |
| fulltext |
22
ОПОВІДІ
НАЦІОНАЛЬНОЇ
АКАДЕМІЇ НАУК
УКРАЇНИ
ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 7: 22—31
Ц и т у в а н н я: Лебєдєв Є.О., Пономарьов В.Д. Стаціонарний режим для системи масового обслуговуван-
ня типу M | M c | c + m із сталою інтенсивністю повторів. Допов. Нац. акад. наук Укр. 2020. № 7. С. 22—31.
https://doi.org/10.15407/dopovidi2020.07.022
Системи масового обслуговування з повторними викликами використовуються при моде-
люванні телекомунікаційних систем, call центрів, комп’ютерних мереж та інших сучасних
систем обробки інформації (за деталями можна звернутись до [1]). У класичних моделях
систем масового обслуговування припускається, що вимога, яка надходить у зайняту сис-
тему, блокується і втрачається. Зустрічається й інший сценарій: заблокована вимога очі-
кує на початок обслуговування у черзі. Однак часто алгоритм обслуговування не допускає
очікування в черзі і заблокована вимога тимчасово залишає систему. Після випадкового
періоду часу вона повертається і знову намагається отримати обслуговування. Така пове-
дінка вимог і моделюється системами з повторними викликами.
Як правило, в системах з повторними викликами заблокована вимога приєднується до
орбіти і звертається до обслуговуючих приладів через випадкові проміжки часу незалежно
https://doi.org/10.15407/dopovidi2020.07.022
УДК 519.21
Є.О. Лебєдєв, В.Д. Пономарьов
НТУ України “Київський політехнічний інститут”
E-mail: leb@unicyb.kiev.ua
Стаціонарний режим для системи
масового обслуговування типу M | M | c | c + m
із сталою інтенсивністю повторів
Представлено членом-кореспондентом НАН України П.С. Кноповим
Розглядається двовимірний марковський процес { ( ), 0}X t t� , фазовий простір якого являє собою решітку в
напівсмузі += … + ×( ) {0,1, , }S X c m Z . Процес { ( ), 0}X t t� описує обслуговування вимог у багатоканальній
системі з повторними викликами та інтенсивністю повторів, яка не залежить від числа повторних вик-
ликів. Спочатку для моделі, що розглядається, знайдена умова ергодичності. Потім отримано матрич но-
векторне подання стаціонарного розподілу через параметри системи. Метод дослідження базується на
апроксимації вихідної моделі за допомогою урізаної з подальшим переходом до границі.
Застосування отриманих результатів продемонстровано на числових прикладах, у яких наведена за-
лежність блокуючої ймовірності та середньої величини черги в стаціонарному режимі від параметрів
системи.
Ключові слова: стаціонарний режим, система з повторними викликами, умова ергодичності, урізана мо-
дель, матрично-векторне подання.
ІНФОРМАТИКА ТА КІБЕРНЕТИКА
23ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 7
Стаціонарний режим для системи масового обслуговування типу M| M | c | c + m із сталою інтенсивністю...
від інших вимог, що знаходяться на орбіті. Це означає, що інтенсивність потоку повтор-
них викликів прямо пропорційна числу вимог на орбіті у поточний момент часу. Однак на
практиці можливі випадки, коли потік повторних викликів є контрольованим і його ін-
тенсивність не залежить від числа вимог на орбіті. Наприклад, у роботі [2] вивчались сис-
теми з повторними викликами і сталою інтенсивністю повторів, що було викликано необ-
хідністю моделювання CSMA/CD протоколу. Автори робіт [3, 4] моделюють TCP трафік,
використовуючи подібні моделі. Стала інтенсивність повторів інтерпретується як інтен-
сивність опитування заблокованих вимог: вільний прилад послідовно опитує заблоковані
вимоги. Час, виділений на це обслуговуючому приладу, збігається з часом повтору.
У подальшому Арталего і Гомес-Корал [5]) запропонували вивчати | | |M M c c -системи
із сталою інтенсивністю повторів використовуючи незалежні від рівня квазінародження і
загибелі процеси (QBD процеси). Теорія таких процесів була розвинута Ньютсом [6] на
основі аналітичних матричних методів. Результатом застосування QBD процесів є ефек-
тивні обчислювальні алгоритми для стаціонарних імовірностей. Такі алгоритми містить ро-
бота [5], в якій використано аналітичний матричний підхід, і робота [7], що основана на
методі розкладу за спектром.
Як було зазначено вище, системи зі сталою інтенсивністю повторів широко викорис-
товуються для розв’язування практичних задач. При цьому значну користь можна мати від
явних аналітичних представлень імовірносних характеристик, що описують процес об -
слу говування у таких моделях. Нажаль, явні формули для стаціонарних імовірностей
бу ли отримані лише у простих випадках [8]. Деякі рекурентні алгоритми для стаціонар-
них імовірностей | | |M M c c m+ -систем наведені у [9]. Для простих часткових випадків
| | |M M c c m+ -систем час очікування початку обслуговування і період зайнятості було вив-
чено у роботі [10].
Робота, що пропонується, має таку структуру. По-перше, ми введемо процес обслугову-
вання для | | |M M c c m+ -системи і знайдемо умови його ергодичності. У подальшому ми
отримаємо явне подання для стаціонарних імовірностей процесу обслуговування через па-
раметри системи. Застосування отриманих результатів продемонстровано на чисельних
прикладах, в яких проаналізована одна з головних інтегральних характеристик моделі.
Математична модель і умова ергодичності. Розглянемо систему з повторними викли-
ками, яка має c однакових обслуговуючих приладів і m місць у черзі для очікування по-
чатку обслуговування. Вхідний потік вимог є пуассонівським з параметром λ . Якщо в мо-
мент надходження вимоги є вільний прилад, вона негайно починає обслуговуватись. Час
обслуговування має експоненціальний розподіл з параметром ν . Якщо у момент надхо-
дження всі прилади зайняті, вимога намагається зайняти місце в черзі для очікування по-
чатку обслуговування. Якщо всі m місць у черзі зайняті, вимога, що надійшла, стає дже-
релом повторних викликів і приєднується до орбіти. Інтенсивність повторів не залежить
від кількості вимог на орбіті і дорівнює μ .
Процес обслуговування вимог у системі, що розглядається, може бути описаний двови-
мірним ланцюгом Маркова з неперервним часом 1 2( ) ( ( ), ( ))TX t X t X t= , 1( ) {0,1, , }X t c m∈ … + ,
2( ) {0,1, }X t ∈ … , який визначається своїми інфінітезимальними характеристиками ( , )( , )i j i ja ′ ′ ,
′ ′ ∈ = … + × …( , ), ( , ) ( ) {0,1, , } {0,1, }i j i j S X c m такого вигляду:
1) якщо 0 , 0i c j< >� , то
24 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 7
Є.О. Лебєдєв, В.Д. Пономарьов
′ ′
′ ′λ = +⎧
⎪ ′ ′μ = + −⎪⎪ ′ ′= ν = −⎨
⎪ ′ ′− λ +μ+ ν =⎪
⎪⎩
( , )( , )
, коли ( , ) ( 1, );
, коли ( , ) ( 1, 1);
, коли ( , ) ( 1, );
( ), коли ( , ) ( , );
0, у протилежному випадку;
i j i j
i j i j
i j i j
a i i j i j
i i j i j
2) якщо , 0с i c m j< + >� , то
′ ′
′ ′λ = +⎧
⎪ ′ ′ν = −⎪= ⎨ ′ ′− λ + ν =⎪
⎪⎩
( , )( , )
, коли ( , ) ( 1, );
, коли ( , ) ( 1, );
( ), коли ( , ) ( , );
0, у протилежному випадку;
i j i j
i j i j
c i j i j
a
c i j i j
3) якщо , 0i c m j= + � , то
′ ′+
′ ′λ = + +⎧
⎪ ′ ′ν = + −⎪= ⎨ ′ ′− λ + ν = +⎪
⎪⎩
( , )( , )
, коли ( , ) ( , 1);
, коли ( , ) ( 1, );
( ), коли ( , ) ( , );
0, у протилежному випадку;
c m j i j
i j c m j
c i j c m j
a
c i j c m j
4) якщо 0 , 0i c m j< + =� , то
[ ]′ ′
′ ′λ = +⎧
⎪ ′ ′∧ ν = −⎪= ⎨ ′ ′− λ + ∧ ν =⎪
⎪⎩
( , 0)( , )
, коли ( , ) ( 1,0);
( ) , коли ( , ) ( 1,0);
( ) , коли ( , ) ( , 0);
0, у протилежному випадку
i i j
i j i
i c i j i
a
i c i j i
,
де ( ) min( , )i c i c∧ = .
Перша компонента 1( ) {0,1, , }X t c m∈ … + дорівнює сумарній кількості зайнятих при ла-
дів і вимог у черзі в момент часу 0t� . Друга компонента 2( ) {0,1, }X t ∈ … вказує на кількість
вимог на орбіті. У подальшому процес 1 2( ) ( ( ), ( ))TX t X t X t= є головним об’єктом наших
досліджень.
Множину станів ( )X t зручно впорядкувати таким чином:
( ) {(0, 0), (1, 0), , ( , 0), (0,1), (1,1), , ( ,1), }S X c m c m= + + .
Тоді інфінітезимальна матриця ланцюга ( )X t може бути подана у блочній формі:
(0,0) (0, 1)
( 1) (0) ( 1)
( 1) (0) ( 1)
Q Q
Q Q Q
Q
Q Q Q
+
− +
− +
⎛ ⎞
⎜ ⎟
⎜ ⎟
⎜ ⎟= ⎜ ⎟
⎜ ⎟
⎜ ⎟
⎜ ⎟⎝ ⎠
, (1)
25ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 7
Стаціонарний режим для системи масового обслуговування типу M| M | c | c + m із сталою інтенсивністю...
де (0, 0)(0, 0)
, 0
c m
ij i j
Q q
+
=
= — тридіагональна матриця з елементами
[ ]⎧− λ + ∧ ν = = +
⎪
∧ ν = − = +⎪= ⎨
λ = + = + −⎪
⎪⎩
(0, 0)
( ) , коли 0, , ;
( ) , коли 1, 1, , ;
, коли 1, 0, , 1;
0, у протилежному випадку;
ij
i c i j c m
i c j i i c m
q
j i i c m
(0, 1)(0, 1)
, 0
(0, , 0, )
c m
ij i j
Q q
+++
=
= = Λ λ діагональна матриця з вектором (0, , 0, )Tλ на голов ній
діагоналі;
(0)(0)
, 0
c m
ij i j
Q q
+
=
= — тридіагональна матриця з елементами
− λ +μ+ ν = = −⎧
⎪− λ + ν = = + +⎪⎪= ∧ ν = − = +⎨
⎪λ = + = + −⎪
⎪⎩
(0)
( ), коли 0, , 1;
( ), коли , 1, , ;
( ) , коли 1, 1, , ;
, коли 1, 0, , 1;
0, ;
ij
i i j c
c i j c c c m
q i c j i i c m
j i i c m
у протилежному випадку
( 1) (0, 1) (0, , 0, )Q Q+ += = Λ λ – діагональна матриця;
( 1)( 1)
, 0
c m
ij i j
Q q
+−−
=
= ,
− μ = + = −⎧
= ⎨
⎩
( 1) , коли 1, 0, , 1;
0, у протилежному випадку.ij
j i i c
q
Подання Q у вигляді (1) гарантує те, що ( )X t є незалежний від рівня квазінароджен-
ня та загибелі процес (QBD процес; див., наприклад, [11], с. 189). Щоб знайти умови ерго-
дичності для ( )X t , розглянемо тридіагональну інфінітезимальну матрицю ( 1) (0)Q Q Q−= + +
( 1)
, 0
c m
ij i j
Q q
++
=
+ = , де
− λ +μ+ ν = = −⎧
⎪− λ + ν = = + + −⎪
⎪− ν = = +
⎪= ∧ ν = − = +⎨
⎪λ +μ = + = −⎪
λ = + = + −⎪
⎪
⎩
( ), коли 0, , 1;
( ), коли , 1, , 1;
, коли ;
( ) , коли 1, 1, , ;
, коли 1, 0, , 1;
, коли 1, , , 1;
0, у протилежному випадку.
ij
i i j c
c i j c c c m
c i j c m
q i c j i i c m
j i i c
j i i c c m
Розв’язуючи систему рівнянь
10T T
c mQ + +ρ = , 11 1T
c m+ +ρ = ,
26 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 7
Є.О. Лебєдєв, В.Д. Пономарьов
де 10c m+ + , 11c m+ + представляють собою ( 1)c m+ + -вимірні вектори, складені з нулів і оди-
ниць відповідно, ми знаходимо
1
1
0 0
1 1 1
! ! !
i k c kc m
i
k ki k c c
−
−
= =
⎧ ⎫λ +μ λ +μ λ +μ λ⎪ ⎪⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ρ = +⎨ ⎬⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ν ν ν ν⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎪ ⎪⎩ ⎭
∑ ∑
для 0, , 1i c= − ,
1
1
0 0
1 1 1
! ! !
c i c k c kc m
i
k kc c k c c
−− −
= =
⎧ ⎫λ +μ λ λ +μ λ +μ λ⎪ ⎪⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ρ = +⎨ ⎬⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ν ν ν ν ν⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎪ ⎪⎩ ⎭
∑ ∑
для , ,i c c m= + .
Умова ергодичності для незалежних від рівня QBD процесів
( 1) ( 1)
1 11 1T T
c m c mQ Q+ −
+ + + +ρ < ρ
у випадку ( )X t приймає вид
1
0
1 1
! !
c m ic
ic c i
−
=
λ +μ λ λ +μ⎛ ⎞ ⎛ ⎞ ⎛ ⎞λ < μ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ν ν ν⎝ ⎠ ⎝ ⎠ ⎝ ⎠
∑ . (2)
Таким чином ми довели такий допоміжний результат.
Лема 1. Якщо умова (2) виконується, то процес ( )X t буде ергодичним.
При виконанні умови (2) через ijπ , ( , ) ( )i j S X∈ будемо позначати стаціонарні імовір-
ності ( )X t . Наша найближча мета — побудувати явні формули для ijπ .
Стаціонарний розподіл. Для того, щоб подати результати аналізу стаціонарного ре жи-
му у стислому вигляді, ми введемо матриці, які визначаються параметрами моделі:
1
c m
ij ij
A a
+
=
= -матриця з елементами 1iia − = μ , 1, 2, , 1i c m= + − ,
, 1,
( )
, 1;
c mj
c
j c m
a
c
j c m
+
μν⎧ ≠ + −⎪⎪ λ= ⎨μ λ + ν⎪ = + −
⎪ λ⎩
усі інші елементи матриці A дорівнюють нулю;
1
c m
ij ij
B b
+
=
= -тридіагональна матриця з еле-
ментами, 1iib − = −λ , 1, 2, ,i c m= + , [( 1) ]iib i c= λ +μ+ − ∧ ν , 1, , 1i c m= + − , 1 ( )iib i c+ = − ∧ ν ,
1, , 1i c m= + − ;
1
c m
ij ij
C c
+
=
= , де 11 1c = , 1 0jc = , 2, ,j c m= + , 1ij i jc b −= , 2, ,j c m= + , 1, ,i c m= + .
Для введених матриць методом Гаусса–Жордана отримаємо такий допоміжний результат.
Лема 2. Матриці 0B , B і C є неособливими, причому:
1.
,( 1)1
0 0 , 1,
( , )
c m
i k
B b i k
+−−
=
=
де
( )
( 1)
0 1
( ) ( )
( 1)! 1 ( 1)!
( , )
( 1)!( 1)!
c i jk c j m
j
j k i j k c
i j c c
b i k
ii
+
+ +
−−
−
+
= − = −
+ − ν − ν ν⎛ ⎞ ⎛ ⎞= + ⎜ ⎟ ⎜ ⎟λ − λ λ− λ ⎝ ⎠ ⎝ ⎠
∑ ∑ , 1, , 1i c= − ,
27ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 7
Стаціонарний режим для системи масового обслуговування типу M| M | c | c + m із сталою інтенсивністю...
( 1)
0
( )
1
( , )
jc m i
j k i
c
b i k
+
+ −
−
= −
ν⎛ ⎞= ⎜ ⎟λ λ⎝ ⎠
∑ , ( ) max(0, )k i k i+− = − , , ,i c c m= + .
2. 1 1
1
0
p
p
B B F
∞
− −
=
= ∑ , де F є діагональна матриця з елементами [( 1) ]iif i c= λ +μ+ − ∧ ν ,
, ,i c c m= + , на головній діагоналі; 1 1 , 1
( , )
c m
i j
B b i j
+
== є матриця, ненульові елементи якої
дорівнюють:
1( , 1)
[( 1) ]
b i i
i c
λ− =
λ +μ+ − ∧ ν
, 2, ,i c m= + ,
1
( )
( , 1)
[( 1) ]
i c
b i i
i c
∧ ν+ =
λ +μ+ − ∧ ν
, 1, , 1i c m= + − .
Щоб побудувати стаціонарний розподіл для процесу обслуговування в | | |M M c c m+ -
системі, розглянемо аналогічну систему із скінченним фазовим простором. Така систе ма
має обмеження на розмір орбіти: нові вимоги втрачаються, якщо всі обслуговуючі прила-
ди зайняті, немає вільних місць для очікування в черзі і на орбіті вже знаходиться N ви мог.
Формально процес обслуговування в системі з обмеженням на розмір орбіти можна опи-
сати ланцюгом Маркова 1 2( , ) ( ( , ), ( , ))TX t N X t N X t N= , 1( , ) {0,1, , }X t N c m∈ … + , 2( , )X t N ∈
{0,1, , }N∈ … . Його інфінітезимальні характеристики ( )
( , )( , )
N
i j i ja ′ ′ , ( , ), ( , ) ( , )i j i j S X N′ ′ ∈ =
{0,1, , } {0 1, , }c m N= + × збігаються з інфінітезимальними характеристиками ( , )( , )i j i ja ′ ′
ланцюга ( )X t у всіх фазових точках, за виключенням граничної ( , )c m N+ :
′ ′+
′ ′ν = + −⎧
⎪ ′ ′= − ν = +⎨
⎪
⎩
( )
( , )( , )
, коли ( , ) ( 1),
, коли ( , ) ( , ),
0, в інших випадках.
N
c m N i j
c i j c m
a c i j c m N
Фазовий простір ( , )S X N процесу ( , )X t N є скінченним, тому ( , )X t N має стаціонар-
ний розподіл і через ( )ij Nπ , ( , ) ( , )i j S X N∈ будемо позначати його стаціонарні ймовірності.
Позначимо 0 1( ) ( ( ), , ( ))T
j j c m jN N N+ −π = π π вектор стаціонарних імовірностей. Спра-
ведливим є такий результат.
Лема 3. Стаціонарні ймовірності процесу ( , )X t N можна подати у такій формі:
00( ) ( ) ( ), 0,1,j jN N N jπ = Δ ⋅π = ,
де 1
0 0 1( ) ( )N B A N−Δ = Δ ,
1 1
1
1 1 1
1 0 1
( )
( ) , 1, 2,
( )
N j
j T N
B A C e
N j
e B B B A C e
− − −
− − −Δ = = ,
1 11 1( , , )T
c me += δ δ , ijδ – символ Кронекера.
Тепер перейдемо до вивчення граничної поведінки векторів, коли N →∞ . Спираючись
на роботу [13] (теорема 8.2.8), можна довести такий результат.
Лема 4. Границі векторів ( )j NΔ , 0,1,j = , коли N →∞ мають подання у формі:
28 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 7
Є.О. Лебєдєв, В.Д. Пономарьов
1
0 0 1B A−Δ = Δ ,
1
1
1 1 1
1 0 1
lim ( ) , 1, 2,
( )
T
j j T j TN
uv C e
N j
e B B B A uv C e
−
− − −→∞
Δ = Δ = = ,
де 1 2( , , , ) 0T
c mu u u u += … > , 1 2( , , , ) 0T
c mv v v v += … > – правий і лівий власні вектори матриці
1B A− , які відповідають перроновому кореню.
Коли N →∞ стаціонарні таціонарні імовірності ( )ij Nπ апроксимують відповідні імо-
вірності ijπ для моделі, що розглядається (див. теорему 2.3 і 2.4 з [1], розділ 2 про стохастич-
ну впорядкованість імовірносних розподілів для процесів міграції). У подальшому ми отри-
маємо явні вирази для ( )ij Nπ та ijπ через параметри моделі, що дозволить оцінити точність
апроксимації.
На основі цієї апроксимації і допоміжних результатів, доведених раніше, ми отримаємо
головний результат.
Теорема 1. Якщо процес ( )X t задовольняє умові леми 1, то
00lim ( )j j j
N
N
→∞
π = π = Δ ⋅π , 1 001 ( ) , 0,1, T
c mj jc m j+ +
μπ = + Δ π =
λ
(3)
де 0 1,( , , )T
j j c m j+ −π = π … π ,
1
00 0
1
1 ( ) 1 ( )T T
j
j
c m c m
−
∞
=
⎧ ⎫λ +μ⎪ ⎪π = + Δ + + Δ⎨ ⎬λ⎪ ⎪⎩ ⎭
∑ .
Як наслідок теореми 1 ми можемо отримати явний вид стаціонарних імовірностей.
Наслідок 1. Якщо процес ( )X t задовольняє умові леми 1, то:
1 1 1
0 0 1
TB Auv C e H− − −π = , 1 1
1 , 1, 2,j T
j r uv C e H j− − −π = = … ,
1 1 1
11 ( )j T T
c mj r c m uv C e H− − − −
+
μπ = +
λ
, 0,1,j = (31)
де 1 1
0 1
1 /
1 ( )
1
T TH c m B A E uv C e
r
− −+ μ λ⎛ ⎞= + +⎜ ⎟⎝ ⎠−
.
Зауважимо, що формули (3) та (31) є простішими, ніж модифікована матрично-гео мет-
рична форма стаціонарних імовірностей, що випливає із загально відомої теорії QBD про-
цесів (див., наприклад, [11], с. 196). Формули (3) та (31) більш точно вказують на структу-
ру стаціонарного розподілу (зважений геометричний розподіл) і вони є джерелом явних
формул для головних показників процесу обслуговування у стаціонарному режимі.
Чисельні результати. З використанням отриманих формул обчислимо деякі показники
процесу обслуговування вимог у системі з повторними викликами, що наводиться. Роз-
глянемо блокуючу ймовірність bπ і середнє число вимог на орбіті 2[ ]E X . Беручи до уваги
результати теореми 1 і наслідку 1, ці показники можна обчислювати за такими формулами:
1 1
1
0
/
1 ( )
1
T T
b c mj
j
c m uv C e H
r
∞
− −
+
=
μ λπ = π = +
−∑ ,
1 1
2 12
0 0
1
[ ] 1 ( )
( 1)
c m
T T
ij
j i
r
E X j c m uv C e H
r
∞ +
− −
= =
+= π = +
−∑ ∑ .
29ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 7
Стаціонарний режим для системи масового обслуговування типу M| M | c | c + m із сталою інтенсивністю...
Вплив параметрів моделі на блокуючу ймовірність і середнє число вимог на орбіті гра-
фічно показано на рис. 1—3.
Представлені на рис. 1—3 графіки дають можливість обирати параметри моделі, що роз-
глядається, таким чином, щоб поліпшити показники ефективності процесу обслуговування
вимог.
Рис. 1. Блокуюча ймовірність b і середнє число вимог на орбіті E[X2] в залежності від
: 1 — c 5, m 2, v 3, 7; 2 — c 5, m 2, v 2, 5; 3 — c 6, m 2, v 3, 5;
4 — c 6, m 4, v 3, 5
Рис. 2. Блокуюча ймовірність b і середнє число вимог на орбіті E[X2] в залежності
від : 1 — c 6, m 4, 5, 5; 2 — c 6, m 2, 5, 5; 3 — c 5, m 2, 5, 5;
4 — c 5, m 2, 5, 7
Рис. 3. Блокуюча ймовірність b і середнє число вимог на орбіті E[X2] в залежності від
: 1 — c 2, m 2, 2, v 2; 2 — c 2, m 3, 2, v 2; 3 — c 2, m 3, 2,5, v 2;
4 — c 3, m 3, 2,5, v 2
30 ISSN 1025-6415. Dopov. Nac. akad. nauk Ukr. 2020. № 7
Є.О. Лебєдєв, В.Д. Пономарьов
Висновки. У роботі представлено аналіз стаціонарного режиму для системи з пов тор-
ними викликами, яка складається з c обслуговуючих приладів, обмеженою чергою і по-
током повторних викликів з орбіти сталої інтенсивності. Отримано явні формули для ста-
ціонарних імовірностей через параметри моделі. У подальшому ці результати можуть бу ти
застосовані до більш детального вивчення моделі: обчислення показників ефективності
процесу обслуговування, розв’язку оптимізаційних задач.
ЦИТОВАНА ЛІТЕРАТУРА
1. Falin G.I. & Templeton J.G.C. Retrial queues. London: Chapman & Hall, 1997. 329 p.
2. Choi B.D., Shin Y.W. and Ahn W.C. Retrial queues with collision arising from unslotted CSMA/CD pro-
tocol. Queueing Systems. 1992. № 11. P. 335—356.
3. Avrachenkov K. and Yechiali U. Retrial networks with finite buffers and their application to internet data
traffic. Probability in the Eng. and Informat. Sci. 2008. 22. P. 519—536.
4. Avrachenkov K. U. Yechiali U. On tandem blocking queues with a common retrial queue. Computers &
Operations Research. 2010. 37. P. 1174—1180.
5. Artalejo J.R., Gomez-Corral A., Neuts M.F. Analysis of multiserver queues with constant retrial rate. Eur. J.
Operat. Research. 2001. 135. P. 569—581.
6. Neuts M.F. Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Baltimore:
The Johns Hopkins Univ. Press, 1981.
7. Do T.V., Chakka R. An efficient method to compute the rate matrix for retrial queues with large number
of servers. Appl. Math. Lett. 2010. 23. P. 638—643.
8. Artalejo J.R. Stationary analysis of the characteristics of the M/M/2 queue with constant repeated
attempts. Opsearch. 1996. 33. P. 83—95.
9. Gomez-Corral A., Ramalhoto M.F. The stationary distribution of a Markovian process arising in the theory
of multiserver retrial queueing systems. Math. and Computer Modelling. 1999. 30. P. 141—158.
10. Gomez-Corral A., Ramalhoto M.F. On the waiting time distribution and the busy period of a retrial queue
with constant retrial rate. Stochastic Modelling and Applications. 2000. 3 (2). P. 37—47.
11. Artalejo J.R., Gomez-Corral A. Retrial queueing systems. A computational approach. Berlin Heidelberg:
Springer, 2008. 317 p.
12. Уолрэнд Дж. Введение в теорию сетей массового обслуживания. Москва: Мир, 1993. 336 с.
13. Хорн Р., Джонсон Ч. Матричный анализ. Москва: Мир, 1989. 655 с.
Надійшло до редакції 16.04.2020
REFERENCES
1. Falin, G. I., Templeton, J. G. C. (1997). Retrial queues. London: Chapman & Hall.
2. Choi, B. D., Shin, Y. W. & Ahn W.C. (1992). Retrial queues with collision arising from unslotted CSMA/CD
protocol. Queueing Systems, No. 11. P. 335-356.
3. Avrachenkov, K. & Yechiali, U. (2008). Retrial networks with finite buffers and their application to internet
data traffic. Probability in the Eng. and Informat. Sci., 22, pp. 519-536.
4. Avrachenkov, K. U. & Yechiali, U. (2010). On tandem blocking queues with a common retrial queue. Com-
puters & Operations Research, 37, pp. 1174-1180.
5. Artalejo, J. R., Gomez-Corral, A. & Neuts, M. F. (2001). Analysis of multiserver queues with constant retrial
rate. Eur. J. Operat. Research., 135, pp. 569-581.
6. Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach. Baltimore:
The Johns Hopkins Univ. Press.
7. Do, T. V. & Chakka, R. (2010). An efficient method to compute the rate matrix for retrial queues with large
number of servers. Appl. Math. Lett., 23, pp. 638-643.
8. Artalejo, J. R. (1996). Stationary analysis of the characteristics of the M/M/2 queue with constant re-
peated attempts. Opsearch, 33, pp. 83-95.
31ISSN 1025-6415. Допов. Нац. акад. наук Укр. 2020. № 7
Стаціонарний режим для системи масового обслуговування типу M| M | c | c + m із сталою інтенсивністю...
9. Gomez-Corral, A. & Ramalhoto, M. F. (1999). The stationary distribution of a Markovian process arising in
the theory of multiserver retrial queueing systems. Math. and Computer Modelling, 30, pp. 141-158.
10. Gomez-Corral, A. & Ramalhoto, M. F. (2000). On the waiting time distribution and the busy period of a ret-
rial queue with constant retrial rate. Stochastic Modelling and Applications, 3 (2), pp. 37-47.
11. Artalejo, J. R. & Gomez-Corral, A. (2008). Retrial queueing systems. A computational approach. Berlin
Heidelberg: Springer.
12. Walrand, J. (1993). An introduction to queueing networks. Мoscow: Mir (in Russian).
13. Horn, R. & Johnson, C. (1989). Matrix analysis. Мoscow: Мir (in Russian).
Received 16.04.2020
E.A. Lebedev, V.D. Ponomarov
Taras Shevchenko National University of Kyiv
E-mail: leb@unicyb.kiev.ua
STATIONARY REGIME FOR A QUEUE
OF THE TYPE | | |M M c c m+ WITH CONSTANT RETRIAL RATE
A bivariate Markov process 1 2{ ( ) ( ( ), ( )) , 0}TX t X t X t t= � whose phase space is a lattice semistrip ( )S X =
{0,1, , }c m Z+= … + × is considered. The first component 1( ) {0,1, , }X t c m∈ … + indicates the summarized number
of busy servers and calls in the queue at the instant 0t� , whereas the second one 2( ) {0,1, }X t ∈ … is the number
of retrial sources. Parameter c Z+∈ is a number of servers and m Z∈ is a maximal size of the queue. Local rates of
( )X t are defined in such a way that ( )X t describes the service policy of a multi-server retrial queue in which the
rate of repeated flow does not depend on the number of sources of repeated calls.
First, using tools of the theory for the QBD-processes (quasi-birth-and-death processes), we study the
ergodicity conditions. Then, under these conditions, we consider a problem of finding the steady state probabilities
for ( )X t . A vector-matrix representation of the probabilities via the model parameters is obtained. The applied
technique uses an approximation of the initial model by a truncated one and the direct passage to the limit. The
obtained formulae are the adequate method to calculate the steady state probabilities.
An application of the main result is demonstrated via numerical examples in which we can see relation
graphs of the blocking probability and the average number of retrials versus system parameters.
Keywords: stationary regime, system with retrial calls, service process, ergodicity condition, truncated model, vector-
matrix representation.
|