Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування
Досліджується система обслуговування M/G/m/r, в якій розподіл часу обслуговування є сумішшю двох експоненціальних розподілів. Одержано необхідну і достатню умову, коли ймовірність відмови системи на інтервалі зайнятості еквівалентна ймовірності монотонної відмови. Отримано також умови, коли основний...
Gespeichert in:
| Datum: | 2011 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2011
|
| Schriftenreihe: | Доповіді НАН України |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/43730 |
| 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: | Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування / I.М. Кузнєцов // Доп. НАН України. — 2011. — № 10. — С. 48-53. — Бібліогр.: 13 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-43730 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-437302013-05-16T03:07:11Z Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування Кузнєцов, І.М. Інформатика та кібернетика Досліджується система обслуговування M/G/m/r, в якій розподіл часу обслуговування є сумішшю двох експоненціальних розподілів. Одержано необхідну і достатню умову, коли ймовірність відмови системи на інтервалі зайнятості еквівалентна ймовірності монотонної відмови. Отримано також умови, коли основний внесок у відмову системи роблять немонотонні відмови. A queueing system M/G/m/r with the service time distribution being a mixture of two exponential distributions is considered. A necessary and sufficient condition when the system failure in a busy period is equivalent to the probability of a monotone failure is obtained. Conditions when nonmonotone failures give the main contribution to the system failure are also obtained. 2011 Article Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування / I.М. Кузнєцов // Доп. НАН України. — 2011. — № 10. — С. 48-53. — Бібліогр.: 13 назв. — укр. 1025-6415 http://dspace.nbuv.gov.ua/handle/123456789/43730 519.872 uk Доповіді НАН України Видавничий дім "Академперіодика" НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| topic |
Інформатика та кібернетика Інформатика та кібернетика |
| spellingShingle |
Інформатика та кібернетика Інформатика та кібернетика Кузнєцов, І.М. Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування Доповіді НАН України |
| description |
Досліджується система обслуговування M/G/m/r, в якій розподіл часу обслуговування є сумішшю двох експоненціальних розподілів. Одержано необхідну і достатню умову, коли ймовірність відмови системи на інтервалі зайнятості еквівалентна ймовірності монотонної відмови. Отримано також умови, коли основний внесок у відмову системи роблять немонотонні відмови. |
| format |
Article |
| author |
Кузнєцов, І.М. |
| author_facet |
Кузнєцов, І.М. |
| author_sort |
Кузнєцов, І.М. |
| title |
Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування |
| title_short |
Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування |
| title_full |
Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування |
| title_fullStr |
Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування |
| title_full_unstemmed |
Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування |
| title_sort |
асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування |
| publisher |
Видавничий дім "Академперіодика" НАН України |
| publishDate |
2011 |
| topic_facet |
Інформатика та кібернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/43730 |
| citation_txt |
Асимптотичний аналіз внеску немонотонних траєкторій у відмову системи обслуговування / I.М. Кузнєцов // Доп. НАН України. — 2011. — № 10. — С. 48-53. — Бібліогр.: 13 назв. — укр. |
| series |
Доповіді НАН України |
| work_keys_str_mv |
AT kuznêcovím asimptotičnijanalízvneskunemonotonnihtraêktoríjuvídmovusistemiobslugovuvannâ |
| first_indexed |
2025-07-04T02:11:02Z |
| last_indexed |
2025-07-04T02:11:02Z |
| _version_ |
1836680544286408704 |
| fulltext |
УДК 519.872
© 2011
I.М. Кузнєцов
Асимптотичний аналiз внеску немонотонних траєкторiй
у вiдмову системи обслуговування
(Представлено академiком НАН України I.М. Коваленком)
Дослiджується система обслуговування M/G/m/r, в як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ї надiйностi для отримання високоточних оцiнок ймо-
вiрнiсних характеристик високонадiйної системи. Першi результати з асимптотичного ана-
лiзу дубльованих систем одержано Б.В. Гнєденком [1, 2]. Iстотний внесок у розвиток асим-
птотичних методiв аналiзу високонадiйних систем, поведiнка яких може бути описана ре-
генеруючим процесом, зробили О.Д. Соловйов та його учнi [3–5]. Бiльш загальнi схеми
дослiджувались I. М. Коваленком [6, 7], В.В. Анiсiмовим [8] та багатьма iншими авторами.
У схемi регенеруючого процесу було доведено [3], що час до першої втрати вимоги у сис-
темi обслуговування має асимптотично експоненцiальний розподiл. Параметр цього розпо-
дiлу залежить як вiд середнього часу iнтервалу зайнятостi, так i вiд iмовiрностi q вiдмови
системи протягом iнтервалу зайнятостi (промiжку часу, коли у системi знаходиться хоча б
одна вимога). Якщо середнiй час iнтервалу зайнятостi у бiльшостi випадкiв апроксимується
середнiм часом обслуговування однiєї вимоги, то обчислення ймовiрностi q є досить склад-
ною задачею. Оцiнцi q було присвячено багато робiт (див., наприклад, [9–12]). В основi
майже всiх асимптотичних методiв оцiнки q лежить принцип монотонних вiдмов, сформу-
льований I.М. Коваленком [13] (див. також [3–5, 7]).
У подальшому втрату вимоги називаємо вiдмовою системи обслуговування. Монотон-
ною є така вiдмова, що з початку iнтервалу зайнятостi i до вiдмови системи не було закiн-
чено обслуговування жодної з вимог, тобто кiлькiсть вимог у системi монотонно зростає.
Всi iншi траєкторiї є немонотонними. Тодi
q = q0 + q1, (1)
де q0 i q1 — ймовiрностi монотонної та немонотонної вiдмов вiдповiдно. У випадку високо-
надiйної системи типовою є така ситуацiя: якщо в iнтервалi зайнятостi вiдбулася вiдмова
системи, то з ймовiрнiстю, близькою до одиницi, ця вiдмова є монотонною, тобто q1 = o(q0).
Iстотнi зусилля дослiдникiв були зосередженi на отриманнi достатнiх умов для виконання
цього спiввiдношення. Так, для системи M/G/m/r (пуассонiвський вхiдний потiк iнтен-
сивнiстю λ, m обслуговуючих пристроїв, r мiсць для очiкування, час обслуговування має
48 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №10
функцiю розподiлу Bǫ(x), що залежить вiд малого параметра ǫ > 0, обслуговування вiдбу-
вається в порядку надходження вимог, вiдмова системи — втрата вимоги) О.Д. Соловйов [9]
довiв, що умова
αm+r+1(ε)
αm+r
1
(ε)
−→
ε→0
0 (2)
є достатньою для виконання спiввiдношення (1). У цiй формулi використано позначення
αk(ε) =
∞
∫
0
xkdBε(x), k > 1.
Застосовуючи бiльш тонкий математичний апарат, I. М. Коваленку [13] вдалося значно
понизити моментнi умови. Зокрема, була отримана верхня оцiнка q1 для q1:
q1 6 q1 = O(λr+1αm−1
1
(ε)αr+2(ε)). (3)
У даному повiдомленнi дослiджується система M/G/m/r, в якiй розподiл часу обслу-
говування є сумiшшю двох експоненцiальних розподiлiв, тобто
B(x) = u(1− e−µ1x) + v(1− e−µ2x), u+ v = 1, µ1 > 0, µ2 > 0.
Припустимо, що µ1 → ∞, v → 0, λ = const, µ2 = const. Метою нашої роботи є вста-
новлення необхiдних та достатнiх умов, коли виконується спiввiдношення (1). Цi умови по-
рiвнюються з достатнiми умовами О.Д. Соловйова та I.М. Коваленка (спiввiдношення (2)
та (3)). Крiм того, наводяться умови, коли основний внесок у вiдмову системи вносять
немонотоннi вiдмови.
Марковський граф переходiв. Поведiнка системи на iнтервалi зайнятостi описується
двовимiрним ланцюгом Маркова, стан якого має вигляд ν = (s, k), де s — загальна кiлькiсть
вимог у системi, а k — кiлькiсть вимог I типу (тобто з iнтенсивнiстю обслуговування µ1), що
знаходяться на обслуговуваннi. При цьому (0, 0) є початковим станом, а всi стани (s, k) з s >
> m+r є станами вiдмови. При цьому q0 — це ймовiрнiсть переходу iз стану (0, 0) у множину
станiв вiдмови по однiй з траєкторiй з монотонно зростаючою першою компонентою, q1 —
ймовiрнiсть вiдмови за однiєю з решта траєкторiй (природно, без повернення у стан (0, 0)).
Ймовiрностi переходу ланцюга Маркова визначаються таким чином (ймовiрнiсть переходу
з (s, k) у (s1, k1) позначаємо P{(s, k) → (s1, k1)}):
якщо s 6 m − 1, то
P{(s, 0) → (s + 1, 0)} =
λv
λ+ sµ2
= O(v),
P{(s, 0) → (s − 1, 0)} =
sµ2
λ+ sµ2
= O(1), s > 1,
P{(s, 0) → (s + 1, 1)} =
λu
λ+ sµ2
= O(1),
P{(s, k) → (s+ 1, k)} =
λv
λ+ kµ1 + (s− k)µ2
= O
(
v
µ1
)
, 1 6 k 6 s,
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №10 49
P{(s, k) → (s+ 1, k + 1)} =
λu
λ+ kµ1 + (s − k)µ2
= O
(
1
µ1
)
, 1 6 k 6 s,
P{(s, k) → (s− 1, k)} =
(s− k)µ2
λ+ kµ1 + (s− k)µ2
= O
(
1
µ1
)
, 1 6 k 6 s,
P{(s, k) → (s− 1, k − 1)} =
kµ1
λ+ kµ1 + (s − k)µ2
= O(1), 1 6 k 6 s;
якщо m 6 s 6 m + r, то
P{(s, 0) → (s + 1, 0)} =
λ
λ+mµ2
= O(1),
P{(m, 0) → (m− 1, 0)} =
mµ2
λ+mµ2
= O(1),
P{(m,k) → (m− 1, k − 1)} =
kµ1
λ+ kµ1 + (m− k)µ2
= O(1), 1 6 k 6 m,
P{(m,k) → (m− 1, k)} =
(m− k)µ2
λ+ kµ1 + (m− k)µ2
= O
(
1
µ1
)
, 1 6 k 6 m,
P{(s, 0) → (s − 1, 0)} =
mµ2v
λ+mµ2
= O(v), s > m+ 1,
P{(s, 0) → (s − 1, 1)} =
mµ2u
λ+mµ2
= O(1), s > m+ 1,
P{(s, k) → (s+ 1, k)} =
λ
λ+ kµ1 + (m− k)µ2
= O
(
1
µ1
)
, 1 6 k 6 m,
P{(s, k) → (s− 1, k)} =
kµ1u+ (m− k)µ2v
λ+ kµ1 + (m− k)µ2
= O(1), 1 6 k 6 m,
P{(s, k) → (s− 1, k − 1)} =
kµ1v
λ+ kµ1 + (m− k)µ2
= O(v), 1 6 k 6 m,
P{(s, k) → (s− 1, k + 1)} =
(m− k)µ2u
λ+ kµ1 + (m− k)µ2
= O
(
1
µ1
)
, 1 6 k 6 m.
Оцiнка ймовiрностi монотонної вiдмови q0. Наведенi спiввiдношення дозволяють
знайти найбiльш iмовiрнi монотоннi траєкторiї вiдмови системи (у подальшому символ O∗(·)
використовується для позначення величин того ж самого порядку).
1. Ймовiрнiсть траєкторiї (0, 0) → (1, 0) → · · · → (m+ r + 1, 0) має порядок O∗(vm).
2. Ймовiрнiсть траєкторiї (0, 0) → (1, 1) → · · · → (m,m) → (m + 1,m) → · · · → (m +
+ r + 1,m) має порядок O∗(1/µm+r
1
).
3. Ймовiрнiсть траєкторiї (0, 0) → (1, 0) → · · · → (k, 0) → (k+1, 1) → · · · → (m,m− k) →
→ (m+1,m−k) → · · · → (m+r+1,m−k) при k = 1, . . . ,m−1 має порядок O∗(vk/µm+r−k
1
).
Оскiльки ймовiрностi переходiв (s, k) → (s + 1, k) при 1 6 s 6 m − 1, 1 6 k 6 s
мають порядок O∗(v/µ1), то ймовiрностi монотонних траєкторiй iншого виду мають бiльш
високий порядок порiвняно з наведеними вище.
Знайдемо порядок ймовiрностi q0 монотонної вiдмови залежно вiд спiввiдношення по-
рядкiв v i µ1. Розглянемо два випадки.
50 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №10
A. Величини v i µ1 змiнюються таким чином, що v → 0, µ1 → ∞ та vmµm+r
1
> c для
деякого c > 0. З цiєї умови випливає, що 1/µm+r
1
6 vm/c. Якщо додатково припустити, що
vµ1 6 d для деякого d < ∞, то
vk
µm+r−k
1
=
(vµ1)
k
µm+r
1
6
dk
c
vm, k = 1, . . . ,m− 1.
Тому
q0 = O∗(vm). (4)
Якщо ж припустити, що vµ1 → ∞, то найбiльш iмовiрною є траєкторiя при k = m− 1:
vm−1
µr+1
1
= vm
1
vµ1
1
µr
1
= o(vm).
Тому також має мiсце спiввiдношення (4).
B. Величини v i µ1 змiнюються таким чином, що v → 0, µ1 → ∞ та vmµm+r
1
→ 0. Тодi
vm = o(1/µm+r
1
). Оскiльки vµ1 = (vmµm+r
1
)1/m(1/µ1)
r/m → 0, то
vk
µm+r−k
1
=
(vµ1)
k
µm+r
1
= o
(
1
µm+r
1
)
, k = 1, . . . ,m− 1.
Тому
q0 = O∗
(
1
µm+r
1
)
. (5)
Необхiдна та достатня умова. Спiввiдношення (4) та (5) лежать в основi доведення
таких тверджень.
Теорема 1. Припустимо, що v → 0, µ1 → ∞, µ2 = const, λ = const. Спiввiдношення
q1 = o(q0) виконується тодi i тiльки тодi, коли v та µ1 змiнюються таким чином, що
vmµm+r
1
→ 0. (6)
Якщо виконується умова (6), то
q0 =
λm+r
m!mr
1
µm+r
1
+ o
(
1
µm+r
1
)
.
Теорема 2. Припустимо, що v → 0, µ1 → ∞, µ2 → 0, λ = const та vmµm+r
1
> c для
деякого c > 0. Тодi q0 = o(q1).
Порiвняємо отриману необхiдну та достатню умову з достатнiми умовами О.Д. Солов-
йова та I.М. Коваленка. Припустимо, що q1 = o(q0). В цьому випадку має мiсце спiввiд-
ношення (6). Тому
vµ1 = (vmµm+r
1
)1/m
(
1
µ1
)r/m
→ 0. (7)
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №10 51
Для розподiлу B(x) k-й момент обчислюється за формулою
αk = u
k!
µk
1
+ v
k!
µk
2
.
Тому умова (2) може бути записана у виглядi
αm+r+1
αm+r
1
=
(m+ r + 1)!uµm+r+1
2
µ1µ2(uµ2 + vµ1)m+r
+
(m+ r + 1)!vµm+r
1
µ2(uµ2 + vµ1)m+r
→ 0. (8)
З умови (7) випливає, що перший доданок у правiй частинi (8) прямує до нуля, коли
µ1 → ∞. Тому спiввiдношення (8) виконується тодi i тiльки тодi, коли vµm+r
1
→ 0.
Достатня умова (3) має такий вигляд:
αm−1
1
αr+2
q0
→ 0.
Спiввiдношення q1 = o(q0) виконується лише тодi, коли має мiсце спiввiдношення (5). Тому
µm+r
1
αm−1
1
αr+2 = µm+r
1
(
u
1
µ1
+ v
1
µ2
)m−1(
u
1
µr+2
1
+ v
1
µr+2
2
)
=
=
1
µm+r+1
2
(uµ2 + vµ1)
m−1
(
uµr+2
2
µ1
+ vµr+1
1
)
→ 0
тодi i тiльки тодi, коли vµr+1
1
→ 0.
Отримано умови, якi можна записати таким чином:
необхiдна та достатня умова (vµ1)
mµr
1 → 0 (теорема 1);
достатня умова О.Д. Соловйова (vµ1)µ
m+r−1
1
→ 0 (спiввiдношення (2));
достатня умова I. М. Коваленка (vµ1)µ
r
1 → 0 (спiввiдношення (3)).
Очевидно, що умова О.Д. Соловйова є найбiльш жорсткою. У випадку однолiнiйної
системи (тобто при m = 1) всi три умови збiгаються.
1. Гнеденко Б.В. О ненагруженном дублировании // Изв. АН СССР. Техн. кибернетика. – 1964. – № 4. –
С. 3–12.
2. Гнеденко Б. В. О дублировании с восстановлением // Там же. – № 5. – С. 111–118.
3. Соловьев А.Д. Асимптотическое поведение момента первого наступления редкого события в регене-
рирующем процессе // Там же. – 1971. – № 6. – С. 79–89.
4. Гнеденко Д.Б., Соловьев А.Д. Оценка надежности сложных восстанавливаемых систем // Там же. –
1975. – № 3. – С. 89–96.
5. Соловьев А.Д., Карасева Н. Г. Оценка среднего времени жизни восстанавливаемых систем // Вестн.
Моск. ун-та. Сер. 1. – 1998. – № 5. – С. 25–29.
6. Коваленко И.Н. Анализ редких событий при оценке эффективности и надежности систем. – Москва:
Сов. радио, 1980. – 209 с.
7. Kovalenko I.N. Approximation of queues via small-parameter method // Advances in Queueing. – Boca
Raton: CRC Press, 1995. – P. 481–506.
8. Anisimov V.V. Switching processes in queueing models. – Chichester: Wiley-ISTE, 2008. – 352 p.
9. Барзилович Е.Ю., Беляев Ю.К., Каштанов В.А. и др. Вопросы математической теории надежно-
сти. – Москва: Радио и связь, 1983. – 376 с.
10. Константинидис Д. Г. Принцип монотонной траектории отказа сложной восстанавливаемой систе-
мы // Вестн. Моск. ун-та. Сер. 1. – 1990. – № 3. – С. 7–13.
52 ISSN 1025-6415 Reports of the National Academy of Sciences of Ukraine, 2011, №10
11. Коваленко И.Н. Оценка интенсивности потока немонотонных отказов в системе обслуживания
(6 λ)/G/m // Укр. мат. журн. – 2000. – 52, № 9. – С. 1219–1225.
12. Коваленко И.Н., Кузнецов Н.Ю. Принцип монотонных отказов и его применение к расчету харак-
теристик надежности структурно сложных систем // Стохастич. модели систем. – Киев: Военная
академия ПВО сухопутных войск, 1986. – С. 25–45.
13. Коваленко И. H. Об оценке надежности сложных систем // Вопp. pадиоэлектpоники. – 1965. – 12,
№ 9. – С. 50–68.
Надiйшло до редакцiї 16.02.2011Iнститут кiбернетики
iм. В.М. Глушкова НАН України, Київ
I.N. Kuznetsov
Asymptotic analysis of a contribution of nonmonotone trajectories to
the queueing system failure
A queueing system M/G/m/r with the service time distribution being a mixture of two exponen-
tial distributions is considered. A necessary and sufficient condition when the system failure in
a busy period is equivalent to the probability of a monotone failure is obtained. Conditions when
nonmonotone failures give the main contribution to the system failure are also obtained.
ISSN 1025-6415 Доповiдi Нацiональної академiї наук України, 2011, №10 53
|