M/M/1 retrial queueing model with variable service rate
UDC 519.21<br> The paper deals with queueing system of the type M/M/1 with repeated claims in the case where the service intensitydepends on the loading of the system, i.e., on the number of claims in the line to be served. We establish the existenceconditions and the formulas...
Збережено в:
| Дата: | 2020 |
|---|---|
| Автори: | , , , , , , , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Institute of Mathematics, NAS of Ukraine
2020
|
| Онлайн доступ: | https://umj.imath.kiev.ua/index.php/umj/article/view/813 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Репозитарії
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507110505185280 |
|---|---|
| author | Bratiichuk, M. S. Chechelnitsky , A. A. Usar, I. Ya. Братийчук, Н. С. Чечельницкий, А. А. Усар, И. Я. Братійчук, М . C. Чечельницький, О. А. Усар, I. Я. |
| author_facet | Bratiichuk, M. S. Chechelnitsky , A. A. Usar, I. Ya. Братийчук, Н. С. Чечельницкий, А. А. Усар, И. Я. Братійчук, М . C. Чечельницький, О. А. Усар, I. Я. |
| author_sort | Bratiichuk, M. S. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2022-03-26T11:01:29Z |
| description | UDC 519.21<br>
The paper deals with queueing system of the type M/M/1 with repeated claims in the case where the service intensitydepends on the loading of the system, i.e., on the number of claims in the line to be served. We establish the existenceconditions and the formulas for ergodic distribution of the number of claims in the system with bounded and unboundedlines of repeated claims. |
| doi_str_mv | 10.37863/umzh.v72i3.813 |
| first_indexed | 2026-03-24T02:04:06Z |
| format | Article |
| fulltext |
УДК 519.21
М. C. Братiйчук (Сiлез. ун-т технологiй, Польща),
О. А. Чечельницький, I. Я. Усар (Київ. нац. ун-т iм. Т. Шевченка)
СИСТЕМА \bfitM /\bfitM /\bfone З ПОВТОРНИМИ ВИМОГАМИ
ТА ЗМIННОЮ IНТЕНСИВНIСТЮ ОБСЛУГОВУВАННЯ
The paper deals with queueing system of the type M/M/1 with repeated claims in the case where the service intensity
depends on the loading of the system, i.e., on the number of claims in the line to be served. We establish the existence
conditions and the formulas for ergodic distribution of the number of claims in the system with bounded and unbounded
lines of repeated claims.
Розглядається система обслуговування типу M/M/1 з повторними вимогами, в якiй iнтенсивностi обслуговування
залежать вiд завантаження системи, тобто вiд кiлькостi вимог, якi знаходяться в черзi на обслуговування. Знай-
дено умови iснування та формули для ергодичного розподiлу кiлькостi вимог у системi у випадку скiнченної та
нескiнченної черги повторних вимог.
1. Вступ. Стандартну систему типу M/M/1/\infty з повторними вимогами можна описати таким
чином. Система складається з oдного обслуговуючого приладу. Вхiдний потiк пуассонiвський
з iнтенсивнiстю \lambda . Вимога, яка надiйшла в систему i знайшла прилад вiльним, негайно надхо-
дить на обслуговування, а пiсля обслуговування залишає систему. Якщо ж прилад зайнятий, то
ця вимога стає повторною i надходить на так звану орбiту. Кожна вимога, яка знаходиться на
орбiтi, через iнтервали часу з показниковим розподiлом з параметром \nu i незалежно вiд iнших
вимог, якi в цей час є на орбiтi, намагається потрапити на обслуговування, i якщо в момент
звернення обслуговуючий пристрiй вiльний, то ця вимога надходить на обслуговування. В iн-
шому випадку вона повертається на орбiту i процес повторюється. Таким чином, кожна вимога,
яка знаходиться на орбiтi, генерує пуассонiвський потiк повторних вимог iнтенсивностi \nu . Час
обслуговування кожної вимоги має показниковий розподiл. Параметр цього розподiлу визнача-
ється таким чином: якщо в момент, коли вимога (з орбiти чи та, що щойно надiйшла) потрапляє
на обслуговування i в цей момент в системi знаходиться j вимог (зрозумiло, що j = i + 1,
де i позначає кiлькiсть вимог на орбiтi), то параметр розподiлу часу її обслуговування буде
\mu j . Змiна iнтенсивностi обслуговування вiдбувається лише в моменти, коли вимога попадає на
обслуговуючий пристрiй.
Таким чином, на вiдмiну вiд традицiйних систем (див. [1, 2]) маємо ситуацiю, коли час об-
слуговування залежить вiд кiлькостi вимог у системi. Математичнi моделi систем iз повторними
викликами мають широке застосування у практицi (див. [3, 4]).
Необхiднiсть вивчати моделi, параметри яких залежать вiд кiлькостi замовлень у системi,
пов’язана з економiчними аспектами роботи таких систем. У конкретних системах ми часто
не можемо впливати на iнтенсивнiсть надходження замовлень, але можемо змiнювати iнтен-
сивнiсть роботи сервера в залежностi вiд кiлькостi замовлень у системi. Тому в залежностi
вiд кiлькостi тих замовлень менеджер може динамiчно керувати полiтикою обслуговування,
покращуючи її економiко-цiновi характеристики. Так, в роботi [5] описано модель, в якiй iн-
тенсивнiсть обслуговування змiнюється, якщо черга досягає певного рiвня T. Це є так звана
порогова стратегiя. Подiбнi схеми розглядалися, наприклад, у роботах [6 – 8]. Метод знахо-
дження ергодичних iмовiрностей для систем iз пороговою стратегiєю полягав у тому (див.,
c\bigcirc М. C. БРАТIЙЧУК, О. А. ЧЕЧЕЛЬНИЦЬКИЙ, I. Я. УСАР, 2020
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3 355
356 М. C. БРАТIЙЧУК, О. А. ЧЕЧЕЛЬНИЦЬКИЙ, I. Я. УСАР
наприклад, [8]), що рiвняння для ергодичних iмовiрностей спочатку розв’язувалися на множи-
нах станiв \{ 0, 1, . . . , T - 1\} i \{ T, T + 1, . . .\} , пiсля чого вiдбувалося „склеювання” розв’язкiв
на межi i = T. У випадку бiльшої кiлькостi порогiв, на яких вiдбувається змiна iнтенсивностi
обслуговування (а така необхiднiсть часто з’являється в конкретних моделях), такий метод стає
громiздким та неефективним.
Мета цiєї статтi — вияснити умови iснування ергодичного розподiлу описаної вище системи,
запропонувати метод дослiдження i знайти точнi формули для цього розподiлу.
2. Математична модель. Зазвичай, дослiдження системи обслуговування розпочинається
з опису її функцiонування за допомогою марковського процесу. Так, коли б в описанiй вище
системi iнтенсивнiсть обслуговування була сталою, тобто \mu i = \mu = \mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}, то цей опис виглядав
би таким чином (див. [2]). Нехай \xi (t) позначає кiлькiсть вимог, яка є на орбiтi в момент часу
t, а \eta (t) визначає стан приладу в цей момент часу: якщо прилад вiльний, то \eta (t) = 0, а якщо
прилад зайнятий обслуговуванням вимоги, то \eta (t) = 1. Двокомпонентний процес (\eta (t), \xi (t)) є
однорiдним марковським процесом iз простором станiв S = \{ (i, j), i = 0, 1, j = 0, 1, 2, . . .\} .
У випадку, коли iнтенсивнiсть обслуговування залежить вiд кiлькостi вимог у системi, на
вiдмiну вiд [2], процес (\eta (t), \xi (t)) вже не буде марковським, але ми можемо зробити його
таким, надавши iнший змiст випадковому процесу \eta (t).
Нехай, як i ранiше, \xi (t) позначає кiлькiсть вимог, яка є на орбiтi в момент часу t. Якщо в
момент часу t обслуговуючий прилад зайнятий обслуговуванням i iнтенсивнiсть цього обслу-
говування є \mu i, i \geq 1, то говоримо, що обслуговуючий прилад знаходиться в режимi i. Якщо ж
в момент часу t обслуговуючий прилад вiльний, то говоримо, що вiн перебуває в режимi i = 0.
Нехай тепер \eta (t) \in \{ 0, 1, 2, . . .\} позначає режим обслуговуючого пристрою в момент часу t.
Зрозумiло, що якщо \xi (t) = i \geq 0, а \eta (t) = 0, то в системi в момент часу t є i вимог,
всi вони знаходяться на орбiтi, а обслуговуючий пристрiй вiльний. А якщо \xi (t) = i \geq 0,
\eta (t) \geq 1, то в системi в момент часу t є i + 1 вимога: одна на обслуговуваннi та i вимог на
орбiтi. Легко зрозумiти, що тепер (\eta (t), \xi (t)) є однорiдним марковським процесом iз фазовим
простором E = \{ (i, j), i \geq 0, j \geq \mathrm{m}\mathrm{a}\mathrm{x}(0, i - 1)\} (див. пояснення нижче). На рис. 1 побудовано
граф iнтенсивностей переходiв цього процесу.
Наведемо деякi пояснення до цього рисунка.
1. Нехай у певний момент часу t = \tau сервер прийняв замовлення на обслуговування i
\xi (\tau - 0) = j \geq 1. Якщо це замовлення не з орбiти, то \eta (\tau ) = j + 1, \xi (\tau ) = j. Якщо ж воно
попало на сервер з орбiти, то \eta (\tau ) = j, \xi (\tau ) = j - 1. Отже, завжди \xi (t) \geq \eta (t) - 1. Звiдси
випливає, що фазовим простором процесу (\eta (t), \xi (t)) є E = \{ (i, j), i \geq 0, j \geq \mathrm{m}\mathrm{a}\mathrm{x}(0, i - 1)\} .
2. Iз стану (0, j) процеc (\eta (t), \xi (t)) може перейти в стан (j + 1, j) (якщо на сервер попала
вимога не з орбiти), i iнтенсивнiсть цього переходу є \lambda , або в стан (j, j - 1) (якщо на сервер
попала вимога з орбiти), i iнтенсивнiсть цього переходу єj\nu . Подiбним чином можна пояснити
iншi переходи на рис. 1.
Ми будемо говорити, що процес (\eta (t), \xi (t)) є ергодичним, якщо iснують границi
\pi ij = \mathrm{l}\mathrm{i}\mathrm{m}
t\rightarrow \infty
\bfP \{ \eta (t) = i, \xi (t) = j/\eta (0) = k, \xi (t) = l)\} > 0
для довiльних i, j, k, l \geq 0, i
\sum
ij
\pi ij = 1.
3. Умова ергодичностi.
Теорема 1. Якщо \mathrm{l}\mathrm{i}\mathrm{m}j\rightarrow \infty
\lambda
\mu j
= q < 1, то процес (\eta (t), \xi (t)) є ергодичним.
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
СИСТЕМА M/M/1 З ПОВТОРНИМИ ВИМОГАМИ ТА ЗМIННОЮ IНТЕНСИВНIСТЮ . . . 357
орбiтi. Легко зрозумiти, що тепер (η(t), ξ(t)) є однорiдним марковським
процесом з фазовим простором E = {(i, j), i ≥ 0, j ≥ max(0, i−1)} (див.
пояснення нижче). На рис.1 побудовано граф iнтенсивностей переходiв
цього процесу.
✻ξ(t)
✲!
η(t)
(0, j) !###############$
jν
❥ (j + 1, j)!
λ
(j, j−1)
µj
■
(0, j−1)! !
(i, j)
µi
■
!
✻
(i, j+1) !
λ
✻
(i, j−1) !
λ
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
''
❘
■
λ
µ1
(1,0)
Рис.1
Декiлька пояснень до цього рисунку.
1. Нехай в певний момент часу t = τ сервер прийняв замовлення на
обслуговування i ξ(τ −0) = j ≥ 1. Якщо це замовлення не з орбiти,
то η(τ) = j + 1, ξ(τ) = j. Якщо ж це замовлення попало на сервер
з орбiти, то η(τ) = j, ξ(τ) = j − 1. Отже, завжди ξ(t) ≥ η(t) − 1 .
Звiдси i випливає, що фазовим простором процесу (η(t), ξ(t)) є E =
{(i, j), i ≥ 0, j ≥ max(0, i − 1)}.
2. З стану (0, j) процеc (η(t), ξ(t)) може перейти в стан (j+1, j) (якщо
на сервер попала вимога не з орбiти), i iнтенсивнiсть цього переходу
є λ, або в стан (j, j − 1) (якщо на сервер попала вимога з орбiти), i
iнтенсивнiсть цього переходу єjν . Подiбним чином можна пояснити
iншi переходи на поданому вище рисунку.
Ми будемо говорити, що процес (η(t), ξ(t)) , є ергодичним якщо iсну-
ють границi
πij = lim
t→∞
P{η(t) = i, ξ(t) = j/η(0) = k, ξ(t) = l)} > 0,
5
Рис. 1
Для доведення цiєї теореми використовується такий результат [2, с. 97].
Теорема 2. Нехай \xi (t) є марковським процесом iз простором станiв S = \{ 0, 1, 2, . . .\} та
iнтенсивностями переходiв qij , i, j \in S, такими, що
\sum \infty
j=0
qij = 0 для довiльних i \in S. Нехай
iснує числова функцiя \varphi (i), i \in S, така, що:
i) \mathrm{i}\mathrm{n}\mathrm{f}i\in S \varphi (i) > - \infty i
\sum
j \not =i
qij (\varphi (j) - \varphi (i)) < \infty , i \in S;
ii) для деякого \varepsilon > 0 має мiсце нерiвнiсть
\sum
j \not =i
qij (\varphi (j) - \varphi (i)) < - \varepsilon для всiх i \in S, за
винятком можливо їх скiнченної кiлькостi.
Тодi процес \xi (t) є ергодичним.
Зауваження 1. Функцiю \varphi (\cdot ), про яку йдеться в теоремi 2, називають тест-функцiєю.
Доведення теореми 1. В якостi тест-функцiї \varphi (\cdot , \cdot ) вiзьмемо функцiю \varphi (i, j) = j - a
i+ 1
,
де a \in (q, 1). Нехай q
(k,l)
(i,j) позначає iнтенсивнiсть переходу процесу (\eta (t), \xi (t)) зi стану (i, j)
у стан (k, l). Тепер для стану (i, j), 1 \leq i \leq j + 1, використовуючи наведений вище граф
переходiв, маємо
\sum
(k,l)\not =(i,j)
q
(k,l)
(i,j) (\varphi (k, l) - \varphi (i, j)) = q
(0,j)
(i,j) (\varphi (0, j) - \varphi (i, j))+
+q
(i,j+1)
(i,j) (\varphi (i, j + 1) - \varphi (i, j)) = \mu i
\biggl(
j - a - j +
a
i+ 1
\biggr)
+ \lambda (j + 1 - j) =
= \mu i
\biggl(
\lambda
\mu i
- ia
i+ 1
\biggr)
. (1)
Аналогiчно для стану (0, j), j \geq 1, отримуємо
\sum
(k,l) \not =(0,j)
q
(k,l)
(0,j) (\varphi (k, l) - \varphi (0, j)) = q
(j,j - 1)
(0,j) (\varphi (j, j - 1) - \varphi (0, j))+
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
358 М. C. БРАТIЙЧУК, О. А. ЧЕЧЕЛЬНИЦЬКИЙ, I. Я. УСАР
+q
(j+1,j)
(0,j) (\varphi (j + 1, j) - \varphi (0, j)) = j\nu
\biggl(
a - 1 - a
j + 1
\biggr)
+ \lambda
\biggl(
a - a
j + 2
\biggr)
<
< j\nu (a - 1) + \lambda . (2)
Iз спiввiдношень (1), (2) випливає, що для всiх достатньо великих i, j та деякого \varepsilon > 0 маємо
\sum
(k,l)\not =(i,j)
(\varphi (k, l) - \varphi (i, j)) < - \varepsilon ,
що i завершує доведення теореми.
4. Формули для ергодичного розподiлу. Опишемо тепер спосiб, який часто буває ко-
рисним при написаннi рiвнянь рiвноваги для ергодичного розподiлу марковського процесу.
Розглянемо ергодичний марковський процес \xi (t) з дискретним фазовим простором S, iнтен-
сивностями переходiв aij , i, j \in S, i нехай \pi i позначає його ергодичний розподiл. Нехай
S = S1 \cup S2, S1, S2 \not = \varnothing i S1 \cap S2 = \varnothing . Величину
\sum
S1\rightarrow S2
aij\pi i, де
\sum
S1\rightarrow S2
означає, що
додавання вiдбувається лише для тих пар iндексiв (i, j), i \in S1, j \in S2, для яких перехiд зi
стану i в стан j є можливим, називаємо потоком iмовiрностей iз множини S1 у множину S2.
Тодi [9]
\sum
S1\rightarrow S2
aij\pi i =
\sum
S2\rightarrow S1
aij\pi i. (3)
Введемо такi позначення:
\kappa = - \lambda /\nu , \beta i = \lambda /(\lambda + \mu i). (4)
Теорема 3. Якщо \mathrm{l}\mathrm{i}\mathrm{m}j\rightarrow \infty \lambda /\mu j < 1, то для процесу (\eta (t), \xi (t)) iснує ергодичний розподiл,
який можна записати у виглядi
\pi 00 =
\Biggl(
1 +
\infty \sum
i=1
b(i)Ai
\Biggr) - 1
, \pi 0j = \pi 00
\lambda
j\nu
j\sum
k=1
\beta j - k
k Ak
(k - 1)!\mu k
, j \geq 1,
\pi ij = \pi 00
\beta j - i+1
i Ai
(i - 1)!\mu i
, j \geq i - 1, i \geq 1,
де
Ai = - \nu
i\sum
k=1
\kappa kH(k, i - k),
b(i) =
1
(i - 1)!\mu i
\Biggl[
\lambda + \mu i
\mu i
+
\kappa
\beta i
i
\Biggl(
\mathrm{l}\mathrm{n}(1 - \beta i) +
i - 1\sum
k=1
\beta k
i
k
\Biggr) \Biggr]
,
а функцiя H(i, k) визначається у процесi доведення теореми.
Доведення. Отже, нехай для процесу (\eta (t), \xi (t)) ергодичний розподiл \pi ij iснує, тобто умова
\mathrm{l}\mathrm{i}\mathrm{m}j\rightarrow \infty
\lambda
\mu j
= q < 1 виконується. Використовуючи рис. 1 та правило (3), записуємо сиcтему
рiвнянь рiвноваги для ергодичного розподiлу
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
СИСТЕМА M/M/1 З ПОВТОРНИМИ ВИМОГАМИ ТА ЗМIННОЮ IНТЕНСИВНIСТЮ . . . 359
j\nu \pi 0j = \lambda
j\sum
i=1
\pi ij - 1, j \geq 1,
\pi ij(\lambda + \mu i) = \lambda \pi ij - 1, j \geq i \geq 1,
\pi jj - 1(\lambda + \mu j) = \lambda \pi 0j - 1 + j\nu \pi 0j , j \geq 1,
\pi 00\lambda = \mu 1\pi 10.
(5)
Наведемо пояснення до цiєї системи рiвнянь. При фiксованому j \geq 1 вiдрiзок, який з’єднує
точки (0, j), (j+1, j) (див. рис. 1), дiлить простiр станiв E процесу (\eta (t), \xi (t)) на двi частини:
E1 = \{ (k, l) : 0 \leq k \leq j,\mathrm{m}\mathrm{a}\mathrm{x}(0, k - 1) \leq l \leq j - 1\} i E2 = \{ (k, l) : 0 \leq k,\mathrm{m}\mathrm{a}\mathrm{x}(j, k - 1) \leq l\} .
Потiк iмовiрностей iз множини E2 у множину E1 дорiвнює j\nu \pi 0j , а з множини E1 у множину
E2 — \lambda
\sum j
i=1
\pi ij - 1. Прирiвнюючи цi потоки, отримуємо перше рiвняння iз (5). Решту рiвнянь
одержуємо, прирiвнюючи потоки ймовiрностей у стани (i, j), j \geq i \geq 1, (j, j - 1), j \geq 1, i
(0, 0) та з них.
Iз другого та третього рiвнянь системи (5), враховуючи позначення (4), маємо
\pi ij = \beta i\pi ij - 1 = \beta j - i+1
i \pi ii - 1 = \beta j - i+1
i
\biggl(
\lambda
\lambda + \mu i
\pi 0i - 1 +
i\nu
\lambda + \mu i
\pi 0i
\biggr)
=
= \beta j - i+2
i
\biggl(
\pi 0i - 1 +
i\nu
\lambda
\pi 0i
\biggr)
, j \geq i \geq 1.
Якщо ж взяти до уваги третє рiвняння в (5), то можемо записати
\pi ij = \beta j - i+2
i
\biggl(
\pi 0i - 1 +
i\nu
\lambda
\pi 0i
\biggr)
, j \geq i - 1, i \geq 1. (6)
Використовуючи тепер вираз для \pi ij у першому рiвняннi системи (5), маємо
j\nu \pi 0j = \lambda
j\sum
i=1
\pi ij - 1 =
j\sum
i=1
\beta j - i+1
i (\lambda \pi 0i - 1 + i\nu \pi 0i) , j \geq 1,
а якщо позначити
\rho i =
(i - 1)!\mu i
(\lambda + \mu i)
(\lambda \pi 0i - 1 + i\nu \pi 0i) , i \geq 1, (7)
то останню рiвнiсть можна записати так:
j\nu \pi 0j =
j\sum
i=1
(\lambda + \mu i)\beta
j - i+1
i
(i - 1)!\mu i
\rho i. (8)
Записуючи (7) у виглядi
\lambda \pi 0i - 1 + i\nu \pi 0i =
\lambda + \mu i
(i - 1)!\mu i
\rho i i \geq 1, (9)
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
360 М. C. БРАТIЙЧУК, О. А. ЧЕЧЕЛЬНИЦЬКИЙ, I. Я. УСАР
отримуємо сиcтему рiвнянь для \pi 0i вiдносно \rho i. Нехай i \leq m < \infty , де m є фiксованим. Якщо
позначити
Am =
\left(
\nu 0 0 . . . 0
\lambda 2\nu 0 . . . 0
. . . . . . . . . . . . . . .
0 0 \lambda . . . m\nu
\right)
, \vec{}\rho (m) =
\left(
(\lambda + \mu 1)\rho 1
\mu 1
(\lambda + \mu 2)\rho 2
\mu 2
(\lambda + \mu 3)\rho 3
2\mu 3
. . .
(\lambda + \mu m)\rho m
(m - 1)!\mu m
\right)
,
\vec{}e(1) =
\left(
1
0
0
. . .
0
\right)
, \vec{}\pi (m) =
\left(
\pi 01
\pi 02
\pi 03
. . .
\pi 0m
\right)
,
то систему рiвнянь (9) з 1 \leq i \leq m можна записати в матричнiй формi
Am\vec{}\pi (m) = \vec{}\rho (m) - \lambda \pi 00\vec{}e(1). (10)
Легко показати, що
A - 1
m = (\alpha kj), \alpha kj =
\kappa k - j
\nu
\prod k - j
l=0
(j + l)
I\{ j \leq k\} ,
а тому з (10) одержуємо
\pi 0j =
1
j!\nu
j\sum
i=1
\kappa j - i(\lambda + \mu i)
\mu i
\rho i + \pi 00
\kappa j
j!
.
Враховуючи (8), маємо
\rho j =
j - 1\sum
i=1
\lambda + \mu i
\mu i
\Biggl[
\beta j - i+1
i
j - i - 1\prod
k=0
(i+ k) - \kappa j - i
\Biggr]
\rho i + \pi 00\lambda \kappa
j - 1. (11)
Позначимо
a(i, l) =
\lambda + \mu i
\mu i
\Biggl[
\beta l+1
i
l - 1\prod
k=0
(i+ k) - \kappa l
\Biggr]
, Cj = \pi 00\lambda \kappa
j - 1.
Тепер (11) можемо записати у виглядi
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
СИСТЕМА M/M/1 З ПОВТОРНИМИ ВИМОГАМИ ТА ЗМIННОЮ IНТЕНСИВНIСТЮ . . . 361
\rho j =
j - 1\sum
i=1
a(i, j - i)\rho i + Cj , j \geq 1. (12)
Для послiдовностi a(i, k), i, k \geq 1, означимо „згортку” таким чином:
a\ast n(i, l) =
l - n+1\sum
k=1
a(i, k)a\ast (n - 1)(i+ k, l - k), a\ast 1(i, l) = a(i, l), 1 \leq n \leq l,
i нехай
H(i, l) =
l\sum
k=1
a\ast k(i, l), l \geq 0, H(i, 0) = 1.
Наведемо допомiжне твердження, необхiдне для подальшого викладу, коротке доведення якого
див. у додатку.
Лема 1. Розв’язок рiвняння (12) можна записати у виглядi
\rho j =
j\sum
i=1
CiH(i, j - i), j \geq 1.
З леми 1 та означення Cj маємо
\rho j = \lambda \pi 00
j\sum
k=1
\kappa k - 1H(k, j - k) = \pi 00Aj . (13)
Iз спiввiдношень (6) – (8) випливає, що справджуються рiвнocтi
\pi ij =
\beta j - i+1
i
(i - 1)!\mu i
\rho i, j \geq i - 1, i \geq 1, \pi 0j =
\lambda
j\nu
j\sum
k=1
\beta j - k
k
(k - 1)!\mu k
\rho k, j \geq 1. (14)
Використовуючи цi рiвностi, пiсля нескладних перетворень маємо
\infty \sum
i=1
\infty \sum
j=i - 1
\pi ij +
\infty \sum
j=1
\pi 0j =
\infty \sum
i=1
\infty \sum
j=i - 1
\beta j - i+1
i
(i - 1)!\mu i
\rho i +
\lambda
\nu
\infty \sum
j=1
1
j
j\sum
i=1
\beta j - i
i
(i - 1)!\mu i
\rho i =
=
\infty \sum
i=1
\lambda + \mu i
(i - 1)!\mu 2
i
\rho i -
\lambda
\nu
\infty \sum
i=1
\rho i
(i - 1)!\mu i\beta i
i
\Biggl[
\mathrm{l}\mathrm{n}(1 - \beta i) +
i - 1\sum
k=1
\beta k
i
k
\Biggr]
=
\infty \sum
i=1
b(i)\rho i,
де
b(i) =
1
(i - 1)!\mu i
\Biggl[
\lambda + \mu i
\mu i
+
\kappa
\beta i
i
\Biggl(
\mathrm{l}\mathrm{n}(1 - \beta i) +
i - 1\sum
k=1
\beta k
i
k
\Biggr) \Biggr]
.
Iз формули (13) та умови нормування отримуємо
1 = \pi 00 +
\infty \sum
i=1
\infty \sum
j=i - 1
\pi ij +
\infty \sum
j=1
\pi 0j = \pi 00 + \pi 00
\infty \sum
i=1
b(i)Ai,
а отже,
\pi 00 =
\Biggl(
1 +
\infty \sum
i=1
b(i)Ai
\Biggr) - 1
. (15)
Формули (13) – (15) завершують доведення теореми.
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
362 М. C. БРАТIЙЧУК, О. А. ЧЕЧЕЛЬНИЦЬКИЙ, I. Я. УСАР
5. Система з обмеженою орбiтою. Якщо кiлькiсть мiсць для чекання на орбiтi обмежено,
наприклад, числом m < \infty , то умови iснування ергодичного розподiлу виконуються автома-
тично. Граф iнтенсивностей переходiв для станiв \{ (i, j) : 0 \leq i \leq m, \mathrm{m}\mathrm{a}\mathrm{x}\{ 0, i - 1\} \leq j \leq
\leq m - 1\} \cup \{ (0,m)\} буде таким же, як i у випадку необмеженої орбiти, а тому маємо таку
систему рiвнянь для ергодичного розподiлу цих станiв:
j\nu \pi 0j = \lambda
j\sum
i=1
\pi ij - 1, 1 \leq j \leq m,
\pi ij(\lambda + \mu i) = \lambda \pi ij - 1, 1 \leq i \leq j \leq m - 1,
\pi jj - 1(\lambda + \mu j) = \lambda \pi 0j - 1 + j\nu \pi 0j , 1 \leq j \leq m - 1,
\pi 00\lambda = \mu 1\pi 10.
(16)
Для станiв \{ (i,m) : 0 \leq i \leq m+ 1\} граф iнтенсивностей переходiв зображено на рис. 2.
необмеженої орбiти, а тому маємо таку систему рiвнянь для ергодичного
розподiлу цих станiв:
⎧
⎪⎪⎪⎪⎪⎪⎪⎪⎨
⎪⎪⎪⎪⎪⎪⎪⎪⎩
jνπ0j = λ
∑j
i=1 πij−1, 1 ≤ j ≤ m,
πij(λ + µi) = λπij−1, 1 ≤ i ≤ j ≤ m − 1,
πjj−1(λ + µj) = λπ0j−1 + jνπ0j, 1 ≤ j ≤ m − 1.
π00λ = µ1π10.
(16)
Для станiв {(i, m) : 0 ≤ i ≤ m+1} граф iнтенсивностей переходiв зобра-
жено на рис.2.
(0, m)! !(m + 1, m)❥"""""""""""""""#
mν
λ
µi
(m, m−1)!
(i, m)✛
µm+1
■
!
!
✻
(i, m−1)
λ
Рис.2
Вiдмiннiсть вiд рис.1 полягає лише в тому, що тепер перехiд зi стану
(i, m) можливий лише до стану (0, m) (коли закiнчиться обслуговування)
i iнтенсивнiсть цього переходу є µi .
Звiдси, в доповнення до системи рiвнянь (16), маємо
⎧
⎨
⎩
πimµi = πim−1λ, 1 ≤ i ≤ m,
πm+1mµm+1 = π0mλ.
(17)
12
Рис. 2
Вiдмiннiсть вiд рис. 1 полягає лише в тому, що тепер перехiд зi стану (i,m) можливий лише
у стан (0,m) (коли закiнчиться обслуговування) i iнтенсивнiсть цього переходу є \mu i.
Звiдси, як доповнення до системи рiвнянь (16), маємо
\pi im\mu i = \pi im - 1\lambda , 1 \leq i \leq m,
\pi m+1m\mu m+1 = \pi 0m\lambda .
(17)
Точно так само, як i в попередньому пунктi, приходимо до формул
\pi ij =
\beta j - i+1
i
(i - 1)!\mu i
\rho i, i - 1 \leq j \leq m - 1, i \geq 1, (18)
\pi 0j =
\lambda
j\nu
j\sum
i=1
\beta j - i
i
(i - 1)!\mu i
\rho i, 1 \leq j \leq m. (19)
Тепер iз системи (17) та спiввiдношень (18), (19) отримуємо
\pi im =
\lambda \beta m - i
i
(i - 1)!\mu 2
i
\rho i, 1 \leq i \leq m, \pi m+1m =
\lambda 2
m\nu \mu m+1
m\sum
i=1
\beta m - i
i
(i - 1)!\mu i
\rho i. (20)
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
СИСТЕМА M/M/1 З ПОВТОРНИМИ ВИМОГАМИ ТА ЗМIННОЮ IНТЕНСИВНIСТЮ . . . 363
З формул (18) – (20) пiсля нескладних перетворень знаходимо
m+1\sum
i=1
m\sum
j=i - 1
\pi ij +
m\sum
j=1
\pi 0j =
m\sum
i=1
m - 1\sum
j=i - 1
\pi ij +
m\sum
i=1
\pi im + \pi m+1m +
m\sum
j=1
\pi 0j =
=
m\sum
i=1
\rho i
(i - 1)!\mu i
m - 1\sum
j=i - 1
\beta j - i+1
i + \lambda
m\sum
i=1
\beta m - i
i
(i - 1)!\mu 2
i
\rho i +
\lambda 2
m\nu \mu m+1
m\sum
i=1
\beta m - i
i
(i - 1)!\mu i
\rho i+
+
\lambda
\nu
m\sum
j=1
1
j
j\sum
i=1
\beta j - i
i
(i - 1)!\mu i
\rho i =
m\sum
i=1
d(i,m)\rho i,
де
d(i,m) =
1
(i - 1)!\mu i
\left[
\lambda + \mu i
\mu i
+
\lambda 2\beta m - i
i
m\nu \mu m+1
- \kappa
m - i\sum
j=0
\beta j
i
j + i
\right]
.
Використовуючи формулу (13) та умову нормування, маємо
1 = \pi 00 +
m+1\sum
i=1
m\sum
j=i - 1
\pi ij +
m\sum
j=1
\pi 0j = \pi 00 + \pi 00
m\sum
i=1
d(i,m)Ai,
а отже,
\pi 00 =
\Biggl(
1 +
m\sum
i=1
d(i,m)Ai
\Biggr) - 1
.
Звiдси та з формул (18) – (20) випливає такий результат.
Теорема 4. Якщо m < \infty — кiлькiсть мiсць для очiкування на орбiтi, то ергодичний
розподiл для процесу (\eta (t), \xi (t)) можна записати у виглядi
\pi 00 =
\Biggl(
1 +
m\sum
i=1
d(i,m)Ai
\Biggr) - 1
, \pi m+1m = \pi 00
\lambda 2
m\mu m+1
m\sum
i=1
\beta m - i
i Ai
\nu (i - 1)!\mu i
,
\pi 0j = \pi 00
\lambda
j\nu
j\sum
i=1
\beta j - i
i Ai
(i - 1)!\mu i
, 1 \leq j \leq m, \pi im = \pi 00
\lambda \beta m - i
i Ai
(i - 1)!\mu 2
i
, 1 \leq i \leq m,
\pi ij = \pi 00
\beta j - i+1
i Ai
(i - 1)!\mu i
, i - 1 \leq j \leq m - 1, i \geq 1,
де
d(i,m) =
1
(i - 1)!\mu i
\left[
\lambda + \mu i
\mu i
+
\lambda 2\beta m - i
i
m\nu \mu m+1
- \kappa
m - i\sum
j=0
\beta j
i
j + i
\right]
.
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
364 М. C. БРАТIЙЧУК, О. А. ЧЕЧЕЛЬНИЦЬКИЙ, I. Я. УСАР
На перший погляд спiввiдношення (16), (17) разом з умовою нормування складають систему
лiнiйних рiвнянь для змiнних \pi ij , яку можна розв’язати вiдомими числовими методами. Але
очевидна перевага формул з теореми 4 полягає в тому, що функцiї H(i, j) не залежать вiд
числа мiсць на орбiтi, а тому, якщо ергодичний розподiл для конкретного m пiдраховано, при
необхiдностi отримати цей розподiл для m + 1 нам не потрiбно рахувати заново цi функцiї.
Досить буде обчислити лише H(m + 1, k), k = 1, 2, . . . ,m. Також при пiдрахунку значення
d(i,m) основна обчислювальна робота ( для великих m) полягає у знаходженнi сум
\sum m - i
j=0
.
Але якщо скористатися рекурентною формулою
d(i,m+ 1) =
\left\{
d(i,m) +
\lambda \beta m - i
i
\nu (i+ 1)!\mu i
\biggl[
\beta i
m+ 1
\biggl(
1 +
\lambda
\mu m+2
\biggr)
- \lambda
m\mu m+1
\biggr]
, 1 \leq i \leq m,
1
m!\mu m+1
\biggl[
\lambda + \mu m+1
\mu m+1
+
\lambda
\nu (m+ 1)
\biggl(
1 +
\lambda
\mu m+2
\biggr) \biggr]
, i = m+ 1,
то можна значно скоротити об’єм обчислень.
Додаток. Доведення леми 1. Нехай j \geq 1 буде фiксованим. Покажемо, що для всiх 1 \leq
\leq k \leq j справджується рiвнiсть
\rho j =
j - k\sum
i=1
\rho ia
\ast k(i, j - i) +
k - 1\sum
l=1
j - k+l\sum
i=1
a\ast (k - l)(i, j - i)Ci + Cj . (21)
Для k = 1 рiвнiсть (21) збiгається з рiвнянням (12), а отже, є справедливою.
Припустимо, що вона справедлива для k = m < j, i покажемо, що вона справедлива i для
k = m+ 1. Використовуючи (12), маємо
\rho j =
j - m\sum
i=1
a\ast m(i, j - i)
\Biggl[
i - 1\sum
l=1
a(l, i - l)\rho l + Ci
\Biggr]
+
m - 1\sum
l=1
j - m+l\sum
i=1
a\ast (m - l)(i, j - i)Ci + Cj =
=
j - m - 1\sum
l=1
\rho l
j - l - m\sum
i=1
a(l, i)a\ast m(l + i, j - l - i) +
m\sum
l=1
j - m+l - 1\sum
i=1
a\ast (m+1 - l)(i, j - i)Ci + Cj =
=
j - m - 1\sum
l=1
\rho la
\ast (m+1)(l, j - l) +
m\sum
l=1
j - m - 1+l\sum
i=1
a\ast (m+1 - l)(i, j - i)Ci + Cj .
Записуючи тепер (21) для k = j - 1 i враховуючи, що \rho 1 = C1 (це виникає з рiвняння (12)),
маємо
\rho j = \rho 1a
\ast (j - 1)(1, j - 1) +
j - 2\sum
l=1
l+1\sum
i=1
a\ast (j - 1 - l)(i, j - i)Ci + Cj =
= C1a
\ast (j - 1)(1, j - 1) +
j - 1\sum
l=2
l\sum
i=1
a\ast (j - l)(i, j - i)Ci + Cj =
=
j - 1\sum
l=1
l\sum
i=1
a\ast (j - l)(i, j - i)Ci + Cj =
j - 1\sum
i=1
j - i\sum
l=1
a\ast l(i, j - i)Ci + Cj =
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
СИСТЕМА M/M/1 З ПОВТОРНИМИ ВИМОГАМИ ТА ЗМIННОЮ IНТЕНСИВНIСТЮ . . . 365
=
j - 1\sum
i=1
H(i, j - i)Ci + Cj =
j\sum
i=1
H(i, j - i)Ci,
що i завершує доведення леми 1.
Лiтература
1. J. R. Artalejo, A. Gomes-Corral, Retrial queueing systems, Comput. Approach, Springer Verlag (2008).
2. G. I. Falin, J. G. C. Templeton, Retrial queues, Chapman & Hall, London (1997).
3. V. V. Anisimov, J. R. Artalejo, Analysis of Markov multiserver retrial queues with negative arrivals, Queueing Syst.,
39, 157 – 182 (2001).
4. E. A. Lebedev, I. A. Makushenko, H. V. Livinska, I. Ya. Usar, On steady-state analysis of [M | M | m| m + n]-type
retrial queueing systems, Inform. Technol. and Math. Modelling, Queueing Theory and Appl., Commun. Comput. and
Inform. Sci., 800, 133 – 146 (2017).
5. D. Gross, J. F. Shortle, J. M. Thompson, C. M. Harris, Fundamental of queueing theory, John Wiley and Sons, Inc.,
New Jersey (2008).
6. A. Economu, S. Kanta, Equilibrium balking strategies in the observable single-server queue with breakdowns and
repairs, Oper. Res. Lett., 36, 696 – 699 (2008).
7. В. И. Клименок, Оптимизация динамического управления режимом работы информационно-вычислительных
систем с повторными вызовами, Автоматика и вычислит. техника, № 1, 25 – 30 (1990).
8. Z. Xuelu, W. Jinting, M. Qing, Optimal design for a retrial queueing system with state-dependent service rate, J.
Systems Sci. and Complexity, 30, 883 – 900 (2017).
9. J. Warland, An introduction to queueing networks, Prentice Hall (1988).
Одержано 16.04.19
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 3
|
| id | umjimathkievua-article-813 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2026-03-24T02:04:06Z |
| publishDate | 2020 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/26/ac5c455bfef8a62fc1159b158c928c26.pdf |
| spelling | umjimathkievua-article-8132022-03-26T11:01:29Z M/M/1 retrial queueing model with variable service rate Система M/M/1 с повторными требованиями и переменной интенсивностью обслуживания Система M/M/1 з повторними вимогами та змінною інтенсивністю обслуговування Bratiichuk, M. S. Chechelnitsky , A. A. Usar, I. Ya. Братийчук, Н. С. Чечельницкий, А. А. Усар, И. Я. Братійчук, М . C. Чечельницький, О. А. Усар, I. Я. UDC 519.21&lt;br&gt; The paper deals with queueing system of the type M/M/1 with repeated claims in the case where the service intensitydepends on the loading of the system, i.e., on the number of claims in the line to be served. We establish the existenceconditions and the formulas for ergodic distribution of the number of claims in the system with bounded and unboundedlines of repeated claims. УДК 519.21&lt;br&gt; В работе рассматривается система обслуживания типа M/M/1 с повторными требованиями, в которой интенсивности обслуживания зависят от загрузки системы, т.е. от количества требований, которые находятся в очереди на обслуживание. Получены условия существования и формулы для эргодического распределения числа требований в системе в случае конечной и бесконечной очереди повторных требований. УДК 519.21&lt;br&gt; Розглядається система обслуговування типу M/M/1 з повторними вимогами, в якiй iнтенсивностi обслуговуваннязалежать вiд завантаження системи, тобто вiд кiлькостi вимог, якi знаходяться в черзi на обслуговування. Знайдено умови iснування та формули для ергодичного розподiлу кiлькостi вимог у системi у випадку скiнченної танескiнченної черги повторних вимог. &nbsp; Institute of Mathematics, NAS of Ukraine 2020-03-28 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/813 10.37863/umzh.v72i3.813 Ukrains’kyi Matematychnyi Zhurnal; Vol. 72 No. 3 (2020); 355-365 Український математичний журнал; Том 72 № 3 (2020); 355-365 1027-3190 uk https://umj.imath.kiev.ua/index.php/umj/article/view/813/8667 Copyright (c) 2020 Микола Сергійович Братійчук, Олександр Анатолійович Чечельницький |
| spellingShingle | Bratiichuk, M. S. Chechelnitsky , A. A. Usar, I. Ya. Братийчук, Н. С. Чечельницкий, А. А. Усар, И. Я. Братійчук, М . C. Чечельницький, О. А. Усар, I. Я. M/M/1 retrial queueing model with variable service rate |
| title | M/M/1 retrial queueing model with variable service rate |
| title_alt | Система M/M/1 с повторными требованиями и переменной интенсивностью обслуживания Система M/M/1 з повторними вимогами та змінною інтенсивністю обслуговування |
| title_full | M/M/1 retrial queueing model with variable service rate |
| title_fullStr | M/M/1 retrial queueing model with variable service rate |
| title_full_unstemmed | M/M/1 retrial queueing model with variable service rate |
| title_short | M/M/1 retrial queueing model with variable service rate |
| title_sort | m/m/1 retrial queueing model with variable service rate |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/813 |
| work_keys_str_mv | AT bratiichukms mm1retrialqueueingmodelwithvariableservicerate AT chechelnitskyaa mm1retrialqueueingmodelwithvariableservicerate AT usariya mm1retrialqueueingmodelwithvariableservicerate AT bratijčukns mm1retrialqueueingmodelwithvariableservicerate AT čečelʹnickijaa mm1retrialqueueingmodelwithvariableservicerate AT usariâ mm1retrialqueueingmodelwithvariableservicerate AT bratíjčukmc mm1retrialqueueingmodelwithvariableservicerate AT čečelʹnicʹkijoa mm1retrialqueueingmodelwithvariableservicerate AT usariâ mm1retrialqueueingmodelwithvariableservicerate AT bratiichukms sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT chechelnitskyaa sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT usariya sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT bratijčukns sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT čečelʹnickijaa sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT usariâ sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT bratíjčukmc sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT čečelʹnicʹkijoa sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT usariâ sistemamm1spovtornymitrebovaniâmiiperemennojintensivnostʹûobsluživaniâ AT bratiichukms sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT chechelnitskyaa sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT usariya sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT bratijčukns sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT čečelʹnickijaa sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT usariâ sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT bratíjčukmc sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT čečelʹnicʹkijoa sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ AT usariâ sistemamm1zpovtornimivimogamitazmínnoûíntensivnístûobslugovuvannâ |