О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS
Вивчено дискретну в часі одноканальну систему обслуговування з повторними викликами при загальних, періодично залежних від номера заявки, дискретних розподілах інтервалів надходження заявок, часу обслуговування та циклу на орбіті. Прийнято дисципліну обслуговування по черзі. Виведено достатню умову...
Saved in:
| Date: | 2013 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Series: | Кибернетика и системный анализ |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/86257 |
| 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: | О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS / И.Н. Коваленко, Е.В. Коба, О.Н. Дышлюк // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 107-112. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-86257 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-862572015-09-12T03:01:39Z О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS Коваленко, И.Н. Коба, Е.В. Дышлюк, О.Н. Системный анализ Вивчено дискретну в часі одноканальну систему обслуговування з повторними викликами при загальних, періодично залежних від номера заявки, дискретних розподілах інтервалів надходження заявок, часу обслуговування та циклу на орбіті. Прийнято дисципліну обслуговування по черзі. Виведено достатню умову ергодичності вкладеного ланцюга Маркова. A discrete-time one-channel queuing system with general inter-arrival, service, and orbit times periodically dependent on the number of arrival is considered. A sufficient condition for the ergodicity of an imbedded Markov chain is derived. 2013 Article О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS / И.Н. Коваленко, Е.В. Коба, О.Н. Дышлюк // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 107-112. — Бібліогр.: 17 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/86257 519.872 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Коваленко, И.Н. Коба, Е.В. Дышлюк, О.Н. О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS Кибернетика и системный анализ |
| description |
Вивчено дискретну в часі одноканальну систему обслуговування з повторними викликами при загальних, періодично залежних від номера заявки, дискретних розподілах інтервалів надходження заявок, часу обслуговування та циклу на орбіті. Прийнято дисципліну обслуговування по черзі. Виведено достатню умову ергодичності вкладеного ланцюга Маркова. |
| format |
Article |
| author |
Коваленко, И.Н. Коба, Е.В. Дышлюк, О.Н. |
| author_facet |
Коваленко, И.Н. Коба, Е.В. Дышлюк, О.Н. |
| author_sort |
Коваленко, И.Н. |
| title |
О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS |
| title_short |
О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS |
| title_full |
О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS |
| title_fullStr |
О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS |
| title_full_unstemmed |
О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS |
| title_sort |
о периодической дискретной однолинейной системе обслуживания с повторными вызовами gi / g / 1 при дисциплине fcfs |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/86257 |
| citation_txt |
О периодической дискретной однолинейной системе обслуживания с повторными вызовами GI / G / 1 при дисциплине FCFS / И.Н. Коваленко, Е.В. Коба, О.Н. Дышлюк // Кибернетика и системный анализ. — 2013. — Т. 49, № 4. — С. 107-112. — Бібліогр.: 17 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT kovalenkoin operiodičeskojdiskretnojodnolinejnojsistemeobsluživaniâspovtornymivyzovamigig1pridisciplinefcfs AT kobaev operiodičeskojdiskretnojodnolinejnojsistemeobsluživaniâspovtornymivyzovamigig1pridisciplinefcfs AT dyšlûkon operiodičeskojdiskretnojodnolinejnojsistemeobsluživaniâspovtornymivyzovamigig1pridisciplinefcfs |
| first_indexed |
2025-07-06T13:43:14Z |
| last_indexed |
2025-07-06T13:43:14Z |
| _version_ |
1836905287995359232 |
| fulltext |
ÓÄÊ 519.872
È.Í. ÊÎÂÀËÅÍÊÎ, Å.Â. ÊÎÁÀ, Î.Í. ÄÛØËÞÊ
Î ÏÅÐÈÎÄÈ×ÅÑÊÎÉ ÄÈÑÊÐÅÒÍÎÉ ÎÄÍÎËÈÍÅÉÍÎÉ
ÑÈÑÒÅÌÅ ÎÁÑËÓÆÈÂÀÍÈß Ñ ÏÎÂÒÎÐÍÛÌÈ
ÂÛÇÎÂÀÌÈ GI G/ / 1 ÏÐÈ ÄÈÑÖÈÏËÈÍÅ FCFS
Êëþ÷åâûå ñëîâà: ñèñòåìû ìàññîâîãî îáñëóæèâàíèÿ, ïîâòîðíûå âûçîâû,
óñòîé÷èâîñòü ñèñòåì ìàññîâîãî îáñëóæèâàíèÿ.
Àâòîðû ýòîé ñòàòüè ðàäû âîçìîæíîñòè îïóáëèêîâàòü åå â þáèëåéíîì íîìåðå
æóðíàëà «Êèáåðíåòèêà è ñèñòåìíûé àíàëèç», ïîñâÿùåííîì 90-ëåòèþ ñî äíÿ
ðîæäåíèÿ àêàäåìèêà Â.Ì. Ãëóøêîâà.
Âèêòîð Ìèõàéëîâè÷ óäåëÿë áîëüøîå âíèìàíèå òåîðèè âåðîÿòíîñòåé è,
â ÷àñòíîñòè, òåîðèè ìàññîâîãî îáñëóæèâàíèÿ. Îí ðàññìàòðèâàë ýòè íàóêè êàê àï-
ïàðàò äëÿ ðåøåíèÿ çàäà÷ êèáåðíåòèêè. Â åãî çíàìåíèòîé êíèãå «Ñèíòåç öèôðî-
âûõ àâòîìàòîâ» [1] ãîâîðèòñÿ î ðîëè òåîðèè ìàññîâîãî îáñëóæèâàíèÿ è ïðèâî-
äèòñÿ ññûëêà íà îäíó èç êíèã îá ýòîé òåîðèè. Àêàäåìèê Â.Ì. Ãëóøêîâ áûë ñîàâ-
òîðîì ðàáîò î ïðîãðàììíûõ ìåòîäàõ òåîðèè ìàññîâîãî îáñëóæèâàíèÿ.
Íà÷èíàÿ ñ 80-õ ãîäîâ XX ñòîëåòèÿ, àêòèâíî ðàçâèâàåòñÿ òåîðèÿ ñèñòåì ñ ïî-
âòîðíûìè âûçîâàìè.  êëàññè÷åñêîé òåîðèè ìàññîâîãî îáñëóæèâàíèÿ ðàññìàò-
ðèâàþòñÿ ñèñòåìû áåç áëîêèðîâêè çàÿâîê: ïðè íàëè÷èè ñâîáîäíîãî êàíàëà ïîñòó-
ïèâøàÿ â ñèñòåìó çàÿâêà íåìåäëåííî îòïðàâëÿåòñÿ íà îáñëóæèâàíèå. Î÷åâèäíî,
òàêèå ìîäåëè ïðåäñòàâëÿþò ñîáîé èäåàëèçèðîâàííóþ êàðòèíó ðåàëüíûõ ïðîöåñ-
ñîâ. Âî ìíîãèõ ðåàëüíûõ ñèñòåìàõ çàÿâêó áëîêèðóþò äî ìîìåíòà, ïîêà íå áóäóò
ñîçäàíû óñëîâèÿ äëÿ åå îáñëóæèâàíèÿ, äàæå åñëè êàíàë ñâîáîäåí.
Îäíèì èç âàæíûõ òèïîâ ñèñòåì ñ áëîêèðîâêîé ÿâëÿþòñÿ ñèñòåìû ñ âîçâðàùå-
íèåì (ïîâòîðåíèåì) çàÿâîê. Òàê, ïðè îáû÷íîé òåëåôîííîé ñâÿçè, óñëûøàâ ÷àñòûå
ãóäêè, àáîíåíò ïîâòîðÿåò âûçîâ ÷åðåç íåêîòîðîå ïîñòîÿííîå èëè ñëó÷àéíîå âðåìÿ;
â ïðîöåññå ïîñàäêè âîçäóøíîãî ñóäíà íà âçëåòíî-ïîñàäî÷íóþ ïîëîñó â ñëó÷àå åå
çàíÿòîñòè âîçäóøíîå ñóäíî îòïðàâëÿåòñÿ â çîíó îæèäàíèÿ, ÷òîáû âîçâðàòèòüñÿ ÷å-
ðåç ïîñòîÿííîå (â äîñòàòî÷íîì ïðèáëèæåíèè) âðåìÿ; ïîäîáíàÿ ñèòóàöèÿ èìååò
ìåñòî è â èíôîðìàöèîííî-òåëåêîììóíèêàöèîííûõ ñèñòåìàõ è ñåòÿõ.
Íàèáîëåå îáùàÿ ìîäåëü ñèñòåìû ìàññîâîãî îáñëóæèâàíèÿ (ÑÌÎ) ñ âîçâðàùå-
íèåì çàÿâîê ïðåäñòàâëåíà â îáçîðíîé ñòàòüå T. Yang è J.G.C. Templeton [2]; îòìåòèì
òàêæå îáçîð Ã.È. Ôàëèíà [3] è åãî ìîíîãðàôèþ ñ J.G.C. Templeton [4]. Áîëüøîé
âêëàä â ðàçâèòèå òåîðèè ñèñòåì îáñëóæèâàíèÿ ñ ïîâòîðåíèåì âíåñëè J.R. Artalejo
è A. Gomez-Corral. Èõ ìíîãî÷èñëåííûå ñòàòüè, â êîòîðûõ îòðàæàåòñÿ ñïåöèôèêà ïî-
âòîðåíèÿ è îáñëóæèâàíèÿ òàêèõ ñèñòåì, îáîáùåíû â [5]. Êðîìå òîãî, J.R. Artalejo
ñäåëàë îáçîð è îïóáëèêîâàë áèáëèîãðàôèþ, â êîòîðîé îòðàæàåòñÿ ïðîöåññ ðàçâèòèÿ
òåîðèè ñèñòåì ñ ïîâòîðåíèåì çàÿâîê [6–8].
Âîçðîñøèå â ïîñëåäíèå ãîäû ïðîèçâîäèòåëüíîñòü è ñëîæíîñòü èíôîðìàöèîí-
íî-òåëåêîììóíèêàöèîííûõ ñèñòåì è ñåòåé ïðåäúÿâëÿþò ïîâûøåííûå òðåáîâàíèÿ
ê êà÷åñòâó ðåøåíèé, ïðèíèìàåìûõ â ïðîöåññå èõ ïðîåêòèðîâàíèÿ, ÷òî, â ñâîþ î÷å-
ðåäü, âëå÷åò çà ñîáîé èíòåíñèâíîå ðàçâèòèå òåîðåòè÷åñêèõ ìåòîäîâ èõ èññëåäîâà-
íèÿ. Âàæíóþ ðîëü ïðè ýòîì èãðàåò ðàçâèòèå òåîðèè ñèñòåì îáñëóæèâàíèÿ è,
â ÷àñòíîñòè, ñèñòåì îáñëóæèâàíèÿ ñ ïîâòîðåíèåì âûçîâîâ (âîçâðàùåíèåì çàÿ-
âîê). Ñóùåñòâåííûé âêëàä â ðàçâèòèå òåîðèè ñèñòåì îáñëóæèâàíèÿ ñ ïîâòîðåíè-
åì è åå ïðèìåíåíèå âíåñëè À.Í. Äóäèí, Â.È. Êëèìåíîê [9], Ä.Þ. Êóçíåöîâ,
À.À. Íàçàðîâ [10], Â.Â. Àíèñèìîâ è Å.À. Ëåáåäåâ [11] è äð.
Ñðåäè ñèñòåì îáñëóæèâàíèÿ ñ ïîâòîðåíèåì ìîæíî âûäåëèòü êëàññ ñèñòåì
ñ äèñöèïëèíîé îáñëóæèâàíèÿ â ïîðÿäêå î÷åðåäè (FCFS). Ýòîò êëàññ ñèñòåì åñ-
òåñòâåííî íàçâàòü ñèñòåìàìè òèïà Ëàêàòîøà â ÷åñòü âåíãåðñêîãî ó÷åíîãî Ëàñëî
Ëàêàòîøà, êîòîðûé âïåðâûå åãî ðàññìîòðåë [12]. Ë. Ëàêàòîø ðåøàë çàäà÷è ìîäå-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 107
© È.Í. Êîâàëåíêî, Å.Â. Êîáà, Î.Í. Äûøëþê, 2013
ëèðîâàíèÿ ïîñàäêè âîçäóøíûõ ñóäåí íà âçëåòíî-ïîñàäî÷íóþ ïîëîñó. Åñëè ïîëî-
ñà íå ñâîáîäíà èëè ïî êàêîé-ëèáî äðóãîé ïðè÷èíå (íàïðèìåð, ïëîõèå ìåòåîóñëî-
âèÿ) âîçäóøíîå ñóäíî íå ìîæåò ñîâåðøèòü ïîñàäêó, îíî íàïðàâëÿåòñÿ â çîíó
îæèäàíèÿ èëè íà âòîðîé êðóã. Íîðìû ýøåëîíèðîâàíèÿ íå äîïóñêàþò îáãîíà íà
êðóãå èëè â çîíå îæèäàíèÿ, âûäåðæèâàþòñÿ òàêæå íîðìû ïðîèçâîëüíîãî, âåðòè-
êàëüíîãî èëè ãîðèçîíòàëüíîãî ýøåëîíèðîâàíèÿ. Òàêèì îáðàçîì, ñîáëþäàåòñÿ
äèñöèïëèíà ïðèíÿòèÿ íà îáñëóæèâàíèå â ïîðÿäêå î÷åðåäè.
Ñèñòåìû òèïà Ëàêàòîøà ÿâëÿþòñÿ ìîäåëÿìè ìíîãèõ ðåàëüíûõ ñèñòåì: îïòè-
÷åñêîãî áóôåðà, call-öåíòðà ñ îæèäàíèåì è àâòîîòâåò÷èêàìè è ò.ä., ïîýòîìó èõ
èññëåäîâàíèå ÿâëÿåòñÿ âàæíûì è àêòóàëüíûì.
Ïðè èññëåäîâàíèè ñèñòåì îáñëóæèâàíèÿ ñ ïîâòîðåíèÿìè âîçíèêàåò ìíîãî
ïðîáëåì, è â ïåðâóþ î÷åðåäü — ïðîáëåìà èõ ýðãîäè÷íîñòè.
Èçó÷àÿ ñèñòåìû îáñëóæèâàíèÿ ñ öèêëè÷åñêèì âðåìåíåì îæèäàíèÿ, Ë. Ëàêà-
òîø âûâåë óñëîâèå ýðãîäè÷íîñòè ñèñòåìû M M/ /1 ñ ïîñòîÿííûì âðåìåíåì T
öèêëà îðáèòû [12]. Â ðàáîòàõ [13, 14] Å.Â. Êîáà îáîáùèëà ðåçóëüòàòû Ë. Ëàêàòî-
øà. Â [13] ìîäåëü Ëàêàòîøà îáîáùàåòñÿ íà ñèñòåìû ñ ðåêóððåíòíûì âõîäÿùèì
ïîòîêîì, ïðîèçâîëüíûìè ðàñïðåäåëåíèÿìè êàê âðåìåíè îáñëóæèâàíèÿ, òàê
è âðåìåíè ïðåáûâàíèÿ çàÿâêè íà îðáèòå. Â òàêîì îáîáùåíèè â ðàáîòå [14]
Å.Â. Êîáà èçó÷èëà ñèñòåìó GI G/ /1, óêàçàâ äîñòàòî÷íûå óñëîâèÿ ýðãîäè÷íîñòè
ñëó÷àéíîé ïîñëåäîâàòåëüíîñòè, îïèñûâàþùåé ñèñòåìó.  íàñòîÿùåé ñòàòüå óêà-
çàííàÿ ñèñòåìà îáîáùàåòñÿ íà ñëó÷àé ïåðèîäè÷åñêîé ñèñòåìû îáñëóæèâàíèÿ.
Âíà÷àëå îïèøåì àëãîðèòì îáñëóæèâàíèÿ çàÿâîê, çàòåì ïðèâåäåì âåðîÿòíîñòíûå
ïðåäïîñûëêè. Îáîçíà÷èì âõîäÿùèé ïîòîê çàÿâîê ( , )t nn � 0 , ãäå t0 0� , ðàçíîñòè
X t tn n n� � �1 — ïîëîæèòåëüíûå âåëè÷èíû, ïîíèìàÿ ïîä tn ìîìåíò ïîñòóïëåíèÿ
â ñèñòåìó n-é çàÿâêè, Yn � 0 — âðåìÿ åå îáñëóæèâàíèÿ. Ïîñòóïèâ â ñèñòåìó â ìî-
ìåíò tn , n-ÿ çàÿâêà íàïðàâëÿåòñÿ íà îáñëóæèâàíèå íåìåäëåííî, åñëè êàíàë è
îðáèòà ñâîáîäíû.  ïðîòèâíîì ñëó÷àå âñå çàâèñèò îò âåëè÷èíû Vn , ãäå Vn � 0 —
âðåìÿ îò tn äî ìîìåíòà, êîãäà áóäåò îáñëóæåíà ( )n �1 -ÿ çàÿâêà. Íà îðáèòó íàïðàâ-
ëÿåòñÿ n-ÿ çàÿâêà è âîçâðàùàåòñÿ ÷åðåç èíòåðâàëû âðåìåíè D D Dn n nN1 2, � �� , ãäå
Dnj � 0 , ÷èñëî N îïðåäåëÿåòñÿ óñëîâèåì, ÷òî â N -é ìîìåíò âîçâðàùåíèÿ ñ îðáè-
òû n-ÿ çàÿâêà âïåðâûå çàñòàåò êàíàë ñâîáîäíûì.
Ââåäåì ñëåäóþùèå îáîçíà÷åíèÿ:
� Wn — âðåìÿ îæèäàíèÿ n -é çàÿâêè, ò.å. âðåìÿ îò ìîìåíòà tn äî ïðèíÿòèÿ åå
íà îáñëóæèâàíèå;
� U W Yn n n� � — âðåìÿ ïðåáûâàíèÿ n-é çàÿâêè â ñèñòåìå;
� V U Xn n n� �� �( )1 , ãäå èñïîëüçóåòñÿ îáû÷íîå îáîçíà÷åíèå a a� � ïðè
a � 0, a� � 0 ïðè a 0.
Òàêèì îáðàçîì, Vn — îñòàòîê âðåìåíè ïðåáûâàíèÿ â ñèñòåìå ( )n �1 -é çàÿâêè
ê ìîìåíòó tn ïîñòóïëåíèÿ n-é çàÿâêè.  ÷àñòíîñòè, åñëè ( )n �1 -ÿ çàÿâêà îáñëóæå-
íà â ìîìåíò tn èëè ðàíåå, òî ïîëàãàåì Vn � 0.
108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
Ðèñ. 1
tn � 1
Un � 1
tn
Xn
Yn
…
Dn1 Dn2 DnN
Yn
Vn
�n
tn + Wn tn + Untn � 1
Un � 1
tn
Xn
à
á
Íà ðèñ. 1 èçîáðàæåíû äâà âîçìîæíûõ ñëó÷àÿ. Íà ðèñ. 1, à ïîêàçàí ñëó÷àé,
êîãäà n-ÿ çàÿâêà ïðèáûâàåò â ñèñòåìó, êîãäà ( )n �1 -ÿ çàÿâêà óæå ïîêèíóëà ñèñòå-
ìó èëè îäíîâðåìåííî ñ ýòèì ìîìåíòîì, òîãäà Wn � 0,Vn � 0. Íà ðèñ. 1, á ïîêàçàí
ñëó÷àé, êîãäà W D D Dn n n nN� � � �1 2 � , ãäå N îïðåäåëÿåòñÿ óñëîâèåì
D D D V D D Dn n n N n n n nN1 2 1 1 2� � �
� � ��� �, , W Vn n n� � � , ãäå � n — âåëè÷è-
íà ïåðåñêîêà ÷åðåç óðîâåíü Vn ñëó÷àéíîãî áëóæäàíèÿ ( , ,... )D D Dn n n1 1 2� . Äëÿ
îáùíîñòè â ñëó÷àå a ïîëîæèì � n � 0. Òàê êàê âåëè÷èíà ïåðåñêîêà îïðåäåëÿåòñÿ
âåëè÷èíîé Vn è öèêëàìè íà îðáèòå Dnj , êðàòêî ìîæíî îáîçíà÷èòü � � �n d� ( , ) ïðè
óñëîâèè, ÷òî Vn � �, ( )D D dnj n� � .
ÌÎÄÅËÈÐÎÂÀÍÈÅ ÏÐÎÖÅÑÑÀ
Ïðåäñòàâèì ñåáå, ÷òî èìååòñÿ äàò÷èê, âûðàáàòûâàþùèé ïîñëåäîâàòåëüíîñòè
( )X n , ( )Yn , ( )Dnk . Òîãäà ïî ñëåäóþùèì ðåêóððåíòíûì ôîðìóëàì âû÷èñëÿþò-
ñÿ âñå ââåäåííûå âûøå õàðàêòåðèñòèêè ïðîöåññà îáñëóæèâàíèÿ.
Ïðè n � 1 èìååì
W V V Dn n n n� � � ( , ), (1)
ãäå
D D Dn n n� ( , , ...)1 2 , (2)
V U Xn n n� �� �( )1 , (3)
U W Yn n n� � , (4)
� ( , )V D D D D Vn n n n nN n� � � � �1 2 � . (5)
Çäåñü
W V Dn n n� �� ( , ) 0 ïðè Vn � 0, (6)
N k D D D Vn n nk n� � � � � �min ( : )0 1 2 � , (7)
� ( , )V D W Vn n n n� � . (8)
Ïðè ìîäåëèðîâàíèè ìîæíî ïîëîæèòü
W0 0� , (9)
V Y0 0� . (10)
ÂÅÐÎßÒÍÎÑÒÍÛÅ ÌÎÄÅËÈ
Àëãîðèòì (1)–(10) âûïîëíÿåòñÿ ïðè ïðîèçâîëüíûõ ïîëîæèòåëüíûõ âåëè÷èíàõ
X n , Yn , Dnj . Èñõîäÿ èç èçâåñòíûõ íàì ðåàëüíûõ ïðèìåðîâ äàííîé ñèñòåìû,
íàèáîëüøåå çíà÷åíèå èìååò âåðîÿòíîñòíàÿ ìîäåëü, â êîòîðîé óêàçàííûå âåëè-
÷èíû X n , Yn , Dnj íåçàâèñèìû â ñîâîêóïíîñòè è îáëàäàþò ôóíêöèÿìè ðàñïðå-
äåëåíèÿ X A xn n~ ( ) , Y B xn n~ ( ) , D D xnj n~ ( ) .
Âûäåëèì äâà âàæíûõ ñëó÷àÿ:
1) îäíîðîäíàÿ ìîäåëü [14]: âñå ââåäåííûå ðàñïðåäåëåíèÿ íå çàâèñÿò îò n ;
2) ïåðèîäè÷åñêàÿ ìîäåëü: âñå ââåäåííûå ðàñïðåäåëåíèÿ ïåðèîäè÷åñêè çàâè-
ñÿò îò n ñ ïåðèîäîì R.
Íà ïåðèîäè÷åñêîé ìîäåëè ìû è ñîñðåäîòî÷èìñÿ â äàííîé ñòàòüå. Ïîìèìî ýòî-
ãî, áóäåì ñ÷èòàòü, ÷òî êîíå÷íû ìîìåíòû � n nX EX1 ( ) � , � n nY EY1 ( ) � ,
� n nD ED1 1( ) � , � n n
D ED2 1
2( ) � . Òàêæå ïðåäïîëîæèì, ÷òî ðàññìàòðèâàåìûå ñëó-
÷àéíûå âåëè÷èíû öåëî÷èñëåííû, è îáîçíà÷èì a P X knk n� �( ) , b P Y knk n� �( ) ,
d P D knk n� �( )1 , k � 0 1 2, , , ... ; a b dn n n0 0 0 0� � � .
 íàó÷íîé ëèòåðàòóðå îïèñàíû ìíîãèå óñëîâèÿ ýðãîäè÷íîñòè ñèñòåì ìàññî-
âîãî îáñëóæèâàíèÿ. Êàê íàèáîëåå ôóíäàìåíòàëüíóþ ìîíîãðàôèþ ñëåäóåò îòìå-
òèòü [15]. Íàñ óäîâëåòâîðÿåò òåîðåìà â ôîðìóëèðîâêå Ã.Ï. Êëèìîâà [16], âîñïðî-
èçâåäåííàÿ òàêæå â [17]: «Ïóñòü ñóùåñòâóåò íåîòðèöàòåëüíàÿ ôóíêöèÿ f i( ) ñî
ñëåäóþùèìè ñâîéñòâàìè:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 109
1) äëÿ íåêîòîðîãî � � 0 è âñåõ i èç ìíîæåñòâà X ñîñòîÿíèé öåïè Ìàðêîâà
( )� n , çà èñêëþ÷åíèåì, âîçìîæíî, íåêîòîðîãî êîíå÷íîãî ìíîæåñòâà,
E f i f in n( ( ) | ) ( )� � �� � �1 ; (11)
2)
E f i i Xn n( ( ) | ) ,� � � �
� �1 . (12)
Òåîðåìà. Åñëè öåïü Ìàðêîâà ( )� n íåïðèâîäèìàÿ, íåïåðèîäè÷åñêàÿ è óäîâ-
ëåòâîðÿåò óñëîâèÿì (11), (12), òî ýòà öåïü ÿâëÿåòñÿ ýðãîäè÷åñêîé».
Ýðãîäè÷åñêèå òåîðåìû äëÿ âëîæåííîé öåïè Ìàðêîâà ( )Wn êàê äëÿ ðåøåò÷à-
òîãî, òàê è äëÿ íåðåøåò÷àòîãî ñëó÷àÿ, äëÿ îäíîðîäíîé ìîäåëè (ñì. âûøå) ïîëó-
÷åíû â [14]. Öåëü íàñòîÿùåé ñòàòüè — ðåøåíèå òàêîé çàäà÷è äëÿ öåëî÷èñëåííîé
ïåðèîäè÷åñêîé ìîäåëè.
ÝÐÃÎÄÈ×ÅÑÊÀß ÒÅÎÐÅÌÀ ÄËß ÖÅËÎ×ÈÑËÅÍÍÎÉ ÏÅÐÈÎÄÈ×ÅÑÊÎÉ ÌÎÄÅËÈ
Ïðåäïîëîæèì, ÷òî ñëó÷àéíûå âåëè÷èíû X n ñ ïîëîæèòåëüíîé âåðîÿòíîñòüþ
ìîãóò ïðèíèìàòü ñêîëü óãîäíî áîëüøèå çíà÷åíèÿ, ò.å.
l nA l n R{ }( ) ,1 1 , (13)
�
�
� � �n
n
n n n
n
R
Y
D
D D X1
1
2 1 1
1
1
2
( )
( )
( ( ) ( )) ( )� � �
�
�
��
�
�
��
�
�
0 , (14)
à òàêæå
ÍÎÄ ( : ) ,k d n Rnk � � 0 1 1 . (15)
Òîãäà öåïè Ìàðêîâà ( , )W nnR� �� 0 èìåþò ýðãîäè÷åñêèå ðàñïðåäåëåíèÿ, íå çà-
âèñÿùèå îò íà÷àëüíûõ çíà÷åíèé W� , ãäå � � �0 1 2 1, , , ..., R .
Äîêàçàòåëüñòâî. Ôèêñèðóåì öåëîå ÷èñëî � , 0 1 �� R , è ðàññìîòðèì
öåïü Ìàðêîâà ( , )X nnR� �� 0 .
Ïðè ëþáûõ ôèêñèðîâàííûõ çíà÷åíèÿõ ñëó÷àéíûõ âåëè÷èí W� , à òàêæå
Y Y R� �� � � �� 1 ñîãëàñíî (13) ìîæíî âûáðàòü äîñòàòî÷íî áîëüøèå X X R� �� �1, ,� ,
òàê ÷òî W R�� � 0 ; ñëåäîâàòåëüíî, äàííàÿ öåïü Ìàðêîâà íåïðèâîäèìà. Òàê êàê,
â ÷àñòíîñòè, ïðè W� � 0 P W WR( | )� �� � � �0 0 0 , îíà òàêæå íåïåðèîäè÷íà.
Èòàê, äëÿ äîêàçàòåëüñòâà òåîðåìû äîñòàòî÷íî ïðîâåðèòü âûïîëíåíèå óñëî-
âèé òåîðåìû Êëèìîâà. Ðàññìîòðèì âíà÷àëå ïðîöåññ âîññòàíîâëåíèÿ, ò.å. ìíî-
æåñòâî ( , )S jj � 0 ñëó÷àéíûõ òî÷åê, ãäå S 0 0� ; S S Dj j j� ��1 , j � 1; D j — íåçà-
âèñèìûå ïîëîæèòåëüíûå ñëó÷àéíûå âåëè÷èíû ñ ðàñïðåäåëåíèåì
a P D kk j� �( ) , k � 0 1 2, , , ... , j � 0 1 2, , , ... ,
ãäå a0 0� , è êîíå÷íûìè ìîìåíòàìè ïåðâîãî è âòîðîãî ïîðÿäêà: �1 1( )D ED� ,
� 2 1
2( )D ED� .
Ïóñòü z � 0 — öåëîå ÷èñëî, � ( )z — âåëè÷èíà ïåðåñêîêà ñëó÷àéíîãî áëóæäà-
íèÿ ( )S j ÷åðåç óðîâåíü z, ò.å. � ( )z S zN� � , ãäå N îïðåäåëÿåòñÿ èç óñëîâèÿ
S z SN N�
1 .
Òî÷íûå è àñèìïòîòè÷åñêèå ñâîéñòâà âåëè÷èíû ïåðåñêîêà èññëåäîâàíû â [18].
Îáîçíà÷èì h P S jj k
k
� �
�
�
� ( )
0
, j � 0 (äèñêðåòíàÿ âåðñèÿ ïëîòíîñòè âîññòà-
íîâëåíèÿ). Òîãäà
E z h idj z j i
ij
z
� ( ) � � �
�
�
�
�
��
00
1
. (16)
Èç òåîðèè âîññòàíîâëåíèÿ èçâåñòíî, ÷òî åñëè ÍÎÄ ( : )k hk � �0 1, òî
lim
( )j
jh
D��
�
1
1�
.
(17)
110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
Ïîñêîëüêó ïîñëåäîâàòåëüíîñòü ( )h j èìååò êîíå÷íûé ïðåäåë, òî îíà îãðàíè÷åíà:
h c jj �, 0. (18)
Èç (16) è (18) íàõîäèì îöåíêó
E z
c
D D� � �( ) ( ( ) ( )) �
2
2 1 .
(19)
Áîëåå òîíêàÿ îöåíêà ïîëó÷àåòñÿ, åñëè âûáðàòü òàêîå s, ÷òî
h
D
j sj
�
�
1
1
�
� ( )
, .
(20)
Òîãäà, èñïîëüçîâàâ äëÿ h j îöåíêó (18) ïðè j s è îöåíêó (20) ïðè j s� , ïîëó-
÷èì íåðàâåíñòâà
h id c id c k k dj
j
s
z j i
i
z j i
ij
s
k
k�
� �
�
�
� �
�
�
� �
� � �� �
0 1 10
1( )
z s� �
�
�
1
, z s� . (21)
Àíàëîãè÷íî
h id
D
idj
j s
z
z j i
i
z j i
ij s
z
� �
�
� �
�
�
� �
�
�
� �
� � �
�
1
1
1 1 11
1 �
� ( )
�
�
�
�
1
1
2 1
1
2
�
�
� �
( )
( ( ) ( )).
D
D D (22)
Èç (21) è (22) ñëåäóåò îöåíêà
E z c k k d
D
D Dk
k z s
�
�
�
� �( ) ( )
( )
( ( ) ( )) � �
�
�
� � �
�
� 1
1
21 1
2 1 . (23)
Ïåðâîå ñëàãàåìîå ïðàâîé ÷àñòè (23) åñòü îñòàòîê ðÿäà, ñõîäÿùåãîñÿ ê
c D D( ( ) ( ))� �2 1� , ò.å. îíî áåñêîíå÷íî ìàëî ïðè ( )z s� � � ; âòîðîå ñëàãàåìîå
ïðè z � � ìîæíî ñäåëàòü ñêîëü óãîäíî áëèçêèì ê
� �
�
2 1
12
( ) ( )
( )
D D
D
�
. Îòñþäà âû-
âîäèì ñëåäóþùåå àñèìïòîòè÷åñêîå ñîîòíîøåíèå:
lim ( )
( )
( ( ) ( ))
z
E z
D
D D
��
� ��
�
� �
1
2 1
2 1 . (24)
Íà îñíîâàíèè íàéäåííûõ îöåíîê ïðîâåðèì âûïîëíåíèå óñëîâèé òåîðåìû
Ã.Ï. Êëèìîâà. Äàëåå ïîëàãàåì, ÷òî w� åñòü ôèêñèðîâàííîå çíà÷åíèå ñëó÷àéíîé
âåëè÷èíû W� . Îáîçíà÷èì E E W W W wn n n� � ��( | )1 � � . Òîãäà
E W W W w ER n
n
R
( | )� � � ��
�
� � � �
1
. (25)
 ñâîþ î÷åðåäü, E E En n n� �1 2 , ãäå
E E W W X
w
R
i R W wn n n i1 1
1
1�
�
�
�� �
�
� � �
�
�
��� ; , |�
� �� �ãäå ,
E E W W W w En n n n2 1 1� � � ��( | )� � .
Âíà÷àëå îöåíèì En1. Ïðè óñëîâèè X w Ri �� / ( )1 , 1 i R , âûïîëíÿþòñÿ
íåðàâåíñòâà
W w
Rw
R
w
R
n � �
�
�
�
�
� �
1 1
;
îòñþäà E n� îöåíèâàåòñÿ ïî ôîðìóëå (23), ãäå ìîæíî ïîëîæèòü z w R� �� / ( )1 .
 ðåçóëüòàòå ïîëó÷àåì
E Y E
w
R
X E X X
w
R
n n n n n n1 1 1 1
1 1
�
�
�
�
��
�
�
�� � � �
�
�� � �� �
, ( ) ( ) ;
�
�
��
�
�
�� . (26)
Èç ñîîòíîøåíèÿ (24), ó÷èòûâàÿ òàêæå, ÷òî
E X
w
R
n w
�
�
�
�
��
�
�
�� � ����
��
�
�1
0
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4 111
êàê îñòàòîê ñõîäÿùåãîñÿ ðÿäà, èìååì
lim lim ( )
( )
( ( ) ( )),
� �
�
�
� �
� ��
�� � �
0
1 1 1
1
2 1
1
2w
n n
n
n nE Y
D
D D � � n X1 ( ) . (27)
Îöåíèâàÿ En2 ñ ïîìîùüþ (19), çàìåòèì, ÷òî
E P X
w
R
Y
c
D Dn
n
R
n n n n2
1
1 2 1
1 2
�
�
�
�
�
�
�
�
� �
� �
�
�
�
� � � �� ( ) ( ( ) ( ))
�
�
�
�
�
�
�
�
�
�
�
�
�
�
. (28)
Ïåðâûé ìíîæèòåëü ïðàâîé ÷àñòè (28) îöåíèâàåòñÿ ñâåðõó âåëè÷èíîé
R R X
w
n( ) ( )�1 1�
�
; âòîðîé, î÷åâèäíî, îãðàíè÷åí.
Ïðîñóììèðîâàâ (27) è (28) ïî n , � �� �1 n R, ïîëó÷èì ëåâóþ ÷àñòü íåðà-
âåíñòâà (14), ó÷èòûâàÿ, ÷òî � �� �( ) ( )Y YR� � . Òàêèì îáðàçîì, óñëîâèå (11) òåî-
ðåìû Êëèìîâà âûïîëíåíî.
Óñëîâèå (12) ñëåäóåò èç òîãî, ÷òî
E W W w w E Y Y ER R R( | ) ( ) ( )� � � � � � � �� �� � � � �� � � � � � �
�� �1 1 ,
ïîñêîëüêó EY Yn n�
�� 1 ( ) è E n�
� ïî óñëîâèþ (19).
Òåîðåìà äîêàçàíà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ã ë ó ø ê î â Â . Ì . Ñèíòåç öèôðîâûõ àâòîìàòîâ. — Ì.: Ôèçìàòãèç, 1962. — 476 ñ.
2. Ya n g T . , T e m p l e t o n J . G . C . A survey on retrial queues // Queueing Systems. — 1987. —
N 3. — P. 201–233.
3. F a l i n G . A survey of retrial queues // Ibid. — 1990. — N 7. — P. 127–167.
4. F a l i n G . I . , T e m p l e t o n J . G . C . Retrial queues. — London: Chapmen & Hall, 1997. —
328 ð.
5. 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: a computational approach. —
Berlin: Springer, 2008. — 318 ð.
6. A r t a l e j o J . R . Accessible bibliography on retrial queues // Math. and Comput. Model. — 1999.
— 30, N 3–4. — P. 1–6.
7. A r t a l e j o J . R . A classified bibliography of research on retrial queues: Progress in 1990–1999 //
Top. — 1999. — 7. — P. 187–211.
8. A r t a l e j o J . R . Accessible bibliography on retrial queues: Progress in 2000-2009 // Math. and
Comput. Model. — 2010. — 51, N 9–10. — P. 1071–1081.
9. D u d i n A . N . , K l i m e n o k V . I . A retrial BMAP/SM/1 system with linear repeated requests //
Queueing Systems. — 2000. — 34. — P. 47–66.
10. Ê ó ç í å ö î â Ä . Þ . , Í à ç à ð î â À . À . Àäàïòèâíûå ñåòè ñëó÷àéíîãî äîñòóïà. — Òîìñê:
Äåëüòàïëàí, 2002. — 253 ñ.
11. À í è ñ è ì î â  .  . , Ë å á å ä å â Å . À . Ñòîõàñòè÷åñêèå ñåòè îáñëóæèâàíèÿ: ìàðêîâñêèå ìî-
äåëè. — Êèåâ: Ëèá³äü, 1992. — 206 ñ.
12. L a k a t o s L . , B a l k e m a A . A . A probability model connected with landing of airplanes //
Safety and Reliability. — Rotterdam: Brookfield, 1999. — P. 151–154.
13. Ê î á à Å . Â . Î ñèñòåìå îáñëóæèâàíèÿ GI G/ / 1ñ ïîâòîðåíèåì çàÿâîê ïðè îáñëóæèâàíèè â ïî-
ðÿäêå î÷åðåäè // Äîï. ÍÀÍ Óêðà¿íè. — 2000. — ¹ 6. — C. 101–103.
14. K o b a E . V . On a GI G/ / 1 retrial queueing system with a FIFO queueing discipline // Theory
Stochast. Proces. — 2002. — 24, N 8. — P. 201–207.
15. Á î ð î â ê î â À . À . Ýðãîäè÷íîñòü è óñòîé÷èâîñòü ñëó÷àéíûõ ïðîöåññîâ. — Ì.: Ýäèòîðèàë
ÓÑÑÐ, 1999. — 440 c.
16. Ê ë è ì î â à . Ï . Ñòîõàñòè÷åñêèå ñèñòåìû îáñëóæèâàíèÿ. — Ì.: Íàóêà, 1966. — 243 c.
17. Ãí å ä å í ê î Á . Â . , Ê î â à ë å í ê î È . Í . Ââåäåíèå â òåîðèþ ìàññîâîãî îáñëóæèâàíèÿ. —-
Ì.: ËÊÈ, 2007. — 400 c.
18. Ô å ë ë å ð Â . Ââåäåíèå â òåîðèþ âåðîÿòíîñòåé è åå ïðèëîæåíèÿ. — Ì.: Ìèð, 1967. — Ò. 2. —
765 c.
Ïîñòóïèëà 04.02.2013
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 4
|