Исследование и оптимизация систем обслуживания с изменяемым режимом работы тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

БЕЛАРУСИ ДЗЯРЖАУНЫ УН1ВЕРС1ТЭТ

" . ОД

УДК 519.872

; 2 МАИ 1933

Бабіцкі Аляксандр Уладзіміравіч

ДАСЛЕДАВАННЕ I АПТЫМ13АЦЫЯ С1СТЭМ АБСЛУГОУВАННЯ СА ЗМЕИНЫМ РЭЖЫМАМ РАБОТЫ

Спсцыяльпасць 01.01.05 - тэорыя імавернасцяу і матэматычпая статыстыка

Аутарэферат. дысертацьп па атрыманне вучонай ступені капдыдата фізіка-матзматьічньїх пап у к

МШСК 1998

Праца выканана у Беларускім дзяржауным універсітзце.

Навуковы кіраунік — доктар фізіка-матзматьічньїх навук,

старшы навуковы супрацоунік Дудзін A.M.

Афіцьіяльньїя апаненты:

доктар фізіка-матзматьічньїх навук, прафесар, Апанасовіч У.У., кандидат фізіка-матзматьічньїх навук, Калмычкоу А.І.

Апаніруючая арганізацьія — Кіеускі нацыянальны універсітзт.

Абарона адбудзецца 22 красавіка 1998 года а 10 гадзіне на пас джанні спецьіялізавапага савета Д 02.01.08 пры Белдзяржупіверсітзі (220050, г. Мінск, праспект Окарыны 4, Універсітзцкі гарадок).

3 дысертацыяй можна азнаёмщца у бібліятзцш Бслдзяржуніверс тэта.

Аутарэферат разасланы

QO сакавіка 1998 г.

Вучоны сакратар спецьіялізаванага савета, дацэнт

АГУЛЬНАЯ ХАРАКТАРЫСТЫКА ПРАЦЫ

Актуальнасць тэмы дысертацьй. Сктэмы масавага абслугоування (СМА) з’яуляюцца адэкватнылп мадэлям1 пры даслсдаванш працэсау абслугоування чэргау у прамысловай 1 сацыяльнай шфраструк-туры, сродках сувяз1, выл1чальнай тэхшцы 1 г.д.

Заусёды мэта\п тэорьи масавага абслугоування было не толыа вывучэнне матэматычных мадэляу пэуных працэсау, атрыманне формул для разлжу 1х характарыстык, але 1 IX аптьп.пзацыя, што было вы-клжана неабходнасцю эфектыунага выкарыстання рэсурсау, скарачэння выдаткау 1 павел1чэння даходау. Напачатку разглядалкя задачы най-лепшай пабудовы астэм, вызначэння аптымальных значэнняу параметра^ на стадьи распрацоуш. У адпаведнасщ з п ат р аб ав анням 1 навукова-тэхшчнага прагрэсу узшкла неабходнасць у даследаванш шруемых СМА, г.зн., таюх мадэляу, у яюх выбар рэжыму работы ажыццяуляецца дынам1чна на працягу 1х функцыянавання 1 вызначаецца станам астэмы у моманты шравання.

Асабл1ва важпас значэнне ташя счстэмы маюць пры вывучэнш працэсау, што адбываюцца у сучасных электронных вьтчальных машинах 1 сетках, сродках сувяз1, аутаматызаваных Четэмах шраван-ня 1 базах даных (БД) дзякуючы вялтм магчымасцям у дакладнасщ адлюстравання 1 значнаму экaнaмiчнaмy эфекту дастасавання атрыма-ных выншау.

Сувязь з буйным! навуковым! праграмалй I тэмамь Даследаванш дысертацьп ажыццяулялкя у рамках наступных праграм:

• Дзяржауная праграма фундаментальных даследаванняу Рэспублт

Беларусь на 1996-2000 г. ’’Метады \ алгарытмы выл1чальнай 1 дыскрэтнай матэматьпа: распрацоука, анал'п, аптым1зацыя 1

адлюстраванне на архлтэктуру выл1чальных сктэм (Алгарытм). Метады 1 канструктыуныя алгарытмы знаходжання шварыянтных мер квазщеплщавых маркаусюх працэсау з манатонпа пераключае-мым шдэксам”.

• ’’Даследаванне двойчы стахастычных працэсау абслугоування”, (шыфр №628/38).

• Рэспублшанская навукова-тэхшчная праграма ”1нфарматыка”. (шыфр 02.03.02), ’’Распрацоука пакета прыкладных праграм раз-

ліку імавернасна-часовьіх характарыстык і аптьшізацьіі функцы навання інфармацьшна-вьілічальньїх сістзм і сетак”.

Мэты і задачы даследапаїшяу. Мзтамі дадзенай працы з’яул юцца даследаванне выпадковых працзсау, што адбываюцца у сістзм. абслугоування са змеиным рэжымам работы: ненадзейнай сістзме канцоунай крьшіцай, адналінейньїх сістзмах з адпачьшкамі і сістзм; з неаднароднай уваходнай плынию, а таксама пабудова эфектыунь вьілічальньїх алгарытмау для разліку імавернасна-часовьіх характары тык згаданых сістзм.

Гзтая мзта вызначае настушшя задачы даследаванняу:

• даследаванне стацыянарнага размеркавання колькасці патрабаваї няу у ненадзейнай сістзме тыпу M|G|1||N, атрыманне на яго асної формул для разліку асноуных характарыстык сістзмьі;

• вывучэнне уздзеяння асноуных відау дьісцьіплін кіравання адпачьп камі у адналінейньїх СМА на зфектыунасць прадзсу абслугоуванн: атрыманне яуных выразау для крытзрыяу якасці функцыянаванв сістзм;

• выяуленне аптымальнай структуры дапушчанай у сістзму неадш роднай уваходнай пльші пры наяунасці і пры адсутнасці адпачьп кау.

НаБуковгья навізна атрыманых вьшікау.

Даследавана ненадзейная СМА з канцоунай крьініцай і адвольны: размеркаваннем часу абслугоування. Ненадзейнасць сістзмьі пал? гае у магчьімасці выхаду прыбора са строю як у час абслугоувак ня, так і у час прастою. Акрамя алгарытму для разліку дакладны зпачзнняу асноунай характарьістьікі — сярэдняга часу знаходжанн патрабаванняу у сістзме — прапанаваны адпаведныя набліжаньїя фор мулы, заснаваныя на асімптотьїцьі паводзін гзтай характарьістьікі прі нарастанні колькасці крьініц да бясконцасці.

Даследаваны шзраг сістзм з адпачьшкамі: сістзма з абмежавальна: дьісцьіплінай абслугоування і гібрьіднай стратзгіяй уключзння; CM; з двума тьшамі адпачынкау і з пераключзннем на іх, залежным а, колькасці абслужаных заявак; сістзма з адзіночньїмі адпачьшкамі, у яко пераключзнне на адпачынак вызначаецца як колькасцю абслужаны заявак, так і даужынёй чаргі; СМА з абагульненьїмі адпачьінкамі.

Вызначана структура аптымальнага набору імавернасньїх прыярь тзтау у задачы фільтрацьіі неаднароднай уваходнай пльші у СМА тьга M|G|1, а таксама аптымальныя імавернасці допуску заявак у сістзму

адпачьшкамі.

Практичная і зканамічная значнасць атрыманых вьшікау.

1. Распрацаваныя алгарытмы разліку часу знаходжання патрабаван-няу у ненадзейнай сістзме М [ С1111N бьілі выкарыстаны у праграм-ным прадукце, прызначаным для ацзнкі і аптьшізацьіі працэсу абслугоування запытау у рзляцыйных базах даных.

2. Вьінікі даследаванняу сістзм з адпачьшкамі часткова бьілі выкарыстаны у пакеце прыкладных праграм ’’СНРИУС”, распрацаваньш у НДЛ прыкладнога імавернаснага аналізу БДУ і прызначаным для знаходжання імавернасна-часовьіх характарыстык і аптьімізацьіі параметрычных стратзгій кіравання у сістзмах масавага абслугоування. Разгледжаныя дьісцьіпліньї абмежавання абслугоування дазваляюць развязваць задачы аптьімізацьіі у сістзмах са змяненнем вытворчых характарыстык на працягу перыяду занятасці.

3. Вызначаная структура аптымальнага развязку задачы фільтрацьіі уваходнай пльїні дазваляе будаваць прадукцыйныя алгарытмы ап-тьімізацьіі допуску у сістзмьі пры адсутнасці механізма назпачзпня прыярытзтау.

Дастасаванне атрыманых вьшікау пры настройцы параметрау функцыя-навання рэальных сістзм дазволіць павьісіць іх эфектыунасць, забяспс-чыць найбольш рацыянальнае выкарыстанне спажываных рзсурсау.

Асноуныя палажзнні, што выносяцца на абарону.

1. Атрыманы асноупыя характарьістьікі працэсу функцыянавання ненадзейнай адналінейнай сістзмьі з канцоунай крьініцай. Распраца-ваны эфектыуныя набліжаньїя формулы для разліку сярэдняга часу знаходжання патрабаванняу у сістзме.

2. Даследаваны СМА з адпачьінкамі, у якіх пераключзнне ажыц-

цяуляецца у адпаведпасці з абмежавальнай, вычарпальнай і кам-бінаванай днсцьіплінамі. Атрыманы я}гныя аналітьічньїя залеж-насці значэнняу часова-імавернасньїх характарыстык сістзм ад параметрау стратзгій кіравання пераключзннямі паміж абслугоу-ваннямі і адпачьшкамі. .

3. Выкрыта структура аптымальнага развязку задачы фільтрацьіі уваходнай пльші у сістзме М|011 і у сістзме з адпачьшкамі.

4. Распрацавана алгарьітмічнае і праграмнае забеспячзнне задач аптымальнага кіравання доступам у рзляцыйных базах даных, а таксама задач праектавання і аптьімізацьіі сістзм з дьшамічнай рзарганізацьіяй інфармацьіі.

Асабістьі уклад дысертанта. У дадзеную працу увайшлі вьінік атрыманыя аутарам самастойиа.

Апрабацыя вьшікау. Вьшікі дьіссртацьіі прадстауляліся і дг кладваліся на канфсрзнцьіі ’’Информационные сети и системы”, (Санкі Пецярбург, 1993), міждзяржаунай навукова-практычнай канферэнць творчай моладзі ’’Актуальные проблемы информатики: математичеі кое, программное и информационное обеспечение” (Мінск, 1994), адз наццатай, трынаццатай і чатырнаццатай Беларускіх зімовьіх школа? семінарах па тзорьіі масавага абслугоування (Мінск, 1995, 1997, 1998).

Публікацьіі. Па тэме дысертацьй надрукавана 12 прац.

Структура і аб’ём дысертацьй. Дысертацыя складаецца уводзін, агульнай характарьіетьікі працы, трох главау, высновау і спіс выкарыстаных крьшіц у 71 назву. Змяшчае 3 рьісункі, 8 таблії Агульны аб’ём працы 105 старонак. .

АСНОУНЫ ЗМЕСТ

У першай главе дысертацьй даследуецца адналінейная ненадзейна СМА з кандоунай крьініцай, якая адпавядае наступнаму апісанню.

На прыбор паступаюць заяукі з N крьініц. Кожная крьшіца атрым лівае права на генерацыю наступнага патрабавання толькі пасля за канчэння абслугоування сістзмай яго папярэдняй заяукі. Час да ге нерацьіі наступнага запыту мае экспанентавае размеркаванне з пара метрам А. Час абслугоування заяукі з’яуляецца вьшадковай вслічьшеі з функцыяй размеркаванця В(х), пераутварэннем Лапласа-Стыльт’ес; (ПЛС) /?(з), пачатковнмі момантамі 61,621^3- Праз экспанентава раз меркаваны з параметрам а час з моманту пачатку абслугоуванн: запыту можа адбыцца адмова (паломка) прыбора. Нягледзячы н; гэта, прыбор паспяхова завершыць абслугоуванне. Але потым еі будзе рамантавацца на прадягу часу, які мае функцыю размеркаванн С(і), ПЛС д(в). Пасля заканчэння рамонту пачынаецца абслугоуванн наступнага патрабавання, калі у чарзе да прыбора будзе, прьшамсі, адн патрабаванне. У выпадку спусташэння чаргі з моманту заканчэнн апошняга рамонту ці абслугоування пачынаецца адлік экспанентав размеркаванага з параметрам а часу да наступнай паломкі. Калі н працягу гэтага прамежку часу не паступае патрабаванне, то пасля яг

заканчэння адбываецца паломка і адразу пачынаецца рамонт. Г.зн., магчымы шматразовы выхад прыбора са строю і яго аднауленне на працягу часу, калі прыбор не заняты абслугоуваннем.

У першым раздзеле гэтай главы вывучаецца стацыянарнае раз-меркаванне колькасці патрабавапняу у сістзме у моманты заканчэння абслугоуванняу і рамонтау, а таксама у адвольны момант. Прапануюц-па алгарытмы для знаходжання дакладных значэнняу характарыстык сістзмьі.

У другім раздзеле атрыманы асімптатьічньїя формулы для сярэд-няга часу {Ум) знаходжання заявак у надзейнай сістзме у выпадку, калі колькасць крьініц патрабаванняу нарастае да бясконцасці пры тым, што інтзнсіунасць генерацьіі кожнай з іх (А) спадає з такой хуткасцю, каб сумарная інтзнсіунасць генерацьіі заявак заставалася нязменнай. ііішьімі словамі, А = Дзе р некаторы дадатны лік. Даказваецца

праудзівасць наступнага вьініку:

Трзці раздзел прысвечаны апісанню формул для падліку набліжа-нага значэння сярэдняга часу знаходжання патрабаванняу у сістзме, дастасаванне якіх патрабуе значна меншых вьілічальньїх аперацый і рэсурсау ЭВМ, чым выкарыстанне алгарытмау атрымання дакладных значэнняу. У аспову пабудовы гэтых формул пакладзены прыведзеныя асімптатьічньїя формулы, а таксама вьінікі даследавання ненадзейнай сістзмьі з бясконцай крьініцай.

У другой главе разглядаюцца адналінейньїя СМА з адпачьінкамі. Пад адпачьінкамі мяркуюцца адзіночньїя ці множныя прамежкі часу, на працягу якіх прыбор пераключаецца на выкананне адрозных ад абслу-гоування чаргі відау работ, такіх як, напрыклад, рзарганізацьія базы даных, абслугоуванне іншьіх чэргау, выкананне прафілактьічньїх, уз-науляльных і іншьіх працэдур.

Агульная мадэль можа быць апісана наступным чынам. На прыбор паступаюць патрабаванні у адпаведнасці са стапыянарным пуасоїш'скім

і).

калі р < 1,

працэсам з параметрам А. Прадугледжана пеабмежаваная колькаси месц для чакання. Час абслугоування з'яуляецца вьшадковай велічьше з фупкцыяй размеркавання £(<), ПЛС /?($), і пачатковьімі момантамі 6,- = /0°° і'іІБ(і), і > 1. Пры наступленні пзуных для кожнай з разглсджаны сістзм умоу прыбор спыняе абслугоуванні і пачьшае адпачьінкі -прамежкі часу вьшадковай працягласці з функцыяй размеркавання Н(і ПЛС і'(я), і пачатковьімі момантамі Л,- = і > 1. Калі

пзунай сістзме выкарыстоуваецца некалькі відау адпачынкау (у другії і чацвёртым раздзелах), то для іх адрознеїшя 5'жываецца верхні індзк< Патрабаванні, што паступаюць падчас адпачынкау, далучаюцца д агульнай чаргі.

Для вывучэння стацыянарнага рэжыму функцыянавання сістзм вы карыстоуваецца метад укладзеных ланцугоу Маркава. У якасці укла дзеных момантау вьібіраюцца як моманты завяршэння абслугоуванняу так і моманты завяршэння адпачынкау. Асноунай мэтай даследавання; першых трох раздзелах з’яуляецца атрыманне формул для стваральны: функцый сумеснага размеркавання колькасці патрабаванняу у сістзм ва укладзеныя моманты і колькасці абслугоуванняу, рзалізаваньїх пасл: апошпяга адпачынку, яны дазваляюць вьівадзіць формулы для разлік; характарыстык сістзм і крытэрыяу якасці іх функцыянавання.

На працягу главы ужываюцца наступныя абазначзнні:

а,- = ^йі=7Мє-а^я(0, і > 0.

0 г- О *•

Разгледжаная у першым раздзеле другой главы СМА адпавяда( агульнай пастаноуцы, згаданай вышэй, і канкрэтызуе яе адносна умо} пераключзшія паміж абслугоуваннямі і адпачьінкамі. У адпаведнасці : абмежавальнай дьісцьіплінай абслугоування прыбор начынае адпачынк: у двух выпадках: 1) у сістзме не засталося неабслужаных патрабаванняу; 2) К заявак бьілі выкананы з пачатку перыяду занятасці. ТЧ/У-гібрьідная стратзгія уключзння мяркуе, што адпачьінкі цьіклічна пау-тараюцца, пакуль у момант заканчэння чарговага адпачынку даужыня чаргі не дасягне узроуню N.

Даказваецца, што дастатковай умовай існавання стацыянарнага стану у сістзме з’яуляецца няроунасць А < ^ ^ ^ .

Абазначьш праз р[^ стацыянарныя імавернасці наяунасці і патрабаванняу у момант заканчэння адпачынку (/ = 0) ці /-га (1 < I < К) з пачатку перыяду занятасці абслугоування. Тады для стваральнаіі функцьіі р(г) — Е/і0 справядліва формула:

р(г) =

п(°)

/3(Л - Лг)(і/(Л - Лг) - 1)

О - Р(А - Аг))0* - і/(А - - Аг))

дг))

1?рУМ** - /?*(А - \г)) +

,І=0 7=^

дзе р^\ 0 < і < N — 1, рд \ N < і < К — 1 — адзіньї развязак сістзмьі лінєйньїх раунанняу:

д!‘

йг1'

'ЛГ-1

.Е‘р^'(^-^(А-А2))+ + К,Е р$г’(гк~і - РК~3(Х - Аг)) і=#

1 < 5 < і, 0 < /, < г» — 1, .

+ *е рф{к - І) = к~ + РО

,7=0 ;=іУ

І2 = г.

= о,

АЬ\ + А/гі '

дзе г\,... ,г( — карані гк — и{\ — Аг)/3^(А — \г) = 0 у абсягу |г| < 1 з кратнасцямі г'і,..., г'(.

У другім раздзеле другой главы вывучаецца СМ А, у якой иры спусташзнні чаргі могуць пачацца адпачьінкі, калі з моманту апошняга адпачынку было абслужана, прьінамсі, Ь патрабаванняу. Пры гэтым спачатку пачынаецца першая фаза, працягласць якой — випадковая велічьіня з функцыяй размеркавання ПЛС ^М(я) і пачатковьші

момантамі /і-1^ = ГгіЯ^)(<), і > 1. Калі за час пєршай фазы у

сістзму паступіла М ці больш патрабаванняу, то адразу узнауляюцца абслугоуванні. У процілегльш вьшадку цьіклічна паутараецца другая фаза, пакуль у момант заканчэння чарговага адпачынку у сістзме не анынецца, прьінамсі, N заявак, пасля чаго пачнецца іх абслугоуванне. Працягласць другой фазы адпачынкау з’яуляеццавьшадковай велічьінсй з функцыяй размеркавання #(2)(<), ПЛС і/2) (в) і пачатковьші момантамі /гР = /0°° і > 1. Калі у момант спусташзння сістзмьі колькасць

абслужаных пасля апошняга адпачынку патрабаванняу меней Ь, прыбор будзе прастойваць у чаканні новых заявак.

Для стваральнай функцьіі тг(г) = 71 <2' стацыянарных імавернас-

цяу 7Г| наяунасці і патрабаванняу у сістзме у адвольны момант вьтедзена формула:

тг(г) =

(1 - Щ/3(Ц1 - г))

м-1

N-1

ал(!1) + а/42) і £ £и,) + £№(

1=0 1=0 / і=1

£-1

(2-/?(А(1-2)))

х Ы(А(1 - *)) _ 1 + (г - 1) £ 4Л+

+ (г/(2)(А(1 - г)) - 1) + Е «/И >

1=0

дзе

= Е 41)а>-1+1 + Е Ща^+и г > О,

1=м

,0-1)

1=1

№ = 7^ге“Л<^0)(<). * > 0, 3 = 1,2.

о

Для сктэмы, даследаванай у трэщм раздзеле другой главы, агуль пая пастаноука дапауняецца наступным ашсаннем парадку пераклю чэння на адпачынш I узнаулення абслугоування. Як 1 у сктэме папя рэдняга раздзела, ажыццяуляецца падлпс колькасщ абслужаных пам1а адпапыпкам'1 патрабаванняу. Адрозненне палягае у тым, што пасл)

' заканчэння абслугоування Ь-та, па лжу пасля апошняга адпачынку па трабавання сктэма пераключыцца на адпачынак, кал! у ёй знаходзщцг не болей К заявак. У выпадку, кал! колькасць заявак у сктэме 5 тэты момант перавышае К, перыяд занятасщ будзе працягвацца, пакул! колькасць заявак у сктэме не зменшыцца да вел^чыш К, пасля чаге сктэма пераключыцца на адпачынак.

Кал1 Четэма робщца пустой I пры гэтым колькасць патрабаванняу; абслужаных пасля апошняга адпачынку, не дасягае вел1чыш Ь, сктэма не пераключаецца на адпачьпш, а чакае прыходу першай заяую. Пасл? адпачынку сктэма узнауляе абслугоувашп адразу жа пры наяунасц патрабаванняу, а пры IX адсутнасщ — чакае 1х наступления.

Абазначым праз 7Г,- стацыянарныя 1мавернасщ знаходжання i патрабаванняу у сктэме у адвольны момант часу, а праз 7г(л) стваральнук функцыю гэтых 1мавернасцяу (тг(г) = £ёо7Г1г')- Яна можа быт вызначана па наступнай формуле:

(1 - \Ь\)Р(\(1 - г))

х

(г - Р{ А(1 - г))) £ с/ш,^ + + А/и с/ + 1

Я-1

^=и \ 1=0

дзе велічьші / знаходзяцца па рэкурэнтных формулах

Ш/У = 0 < / < і, ги[У = 0, г < I,

І+1 . .

ші?і = Е №^т1)аі-т+і + ги^о~1)аі, г’>1 > °> 1 < І + 3, 1 < 7 < Ь,

т= 1

= 0, I > і + І, г, / > 0,

а велічьші с/ з’яуляюцца развязкам сістзмьі лінейньїх раунанняу

У разгледжанай у чацвертым раздзеле другой главы сістзме ад-пачьінкі палынаюцца пры апусташэпш сістзмьі. Яны падзяляюцца на два відьі: асноуныя і дадатковыя. Асноуныя адпачьінкі уяуляюць сабой паслядоунасць з К прамежкау часу выпадковай працягласці з фупкпьіямі размеркавання ПЛС і/М(я) і пачатковьшімомаптамі /і; , і = 1,2,

1 < У < К. Калі да закапчэння К-га асноунага адпачынку сістзма застаецца пустой, то пачыпаецца адлік экспансптава размеркаванага часу з параметрам а, пасля якога у выпадку непаступленпя у сістзму заявак пачнецца паслядоунасць дадатковых адпачынкау. Працягласць ./-га дадатковага адпачынку мае функцыю размеркавання ПЛС

*СЛ(5) і пачатковыя моманты і = 1,2, 1 < 7 < Ь. Калі па працягу дадатковых адпачынкау не прьіходзілі заяукі, то зноу будзе адлічвацца экспапентава размеркаваны час з параметрам а да пачатку чарговай паслядоунасці дадатковых адпачынкау. Такім чынам, да паступлен-ня першай заяукі дадатковыя адпачьшкі могуць паутарыцца некалькі разоу. Калі надыход першай заяукі у пустую сістзму прыпадае на прамежак часу перад дадатковьімі адпачьінкамі, то яе абслугоуванне пачынаецца адразу жа. У выпадку паступлення заяукі падчас нскато-рага адпачынку абслугоуванне узнаулясцца пасля яго закапчэння.

Няхай р,-, (рр\ р'Р) — 1мавернасць наяунасщ г патрабаванняу счстэме у ыомант завяршэння абслугоування (.7-га асноунага щ дада' ковага адпачынку). Для стваральных функцый гэтых 1мавернасцяу:

00 • /л 00 г л ■

р{2) = Ер.-*’. рЬ){г) = Е р\ 1 < 3 < К,

>=о

1=0

. «О I >\ .

Р{з\г) = Ер!'2\ 1 <з<ь, 1=0

справядл1вы наступныя формулы р0/3(А(1 - г))

/ к , ,

Хг П ^т>(А)

р{г) =

г-р(Щ-г))

771=1

а + А - а П *(т)(А)

, т=1

-1+

а П ^(т)(А)

+-

т=1

I 3-1

а + Х-а П ^т\Х);=1 т=1

т=1 К 3-1

Е П Р^(А)(«/У)(А(1-г))-*/«(А)) +

+ Е П ^т>(А)(«/0)(А(1-г))-1/0)(А)) ,

; = 1 т=1 /

р(;)(г) = Ро П 1/(т)(А)^(-')(А(1 - -г)), 1 < j < К,

т= 1

р0а П ^(т)(А)

ри){г) =---------------------- П *Н(А)*0)(А(1 - г)), 1 < 1 < Ц

а + Х-а П £>(т)(А)т=1

т=1

дзе

Ра

к

(1 - АЬО/ [Е П ^(т)(А) (1 + АА(Л - хь)

+-

П ^(т)(А) / ь ^ 0

т=1 ' А + а Е П *(т)(А) (1 + Ал|;) - АЬХ)

а + А - а П ^(т)(А) 4 ;=1 т=1

т=1

У трэцяй главе даследуюцца задачы аптыыальнай фшьтрацьп увг ходнай плыш. Выбарам найлепшых значэнняу для шавернасцяу д; лучэння заявак да чарп дасягаецца ышшум сярэдшх страт, што няс

сктэма у адзшку часу. Страты сктэмы складаюцца са штрафау, што спаганяюцца за адмову допуску патрабаванняу у сктэму, а таксама з выдаткау, звязаных са знаходжаннем у сктэме принятых заявак.

У першым раздзеле для Четэмы тыпу M|G|1 даследавана фшьтра-цыя неаднароднай уваходнай плыш. У адналшейную Четэму з бясконцай чаргой паступае п стацыянарных пуасонаусих плыняу з штэнаунасцям1 •^й 1 < г < п. Заяую г-ra тыпу пры паступленш дапускаюцца у сктэму з шавернасцю гу,-, а з дадатковай iiviaBepiiacmo 1 — пакщаюць сктэму неабслужаньп.п. Аблугоуванне патрабаванняу г-га тыпу ажыццяуляецца на працягу выпадковага часу з еярэдшм значэннем b; i друпм момантам d{. Пры адмове прыняцця заяуш г-га тыпу сктэма страчвае а,- грашовых адзшак, у процшеглым выпадку яна нясе страты вел1чыш с,- за адзшку часу знаходжання гэтага патрабавання у сктэме. Мяркуецца, што заяую трапляюць на прыбор у парадку паступлення. Трэба выбарам ап-тымальных значэнняу 1мавернасцяу допуску g,-, 1 < г < гг, мш!м1заваць еярэднюю суму страт, што нясе сктэма у адзшку часу. Для гэтай вел1чыш маем формулу

п ( п \ Е 9і-Мі

bQ э II :м >- QjCj Ьі+ /,=1" \ + (1 - qj) а.

j=i 2 1 - Е V \ і=і } )

а зыходная задача зводзіцца да наступнай задачы аптьімізацьіі:

[ЯЗЬ •••,5 »)-♦ тіп

' < 1,

. О < <?; < 1, 1 < г < гг.

Даказваецца, што існує такі развязак гэтай задачы, усе кампаненты якога акрамя адной роуны межавым значэнням 0 ці 1. У адпаведнасці з гэтым фактам, аптымальны набор імавернасцяу допуску заявак у сктэму шукаецца еярод такіх наборау д,-, 1 < і < ті, дзе толькі адна кампанента адрозніваецца ад 0 і ад 1. Для пабудовы такіх наборау трэба выканаць наступпыя дзеянні:

1. Сярод мноства усіх уваходных плыняу Р = {1,...,п}. вылучыць падмноства <5 плыняу, принятых у сістзму цалкам (д* = 1, і Є €>), даследаванне С) працягваць, калі выконваецца умова £ А,6; < 1.

ієО

2. Для кожнай пльїні і з мноства .Р\<5 знайсці аптымальнае значэнне

д] па формуле

„=тіп 1,ш 0,^ В-

{с5В + Ь3С) (сі, В + 6,-Р) с, <1$ 1 2 с;- 6^

дзе

I? = Ц АД-, С=ЕА.-с.-, Я = 1 - £ А,-Ь{.

>'Є<? ІЄ(? <Є<?

Мяркуючы велічьгаі ?і, г Є Р\{ф и _/} роуньші нулю, разлічьіць значэнне фупкцыянала іР(ді,..., д„).

Набор, на якім атрымана найменшас значэнне сярздніх страт сістзмьі у адзінку часу ^(<7ь • • •, ?п), і з’яуляецца найлепшым наборам імавернасцяу допуску заявак у сістзму.

У другім раздзеле трэцяй главы для вывучэння задачы фільтрацьіі у СМА з адпачьшкамі разглядаецца дапаможная сістзма.

У занятым стане у сістзму паступаюць заяукі у адпаведнасці са стацыянарным пуасонаускім працэсам з параметрам Аі- Час аб-слугоування паступіушьіх заявак з’яуляецца выпадковай велічьіней з функцыяй размеркавання В^(і), пераутварэннем Лапласа-Стыльт’еса першым і другім пачатковьші момантамі 6^ і Пасля

спусташэння чаргі адразу жа пачынаюцца адпачьшкі — прамежкі часу выпадковай працягласці з функцыяй размеркавання Н{і), ПЛС ^(з), канцоуньїмі пачатковнмі момантамі /іі, 1і2- Пры пераходзс на адпачьшкі інтзнсіунасць уваходнай пльші мяняецца з велічьіні Аі на велічьшю Аг-Адпачьшкі паутараюцца, пакуль у момант завяршэння адпачынку у сістзме не будуць знойдзеїш патрабаванні. Гэтыя патрабаванні будуць абслугоувацца выпадковы час з функцыяй размеркавання В№(і), ПЛС р№(з), канцоуньїмі пачатковьімі момантамі Ь^\ Ь^- Мяркуецца, што парадак абслугоування заявак вызначаецца парадкам іх паступлення.

Для стваральнай функцьіі 7г(г) = жіг' стацыянарных імавернасцяу щ наяунасці і патрабаванняу у сістзме у адвольны момант часу атрымаиы выраз:

,(2)=

Лі(і-А^ + АаЬІ4)

1 - и(А2(1 -*)) А2(1 - *)

А] (г - р(2) (А,(1 - г))) \ 1-х +

(/?(» (А,(1 - г)) - рУ (А,(1 - г))) {и (А2 (і - Р™ (А,(1 - *)))) - і) + г - /3(.) (А,(1 - г))

Для ПЛС часу знаходжапня у сістзме патрабаванняу, што паступілі падчас адпачынку иД°)(з) ці падчас перыяду занятасці выведзены

формулы:

(0)/ \ = у{з)-у{\, (1-рУ(з))) Ь, (А2 - з - А 2/3(Ч(а)) ’

ЦТ

= (і — АіМ1}) (Л2 (і-/Я(д)))-і)

; А2А1Ь(12) (Аі - 5 - АцЗШф) ’

Для задачьі фільтрацьіі уваходнай плині у сістзме з адпачьшкамі дзталева разглядаецца вьіпадак адпароднай уваходнай пльті.

Такім чьшам, папярздняе апісанне сістзмьі пабьівае наступньї вигляд. Мяркуем, што заяукі у сістзму паступаюць у адпаведнасці са стацмянарньш пуасонаускім працзсам з параметрам А. Заяукі дапускаюцца у сістзму з імавернасцю д, калі япьі паступаюць падчас абслугоування, і з імавернасцю г, калі яньї паступаюць падчас адпа-чинку. Час абслугоування має сярздняе значзнне Ьі і другі пачат-ковьі момант Ь2. Сістзма штрафуецца па суму а у випадку адмопм прьіняцця заяукі, а таксама на суму с за адзінку часу знаходжаїшя адиоГі заяукі, прьшятан у сістзму. Ва усім астатнім апісанне сістзмьі адпавядае вьішзйзгаданаму.

Больш зручнай для вьівучзння з’яуляецца задача пошуку аптьімаль-ньіх велічьінь Аі = дА і А2 = гА. Для велічьші сярздняй сумьі страт у адзіпку часу маєм вьіраз:

с,,2 А; ((сь, - о)(і - л,*,) + |г.2Ді)

ґ(Л„Лг)-Ла + — Л, + - (1_Лі6і + Аі6і)(і_Ді6і) •

Такім чьшам, для вызначэння аптымальных значэпняу Лі і Лг маем наступную задачу аптьімізацьіі:

^(Аі, А2) -> тіп,

Аі ,Л2

ХіЬі < 1,

,0< А,,А2< А. ■

Яе развязак зпаходзіцца унутры абсягу, зададзенага няроунасцямі, у пункце:

а; = ^

й

Ь\ \е (1 — А1&1)

— 1 + А^Ь]

1 >

дзе

(р\3 ((}\2 _ (12 „ /ЙЧ» й2

С?=(з) +Ы ’ р~~з^’ 9~ Ш +«’

сЛ2 1 /■ , сЬ2\ , С&2

е — гл^!5 £_ьД 1 а 2&1 у ’ 26Г

кал1 0 < А| < А, 0 < А£ < А, або у тым з яго межавых пунктау:

1. А2 = О, А1 можа набываць любое значэнне;

2. А2 = А, ■

А]^ = гшп

А,-

2 I а — сЬх

\

2Ь{(а — сЬ{) + с&2

3. А1 = О,

А2 = шт |А,тах |о, ^ ~^(а — с^0 — /^1}}

4. А^ = А (гзты выпадак разглядаецца толыа пры выкананш няроу-насщ А&1 < 1),

А2 = тт |А,тах |о, ^ ^(а — сЬ^)(1 — ХЬ\) — "трА^ — 1 + АЬ^ у/611|;

дзе функцыянал Р(\1, Д2) набывае найменшае значэнне.

высновы

Даследавана СМА з канцоунай крышцай 1 паломкам1 прыбора, яыя не перашкаджаюць даабслугоуванню патрабаванняу. Раепрацаваны алгарытм для разлшу дакладных значэнняу асноуных характарыстык астэмы. Прапанаваны таксама набл1жаныя формулы для сярэдня-га часу знаходжання патрабаванняу у астзые, яюя грунтуюцца на аамптатычных паводзшах гэтай характарыстыю у надзейнай сктэме

M|G|1||N. Алгарытмы бьілі рзалізаваньї у выглядзе праграмнага срод-ку, прызначанага для ацзнкі прадукцьійнасці функцыянавання рэляцый-ных баз даных і аптьімізацьіі кіравання працэсам пабудовы індзксау на табліцьі базы.

Для даследаваных адналіпейньїх сістзм масавага абслугоування з адпачьінкамі зпойдзены формулы для стацыянарнага размеркавання колькасці патрабаванняу у сістзме у адвольпы і ва укладзеныя момапты, а таксама для такіх характарыстык сістзм, як сярэдняя даужыня чаргі, сярэдняя працягласць перыяду занятасці, сярэдняя колькасць пераключзнняу з адпачынкау на абслугоуваппі, сярэдняя колькасць адпачынкау у адзінку часу.

Атрыманне яунага выгляду залежнасці крытэрыю якасці функцыянавання сістзм ад іх параметрау дазволіла пабудаваць эфектыуныя працэдуры для пошуку на ЭВМ аптымальных стратзгій кіравання пєраключзннямі паміж абслугоуваннямі і адпачьінкамі. Вьілічальньїя эксперыменты пацвердзілі мэтазгодпасць выкарыстання дьісцьіпліп аб-межавання няспыннай працы прыбора у сістзмах са спадальпым харак-тарам прадукцьійнасці на перыядах занятасці.

Даследаваны заданы фільтрацьіі неаднароднай уваходнай пльші у адналіпейньїх СМА з адсутнасцю назначэння прыярытэтау з функцыя-налам якасці у выглядзе сярэдняй сумы страт, што пясе сістзма у вьініку адмовы прыняцця заявак і пры утрьіманні чаргі. Высвятленпе структуры аптымальнага набору імавернасцяу допуску патрабаванняу розных тыпау у сістзму M|G|1 дазволіла распрацаваць канструктыуны алгарытм развязання задачы.

Даследавана задача фільтрацьіі аднароднай уваходнай пльші у СМА з адпачьшкамі, вызначаны аптымальныя інтзнсіунасці плыняу, што дапускаюцца у сістзму падчас абслугоуванняу і падчас адпачынкау.

СПІС АПУБЛ1КАВАНЫХ ПА ТЭМЕ ДЫСЕРТАЦЫ1 ПРАЦ

1. Бабицкий А.В., Дудпн А.Н. Математическая модель функциониро-

вания баз данных с постоянным обновлением информацип// Информационные сети и системы. Тез. докл. - Санкт-Петербург, 1993. -С. 35-37. -

2. Бабицкий А.В. Ненадежная система массового обслуживания с ко-

нечным источником// Актуальные проблемы информатики: математическое, программное и информационное обеспечение. Тез. докл. - Минск, 1994. - С. 94-95.

3. Бабицкий А.В. СМО с Т-ограниченной дисциплиной обслуживания и отдыхами// Исследование сетей связи и компьютерных сетей методами теории массового обслуживания. Тез. докл. - Минск, 1995. - С.18-19.

4. Дудин А.Н., Бабицкий В.А., Бабицкий А.В., Клименок В.И., Ше-тиков Г.И. Пакет прикладных программ СИРИУС. Назначение и содержание// Исследование сетей связи и компьютерных сетей методами теории массового обслуживания. Тез. докл. - Минск, 1995. - С. 53-54.

5. Бабицкий А.В., Дудин А.Н., Клименок В.И. К расчету характеристик ненадежной системы массового обслуживания с конечным источником// Автоматика и телемеханика. - 1996. - №І. - С. 92104.

6. Babitski A.V. Asymptotic formulae for sojorn time in M|G|l||N queue// Массовое обслуживание. Потоки, системы, сети. Тез. докл. -Минск, 1997. - С. 122-123.

7. Babitsky A.V. M|G|1 vacation model with limited service discipline and hybrid switching-on policy// Math, problems in Eng. - 1997. - V.3. -P. 243-253.

8. Babitski A.V. M|G|1 model with multiple vacations controlled by the number of served customers// Статистический и прикладной анализ временных рядов. Тез. докл. - Брест, 1997. - С. 23-24.

9. Babitski A.V. Single server queue with general vacations// Статистический и прикладной анализ временных рядов. Тез. докл. - Брест, 1997. - С. 25-26.

10. Babitski A.V. M|G|1 vacation model with hybrid service discipline// Сб. Статистический и прикладной анализ временных рядов. - Брест, 1997. - С. 133-139.

11. Babitski A.V. Input flow filtration problem for some single server models// Сб. Статистический и прикладной анализ временных рядов.

- Брест, 1997. - С. 139-145.

12. Babitski A.V. Optimization of the input flow in a single server vacation model// Массовое обслуживание. Потоки, системы, сети. Тез. докл.

- Минск, 1998. - С. 86-87.

РЭЗЮМЕ

Бабіцкі Аляксандр Уладзіміравіч

ДАСЛЕДАВАННЕ I АПТЫМ13АЦЫЯ С1СТЭМ АБСЛУГОУВАННЯ СА ЗМЕИНЫМ РЭЖЫМАМ РАБОТЫ

Ключавыя словы: сістзма масавага абслугоування, сістзма з ад-пачьгакамі, працэс абслугоування, стацыянарнае размеркавапне, філь-трацыя уваходнай пльїні.

Аб’ектамі даследаванняу дысертацыйнай працы з’яуляюцца сістзмьі масавага абслугоування са змеиным рэжымам работы.

Мэта працы заключаецца у атрьіманні апалітьічньїх залежнасцяу

і пабудове эфектыуных вьілічальпьіх алгарытмау для разліку імапер-насна-часовых характарыстык ненадзейнай СМА з канцоунай крьшіцай, адналінейньїх сістзм з адпачьшкамі і сістзм з неаднароднай уваходнай плынпю.

У дысертацьй атрыманы алгарытмы для разліку дакладпых і набліжаньїх значэнпяу сярздпяга часу зиаходжанпя патрабаваппяу у ненадзейнай СМА з канцоунай крьініцай і адвольпым размеркаваннем часу абслугоування.

Даследаваны шзраг сістзм з адпачьшкамі, для якіх атрыманы су-месныя стваральныя функцьіі стацыянарпага размеркавання колькасці заявак у сістзме і колькасці абслужаных пасля апошпяга адпачьшку па-трабаванняу, што дазваляюць вывучаць працзсьг спадання прадукцьш-насці сістзм на перыядах запятасці.

Вызначана структура аптымальнага разпязку задачы фільтрацьіі неаднароднай уваходнай пльїні у адпалінейнан сістзме масавага абслугоування, а таксама аптымальныя імавернасці допуску заявак у сістзму з адпачьшкамі.

Дастасаванне атрыманых вьшікау пры настройцы параметрау фун-кцыянавання рзальных сістзм дазволіць павьісіць іх зфектыунасць, за-бяспечыць найбольш рацыяпальнае выкарыстанне спажываных рзсур-сау.

РЕЗЮМЕ

Бабицкий Александр Владимирович

ИССЛЕДОВАНИЕ И ОПТИМИЗАЦИЯ СИСТЕМ ОБСЛУЖИВАНИЯ С ИЗМЕНЯЕМЫМ РЕЖИМОМ РАБОТЫ

Ключевые слова: система массового обслуживания, система с отдыхами, процесс обслуживания, стационарное распределение, фильтрация входного потока.

Объектами исследований диссертационной работы являются системы массового обслуживания с изменяемым режимом работы.

Цель работы заключается в получении аналитических зависимостей и построении эффективных вычислительных алгоритмов для расчета вероятностно-временных характеристик ненадежной СМО с конечным источником, однолинейных систем с отдыхами и систем с неоднородным входным потоком.

В диссертации получены алгоритмы для расчета точных и приближенных значений среднего времени пребывания требований в ненадежной системе с конечным источником и произвольным распределением времени обслуживания.

Исследован ряд систем с отдыхами, для которых получены совместные производящие функции стационарного распределения числа заявок в системе и числа обслуженных после последнего отдыха требований, которые позволяют изучать процессы убывания производительности систем на периодах занятости.

Определена структура оптимального решения задачи фильтрации неоднородного входного потока в однолинейной системе массового обслуживания, а также оптимальные вероятности допуска заявок в систему с отдыхами.

Применение полученных результатов при настройке параметров функционирования реальных систем позволит повысить их эффективность, обеспечит наиболее рациональное использование потребляемых ресурсов.

SUMMARY

Babitski Aliaksandr

INVESTIGATION AND OPTIMIZATION OF QUEUEING SYSTEMS WITH MODIFIABLE REGIME OF WORK

Keywords: queueing system, vacation model, service process, stationary distribution, input flow filtration.

The objects of the thesis research are queueing systems with modifiable regime of work.

The aim of the paper is obtaining of analytical dependencies and construction of effective calculating algorithms for computing of stochastic and temporal characteristics of an unreliable queue with finite source, single server vacation models and systems with heterogeneous input flow.

Algorithms for computing of the exact and approximate values of the mean sojourn time in the unreliable queue with finite source and arbitrary service time distribution are obtained in the paper.

A sequence of vacation models is investigated. Joint generating functions of stationary distributions of the number of customers in the system and the number of customers served after the last vacation time are derived. They allow to study processes of system performance decrease at busy periods.

The structure of the optimal solution of an heterogeneous input flow filtration problem in a single server queue and the optimal probabilities of arriving customer admittance to a vacation model are determined.

The application of the achieved results in the tuning of working parameters of real systems allows to increase their effectiveness, offers the most rational utilization of consuming resources.