Системы с повторными вызовами и переменной интенсивностью входящего потока
Розглянуто системи з повторними викликами типу MQ / M / m / ∞ зі змінною інтенсивністю вхідного потоку, для яких знайдено умову існування стаціонарного режиму. Для розрахунку стаціонарних ймовірностей використано метод апроксимації. Запропонований алгоритм застосовано для розв’язання задачі оптиміза...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86243 |
| 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: | Системы с повторными вызовами и переменной интенсивностью входящего потока / И.Я. Усар, Е.А. Лебедев // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 151-159. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860262643666780160 |
|---|---|
| author | Усар, И.Я. Лебедев, Е.А. |
| author_facet | Усар, И.Я. Лебедев, Е.А. |
| citation_txt | Системы с повторными вызовами и переменной интенсивностью входящего потока / И.Я. Усар, Е.А. Лебедев // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 151-159. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто системи з повторними викликами типу MQ / M / m / ∞ зі змінною інтенсивністю вхідного потоку, для яких знайдено умову існування стаціонарного режиму. Для розрахунку стаціонарних ймовірностей використано метод апроксимації. Запропонований алгоритм застосовано для розв’язання задачі оптимізації в класі порогових стратегій.
The paper addresses retrial queues MQ / M / m / ∞ with variable rate of input flow. For such queues, a condition of the existence of stationary mode is found. The approximation approach is used in the calculation of stationary probabilities. The proposed scheme was applied to solve an optimization problem in a class of threshold strategies.
|
| first_indexed | 2025-12-07T18:57:06Z |
| format | Article |
| fulltext |
ÓÄÊ 519.21
È.ß. ÓÑÀÐ, Å.À. ËÅÁÅÄÅÂ
ÑÈÑÒÅÌÛ Ñ ÏÎÂÒÎÐÍÛÌÈ ÂÛÇÎÂÀÌÈ
È ÏÅÐÅÌÅÍÍÎÉ ÈÍÒÅÍÑÈÂÍÎÑÒÜÞ ÂÕÎÄßÙÅÃÎ ÏÎÒÎÊÀ
Êëþ÷åâûå ñëîâà: ñèñòåìà ñ ïîâòîðíûìè âûçîâàìè, ñòàöèîíàðíûé ðåæèì,
ïîðîãîâàÿ ñòðàòåãèÿ, îïòèìèçàöèÿ.
Ðåçóëüòàòû äëÿ ñèñòåì ñ ïîâòîðíûìè âûçîâàìè ïðåäñòàâëÿþò îäèí èç âàæíûõ
ðàçäåëîâ òåîðèè ìàññîâîãî îáñëóæèâàíèÿ [1]. Ïîäðîáíûé îáçîð ñîîòâåòñòâóþ-
ùèõ ðåçóëüòàòîâ ìîæíî íàéòè â [2, 3]. Ñèñòåìû ñ ïîâòîðíûìè âûçîâàìè øèðî-
êî èñïîëüçóþòñÿ â êà÷åñòâå ìàòåìàòè÷åñêîé ìîäåëè äëÿ ðåàëüíûõ ñèñòåì â ýêî-
íîìèêå, ïðàêòèêå ïðîåêòèðîâàíèÿ êîìïüþòåðíûõ ñåòåé, ñîâðåìåííûõ ñèñòåìàõ
ìîáèëüíîé ñâÿçè, äëÿ îïèñàíèÿ ïîñàäêè âîçäóøíûõ ñóäîâ è äð. [4–6], ÷òî îáú-
ÿñíÿåò èíòåíñèâíîå ðàçâèòèå çà ïîñëåäíèå äåñÿòèëåòèÿ òåîðèè ýòèõ ñèñòåì.
Õàðàêòåðíàÿ îñîáåííîñòü ðàññìàòðèâàåìûõ ñèñòåì çàêëþ÷àåòñÿ â òîì, ÷òî
â ñëó÷àå çàíÿòîñòè âñåõ ïðèáîðîâ ïðèáûâøèå òðåáîâàíèÿ ïîïàäàþò íà âèðòóàëü-
íóþ îðáèòó è ïîòîì ñíîâà ÷åðåç ñëó÷àéíûé ïðîìåæóòîê âðåìåíè ïîâòîðÿþò ïî-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 151
© È.ß. Óñàð, Å.À. Ëåáåäåâ, 2013
ïûòêó ïîëó÷èòü îáñëóæèâàíèå. Îòìåòèì, ÷òî â ðàìêàõ ìîäåëåé ñèñòåì ñ ïîâòîð-
íûìè âûçîâàìè ìîæíî ñòàâèòü è ðåøàòü çàäà÷è îïòèìàëüíîãî âûáîðà ïàðàìåò-
ðîâ ñèñòåìû, ÷åìó è ïîñâÿùåíà íàñòîÿùàÿ ñòàòüÿ.  íåé ðàññìîòðåíà ñèñòåìà
îáñëóæèâàíèÿ ñ ïîâòîðíûìè âûçîâàìè òèïà M M mQ / / / �, â êîòîðîé èíòåíñèâ-
íîñòü âõîäÿùåãî ïîòîêà � j çàâèñèò îò j — êîëè÷åñòâà èñòî÷íèêîâ ïîâòîðíûõ
âûçîâîâ. Âðåìÿ îáñëóæèâàíèÿ íà êàæäîì èç m ïðèáîðîâ ïîêàçàòåëüíîå ñ ïàðà-
ìåòðîì �. Åñëè âñå ïðèáîðû çàíÿòû, òî òðåáîâàíèå ïåðåõîäèò íà îðáèòó è ïîâòî-
ðÿåò ïîïûòêó ïîëó÷èòü îáñëóæèâàíèå ÷åðåç ñëó÷àéíîå âðåìÿ, êîòîðîå èìååò ïî-
êàçàòåëüíîå ðàñïðåäåëåíèå ñ ïàðàìåòðîì �. Èíòåíñèâíîñòè îáñëóæèâàíèÿ è ïî-
âòîðíûõ âûçîâîâ ÿâëÿþòñÿ ïîñòîÿííûìè. Cèìâîë � â êîäèðîâêå ñèñòåìû
îáîçíà÷àåò åìêîñòü îðáèòû.
Äëÿ ïîèñêà ñòàöèîíàðíîãî ðàñïðåäåëåíèÿ ïðîöåññà îáñëóæèâàíèÿ â ñèñòåìå
M M mQ / / / � ïðåäëîæåí ïîäõîä, ñîñòîÿùèé èç äâóõ ýòàïîâ: íà ïåðâîì íàõîäÿò-
ñÿ ÿâíûå ôîðìóëû ñòàöèîíàðíîãî ðàñïðåäåëåíèÿ â âåêòîðíî-ìàòðè÷íîé ôîðìå
äëÿ êîíå÷íîé îðáèòû, íà âòîðîì — ñòàöèîíàðíûå âåðîÿòíîñòè äëÿ áåñêîíå÷íîé
îðáèòû àïïðîêñèìèðóþòñÿ âåðîÿòíîñòÿìè, ïîëó÷åííûìè íà ïåðâîì ýòàïå.
ÌÀÐÊÎÂÑÊÀß ÌÎÄÅËÜ ÏÐÎÖÅÑÑÀ ÎÁÑËÓÆÈÂÀÍÈß
È ÏÎÑÒÀÍÎÂÊÀ ÎÏÒÈÌÈÇÀÖÈÎÍÍÎÉ ÇÀÄÀ×È
 êà÷åñòâå ìîäåëè ïðîöåññà îáñëóæèâàíèÿ ðàññìîòðèì äâóõìåðíóþ öåïü Ìàð-
êîâà Q t Q t Q t( ) ( ( ), ( ))� 1 2 ñ íåïðåðûâíûì âðåìåíåì â ôàçîâîì ïðîñòðàíñòâå
S I J� � , I m� { }0 1, , ,� , J � { }0 1, , � , ãäå Q t1 ( ), Q t2 ( ) — êîëè÷åñòâî çàíÿòûõ
ïðèáîðîâ è èñòî÷íèêîâ ïîâòîðíûõ âûçîâîâ ñîîòâåòñòâåííî. Èíôèíèòåçèìàëü-
íûå õàðàêòåðèñòèêè q i j i j( , )( , )� � öåïè Q t( ) çàäàíû ñëåäóþùèìè ñîîòíîøåíèÿìè:
— åñëè i m j J� � �0 1 1, , , ,� , òî
q
i j i j
i i j i
i j i j
j
( , )( , )
( , ) ( , ),
( , ) (
� � �
� � � �
� � �
�
�
ïðè
ïðè
1
�
� � � � �
� � � � �
1
1 1
, ),
( , ) ( , ),
( ) ( , )
j
j i j i j
i j i jj
�
� � �
ïðè
ïðè �
�
�
�
�
�
( , ),i j
0
(1)
— åñëè i m j J� �, , òî
q
i j m j
m i j m
m j i j
j
( , )( , )
( , ) ( , ),
( , ) (
� � �
� � � �
� � �
�
�
ïðè
ïðè
1
�
� � � � �
�
�
�
�
�
1
0
, ),
( ) ( , ) ( , ),
j
m i j m jj� � ïðè
(2)
Âûÿñíèì óñëîâèÿ ñóùåñòâîâàíèÿ ñòàöèîíàðíîãî ðåæèìà äëÿ ïðîöåññà Q t( ).
Ëåììà 1. Ïóñòü � ��
�lim sup
j
j . Òîãäà ïðè
�
�m
1 öåïü Q t( ) ýðãîäè÷åñêàÿ
è åå ïðåäåëüíîå ðàñïðåäåëåíèå ñîâïàäàåò ñ åäèíñòâåííûì ñòàöèîíàðíûì.
Äîêàçàòåëüñòâî.  êà÷åñòâå òåñò-ôóíêöèé Ëÿïóíîâà ðàññìîòðèì ôóíêöèè
âèäà
�( , ) , ( , )i j ai j i j S� � � . (3)
Äëÿ óêàçàííûõ òåñò-ôóíêöèé ñðåäíèé ïåðåíîñ
y q i j i jij i j i j
i j i j
� � � �� �
� � �
� ( , )( , )
( , ) ( , )
( ( , ) ( , ))� �
ñîñòàâèò
y
a i a j a i m
m a i m
ij
j
j
�
� � � � � �
� �
�
� � ��
� �
1 0 1), ,
, .
152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
â îñòàëüíûõ ñëó÷àÿõ;
â îñòàëüíûõ ñëó÷àÿõ.
Ïðè
�
�m
1 äëÿ ëþáîãî a
m
�
�
�
�
�
�
�
�
�
,1 ñóùåñòâóåò òàêîå �� 0, ÷òî yij
�� äëÿ
âñåõ ( , )i j S� çà èñêëþ÷åíèåì êîíå÷íîãî ÷èñëà ñîñòîÿíèé ( , )i j S� . Òàêèì îáðà-
çîì, äëÿ òåñò-ôóíêöèé (3) âûïîëíÿþòñÿ óñëîâèÿ òåîðåìû Òâèäè èç [2].
Ëåììà äîêàçàíà.
Ïåðåìåííûé õàðàêòåð èíòåíñèâíîñòè âõîäÿùåãî ïîòîêà â ìîäåëÿõ òèïà
M M mQ / / / � äàåò âîçìîæíîñòü ñòàâèòü è ðåøàòü äëÿ íèõ ðàçëè÷íûå îïòèìèçà-
öèîííûå çàäà÷è. Ðàññìîòðèì êëàññ ïîðîãîâûõ ñòðàòåãèé, êîòîðûå çàäàþòñÿ ÷èñ-
ëàìè 0 0 1 1� � � �
� ��H H H HN N� , � � �H H H H N( , , , )1 2 1� , ãäå N —
ôèêñèðîâàííîå ÷èñëî. Åñëè â ìîìåíò âðåìåíè t � 0 êîëè÷åñòâî èñòî÷íèêîâ
ïîâòîðíûõ âûçîâîâ Q t H Hi i2 1( ) [ , )� � , i N�1, ,� , òî áóäåì ãîâîðèòü, ÷òî ñèñòå-
ìà ñ ïîâòîðíûìè âûçîâàìè ôóíêöèîíèðóåò â i-ì ðåæèìå è èíòåíñèâíîñòü âõîäÿ-
ùåãî ïîòîêà ðàâíà hi . Äðóãèå ïàðàìåòðû îò ðåæèìà íå çàâèñÿò. Âûáîð ïîðîãîâîé
ñòðàòåãèè îçíà÷àåò ôèêñàöèþ çàâèñèìîñòè � j îò ÷èñëà èñòî÷íèêîâ ïîâòîðíûõ
âûçîâîâ: � j ih� , j H Hi i� �[ , )1 , i N�1, ,� . Èíäåêñ H , Q t Q t H( ) ( , ), ,� � ïðèñâî-
èì ñîîòâåòñòâóþùåìó ïðîöåññó îáñëóæèâàíèÿ è åãî õàðàêòåðèñòèêàì.
Ïóñòü S t H1 ( , ) — êîëè÷åñòâî âûçîâîâ, îáñëóæèâàíèå êîòîðûõ çàâåðøåíî
â ñèñòåìå çà âðåìÿ t; S t H2 ( , ) — êîëè÷åñòâî ïåðâè÷íûõ âûçîâîâ, êîòîðûå ïîëó-
÷èëè îòêàç â îáñëóæèâàíèè è ñòàëè ïîâòîðíûìè; S t H3 ( , ) — êîëè÷åñòâî ïåðå-
êëþ÷åíèé èíòåíñèâíîñòè âõîäÿùåãî ïîòîêà. Åñëè ñóùåñòâóþò ïðåäåëû
lim ( , )
t
it S t H
��
�1 , òî îáîçíà÷èì èõ S Hi ( ), i �1 2 3, , .
Ðàññìîòðèì îïòèìèçàöèîííóþ çàäà÷ó
W H C S H C S H C S H( ) ( ) ( ) ( ) max� � � �1 1 2 2 3 3 , (4)
0 0 1 1 2 10 1 1� � � �
� � � � ��H H H H H i NN N i� � �, { , , }, , , , ,
ãäå C1 — ïðèáûëü, ñâÿçàííàÿ ñ îáñëóæèâàíèåì îäíîãî âûçîâà; C2 — øòðàô
çà îòêàç â îáñëóæèâàíèè ïåðâè÷íîãî âûçîâà è ïåðåâîä åãî íà îðáèòó; C3 —
øòðàô çà ïåðåêëþ÷åíèå èíòåíñèâíîñòè âõîäÿùåãî ïîòîêà.
Ðåøåíèåì çàäà÷è (4) ÿâëÿåòñÿ òàêàÿ ïîðîãîâàÿ ñòðàòåãèÿ H , êîòîðàÿ ìàêñè-
ìèçèðóåò ñðåäíèé äîõîä îò ðàáîòû ñèñòåìû. Ïîäîáíûå îïòèìèçàöèîííûå çàäà÷è
äëÿ îäíîêàíàëüíûõ ñèñòåì ñ ïîâòîðíûìè âûçîâàìè ðàññìîòðåíû â [7, 8].
 óñëîâèÿõ ñóùåñòâîâàíèÿ ñòàöèîíàðíîãî ðåæèìà (óñëîâèÿ ëåììû 1) ïðå-
äåëüíûå ôóíêöèîíàëû S Hi ( ), i �1 2 3, , , òîæå ñóùåñòâóþò è èõ ìîæíî âûïèñàòü,
ïîäñòàâèâ ñòàöèîíàðíûå âåðîÿòíîñòè � ij i j I J, ( , )� � :
S H i Hij
i
m
j
1
10
( ) ( )�
��
�
�� �� , S H h Hi
i
N
m j
j H
H
i
i
2
1
1
1
( ) ( )�
� �
�
� �
�
� ,
S H h H Hi mH i kH
k
m
i
N
i i3 1
0
1
1
1
( ) ( )� �
�
�
�
�
�
�
�
��
�
�
�
�
�� � � � .
Òàêèì îáðàçîì, äëÿ ðåøåíèÿ îïòèìèçàöèîííîé çàäà÷è íåîáõîäèìû ýôôåê-
òèâíûå àëãîðèòìû ðàñ÷åòà ñòàöèîíàðíîãî ðàñïðåäåëåíèÿ äëÿ ñèñòåìû òèïà
M M mQ / / / �.
ÑÒÀÖÈÎÍÀÐÍÛÅ ÂÅÐÎßÒÍÎÑÒÈ ÄËß ÑÈÑÒÅÌÛ Ñ ÊÎÍÅ×ÍÎÉ ÎÐÁÈÒÎÉ
Ñèñòåìà ñ ïîâòîðíûìè âûçîâàìè è êîíå÷íîé îðáèòîé èìååò îãðàíè÷åíèå N íà
ìàêñèìàëüíî âîçìîæíîå êîëè÷åñòâî èñòî÷íèêîâ ïîâòîðíûõ âûçîâîâ. Èíôèíèòåçè-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 153
ìàëüíûå õàðàêòåðèñòèêè q
i j i j
N
( , )( , )
( )
� �
äëÿ ïðîöåññà îáñëóæèâàíèÿ Q tN( ) ( ) �
� ( ( ), ( ))( ) ( )Q t Q tN N
1 2
ñîâïàäàþò ñ (1) ïðè i m� 0 1 1, , , –� è j N� 0 1, , ,� , à òàê-
æå ñ (2) ïðè i m� è j N� �0 1 1, , ,� .
Åñëè i m� è j N� , òî
q
m i j m N
m i j
m N i j
N
( , )( , )
( )
( , ) ( , ),
( ,
� �
�
� � � �
� � �
�
�
ïðè
ïðè
1
) ( , ),�
�
�
�
m N
0 â îñòàëüíûõ ñëó÷àÿõ.
Öåïü Ìàðêîâà Q tN( ) ( ) ïðèíèìàåò çíà÷åíèå â êîíå÷íîì ìíîæåñòâå ñîñòîÿ-
íèé S I JN N( ) ( )� � , J NN( ) { , , , }� 0 1 � , è ÿâëÿåòñÿ ýðãîäè÷åñêîé. Îáîçíà÷èì åå
ñòàöèîíàðíîå ðàñïðåäåëåíèå � ij
N( ) , ( , ) ( )i j S N� .
Ïîñêîëüêó èíòåíñèâíîñòü âõîäÿùåãî ïîòîêà çàâèñèò îò êîëè÷åñòâà ïîâòîð-
íûõ âûçîâîâ, äëÿ ïîèñêà ñòàöèîíàðíûõ âåðîÿòíîñòåé íåâîçìîæíî èñïîëüçîâàíèå
ïðîèçâîäÿùèõ ôóíêöèé.  ðàññìàòðèâàåìîì ñëó÷àå íà îñíîâàíèè òåîðåìû î ðà-
âåíñòâå ïîòîêîâ âåðîÿòíîñòåé ÷åðåç ãðàíèöó çàìêíóòîãî êîíòóðà â ñòàöèîíàðíîì
ðåæèìå ïðåîáðàçóåì ñèñòåìó óðàâíåíèé Êîëìîãîðîâà ê âèäó, êîòîðûé ïîçâîëèò
âûïèñàòü ñòàöèîíàðíûå âåðîÿòíîñòè â ÿâíîì âåêòîðíî-ìàòðè÷íîì âèäå.
×òîáû ñôîðìóëèðîâàòü îñíîâíîé ðåçóëüòàò, ââåäåì îáîçíà÷åíèÿ. Ïóñòü A j( ),
j N� �0 1 1, , ,� , — òðåõäèàãîíàëüíàÿ ìàòðèöà âèäà
A j
a a
a a a
a a
( )
( ) ( )
( ) ( ) ( )
( ) (
�
�
� �
�
0
0
0
1 1
0
1
2 2
0 0 0 0 0
0 0 0 0
0
�
�
0
2
2 2
0
2
0 0 0
0 0 0 0
0 0 0 0
) ( )
( ) ( ) ( )
a
a a a
m m m
�
�
�
� �
�
�
� � � � � � � �
�
� 0
1 1
0a a
m m�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�( ) ( )
,
ãäå a i ji j
( )0 � � �� � �, i m� �0 1 1, , ,� ; a i mi j
( ) , , , ,� � � � �� 0 1 2� ; a ii
( )� � � �,
i m� �1 2 1, , ,� ;
B C�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
0 0 0�
�
� � � � �
�
�
�
,
1
0 0 0 1
0 0 0 1
0 0 0 1
�
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
ÿâëÿþòñÿ ìàòðèöàìè ðàçìåðíîñòè ( )m m� .
Îáîçíà÷èì òðåóãîëüíóþ ìàòðèöó
D N
N
N N
N
N
N( )
( )
( )�
� �
� � �
�
�
� � �
� � � �
�
0 0 0 0
2 0 0 0
3 0 0
�
�
�
� � � � � �
� � � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�N N N mN� � � � �� ( ) ( )1
,
à òàêæå âåêòîðû
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
� � � �' ( ) ( , , , )( ) ( ) ( ) ( )N
j
N
j
N
m j
Nj �
�0 1 1
� ,
G j
j
G G GN
N
N
N j
N
j
N
m j
N' ( )
' ( )
( , , , )( )
( )
( )
( ) ( ) ( )� �
�
�
�
0
0 1 1
� .
Îáîçíà÷èì ( )m�1 -ìåðíûé âåêòîð, ñîñòîÿùèé èç åäèíèö, 1 1( )m� ; ( )m�1 -ìåð-
íûé âåêòîð, i-ÿ êîìïîíåíòà êîòîðîãî ðàâíà åäèíèöå, à îñòàëüíûå ðàâíû íóëþ,
e mi ( )�1 ; 1, ei — àíàëîãè÷íûå âåêòîðû ðàçìåðíîñòè m.
Òåîðåìà 1. Åñëè � j j N� �0 0 1, , , ,� , òî ñòàöèîíàðíûå âåðîÿòíîñòè � ij
N( ) ,
( , ) ( )i j S N� , èìåþò ñëåäóþùèé âèä:
�
�
�
�
1
2
1
0
1
N
N
N
N
m N
N
N
N D N N
( )
( )
( )
( ) ( )(
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� � �1 1 1 0 1 11( ) ( )), , , ,m e m j NN� � � � �� ; (5)
�
�
�
� �
mN
N N
N
N
N m
m
G N N e j N( )
( )
( ) ( )( ), , , ,� � � � �0 1 0 1 1� ;
� � � � � � �
�
�
� �
j
N N
N N j
N
N
j
G N T N T j j( )
( )
( )
!
!
( ) ( ) ( ), , ,0 1 0 1� � , N �1; (6)
�
� �
�mj
N N
N N j
j
N
N
j
G N T N T j j( )
( )
( )
!
!
( ) ( ) ( ) ,� � � � � � �
�
0 1 1 1� 0 1 1, , , ,� N � (7)
ãäå
�
�
0
0
1
1 1
N
N N
N j
j
N
G N N
j
T N( ) ( ) ( ) !
!
( )� � � � �
�
�
�
�
�
��
�
�
�
� �
�� � �
�
�
�
�
�
� � �
�
�
�
�
!
�
"�
�
T j T j
m
N e
j
N m( ) ( ) ( )1
1
1
1
1
1
� �
� � , (8)
G N
D N N m e m
N
N
( ) ( )
( )( ( ) ( ))
�
� � �
�
�
�
�
�
��
1
1 1 11
1� �
,
(9)
T j B
m
C A j j N
j
( ) ( ), , , ,� �
�
�
�
�
�
� � ���
�
1 0 1 1� .
Äîêàçàòåëüñòâî. Äëÿ óäîáñòâà îáîçíà÷èì � �ij
N
ij
( ) ~� , G Gij
N
ij
( ) ~
� ,
( , ) ( )i j S N� . Äëÿ êàæäîãî k m� �0 1 1, , ,� ðàçîáüåì S N( ) íà äâà ïîäìíîæåñòâà:
E N N k Nk � {( , ), ( , ), , ( , )}0 1 � è E S Ek
N
k� ( ) \ . Â ñèëó ðàâåíñòâà ïîòîêîâ âåðî-
ÿòíîñòåé ÷åðåç çàìêíóòûé êîíòóð â ñòàöèîíàðíîì ðåæèìå [6] èìååì
N N N NN N k N N kN�� �� �� � � �~ ~ ~ ( )~0 1 1� � � � � ���
� � � ��( ) ~ , , , ,k k mk N1 0 1 11�� � . (10)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 155
Äëÿ
~
~
~
, ( , ) ( )G i j Sij
ij
N
N� �
�
� 0
, ïåðâûå ( )m�1 óðàâíåíèÿ èç ñèñòåìû (10) èìå-
þò âèä ~
~
( )( ( ) ( ))
G
G
D N N m e m
N
m N
N
1
1
1
11 1 1�
�
�
�
�
�
�
�
�
�
�
�
�
� � � �� � ,
÷òî äàåò (9). Èç (10) ïðè k m� �1 ïîëó÷àåì
~ ~
( )( )G
m
G N N emN N m� � �
1
1
�
� � .
(11)
Íàéäåì
~
Gmj ïðè óñëîâèè, ÷òî j N� �0 1 1, , ,� . Ðàçîáüåì S N( ) íà äâà ïîä-
ìíîæåñòâà: S S jj
N N( ) ( ){( , ) : }� � �
è S S Sj
N N
j
N( ) ( ) ( )\� . Ñíîâà èñïîëüçóÿ
ðàâåíñòâî ïîòîêîâ âåðîÿòíîñòåé ÷åðåç çàìêíóòûé êîíòóð, èìååì � �j mj
~ �
� � � � �� � �( ) ~ ( ) ~j jj m j1 10 1 1 1�� ��� , îòêóäà ïîëó÷àåì
~ ( ) ~
' ( ) , , , ,G
j
G j j Nmj
j
�
�
� � �
1
1 1 0 1 1
�
�
� . (12)
Ðàññìîòðèì m N� çàìêíóòûõ êîíòóðîâ, êîòîðûå ñîäåðæàò îäíó òî÷êó ( , )i j
èç îáëàñòè
~
{ , , , } {( , , }( )S m NN � � � �0 1 1 0 1 1� � . Ñîîòâåòñòâóþùèå óðàâíåíèÿ
äëÿ
~
Gij , ( , )
~ ( )i j S N� , èìåþò âèä
( )
~ ~
, ,� � �j j jj G G i� � �0 1 0 (13)
( )
~
( )
~ ~
( )
~
� � � � � �j ij i j j i j ii j G j G G i G� � � � � � �� � � �1 11 1 1 1 j i m, , , , .� �1 2 2� (14)
Ïðè i m� �1 ñ ó÷åòîì (12) ïîëó÷àåì
( ( ) )
~
� � �j m jm j G� � � ��1 1
� � � �
�
�� � �( )
~ ~ ( ) ~
' ( )j G G
j m
G jm j j m j
j
1
1
1 12 1 2� �
��
�
. (15)
Ïðåäñòàâèì cèñòåìó (13)–(15) â âåêòîðíî-ìàòðè÷íîì âèäå
~
' ( ) ( )
~
' ( ) ( )G j j G j B
m
C A j
j
� � � �
�
�
�
�
�
� ��1 1 1�
�
�
� � � �( )
~
' ( ) ( ), , , , –j G j T j j N1 1 0 1 1� � . (16)
Ïîäñòàâëÿÿ ïðàâóþ ÷àñòü (16) â (12), èìååì
~ !
!
~
' ( ) ( ) ( ) , , , ,G
N
j
G N T N T j j Nmj
N j
j
� � � � � � �
��
�
1 1 1 0 1 1� � .
Óñëîâèå íîðìèðîâêè äëÿ ñòàöèîíàðíûõ âåðîÿòíîñòåé ~ , ( , )� ij i j S� , ïîçâî-
ëÿåò íàéòè ~� 0 N . Ýòî äàåò ôîðìóëó (8). Ñîîòíîøåíèÿ (5)–(7) ÿâëÿþòñÿ ïðÿìûì
ñëåäñòâèåì (11)–(16).
Òåîðåìà äîêàçàíà.
Î÷åâèäíî, ôîðìóëû (5)–(9) ïðåäñòàâëÿþò ñîáîé ýôôåêòèâíóþ ðåêóððåíòíóþ
ïðîöåäóðó äëÿ âû÷èñëåíèÿ ñòàöèîíàðíîãî ðàñïðåäåëåíèÿ.
156 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Åñëè ñïðàâåäëèâû óñëîâèÿ ëåììû 1 è N � �, òî ñòàöèîíàðíûå âåðîÿòíîñòè
� ij
N Ni j S( ) ( ), ( , )� , ñõîäÿòñÿ ê ñîîòâåòñòâóþùèì âåðîÿòíîñòÿì ñèñòåìû òèïà
M M mQ / / / �.
ÑËÅÄÑÒÂÈß ÄËß ÑËÓ×Àß ÄÂÓÕ ÎÁÑËÓÆÈÂÀÞÙÈÕ ÏÐÈÁÎÐÎÂ
Ðàññìîòðèì ñèñòåìó òèïà M MQ / / /2 �. Â ýòîì êëàññå ìîäåëåé ìîæíî ïðî-
âåñòè áîëåå ïîäðîáíûé àíàëèç è ïîëó÷èòü ÿâíûå ôîðìóëû.
Ïîëîæèì, íå íàðóøàÿ îáùíîñòè, � �1 è
A j
k
k k
i j
i
k k
k kk i
j
( )
( )
[( ) ]
, ,
�
� � � �
� �
�
�
�
#
1 1
1
1
2
1 � � �
� � � �
, ,i j�
�
�
�
ãäå �
�
�
�
k
k k� �
2 2
— çàãðóçêà ñèñòåìû ïåðâè÷íûìè òðåáîâàíèÿìè, êîãäà
Q t k2 ( ) � .
Ñëåäñòâèå 1. Ïðè óñëîâèÿõ � j � 0, j � 0 1, , ,� è lim sup /
j
j� 2 1
äëÿ ñèñòå-
ìû ñ ïîâòîðíûìè âûçîâàìè òèïà M MQ / / /2 � ñòàöèîíàðíûå âåðîÿòíîñòè èìå-
þò âèä
�
�
0 j
j
j
R
j
�
!
, �
� �
�
1 j
j j
j
j R
j
�
�( )
!
,
�
� �
� �
� � � �
� �
2
1
21 1
1
j
j j
j
j
j j
j j
j R
j
j j
�
� � �
$
� �
� �
�( ( ) )
!
[( ) ]
� � �1 1( )j �
, (17)
ãäå
R
i A j
i
i
i A i
j
i i
i
i
i
ji ji
j
�
� �
�
� �
� �
�
�
��
( ) ( )
! ! ( )
1 1
10
� �
�
� �
�
�
��
�
�
� � �
�
� � �� �
�
�
��
( ( ) ) ( )
!
( )1 1 1 11 1
0
1
1� �
� �
� �i i
i
i
i
j
ii A j
i
i
� �i
i
ji j i A i! ( )�
!
�
"��
�
�
�
1
1
. (18)
Äîêàçàòåëüñòâî. Ñíà÷àëà èçó÷èì ìîäåëü M M NQ / / /2 , ãäå N — ìàêñè-
ìàëüíî âîçìîæíîå êîëè÷åñòâî èñòî÷íèêîâ ïîâòîðíûõ âûçîâîâ. Ïðèìåíèì ê ýòîé
ñèñòåìå ðåçóëüòàòû òåîðåìû 1, êîòîðàÿ äàåò ÿâíûå ôîðìóëû äëÿ ñòàöèîíàðíûõ
âåðîÿòíîñòåé. Äåéñòâèòåëüíî, â äàííîì ñëó÷àå
B C A j
j
j
j j
j
�
�
�
�
�
�
� �
�
�
�
�
�
� �
� �
� � �
�
�
0 1
0 0
0 1
0 1 1 1
, , ( )
� � �
� �
��
�
�
��
è
T j
j j
j
j
j j
j j j
j
( )
[( ) ]
( )( )
�
� �
� � �
�
�
�
��
�
�
1 1 1
12� � � �
� � � �
� �
�� , j N� �0 1 1, , ,� .
Èç ôîðìóë (5)–(9) ïîñëå ñîîòâåòñòâóþùèõ ïðåîáðàçîâàíèé ïîëó÷àåì
� �
�
0 0j
N
N
N
N j
jN A N
j
( ) ( ) ! ( )
!
�
�
, � �
� � �
1 0j
N
N
N
N j
j jN j A N
j
( ) ( ) ! ( ) ( )
!
�
��
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 157
� �
� � �
�2 0
1 11 1
0
j
N
N
N
N j
j j
j
N j A N
j
j( ) ( ) ! ( ( ) ) ( )
!
, ,�
� � �
�
�
� �
1 1, ,� N � ,
� � � �
1 0N
N
N
N
N N( ) ( ) ( )� � , � �
� � �
2 0
2
2N
N
N
N N N N( ) ( ) ( )
�
� �
,
� � �
� � �
0
0
1
1
1
N
N
N
N j
j j
j
N
N N
j A N
j
( ) !
( ) ( )
!
� � � �
� �
�
�
��
�
�
�
�
�
� � �
� �
�
� �
�
�
�N
j A N
j
N
N j
j j
jj
N
N!
( ( ) ) ( )
!
((
� � �
�
� �
1 1 1
2
1 1
0
1
) )2
1
�
!
�
"�
�
N� .
Ïåðåõîäÿ ê ïðåäåëó â ýòèõ ôîðìóëàõ ïðè N � �, ïîëó÷àåì
R N A N
i A N
i A
j
N N
N N
j
N
i i
i
% �
� �
�� ��
lim ! ( ) lim
( ) ( )
!
( )� �
� �
�
0
1
ji
N
N( )�
�
� �
�
�� 0
1
�
� � �
!
�
��
� �
�
�
�lim
( ( ) ) ( )
! ( )N
i i
i
i
ji
N i A N
i A N
1 11 1
0
1 � �
� � "�
�1
.
Åñëè i j N,
, òî
A N
A N
A j i j
A i i j
A i
i
j
i
i
j
( )
( )
( ), ,
( ) , ,
( ),
�
� �
�
åñëè
åñëè
å
1
1 ñëè i j�
�
�
� ,
è ïîýòîìó
lim ! ( )
( ) ( )
!
( )
N N
N N
j
i i
i
i
j
iN A N
i A j
i�� �
�
� �
�
�
�� �
� �
�
�
0
0
1 1 �
�
��
�
� �
�
�
i
i A ii
ji j
�
�! ( )1
�
� � �
�
� � �� �
�
�
��
( ( ) ) ( )
!
( )1 1 1 11 1
0
1
1� �
� �
� �i i
i
i
i
j
ii A j
i
i
� �i
i
ji j i A i! ( )�
!
�
"��
�
�
�
1
1
.
Èç ýòèõ ñîîòíîøåíèé ïîëó÷àåì (17), (18). Ñëåäñòâèå äîêàçàíî.
Èçó÷èì ñêîðîñòü ñõîäèìîñòè ñòàöèîíàðíûõ âåðîÿòíîñòåé äëÿ ñèñòåì
M M NQ / / /2 è M MQ / / /2 �. Àíàëèçèðóÿ ÿâíûé âèä ôîðìóë äëÿ � ij è � ij
N( ) ,
ïîëó÷àåì ñëåäóþùèé ðåçóëüòàò.
Cëåäñòâèå 2. Ïóñòü äëÿ ñèñòåìû M MQ / / /2 � ñïðàâåäëèâû óñëîâèÿ
ñëåäñòâèÿ 1. Òîãäà äëÿ ëþáîãî j èìååì
lim ( )! ( )| |
!
( )
N
N
j j j
N
j
j
N A N
j�� �
� � �2
1
2
0 0 2 2
� � �
� �
,
lim ( )! ( )| |
!
( )
N
N
j j j
N j
j
j
N A N
j
j�� �
� � �
�
2
2
1 1 2 2
� � �
� �
� �
,
lim ( )! ( )| |
( )( )
N
N
j j j
N j
j
N A N
j
��
�
�
� � �
� � �
2
1 1
2
1 2 2
1
� � �
� �
� j j
j!� ��2 2
,
158 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
ãäå
�
� �
�
� �
� �
j
i i
i
i i
i
i
i A j
i
i A j
i
�
� �
�
� � �� �( ) ( )
!
( ( ) ) ( )
!
1 1 11 1
i
j
i
j
�
�
�
�� �
0
1
0
�
� �
�
� � �
�� �
�
��
1 1 1
11
1� �
�
� �
� �
i
i
ji j
i
i
i
j
i
i A i
i
i A i! ( )
( )
! ( )i j�
�
� .
Ðàññìîòðèì ïðèìåð ñèñòåìû òèïà M MQ / / /2 20 , ôóíêöèîíèðóþùåé â äâóõ
ðåæèìàõ, âûáîð êîòîðûõ îïðåäåëÿåòñÿ ïîðîãîì H �{ , , , }1 2 19� . Çàôèêñèðîâàíû
ñëåäóþùèå ïàðàìåòðû ñèñòåìû: h1 2 5� , ; h2 0 5� , ; � �1; � � 0 1, . Êîýôôèöèåíòû
êà÷åñòâà ðàâíû: C1 6� , C2 2� , C3 4� .
Ïðîãðàììà, íàïèñàííàÿ íà îñíîâå ïîëó÷åííûõ ôîðìóë, äàåò ñëåäóþùèå
çíà÷åíèÿ öåëåâîãî ôóíêöèîíàëà:
W W W W( ) , ; ( ) , ; ( ) , ; ( ) ,1 3 29487 2 3 42729 3 3 53285 4 3 6186� � � � 1;
W W W W( ) , ; ( ) , ; ( ) , ; ( ) ,5 3 68956 6 3 74924 7 3 80022 8 3 8443� � � � 7;
W W W W( ) , ; ( ) , ; ( ) , ; ( ) ,9 3 88309 10 3 91744 11 3 94823 12 3 9� � � � 7605;
W W W W( ) , ; ( ) , ; ( ) , ; ( ) ,13 4 00132 14 4 02418 15 4 04396 16 4� � � � 05742;
W W W( ) , ; ( ) , ; ( ) ,17 4 05189 18 3 97815 19 3 61672� � � .
Òàêèì îáðàçîì, ìàêñèìóì öåëåâîé ôóíêöèè 4 05742, äîñòèãàåòñÿ äëÿ ïîðîãà
H �16.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ê î â à ë å í ê î È . Í . , Ê î á à Å . Â . Ê êëàññèôèêàöèè ÑÌÎ ñ ïîâòîðåíèåì âûçîâîâ // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2010. — ¹ 3. — Ñ. 84–91.
2. F a l i n G . I . , T e m p l e t o n J . G . C . Retrial Queues. — London: Chapman and Hall, 1997. — 317 p.
3. A r t a l e j o J . R . , G o m e z - C o r r a l A . Retrial Queueing Systems. — Berlin: Springer, 2008. — 317 p.
4. A r t a l e j o J . R . , F a l i n G . I . Standard and retrial queueing systems: A comparative analysis // Revista
Matematica Complutense. — 2002. — 15. — P. 101–129.
5. A n i s i m o v V . V . , A r t a l e j o J . R . Analysis of Markov multiserver retrial queues with negative arriv-
als // Queuing Systems. — 2001. — 39. — P. 157–182.
6. Ó î ë ð ý í ä Ä æ . Ââåäåíèå â òåîðèþ ñåòåé ìàññîâîãî îáñëóæèâàíèÿ. — Ì.: Ìèð, 1993. — 336 c.
7. Ê ë è ì å í î ê  . È . Îïòèìèçàöèÿ äèíàìè÷åñêîãî óïðàâëåíèÿ ðåæèìîì ðàáîòû èíôîð-
ìàöèîííî-âû÷èñëèòåëüíûõ ñèñòåì ñ ïîâòîðíûìè âûçîâàìè // Àâòîìàòèêà è âû÷èñëèòåëüíàÿ òåõíèêà.
— 1990. — ¹ 1. — Ñ. 25–30.
8. Ä ó ä è í À . Í . , Ê ë è ì å í î ê  . È . Îïòèìèçàöèÿ äèíàìè÷åñêîãî óïðàâëåíèÿ âõîäíîé íàãðóçêîé
â óçëå èíôîðìàöèîííî-âû÷èñëèòåëüíîé ñåòè // Òàì æå. — 1991. — ¹ 2. — Ñ. 25–31.
Ïîñòóïèëà 13.12.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 159
|
| id | nasplib_isofts_kiev_ua-123456789-86243 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:57:06Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Усар, И.Я. Лебедев, Е.А. 2015-09-10T19:10:24Z 2015-09-10T19:10:24Z 2013 Системы с повторными вызовами и переменной интенсивностью входящего потока / И.Я. Усар, Е.А. Лебедев // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 151-159. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86243 519.21 Розглянуто системи з повторними викликами типу MQ / M / m / ∞ зі змінною інтенсивністю вхідного потоку, для яких знайдено умову існування стаціонарного режиму. Для розрахунку стаціонарних ймовірностей використано метод апроксимації. Запропонований алгоритм застосовано для розв’язання задачі оптимізації в класі порогових стратегій. The paper addresses retrial queues MQ / M / m / ∞ with variable rate of input flow. For such queues, a condition of the existence of stationary mode is found. The approximation approach is used in the calculation of stationary probabilities. The proposed scheme was applied to solve an optimization problem in a class of threshold strategies. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Системы с повторными вызовами и переменной интенсивностью входящего потока Системи з повторними викликами і змінною інтенсивністю вхідного потоку Retrial queues with variable rate of input flow Article published earlier |
| spellingShingle | Системы с повторными вызовами и переменной интенсивностью входящего потока Усар, И.Я. Лебедев, Е.А. Системный анализ |
| title | Системы с повторными вызовами и переменной интенсивностью входящего потока |
| title_alt | Системи з повторними викликами і змінною інтенсивністю вхідного потоку Retrial queues with variable rate of input flow |
| title_full | Системы с повторными вызовами и переменной интенсивностью входящего потока |
| title_fullStr | Системы с повторными вызовами и переменной интенсивностью входящего потока |
| title_full_unstemmed | Системы с повторными вызовами и переменной интенсивностью входящего потока |
| title_short | Системы с повторными вызовами и переменной интенсивностью входящего потока |
| title_sort | системы с повторными вызовами и переменной интенсивностью входящего потока |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86243 |
| work_keys_str_mv | AT usariâ sistemyspovtornymivyzovamiiperemennoiintensivnostʹûvhodâŝegopotoka AT lebedevea sistemyspovtornymivyzovamiiperemennoiintensivnostʹûvhodâŝegopotoka AT usariâ sistemizpovtornimiviklikamiízmínnoûíntensivnístûvhídnogopotoku AT lebedevea sistemizpovtornimiviklikamiízmínnoûíntensivnístûvhídnogopotoku AT usariâ retrialqueueswithvariablerateofinputflow AT lebedevea retrialqueueswithvariablerateofinputflow |