Системи обслуговування з вiдновлюючим рiвнем
Предлагается новый подход к изучению характеристик системы обслуживания типаM/G/1/b с ограниченной очередью и восстановительным уровнем входного потока требований. Получен удобный вычислительный алгоритм для стационарных характеристик системы, эффективность которого продемонстрирована на примере кон...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут математики НАН України
2014
|
| Назва видання: | Український математичний журнал |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/165110 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Системи обслуговування з вiдновлюючим рiвнем / М.С. Братiйчук, Д. Слiвiнська // Український математичний журнал. — 2014. — Т. 66, № 1. — С. 30–40. — Бібліогр.: 5 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-165110 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1651102020-02-12T01:27:16Z Системи обслуговування з вiдновлюючим рiвнем Братiйчук, М.С. Слiвiнська, Д. Статті Предлагается новый подход к изучению характеристик системы обслуживания типаM/G/1/b с ограниченной очередью и восстановительным уровнем входного потока требований. Получен удобный вычислительный алгоритм для стационарных характеристик системы, эффективность которого продемонстрирована на примере конкретной системы. A new approach is proposed for the investigation of the characteristics of queueing systems of the M/G/1/b-type with finite waiting rooms and a resume level of the input flow. A convenient algorithm is proposed for the numerical evaluation of stationary parameters of the system. Its efficiency is demonstrated for a specific system. 2014 Article Системи обслуговування з вiдновлюючим рiвнем / М.С. Братiйчук, Д. Слiвiнська // Український математичний журнал. — 2014. — Т. 66, № 1. — С. 30–40. — Бібліогр.: 5 назв. — укр. 1027-3190 http://dspace.nbuv.gov.ua/handle/123456789/165110 519.21 uk Український математичний журнал Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Статті Статті |
| spellingShingle |
Статті Статті Братiйчук, М.С. Слiвiнська, Д. Системи обслуговування з вiдновлюючим рiвнем Український математичний журнал |
| description |
Предлагается новый подход к изучению характеристик системы обслуживания типаM/G/1/b с ограниченной очередью и восстановительным уровнем входного потока требований. Получен удобный вычислительный алгоритм для стационарных характеристик системы, эффективность которого продемонстрирована на примере конкретной системы. |
| format |
Article |
| author |
Братiйчук, М.С. Слiвiнська, Д. |
| author_facet |
Братiйчук, М.С. Слiвiнська, Д. |
| author_sort |
Братiйчук, М.С. |
| title |
Системи обслуговування з вiдновлюючим рiвнем |
| title_short |
Системи обслуговування з вiдновлюючим рiвнем |
| title_full |
Системи обслуговування з вiдновлюючим рiвнем |
| title_fullStr |
Системи обслуговування з вiдновлюючим рiвнем |
| title_full_unstemmed |
Системи обслуговування з вiдновлюючим рiвнем |
| title_sort |
системи обслуговування з вiдновлюючим рiвнем |
| publisher |
Інститут математики НАН України |
| publishDate |
2014 |
| topic_facet |
Статті |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/165110 |
| citation_txt |
Системи обслуговування з вiдновлюючим рiвнем / М.С. Братiйчук, Д. Слiвiнська // Український математичний журнал. — 2014. — Т. 66, № 1. — С. 30–40. — Бібліогр.: 5 назв. — укр. |
| series |
Український математичний журнал |
| work_keys_str_mv |
AT bratijčukms sistemiobslugovuvannâzvidnovlûûčimrivnem AT slivinsʹkad sistemiobslugovuvannâzvidnovlûûčimrivnem |
| first_indexed |
2025-07-14T17:55:05Z |
| last_indexed |
2025-07-14T17:55:05Z |
| _version_ |
1837645910491791360 |
| fulltext |
УДК 519.21
М. С. Братiйчук, Д. Слiвiнська (Шльон. техн. ун-т, Iн-т математики, Глiвiце, Польща)
СИСТЕМИ ОБСЛУГОВУВАННЯ З ВIДНОВЛЮЮЧИМ РIВНЕМ
A new approach is proposed for the investigations of the characteristics of queueing systems of M/G/1/b type with
finite waiting rooms and a resume level of input flow. A convenient algorithm is proposed for the numerical evaluation of
stationary parameters of the system. Its efficiency is demonstrated for a specific system.
Предлагается новый подход к изучению характеристик системы обслуживания типа M/G/1/b с ограниченной
очередью и восстановительным уровнем входного потока требований. Получен удобный вычислительный алгоритм
для стационарных характеристик системы, эффективность которого продемонстрирована на примере конкретной
системы.
1. Вступ. Розглянемо систему обслуговування типу M/GI/1/b з обмеженою чергою, в якiй
вхiдний струмiнь вимог описується процесом Пуассона з параметром λ. Дисциплiна обслу-
говування є FIFO (перший прийшов-перший обслужився), функцiя розподiлу часу обслуго-
вування є F (x) з m =
∫ ∞
0
xdF (x) < ∞ i система має лише b − 1 мiсце, на яких вимоги
можуть чекати на обслуговування. Процес функцiонування системи має одну особливiсть. Во-
на полягає в наявностi вiдновлюючого рiвня a (a < b), який функцiонує таким чином. Нехай
ξa(t, b) позначає число вимог у системi в момент часу t i ξa(0, b) ∈ [0, b). До моменту часу
τ1(b) = inf{t > 0: ξa(t, b) = b} дана система працює як стандартна система типу M/GI/1/b.
Але в момент часу τ1(b) припиняється надходження вимог до системи, i лише коли довжина
черги зменшиться до a, надходження вимог вiдновлюється. Описану систему будемо позначати
Ma/GI/1/b. Введення вiдновлюючого рiвня переслiдує двi головнi цiлi. Якщо для стандартної
системи M/GI/1/b починаючи вiд моменту часу τ1(b) можуть вiдбуватися втрати вимог, то в
системi Ma/GI/1/b в момент часу τ1(b) ми можемо повiдомити про переповнення системи, що
дасть змогу переорiєнтувати потенцiйнi вимоги на iнший сервер. Останнє є особливо важливим
для комунiкацiйних систем, мереж обслуговування i т. п. Крiм того, така схема надходження
вимог дозволяє зменшити загальне навантаження системи (особливо для випадку, коли коефi-
цiєнт навантаження ρ = mλ > 1), що, в свою чергу, скорочує час чекання на обслуговування.
Подiбна система була вперше запропонована в [1], а в монографiї [2] можна знайти обчи-
слювальний алгоритм для стацiонарного розподiлу кiлькостi вимог (позначимо його πk(a, b),
0 ≤ k ≤ b) в таких системах. На нашу думку, цей алгоритм має два суттєвi недолiки. По-перше,
вiн не веде до точних формул для розподiлу πk(a, b), а є лише деякою рекурентною процедурою
для обчислення цього розподiлу. По-друге, для знаходження πk(a, b) використовується умова
нормування
∑b
k=0
πk(a, b) = 1, а тому, якщо ми хочемо знайти, наприклад, лише π1(a, b),
нам потрiбно обчислити всi πk(a, b). Наслiдком цих недолiкiв є те, що якщо ми розглядаємо
оптимiзацiйнi задачi для таких систем i числа a, b використовуються як параметри керування,
то при змiнi цих параметрiв нам потрiбно повторити всi обчислення заново, що, в свою чергу,
значно збiльшує об’єм обчислень.
У цiй статтi ми пропонуємо iнший пiдхiд, який базується на методi потенцiалу Королюка [5]
i приводить до точних формул для πk(a, b). Особливо важливою обставиною є те, що функцiї,
в термiнах яких записано цi формули, не залежать вiд a та b, а визначаються лише основними
c© М. С. БРАТIЙЧУК, Д. СЛIВIНСЬКА, 2014
30 ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
СИСТЕМИ ОБСЛУГОВУВАННЯ З ВIДНОВЛЮЮЧИМ РIВНЕМ 31
параметрами системи, тобто λ та F (x). Отже, вирахувавши цi функцiї один раз, ми можемо
використовувати їх при змiнi a та b. Це значно прискорює процес розв’язання оптимiзацiйних
задач.
У випадку a = b−1 наша модель зводиться до системи типу M/GI/1/b без вiдновлюючого
рiвня i ми отримуємо обчислювальний алгоритм для ергодичного розподiлу стандартної сис-
теми M/GI/1/b . Зауважимо, що цей алгоритм є простiшим, нiж вже вiдомi алгоритми (див.,
наприклад, [2, 3]).
2. Позначення, допомiжнi факти та основнi результати. Символами En, Pn будемо
позначати умовне математичне сподiвання та умовну ймовiрнiсть при умовi, що ξa(0, b) = n,
а якщо n = 1, то будемо писати E, P. Позначимо f(s) =
∫ ∞
0
e−sxdF (x), F (x) = 1− F (x), i
означимо послiдовностi pi(s), i ≥ −1, qi(s), i ≥ 0 s ≥ 0, за допомогою спiввiдношень
pi(s) = f−1(s)
∞∫
0
e−(λ+s)x
(λx)i+1
(i+ 1)!
dF (x), qi(s) =
∞∫
0
e−(λ+s)x
(λx)i
i!
F (x)dx.
Нехай
qn(s) =
∞∑
i=n
qi(s), fl(s, k) = qk−l(s) + I{k = b}qb−l+1(s),
g(s, k) = I{k ∈ [a+ 1, b− 1]}s−1f b−k(s)(1− f(s)).
Тут i далi I{A} дорiвнює 0 або 1 в залежностi вiд того, вiдбулася подiя A чи нi. Нехай
послiдовнiсть Rk(s), k = 0, 1, 2, . . . , є такою, що R0(s) = 1 i
∞∑
k=1
zkRk(s) = z
(
f
(
s+ λ(1− z)
)
− z
)−1
, |z| < ν(s), (1)
де ν(s) — єдиний корiнь рiвняння f
(
s+ λ(1− z)
)
−z = 0 на iнтервалi [0; 1].
У статтi [4] було доведено, що загальний розв’язок рiвняння
ϕ(n)− f(s)
b−n−2∑
i=−1
pi(s)ϕ(n+i) = ψn, 1 ≤ n ≤ b− 1,
можна записати таким чином:
ϕ(n) = Rb−n−1(s)ϕ(b− 1)−
b−n−1∑
k=1
Rk(s)ψn+k, 0 ≤ n ≤ b− 1. (2)
Нехай τ(b) = inf{t ≥ 0: ξa(t, b) = 0} — перший перiод зайнятостi i для s > 0 позначимо
ϕn(t, k) = Pn{ξa(t, b) = k, τ(b) > t}, Φn(s, k) =
∞∫
0
e−sxϕn(t, k)dt.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
32 М. С. БРАТIЙЧУК, Д. СЛIВIНСЬКА
Введемо також наступнi позначення:
∆(s, n) = (1− f(s))D(s, n) +Rb−a−1(s)−
(
1− f1−b+a(s)
)
Rb−n−1(s),
∆1(s, k) = (1− f(s))D1(s, k)− g(s, k)f−b+a(s)
(
1 + (1− f(s))
b−1∑
i=1
Ri(s)
)
−
−
(
1−f1−b+a(s)
) b−1∑
i=1
Ri(s)fi(s, k) +
b−a−1∑
i=1
Ri(s)fi+a(s, k),
∆2(s, k) = D2(s, k) + g(s, k)f−b+a(s)Rb−1(s),
(3)
де
D(s, n) = Rb−a−1(s)
b−n−1∑
i=1
Ri(s)−Rb−n−1(s)
b−a−1∑
i=1
Ri(s),
D1(s, k) =
b−a−1∑
i=1
Ri(s)fi+a(s, k)
b−1∑
i=1
Ri(s)−
b−a−1∑
i=1
Ri(s)
b−1∑
i=1
Ri(s)fi(s, k),
D2(s, k) = Rb−a−1(s)
b−1∑
i=1
Ri(s)fi(s, k)−Rb−1(s)
b−a−1∑
i=1
Ri(s)fi+a(s, k).
Теорема 1. Для 1 ≤ n ≤ b− 1, 1 ≤ k ≤ b та s > 0 маємо
Φn(s, k) = Rb−1−n(s)B1(s, k) +
(
1 +
(
1− f(s)
) b−n−1∑
i=1
Ri(s)
)
B2(s, k)−
−
b−n−1∑
i=1
Ri(s)fi+n(s, k), (4)
де
B1(s, k) =
∆1(s, k)
∆(s, 0)
, B2(s, k) =
∆2(s, k)
∆(s, 0)
. (5)
Наслiдок 1. Для 1 ≤ n ≤ b− 1
Ene
−sτ(b) =
∆(s, n)
∆(s, 0)
.
Нехай Rk = lims→0Rk(s), fl(k) = lims→0 fl(s, k), pi = lims→0 pi(s). Зрозумiло, що
∞∑
k=1
zkRk = z
(
f
(
λ(1− z)
)
− z
)−1
(6)
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
СИСТЕМИ ОБСЛУГОВУВАННЯ З ВIДНОВЛЮЮЧИМ РIВНЕМ 33
для достатньо малих |z|, а оскiльки qi(0) = λ−1pi, i ≥ 0, то
fl(k) = λ−1I{k ∈ [l, b− 1]}pk−l + λ−1I{k = b}
∞∑
i=b−l
pi. (7)
Теорема 2. Для 0 ≤ k ≤ b маємо
πk(a, b)
π0(a, b)
=
Rk −Rk−1, k ∈ [1, a],
R(a, b)
(
1 + ρ−Rk−a
)
+Rk −Rk−1, k ∈ [a+ 1, b− 1],
R(a, b)
(
(1− ρ)
∑b−a−1
i=1 Ri − b+ a+ 1
)
−
−(1− ρ)Rb−1 + 1, k = b,
де
π0(a, b) =
(
ρ
(
Rb−1 −R(a, b)
b−a−1∑
i=1
(Ri − 1)
)
+ 1
)−1
,
R(a, b) = (Rb−1 −Rb−2)/Rb−a−1.
(8)
Для a = b− 1 отримуємо формули для ергодичного розподiлу довжини черги в системi без
вiдновлюючого рiвня.
Наслiдок 2. Для 0 ≤ k ≤ b маємо
π0(b) =
(
ρRb−1 + 1
)−1
, πk(b) = π0(b)(Rk −Rk−1), 1 ≤ k ≤ b− 1,
πb(b) = π0(b)(1− (1− ρ)Rb−1).
(9)
3. Доведення основних результатiв. Доведення теореми 1. Для функцiї Φn(s, k), викорис-
товуючи формулу повної ймовiрностi на промiжку обслуговування першої вимоги, отримуємо
рiвняння
Φn(s, k)− f(s)
b−n−2∑
l=−1
pl(s)Φn+l(s, k) = f b−a(s)pb−n−1(s)Φa(s, k)+
+g(s, k)p̄b−n−1(s) + fn(s, k) (10)
з граничною умовою Φ0(s, k) = 0. Використовуючи тепер (10), маємо
Φn(s, k) = Rb−1−n(s)B1(s, k) +
(
1 + (1− f(s))
b−n−1∑
i=1
Ri(s)
)
B2(s, k)−
−
b−n−1∑
i=1
Ri(s)fi+n(s, k), 1 ≤ n ≤ b− 1,
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
34 М. С. БРАТIЙЧУК, Д. СЛIВIНСЬКА
де
B1(s, k) = Φb−1(s, k)− f−1(s)g(s, k)− f b−a−1(s)Φa(s, k),
B2(s, k) = f−1(s)g(s, k) + f b−a−1(s)Φa(s, k).
Покладаючи тут n = a, отримуємо перше рiвняння для B1(s, k) та B2(s, k):
Rb−1−a(s)B1(s, k) +
(
(1− f(s))
b−a−1∑
i=1
Ri(s) + 1− fa−b+1(s)
)
B2(s, k) =
=
b−a−1∑
i=1
Ri(s)fi+a(s, k, b)− g(s, k)fa−b(s).
З Φ0(s, k) = 0 одержуємо друге рiвняння
Rb−1(s)B1(s, k) +
(
1 + (1− f(s))
b−1∑
i=1
Ri(s)
)
B2(s, k) =
b−1∑
i=1
Ri(s)fi(s, k).
Тепер для B1(s, k), B2(s, k) маємо систему двох лiнiйних рiвнянь, визначник якої задається
спiввiдношенням (3). Використовуючи формули Крамера, отримуємо (5).
Наслiдок 1 випливає з (4), якщо перейти до суми в обох частинах цiєї формули по k вiд 1
до b.
Доведення теореми 2. З наслiдку 1 отримуємо
Eτ(b) = m
(
R(a, b)
b−a−1∑
i=1
(1−Ri) +Rb−1
)
.
Спiввiдношення π0(a, b) = limt→∞P{ξa(t, b) = 0} =
(
λEτ(b) + 1
)−1
є вiдомим i, отже, (8)
доведено.
Нехай ξa(0, b) = 1 i τi(b) = inf{n > τi−1(b); ξa(t, b) = 0}, i = 1, 2, ..., τ0(b) = 0, а ξi,
i = 1, 2, . . . , — час, коли вiльний прилад чекає на вимогу починаючи з моменту τi(b). Зрозумiло,
що τ1(b) = τ(b) i випадковi величини ξi, i ≥ 1, є незалежними з показниковим розподiлом з
параметром λ. Моменти ξi + τi(b), i = 1, 2, . . . , утворюють процес вiдновлення, i нехай H(x)
— його функцiя вiдновлення, тобто H(x) =
∑∞
i=0
Φ∗i(x), де Φ(x) = P{τ1(b) + ξ1 < x}. Для
0 < k ≤ b маємо
P{ξa(t, b) = k} = P{ξa(t, b) = k, τ(b) > t}+
t∫
0
P{ξa(t− u, b) = k}dΦ(u).
Отже,
P{ξa(t, b) = k} =
t∫
0
P{ξa(t− u, b) = k, τ(b) > t− u}dH(u), 0 < k ≤ b.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
СИСТЕМИ ОБСЛУГОВУВАННЯ З ВIДНОВЛЮЮЧИМ РIВНЕМ 35
За вузловою теоремою вiдновлення маємо
lim
t→∞
P{ξa(t, b) = k} = λπ0(a, b)
∞∫
0
P{ξa(u, b) = k, τ(b) > t}du. (11)
Покладаючи в (4) s = 0, n = 1, отримуємо
∞∫
0
P{ξa(t, b) = k, τ(b) > t}dt = Rb−2B1(k) +B2(k)−
b−2∑
i=1
Rifi+1(k) (12)
для всiх 1 ≤ n ≤ b− 1, 1 ≤ k ≤ b, де
B1(k) = R−1b−a−1
(
b−a−1∑
i=1
Rifi+a(k)−mI{k ∈ (a, b)}
)
,
B2(k) =
b−1∑
i=1
Rifi(k)− Rb−1
Rb−a−1
(
b−a−1∑
i=1
Rifi+a(k) +mI{k ∈ (a, b)}
)
.
(13)
Використовуючи (6), можемо перевiрити, що
n∑
i=1
Ripn−i = Rn − 1,
n∑
i=1
Ri
∞∑
k=n+1−i
pk = (mλ− 1)
n∑
i=1
Ri + n
для всiх n ≥ 1, що разом з (7) дає
b−a−1∑
i=1
Rifi+a(k) = λ−1(Rk−a − 1)I{k ∈ [a+ 1, b− 1]},
b−1∑
i=1
Rifi(b) = λ−1
(
(ρ− 1)
b−1∑
i=1
Ri + b− 1
)
.
Використовуючи це в (13), отримуємо
Rb−2B1(k) +B2(k)−
b−2∑
i=1
Rifi+1(k) =
= λ−1
Rk −Rk−1, k ∈ [1, a],
Rk −Rk−1 +R(a, b)
(
1 + ρ−Rk−a
)
, k ∈ [a+ 1, b− 1],
R(a, b)
(
(1− ρ)
b−a−1∑
i=1
Ri − b+ a+ 1
)
−
−(1− ρ)Rb−1 + 1, k = b.
Застосовуючи тепер (11), (12), завершуємо доведення теореми.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
36 М. С. БРАТIЙЧУК, Д. СЛIВIНСЬКА
4. Iншi стацiонарнi характеристики системи. Крiм ергодичного розподiлу кiлькостi
вимог є ще ряд iнших параметрiв, якi можуть використовуватися для опису ефективностi працi
системи. Для системи Ma/GI/1/b ми розглянемо ще такi характеристики: кiлькiсть вимог,
якi були обслугованi за одиницю часу в стацiонарному режимi, та число блокувань вхiдного
струменя вимог (теж за одиницю часу i в стацiонарному режимi). Позначимо цi величини
вiдповiдно Nser(a) та Nblo(a). Нехай також Nser позначає кiлькiсть вимог, якi були обслугованi
за одиницю часу в стацiонарному режимi для системи без вiдновлюючого рiвня M/GI/1/b.
Далi нам будуть потрiбнi середнi значення вказаних характеристик, i щоб не збiльшувати об’єм
статтi, обмежимося лише ними.
Теорема 3. Мають мiсце рiвностi
ENser(a) = λπ0(a, b)
(
Rb−1 −R(a, b)
b−a−1∑
k=1
(Rk − 1)
)
, (14)
ENblo(a) = λπ0(a, b)R(a, b), ENser = λπ0(b)Rb−1. (15)
Доведення. Нехай N(t) — кiлькiсть вимог, якi були обслугованi на iнтервалi [0, t], i Φn(s) =
=
∫ ∞
0
e−stEnN(t)dt, s > 0. Мiркуючи так само, як i при доведеннi теореми 1, отримуємо
для 1 ≤ n ≤ b рiвняння
Φn(s)− f(s)
b−n−2∑
l=−1
pl(s)Φn+l(s) =
=
f(s)
s
+ pb−n−1(s)
(
f2(s)(1− f b−a−1(s))
s(1− f(s))
+ f b−a(s)
)
Φa(s) (16)
з граничною умовою
Φ0(s) =
λ
s+ λ
Φ1(s). (17)
Застосовуючи (2) до (16), маємо
Φn(s) = Rb−n−1(s)Db(s) + f b−a−1(s)
(
(1− f(s))
b−n−1∑
k=1
Rk(s) + 1
)
Φa(s)+
+Ψb−n(s), (18)
де
Db(s) = Φb−1(s)− f b−a−1(s)Φa(s),
Ψn(s) = −f(s)(1− f b−a−1(s))(Rn−1(s)− 1)
s(1− f(s))
− f b−a(s)
s
n−1∑
k=1
Rk(s).
З (18) для n = a та граничної умови (17) отримуємо сиcтему лiнiйних рiвнянь дляDb(s), Φa(s).
Нехай ∆(s) позначає визначник цiєї системи. Оскiльки, як вiдомо, стацiонарнi характеристики
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
СИСТЕМИ ОБСЛУГОВУВАННЯ З ВIДНОВЛЮЮЧИМ РIВНЕМ 37
системи не залежать вiд її початкового стану, то достатньо розглянути лише Φa(s). Тодi
Φa(s) =
∞∫
0
e−stEaN(t)dt =
∆1(s)
∆(s)
,
де
∆1(s) = Ψb−a(s)
( λ
s+ λ
Rb−2(s)−Rb−1(s)
)
+Rb−a−1(s)
(
Ψb(s)−
λ
s+ λ
Ψb−1(s)
)
.
Виконуючи простi обчислення, отримуємо спiввiдношення
lim
s→0
s−1∆(s) = Rb−a−1
[
mR(a, b)
b−a−1∑
k=1
(Rk − 1)−mRb−1 −
1
λ
]
= − Rb−a−1
λπ0(a, b)
,
lim
s→0
s∆1(s) = Rb−a−1
[
R(a, b)
b−a−1∑
k=1
(Rk − 1)−Rb−1
]
.
Тому
ENser(a) = lim
t→∞
(
EaN(t+ 1)−EaN(t)
)
=
= lim
s→0
s
(es − 1)
∞∫
0
e−stEaN(t)dt−
1∫
0
e−stEaN(t)dt
= lim
s→0
s2Φa(s) =
= lim
s→0
s∆1(s)
s−1∆(s)
= λπ0(a, b)
(
Rb−1 −R(a, b)
b−a−1∑
k=1
(Rk − 1)
)
.
Для доведення (15) позначимо
τ0(a, b) = 0, τk(a, b) = inf{t > τk−1(a, b) : ξa(t, b) = b}, k = 1, 2, . . . ,
i нехай ηn(a, b) = τn+1(a, b) − τn(a, b), n ≥ 0. Зрозумiло, що для n ≥ 1 випадковi величини
ηn(a, b) є незалежними та однаково розподiленими.
Розглянемо тепер стандартну систему M/GI/1/b без вiдновлюючого рiвня, з необмеженою
чергою, i нехай ξ(t) позначає число вимог у сиcтемi в момент часу t. Покладемо τ(b) =
= inf{t > 0: ξ(t) = b}, i нехай γ(b) — залишковий час обслуговування в момент часу τ(b)
для цiєї системи. Зрозумiло, що розподiл випадкових величин ηn(a, b), n ≥ 1, збiгається з
розподiлом випадкової величини γ(b) +
∑b−a−1
i=1
βi + τ(b) при умовi, що ξ(0) = a. Тут βi,
i ≥ 1, є незалежними випадковими величинами з функцiєю розподiлу F (x). Нехай ν(t) =
= max
{
k :
∑k
n=0
ηn(b) < t
}
— процес вiдновлення (взагалi кажучи, з затримкою) i якщо
M(t) = 1 + Eν(t) — його функцiя вiдновлення, то
ENblo(a) = lim
t→∞
(M(t+ 1)−M(t)) =
(
Ea
(
γ(b) + τ(b)
)
+m(b− a− 1)
)−1
. (19)
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
38 М. С. БРАТIЙЧУК, Д. СЛIВIНСЬКА
Позначимо ψn = En(τ(b) + γ(b)). Для 1 ≤ n ≤ b стандартними мiркуваннями отримуємо
ψn =
b−n−1∑
i=0
∞∫
0
(
x+ ψn+i−1
)
e−λx
(λx)i
i!
dF (x) +
∞∫
0
xP
{
b−n∑
i=1
αi < x
}
dF (x) (20)
i ψ0 = λ−1 + ψ1. Тут αi позначає довжину iнтервалу мiж вимогами у вхiдному струменi.
Випадкова величина
∑b−n
i=1
αi має розподiл Ерланга, i ми можемо трансформувати (20) в
ψn −
b−n−2∑
i=−1
piψn+i = m.
Розв’язок цього рiвняння ми отримуємо з (2), тодi з граничної умови ψ0 = λ−1 + ψ1 маємо
ψn =
mRb−1 + λ−1
Rb−1 −Rb−2
Rb−n−1 −m
b−n−1∑
k=1
Rk,
а тому
Ea(τ(b) + γ(b)) =
mλRb−1 + 1
λR(a, b)
−m
b−a−1∑
k=1
Rk,
що разом з (19) дає першу формулу в (15). Друга формула випливає з першої, якщо взяти
a = b− 1.
Теорему 3 доведено.
5. Числовий приклад. Для обчислень ми використовували пакет MATEMATIKA. Легко
зауважити, що всi характеристики, якi розглядаються в цiй статтi, виписуються в термiнах
функцiї Rn, для якої з (6) отримуємо наступний рекурентний алгоритм:
R1 =
1
p−1
, Rn+1 = R1
(
Rn −
n−1∑
k=0
pkRn−k
)
, n ≥ 1.
Нехай для системи з вiдновлюючим рiвнем Cser, Cblo, Clos позначають вiдповiдно плату за
обслуговану вимогу, вартiсть одного блокування та плату за втрачену вимогу.
ClenEξa(∞, b) та ClenEξ(∞) позначають сукупнi витрати, пов’язанi з чеканням у черзi для
системи з вiдновлюючим рiвнем та без нього.
Загальний кошт працi системи буде тепер таким:
F (a, b) = CserENser(a)− CbloENser(a)− Clen
b∑
k=1
kπk(a, b)
для системи з вiдновлюючим рiвнем та
F (b) = CserENser − ClosENlos − Clen
b∑
k=1
kπk(b)
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
СИСТЕМИ ОБСЛУГОВУВАННЯ З ВIДНОВЛЮЮЧИМ РIВНЕМ 39
для системи без нього.
З теореми 3 випливає, що
F (a, b) = λπ0(a, b)
(
CserRb−1 −R(a, b)
(
Cser
b−a−1∑
k=1
(Rk − 1) + Cser
))
−
−Clen
b∑
k=1
kπk(a, b).
Якщо для системи M/G/1/b без вiдновлюючого рiвня Nar(t), Nser(t), Nlos(t) позначають
вiдповiдно число вимог, якi надiйшли, були обслугованi та були втраченi на iнтервалi [0, t] при
умовi, що ξ(0) = n, то n+Nar(t) = Nlos(t) +Nser(t) + ξ(t). Маємо
En[Nar(t)−Nar(t− 1)] = En[Nlos(t)−Nlos(t− 1)] + En[Nser(t)−Nser(t− 1)]+
+Enξ(t)−Enξ(t− 1).
Зрозумiло, що En[Nar(t)−Nar(t− 1)] = λ, а тому
lim
t→∞
En[Nlos(t)−Nlos(t− 1)] = λ− lim
t→∞
En[Nser(t)−Nser(t− 1)] =
= λ−ENser = λ
(
1− π0(b)Rb−1
)
.
Звiдси випливає формула для функцiї F (b):
F (b) = λπ0(b)Rb−1
(
Cser + Clos
)
− λClos − Clen
b∑
k=1
kπk(b).
Приклад. Розглянемо систему з λ = 1, 4 та щiльнiстю розподiлу часу обслуговування
f(x) =
32,4
Γ(2, 4)
e−3xx1,4 (гамма-розподiл з параметрами 3; 2, 4). Нехай b = 20.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
40 М. С. БРАТIЙЧУК, Д. СЛIВIНСЬКА
У цьому випадку ρ = 1, 12. На рисунку точки, вiдмiченi знаком �, вiдповiдають системi з
вiдновлюючим рiвнем, а точки, вiдмiченi знаком F, — системi без такого рiвня. Нехай також
Sser = 5, 1, Sblo = 1, 5, Slen = 0, 42, Slos = 2, Ssho = 0, 2.
Iз графiкiв функцiй F (a, 20), F (20) випливає, що для 5 ≤ a ≤ 17 система з вiдновлюючим
рiвнем працює ефективнiше за систему без вiдновлюючого рiвня, для якої F (20) = −0, 183.
1. Takagi H. A analysis of a finite-capacity M/G/1 queue with a resume level // Perform. Eval. – 1985. – 5, № 3. –
P. 197 – 203.
2. Takagi H. Queueing analysis. – The Netherlands: Elsevier Sci. Publ., 1993. – Vol. 2.
3. Srinivasa Rao T.S.S., Gupta U. C. A simple method for cimputing state probabilities of the M/G/1 and GI/N/1
finite waiting space queues // ZOR-Math. Metods of Operat. Res. – 1996. – 43. – P. 97 – 106.
4. Bratiychuk M., Borowska B. Explicit formulae and convergence rate for the system E/G/1/N // Communs Statist.
Stochast. Models. – 2001. – 18. – P. 71 – 78.
5. Korolyuk V. S. Boundary problems for compound Poisson process. – Kiev: Naukova Dumka, 1975.
Одержано 28.12.12
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 1
|