О двухциклической системе обслуживания
Ласло Лакатош [1, 2] ввел в рассмотрение систему обслуживания, в которой время ожидания V требования увеличивается до величины W, кратной T. Эта постановка задачи взята из авиации: величина T интерпретируется как время обхода самолетом круга, на который он отправляется в случае занятости взлетно-пос...
Saved in:
| Date: | 2015 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2015
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/124758 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | О двухциклической системе обслуживания / И.Н. Коваленко // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 59-64. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124758 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1247582017-10-05T03:02:43Z О двухциклической системе обслуживания Коваленко, И.Н. Системный анализ Ласло Лакатош [1, 2] ввел в рассмотрение систему обслуживания, в которой время ожидания V требования увеличивается до величины W, кратной T. Эта постановка задачи взята из авиации: величина T интерпретируется как время обхода самолетом круга, на который он отправляется в случае занятости взлетно-посадочной полосы. В настоящей статье изучается схема обслуживания, в которой V увеличивается до величины T1x+T2y , где T1 и T2 — заданные числа (времена обхода двух кругов), x и y — зависимые от V целые числа (количества их обходов). Доказана эргодическая теорема для соответствующей вложенной цепи Маркова. Приведен алгоритм вычисления x и y по заданному значению V. Л. Лакатош ввів до розгляду систему обслуговування, в якій час очікування V вимоги збільшується до величини, кратної T. Ця модель умотивована проблемами авіації: T інтерпретується як час обходу літаком кола у випадку зайнятості смуги для зльоту і посадки. У даній статті вивчається система обслуговування, в якій V зростає до величини T1x+T2y, де T1 і T2 — задані числа (терміни часу обходу двох кіл), x та y — залежні від V цілі числа (кількість обходів). Доведено ергодичну теорему для відповідного ланцюга Маркова. Наведено алгоритм обчислення x та y за заданим значенням V. L. Lakatos introduced a queuing system in which the waiting time V of a customer is increased up to a value multiple of T. The model is motivated by a problem occurred in aviation. Indeed, T is just the aircraft round time of the emergency circle as soon as the runway is occupied. In the presented paper, a queuing system is considered in which V is increased up to the time T1x+T2y, where T1 and T2 are constant time intervals (round times of two emergency circles) whereas x and y are V-dependent integers (numbers of rounds). An ergodic theorem is proved for a proper embedded Markov chain. An algorithm is given to compute x and y given V. 2015 Article О двухциклической системе обслуживания / И.Н. Коваленко // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 59-64. — Бібліогр.: 9 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124758 519.572 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Коваленко, И.Н. О двухциклической системе обслуживания Кибернетика и системный анализ |
| description |
Ласло Лакатош [1, 2] ввел в рассмотрение систему обслуживания, в которой время ожидания V требования увеличивается до величины W, кратной T. Эта постановка задачи взята из авиации: величина T интерпретируется как время обхода самолетом круга, на который он отправляется в случае занятости взлетно-посадочной полосы. В настоящей статье изучается схема обслуживания, в которой V увеличивается до величины T1x+T2y , где T1 и T2 — заданные числа (времена обхода двух кругов), x и y — зависимые от V целые числа (количества их обходов). Доказана эргодическая теорема для соответствующей вложенной цепи Маркова. Приведен алгоритм вычисления x и y по заданному значению V. |
| format |
Article |
| author |
Коваленко, И.Н. |
| author_facet |
Коваленко, И.Н. |
| author_sort |
Коваленко, И.Н. |
| title |
О двухциклической системе обслуживания |
| title_short |
О двухциклической системе обслуживания |
| title_full |
О двухциклической системе обслуживания |
| title_fullStr |
О двухциклической системе обслуживания |
| title_full_unstemmed |
О двухциклической системе обслуживания |
| title_sort |
о двухциклической системе обслуживания |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2015 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124758 |
| citation_txt |
О двухциклической системе обслуживания / И.Н. Коваленко // Кибернетика и системный анализ. — 2015. — Т. 51, № 1. — С. 59-64. — Бібліогр.: 9 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kovalenkoin odvuhcikličeskojsistemeobsluživaniâ |
| first_indexed |
2025-07-09T01:59:20Z |
| last_indexed |
2025-07-09T01:59:20Z |
| _version_ |
1837132793180585984 |
| fulltext |
ÓÄÊ 519.572
È.Í. ÊÎÂÀËÅÍÊÎ
Î ÄÂÓÕÖÈÊËÈ×ÅÑÊÎÉ ÑÈÑÒÅÌÅ ÎÁÑËÓÆÈÂÀÍÈß
Àííîòàöèÿ. Ëàñëî Ëàêàòîø [1, 2] ââåë â ðàññìîòðåíèå ñèñòåìó îáñëóæèâàíèÿ, â êîòîðîé
âðåìÿ îæèäàíèÿ V òðåáîâàíèÿ óâåëè÷èâàåòñÿ äî âåëè÷èíû W , êðàòíîé T . Ýòà ïîñòàíîâêà
çàäà÷è âçÿòà èç àâèàöèè: âåëè÷èíà T èíòåðïðåòèðóåòñÿ êàê âðåìÿ îáõîäà ñàìîëåòîì êðó-
ãà, íà êîòîðûé îí îòïðàâëÿåòñÿ â ñëó÷àå çàíÿòîñòè âçëåòíî-ïîñàäî÷íîé ïîëîñû.  íàñòîÿ-
ùåé ñòàòüå èçó÷àåòñÿ ñõåìà îáñëóæèâàíèÿ, â êîòîðîé V óâåëè÷èâàåòñÿ äî âåëè÷èíû
T x T y1 2� , ãäå T1 è T2 — çàäàííûå ÷èñëà (âðåìåíà îáõîäà äâóõ êðóãîâ), x è y — çàâèñè-
ìûå îò V öåëûå ÷èñëà (êîëè÷åñòâà èõ îáõîäîâ). Äîêàçàíà ýðãîäè÷åñêàÿ òåîðåìà äëÿ ñîîò-
âåòñòâóþùåé âëîæåííîé öåïè Ìàðêîâà. Ïðèâåäåí àëãîðèòì âû÷èñëåíèÿ x è y ïî
çàäàííîìó çíà÷åíèþ V .
Êëþ÷åâûå ñëîâà: ñèñòåìû ìàññîâîãî îáñëóæèâàíèÿ, ñèñòåìû ñ ïîâòîðíûìè âûçîâàìè,
ñèñòåìû òèïà Ëàêàòîøà, ïðîöåññ ïîñàäêè ñàìîëåòîâ.
Âåíãåðñêèé ìàòåìàòèê Ëàñëî Ëàêàòîø ââåë â ðàññìîòðåíèå ñèñòåìó ìàññîâî-
ãî îáñëóæèâàíèÿ òèïà FCFS, â êîòîðîé âðåìÿ îæèäàíèÿ V òðåáîâàíèÿ óâåëè-
÷èâàåòñÿ äî âåëè÷èíû, êðàòíîé ïîñòîÿííîé âåëè÷èíå T , è íàçâàë åå öèêëè-
÷åñêîé ñèñòåìîé îáñëóæèâàíèÿ [1, 2]. Ïîñòàíîâêà çàäà÷è âçÿòà èç èçó÷åíèÿ
ïðîöåññà îáñëóæèâàíèÿ ïîòîêà ñàìîëåòîâ, çàõîäÿùèõ íà ïîñàäêó â àýðîïîð-
òó ñ åäèíñòâåííîé âçëåòíî-ïîñàäî÷íîé ïîëîñîé (ÂÏÏ). Åñëè â ìîìåíò ïðè-
áëèæåíèÿ ñàìîëåòà ÂÏÏ çàíÿòà, ñàìîëåò íàïðàâëÿåòñÿ â çîíó îæèäàíèÿ, ãäå
ñîâåðøàåò îáõîä «êðóãà» (îðáèòû) çà ïîñòîÿííîå âðåìÿ T . Òàêèì îáðàçîì,
âìåñòî íîìèíàëüíîãî âðåìåíè îæèäàíèÿ V ôàêòè÷åñêîå âðåìÿ îæèäàíèÿ ðàâ-
íî W T V T� ] / [ , ò.å. V óâåëè÷èâàåòñÿ íà íåêîòîðóþ ñëó÷àéíóþ âåëè÷èíó
� � �W V , ñðåäíåå çíà÷åíèå êîòîðîé ñîñòàâëÿåò ïðèìåðíî T / 2 ïðè îòíîñè-
òåëüíî ìàëîì T . Ñèñòåìû òèïà Ëàêàòîøà, îáîáùàþùèå åãî âåðîÿòíîñòíûå
ìîäåëè, èçó÷åíû â ðàáîòàõ [3, 4].
Åñòåñòâåííî èçó÷èòü ñèñòåìó îáñëóæèâàíèÿ òèïà Ëàêàòîøà, â êîòîðîé ìîæ-
íî äîáèòüñÿ çíà÷èòåëüíî ìåíüøåãî çíà÷åíèÿ �. Îäíèì èç âîçìîæíûõ ïîäõîäîâ
ÿâëÿåòñÿ ïðèìåíåíèå ñèñòåìû ñ äâóìÿ «êðóãàìè» (îðáèòàìè) ñ âðåìåíåì ïðî-
õîæäåíèÿ T1 è T2 . Â òàêîé ñèñòåìå
W T x T y� �1 2 ,
ãäå x è y — öåëûå ÷èñëà; îíè ðàâíû êîëè÷åñòâó îáõîäîâ ïåðâîãî è âòîðîãî
«êðóãîâ». Åñëè T1 è T2 — íåñîèçìåðèìûå âåëè÷èíû, ò.å. T a1 � � , T b2 � � , ãäå
a è b — öåëûå ÷èñëà ñ íàèáîëüøèì îáùèì äåëèòåëåì åäèíèöà, òî � � � ïðè
äîñòàòî÷íî áîëüøîì V .
Èçó÷åííàÿ â ïðåäñòàâëåííîé ñòàòüå ñèñòåìà òèïà GI G/ /1ñ äèñöèïëèíîé îá-
ñëóæèâàíèÿ FCFS è äâóìÿ «êðóãàìè» â çîíå îæèäàíèÿ íàçâàíà íàìè «äâóõöèêëè-
÷åñêîé ñèñòåìîé îáñëóæèâàíèÿ».
Ïðèâåäåí àëãîðèòì ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ âëîæåííîé öåïè Ìàð-
êîâà ( )Wn ïðîöåññà îáñëóæèâàíèÿ. Íàéäåíî óñëîâèå ýðãîäè÷íîñòè öåïè ( )Wn äëÿ
íåñêîëüêî áîëåå îáùåé ñèñòåìû, â êîòîðîé W s Vn n� ( ), ãäå s t( ) — ïðîèçâîëüíàÿ
äåòåðìèíèðîâàííàÿ íåóáûâàþùàÿ ôóíêöèÿ. Èñïîëüçîâàíà èçâåñòíàÿ òåîðåìà
Tweedie îá îöåíêå ñðåäíåãî âðåìåíè ïðåáûâàíèÿ ñëó÷àéíîé ïîñëåäîâàòåëüíîñòè
â ìíîæåñòâå ñîñòîÿíèé.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 59
© È.Í. Êîâàëåíêî, 2015
ÎÏÈÑÀÍÈÅ ÑÈÑÒÅÌÛ ÎÁÑËÓÆÈÂÀÍÈß
Ðàññìàòðèâàåòñÿ îäíîêàíàëüíàÿ ñèñòåìà îáñëóæèâàíèÿ ñ ïîâòîðíûìè çàÿâêàìè
(retrial queue) ñ äèñöèïëèíîé îáñëóæèâàíèÿ â ïîðÿäêå î÷åðåäè (FCFS) è ïåðå-
ìåííûì (çàâèñèìûì îò äðóãèõ âåëè÷èí) ÷èñëîì öèêëîâ íàõîæäåíèÿ òðåáîâà-
íèÿ íà îðáèòå.
Îáîçíà÷èì ( , )t nn � 0 âõîäÿùèé ïîòîê òðåáîâàíèé, ( , )Y nn � 0 — ïîñëåäîâà-
òåëüíîñòü äëèòåëüíîñòåé îáñëóæèâàíèÿ òðåáîâàíèé, ( , )W nn � 0 — ïîñëåäîâà-
òåëüíîñòü äëèòåëüíîñòåé îæèäàíèÿ òðåáîâàíèÿìè íà÷àëà îáñëóæèâàíèÿ. Îáîçíà-
÷èì òàêæå Z t tn n n� � �1, V W Y Zn n n n� � �� � �( )1 1 . Ïðè n � 1 âûïîëíÿåòñÿ ñëåäó-
þùåå óðàâíåíèå:
W s W Y Z s Vn n n n n� � � �� �( ) ( )1 1 , (1)
ãäå s t( ) — äåòåðìèíèðîâàííàÿ íåóáû-
âàþùàÿ ôóíêöèÿ, óäîâëåòâîðÿþùàÿ
óñëîâèþ s t t( ) � , t � 0, è ðàâíàÿ 0 ïðè
t � 0 (ðèñ. 1).
Ôîðìóëà (1) ñëóæèò îñíîâàíèåì àë-
ãîðèòìà ñòàòèñòè÷åñêîãî ìîäåëèðîâàíèÿ
ïîñëåäîâàòåëüíîñòè ( )Wn .
Ââåäåì âåëè÷èíó
� ( ) ( )t s t t� � � 0 .
Òîãäà óðàâíåíèå (1) ìîæíî ïåðåïèñàòü òàê:
W W Y Z W Y Zn n n n n n n� � � � � �� � � �1 1 1 1�( ).
Ïîëîæèì
� �� � �
�
lim ( )
t
t Y ZE { }0 1 . (2)
Ïðåäïîëîæèì, ÷òî Y Z nn n� � �1 1, , — íåçàâèñèìûå ñëó÷àéíûå âåëè÷èíû
ñ îáùåé ôóíêöèåé ðàñïðåäåëåíèÿ C x Y Z x x( ) ,� � �
�P{ }0 1 , è êîíå÷íûì ìàòå-
ìàòè÷åñêèì îæèäàíèåì c x dC x�
�
� ( ) .
Èç ôîðìóëû (2) ñëåäóåò ñîîòíîøåíèå
lim |
t
n n nW W W t c
�
� �� � � �E { }1 1 � . (3)
ÝÐÃÎÄÈ×ÅÑÊÀß ÒÅÎÐÅÌÀ
Òåîðåìà. Ïðåäïîëîæèì, ÷òî ñóùåñòâóþò ÷èñëà � � �
0 0 0, , , äëÿ êîòîðûõ
âûïîëíÿþòñÿ íåðàâåíñòâà
E{ Y }+0� �( )t Z c� � � �1 , t � �, (4)
C ( )� � 1,
C ( )�
� 0 , (5)
� � � �� � � � �d t t
def
sup ( ( ), )0 . (6)
Òîãäà ñëó÷àéíàÿ ïîñëåäîâàòåëüíîñòü ( , )W nn � 0 ÿâëÿåòñÿ ýðãîäè÷åñêîé îäíî-
ðîäíîé öåïüþ Ìàðêîâà íà ìíîæåñòâå ñîñòîÿíèé �� .
Çàìå÷àíèå. Åñëè âñå Wn êðàòíû �
0 , òî óñëîâèå t � â ôîðìóëàõ (2), (3)
ñëåäóåò ïîíèìàòü êàê t n� � , n � .
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1
tntn � 1 Zn
Wn � 1 + Yn � 1
Vn
Wn � s(Vn)
Ðèñ. 1
Äîêàçàòåëüñòâî. Èç ðàâåíñòâà (1) ñëåäóåò, ÷òî ( , )W nn � 0 — îäíîðîäíàÿ
öåïü Ìàðêîâà. Ñóùåñòâîâàíèå ÷èñåë � è �, óäîâëåòâîðÿþùèõ óñëîâèþ (4), âûòå-
êàåò èç íåðàâåíòñâà (3), åñëè � � �c 0 . Ìíîæåñòâî ìîìåíòîâ âðåìåíè { }n � 0 ðàç-
áèâàåòñÿ íà ÷åðåäóþùèåñÿ îòðåçêè �k ñ êîëè÷åñòâîì ýëåìåíòîâ �k , íà êîòîðûõ
Wn � �, è îòðåçêè ��k ñ êîëè÷åñòâîì ýëåìåíòîâ ��k , íà êîòîðûõ Wn � �.
Âíà÷àëå ðàññìîòðèì îòðåçîê � � ��k n n{ }, ,1 � . Ïóñòü wn � � — ôèêñèðîâàí-
íîå çíà÷åíèå Wn . Ïóñòü òàêæå r �] / [� � . Åñëè Y Z Y Zn n n r n r�
�
� � � �1 1� �, ,� ,
òî Wn r�
� ; ñëåäîâàòåëüíî, � ��k r. Åñëè äàííàÿ öåïî÷êà íåðàâåíñòâ íå âûïîëíÿ-
åòñÿ è �
�k r, òî ðàññìîòðèì ñîáûòèå { }Y Z Y Zn r n r n r n r� � � � � ��
�
1 2 1 2� �, ,� ,
â ñëó÷àå âûïîëíåíèÿ êîòîðîãî � ��k r2 . Ïðîäîëæàÿ ýòîò ïðîöåññ, ïîëó÷èì íåðà-
âåíñòâî
P{ } ,�
� � � �� �k n
r iir w C i| ( ( ( )) )1 1 0 ,
ñïðàâåäëèâîå ïðè ëþáîì wn � �.
Ïðîñóììèðîâàâ ýòî íåðàâåíñòâî ïî i , ïîëó÷èì îöåíêó
E{ }� � �� �k n
rw r C| / ( ( ))1 .
Åñëè ïåðåñêîê Wn èç ��k â �l ïðîèñõîäèò íà m-ì øàãå, ò.å. Wm� �1 �, Wm � �,
òî W d Y Zm m m� � � ��� | |1 ; ñëåäîâàòåëüíî,
E{ }W W w d x dC xm m m| | | ( )� �
�
� � � � � �1 1 � � .
Ðàññìîòðèì ñòîÿùèå ïîäðÿä îòðåçêè � � � � � ��k kn n n{ }, , ,1 1� � è �l �
� �{ }m m, ,1 � . Äëÿ íàñ âàæíî îöåíèòü E{ }Wm íà îñíîâàíèè ñâîéñòâ ��k . Íà
îñíîâàíèè èçâåñòíîé òåîðåìû Tweedie [5] (ñì. òàêæå [7, ãë. 1])
E{ } E{ }� �l mW� / .
Èíäåêñ m ñëó÷àåí, â çàâèñèìîñòè îò çíà÷åíèÿ ��k . Ìîæíî çàïèñàòü íåðàâåíñòâî
E{ } P{ }W r ir d x dC xm k
i
� �
� �
�
�
�
�
�
�
�
�
�
�
�
� �� �
0
| | ( )
� � �
�
�
�
�
�
�
�
�
�
�
�r v d x dC x C r| | ( ) / ( ( ))1 � .
Åñëè îòðåçîê �0 íà÷àëüíûé, ò.å. �0 0 1� { }, ,� , òî ïðè ôèêñèðîâàííîì
W w0 0� èìååì E � �0 0� w / , íà îñíîâàíèè òîé æå òåîðåìû Tweedie. Èç íàé-
äåííûõ íåðàâåíñòâ ñëåäóåò, ÷òî E{ }�k è E{ }��k êîíå÷íû. Âñå îíè ðàâíîìåðíî
îãðàíè÷åíû, çà èñêëþ÷åíèåì, âîçìîæíî, E{ }�0 .
Ñíîâà ðàññìîòðèì îòðåçîê � � ��k m m{ }, ,1 � , è ïóñòü ôèêñèðîâàíî
W wm m� � �. Åñëè Y Z dm m� � � � � ��1 � �( ) , òî ëèáî 0 1� � � � ��W s W dm m( )�
� � � � � �( )W d d Wm m� �, ëèáî Wm� �1 0. Ñëåäîâàòåëüíî, ïðè r-êðàòíîì ïîâòî-
ðåíèè íåðàâåíñòâ Y Zn n� � ��1 � áóäåò Wm r� � 0. Èòàê, äëÿ ëþáîãî èíòåðâàëà
� � ��k m m{ }, ,1 � , íåçàâèñèìî îò ïðåäûäóùåãî,
P{ }W Cm r
r
� � � �
0 0( )� (7)
ïî óñëîâèþ (5).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 61
Íàêîíåö, çàìåòèì, ÷òî
P{ }W W C Cn n� � � � � �
1 0 0 0 0| ( ) ( )� . (8)
Èç ðàâíîìåðíîé îãðàíè÷åííîñòè E{ }�k , E{ }��k è íåðàâåíñòâ (7), (8) ñëåäóåò,
÷òî ñëó÷àéíàÿ ïîñëåäîâàòåëüíîñòü ( , )W nn � 0 ïðåäñòàâëÿåò ñîáîé ýðãîäè÷åñêóþ
âîçâðàòíóþ ïîñëåäîâàòåëüíîñòü, äëÿ êîòîðîé ñîáûòèå { }Wn � 0 ÿâëÿåòñÿ ðåêóð-
ðåíòíûì ñîáûòèåì (ñì. [6, ãë. Õ²²²]).
Òåîðåìà äîêàçàíà.
ÖÈÊËÈ×ÅÑÊÀß ÑÈÑÒÅÌÀ ÎÁÑËÓÆÈÂÀÍÈß ÒÈÏÀ ËÀÊÀÒÎØÀ
Äàííàÿ ñèñòåìà õàðàêòåðèçóåòñÿ òåì, ÷òî s t t t( ) ] / [,� �� � 0 , ãäå �
0 — ïî-
ñòîÿííîå ÷èñëî (â îáîçíà÷åíèè Ëàêàòîøà � � T). Ýòî ÷èñëî èíòåðïðåòèðóåòñÿ
êàê âðåìÿ ïðåáûâàíèÿ òðåáîâàíèÿ íà îðáèòå ìåæäó ïîïûòêàìè ïîïàñòü íà îá-
ñëóæèâàíèå.
Ïðåäïîëîæèì, ÷òî W0 — âåëè÷èíà, êðàòíàÿ � . Òîãäà è âñå Wn áóäóò êðàò-
íû � .  ïðåäïîëîæåíèè, ÷òî ñëó÷àéíàÿ âåëè÷èíà Y Z0 1� èìååò ïëîòíîñòü âåðî-
ÿòíîñòè c t( ) , ñïðàâåäëèâà ôîðìóëà
lim ( ) ( ) ( )
( )
m
k
k
k
m Y Z k x c x dx
�
�� �
� � � ���E{ }� � �
�
�
0 1
1
. (9)
Åñëè æå Y Z0 1� êðàòíî � , òî � ( )m Y Z� � � �0 1 0 ñ âåðîÿòíîñòüþ 1. Â íåêîòî-
ðûõ ñëó÷àÿõ âûðàæåíèå (9) ìîæåò áûòü ïðåäñòàâëåíî â çàìêíóòîì âèäå.
Ïðèìåð. Ïóñòü Y0 , Z1 — íåçàâèñèìûå ýêñïîíåíöèàëüíûå âåëè÷èíû ñ ïàðà-
ìåòðàìè � è � ñîîòâåòñòâåííî. Òîãäà
c x
e x
e x
x
x
( )
( / ( )) ,
( / ( )) .
�
� �
�
�
�� � �
�� � �
�
�
ïðè
ïðè
0
0
�
�
�
Èç ôîðìóëû (9) ïîëó÷àåì
lim ( )
m
m Y Z
�
� � �E{ }� � 0 1
� � � � � �� �� � � �� � �e e e� � ��( ) / ( )( )1 1
� � � � �� �� � � � �� �( ) / ( ( )( ))e e� ��1 1 . (10)
Ïðè ýòîì
c � �( ) / ( )� � �� . (11)
Ñ èñïîëüçîâàíèåì ôîðìóë (10), (11) ëåãêî ïîêàçàòü, ÷òî óñëîâèå ýðãîäè÷íîñòè
èìååò âèä
lim ( )
m
m Y Z c
�
� � � �E{ }� � 0 1 0 . (12)
Óñëîâèå (12) ñ ïîìîùüþ ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ ïðèâîäèòñÿ ê óñëîâèþ
�
�
� �
�
�
�
�
� �
�
e e
e
� �
�
( )1
1
,
ïîëó÷åííîìó â ñòàòüå Ë. Ëàêàòîøà [2].
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1
ÄÂÓÕÖÈÊËÈ×ÅÑÊÀß ÑÈÑÒÅÌÀ ÎÁÑËÓÆÈÂÀÍÈß
Ïóñòü èìååòñÿ îäíîêàíàëüíàÿ ñèñòåìà îáñëóæèâàíèÿ ñ îæèäàíèåì òèïà FCFS
ñ õàðàêòåðèñòèêàìè C x( ), s t( ), Wn , îïðåäåëåííûìè âûøå â îáùåì ñëó÷àå.
Äâóõöèêëè÷åñêîé ñèñòåìîé îáñëóæèâàíèÿ íàçîâåì ñèñòåìó îïðåäåëåííîãî
âûøå òèïà, äëÿ êîòîðîé ôóíêöèÿ s t( ) ïðè t � 0 îïðåäåëÿåòñÿ ôîðìóëîé
s t T x T y( ) � �1 2 ,
ãäå T1, T2 — ïîëîæèòåëüíûå ÷èñëà; ( , ) min ( )x y T i T j t� � �arg 1 2 , i j,
�� 0
� { }0 1 2, , ,� .  èíòåðïðåòàöèè ñ ïîñàäêîé ñàìîëåòîâ T1 è T2 îçíà÷àþò äëè-
òåëüíîñòè îáëåòà ñàìîëåòîì äâóõ «êðóãîâ», x è y — êîëè÷åñòâà îáëåòîâ ïåð-
âîãî è âòîðîãî «êðóãà».
Ïóñòü Vn — âðåìÿ îò ìîìåíòà tn äî ìîìåíòà îêîí÷àíèÿ îáñëóæèâàíèÿ
n �1-ãî òðåáîâàíèÿ, åñëè ýòî âðåìÿ ïîëîæèòåëüíî, è íóëü â ïðîòèâíîì ñëó÷àå. Ïîëà-
ãàåì N V Nn n� �] / [� , ãäå �
0 — çàäàííîå ÷èñëî. Ïóñòü, äàëåå, T T1 2 0
— çà-
äàííûå ÷èñëà, êðàòíûå � : T a1 � � , T b2 � � , ãäå a, b — íàòóðàëüíûå ÷èñëà, ïðè-
÷åì í.î.ä. ( , )a b �1. Ëþáîìó öåëîìó N ñîïîñòàâèì N �1, åñëè óðàâíåíèå
ax by N� � ðàçðåøèìî â öåëûõ íåîòðèöàòåëüíûõ ÷èñëàõ; â ïðîòèâíîì ñëó÷àå ïî-
ëàãàåì N � 0. Åñëè óêàçàííîå óðàâíåíèå ðàçðåøèìî, èç ìíîæåñòâà ðåøåíèé
âûáèðàåì ( , )x yN N , ó êîòîðîãî x N ìàêñèìàëüíî. Òàê, ïðè a � 3, b � 2, N �10
èìååì äâà ðåøåíèÿ: (0, 5) è (2, 2) — ïîëàãàåì ( , ) ( , )x y10 10 2 2� .
Ïðè ñòàòèñòè÷åñêîì ìîäåëèðîâàíèè èëè âûáîðå ( , )x yN N â ðåàëüíîì ìàñ-
øòàáå âðåìåíè ïîëåçíî çàðàíåå ðàññ÷èòàòü òàáëèöó òðîåê ( , , ) N N Nx y . Ýòî
ìîæíî ñäåëàòü ïî ðåêóððåíòíîé ôîðìóëå.
Ïîëàãàåì:
N � 0, N � 0;
( , , ) ( , , ) 0 0 0 1 0 0x y � ;
N N b� � �0 0, ;
( , , ) ( , , ) b b bx y � 1 0 1 ,
N N a N a N b� � �� � �( )1 , åñëè N b
:
x x xN N a N a N a N b N b� � � �� � � � � ( ) ( )1 1 , åñëè N b
, N �1,
y y yN N a N a N a N b N b� � � �� � � � � ( ) ( )1 1 , åñëè N b
, N �1.
Óêàçàííûìè ôîðìóëàìè îïðåäåëÿåòñÿ ( , )x yN N äëÿ òåõ N , äëÿ êîòîðûõ óðàâ-
íåíèå ax by N� � èìååò ðåøåíèå â öåëûõ íåîòðèöàòåëüíûõ ÷èñëàõ. Äëÿ
îñòàëüíûõ N , ò.å. òàêèõ, äëÿ êîòîðûõ N � 0, ìîæíî òàêæå îïðåäåëèòü
( , )x yN N , êàê ( , )x yM M , ãäå M r N� ( ) — ìèíèìàëüíîå ÷èñëî, áîëüøåå N ,
äëÿ êîòîðîãî M �1. Î÷åâèäíî, âìåñòî òî÷íîãî ðàâåíñòâà ax by N� � äëÿ òà-
êèõ N áóäåò
N ax by N bN N� � � � .
Âû÷èñëåíèå ( , )x yN N äëÿ N N: � 0 ìîæíî ïðîèçâîäèòü ñïðàâà íàëåâî ïî ðå-
êóððåíòíîé ôîðìóëå
( , ) ( , )x y x yN N N N� � �1 1 , åñëè N � 0,
íà÷èíàÿ ñî çíà÷åíèÿ N a b0 1 1� � �( )( ).
Ôóíêöèÿ s t( ) ðàññ÷èòûâàåòñÿ ïî ôîðìóëå
s t T x T yr N r N( ) ( ) ( )� �1 2 ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1 63
ãäå
N t�] / [� ,
r N r N r( ) min ( : )� � � 1 .
Ñïðàâåäëèâà îöåíêà
t s t t b� � � �( ) / (] / [ )� 1 .
Ïðè áîëüøèõ N âû÷èñëåíèå ( , , ) N N Nx y ìîæíî óïðîñòèòü, èñïîëüçîâàâ ñëå-
äóþùèé ïðèåì. Ïóñòü N ka l� � , ãäå k
0, ( )( ) ( )a b l a b� � � � �1 1 1 . Èç çàðàíåå
âû÷èñëåííîé òàáëèöû âûáèðàåì çíà÷åíèå âåêòîðà ( , , ) l l lx y (ãäå, î÷åâèäíî,
l �1) è ïîëàãàåì
( , , ) ( , , ) N N N l lx y k x y� �1 .
Òàêèì îáðàçîì, â òàáëèöó òðîåê ( , , ) N N Nx y íóæíî çàïèñûâàòü ëèøü èõ
çíà÷åíèÿ ïðè N a b� �( )1 .
Ñëåäñòâèå òåîðåìû. Ïóñòü âûïîëíåíû óñëîâèÿ
( ) ( )
( )
k x c x dx c
k
k
k
�
�
�
� � �
���
��
1
0,
C ( )�
� 0
äëÿ íåêîòîðîãî �
�( )b 1 � . Òîãäà â äâóõöèêëè÷åñêîé ñèñòåìå îáñëóæèâàíèÿ
öåïü Ìàðêîâà ( , )W nn � 0 ýðãîäè÷íà.
Äîêàçàòåëüñòâî ñîñòîèò â ïðîâåðêå óñëîâèé òåîðåìû. Ñóùåñòâåííî èñïîëü-
çóåòñÿ òîò ôàêò, ÷òî äëÿ ëþáîãî N a b� � �( )( )1 1 óðàâíåíèå ax by N� � èìååò ðå-
øåíèå â öåëûõ íåîòðèöàòåëüíûõ ÷èñëàõ, êîëü ñêîðî a è b — âçàèìíî ïðîñòûå
íàòóðàëüíûå ÷èñëà.
Àâòîð áëàãîäàðåí Þ.Ñ. Ìèøóðå çà óêàçàíèå ýëåêòðîííûõ ñòàòåé [8, 9], â êî-
òîðûõ ïðèâîäèòñÿ äîêàçàòåëüñòâî ýòîãî ôàêòà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. L a k a t o s L . On a simple continuous cyclic-waiting problem // Annales Univ. Sci. Bud. Sect. Comp. —
1994. — 14. — P. 105–113.
2. L a k a t o s L . On a cyclic-waiting queueing system // Theory of Stochastic Processes. — 1996. — 2, N 18.
— P. 176–180.
3. K o b a E . V . On a GI G/ / 1 retrial queueing system with a FIFO queueing discipline // Theory of Stochas-
tic Processes. — 2002. — 24, N 8. — P. 201–207.
4. Ê î á à Å .  . Óñëîâèÿ óñòîé÷èâîñòè íåêîòîðûõ òèïîâûõ ñèñòåì îáñëóæèâàíèÿ ñ âîçâðàùåíèåì çàÿ-
âîê // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2005. — ¹ 1. — Ñ. 124–127.
5. T w e e d i e R . L . Sufficient conditions for ergodicity and recurrence of Marcov chains on a general state
space // Stoch. Processes Appl. — 1975. — 3, N 4. — P. 385–403.
6. Ô å ë ë å ð Â . Ââåäåíèå â òåîðèþ âåðîÿòíîñòåé è åå ïðèëîæåíèÿ. — Ì.: Ìèð, 1967. — Ò. 1. — 527 ñ.
7. Á î ð î â ê î â À . À . Ýðãîäè÷íîñòü è óñòîé÷èâîñòü ñëó÷àéíûõ ïðîöåññîâ. — Ì.: Åäèòîðèàë ÓÐÑÑ,
1999. — 440 c.
8. W h a t are the subsemigroups of ( , )N � ?: — http://math.stackexchange.com/questions/164164/what-are-
the-subsemigroups-of-mathbb-n.
9. S h a l l i t J . The Frobenius Problem and its generalizations. — http://cs.uwaterloo.ca/~shallit/Talks/frob6.pdf.
Ïîñòóïèëà 06.05.2014
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 1
|