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

Pf 6 О М1Н1СТЕРСТЭО ОСВ1ТИ УКРА11Й

2 1 J!'P |ЗС]^1ВСЬШ 1НСТИТУТ iHJEHEPiB ЦИВШЮ! ABiAIlit

На права* рукопису КОБА Олена В1ктор1вна

АНАЛ1ТИЧН1 t СТАТИСТИЧН! МОДШ СИСТЕМ ОБСЛУГОВУВАННЯ ПОТОК1В МНОШШИХ ЗАЯВОК

Спеи1алья1сть 0S.13.01 -Управл1яяя в te.cHl4HHX системах

А ВТ О РЕФЕРАТ дисертацП на здобуття вченого стуйеня кандидата техя!чних наук

Ки1в 1994

Робота виконана в Ки1вському 1нститут1 1.н*енер*в цив1льао1 ав!ацИ.

Науковий Kepiвник - доктор тедйчних наук, професор Дем'янчух B. C.

. Науковий консультант - академ!к АН Укра1ни,

доктор ф1зико-иатеыатичншс наук, доктор техн!чник наук, професор Коваленко I.U.

0ф1ц1йв1 оповевти - доктор техн1чних наук, професор Кудиненко A. B. - доктор техн!чних наук, професор Креденцер Б. П.

Ведуча оргав!зад1я: 1нститут програмних систем АН Укра1ни.

Захист в1дбудеться 'б® року о//-7годин!

на еас1данн1 слец1ал1зовано1 ради К 072.04.02 при Швськоку 1нотитут1 1нжечер1в цив1льно1 asiaiül.

Адреса: 252058, Ки1в-58, пр.Космонавта Комарова,!, ШЦА-

3 дисертац1ею uozhi ознайоыитися в ditaioteui Kl1ДА.

Автореферат роз1сланий МУИС'^ 1994 року.

Вчений секретар

опец1ал!зовано1 ради

кандидат техн1чних наук

Баскакова А.Г.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальность теми. Одн1ев з важливих характеристик техн1чних . систек обслутовування 1, . эокрема, автоматазованих систем управл1ння пов1тряним рухом (АС УПР) с 1х пропускяа спроможн1сть. В иив1льн1й ав!ац11 п!д пропускнои спромсшйстс прийнято розумIти максимально можлнв! 1нтенсивност1 поток1в пов1тряних суден при яких забезпечувться норматив«! вимоги до ■ безпекя польот!в. В найпрост!ш!й постансзц! задача про пропуски'/ спромога1сть система, формулюеться як дежа задача теорП масового обслуговувакня (ТМОЗ. Пзт1к об'сктхв, да ойслугсвувться, схематизуеться як пот ¡.к однор1дних под!Я. Шганачагться так1 рсновн1' понягтя як канал обслуговування, час обслуговування як вгаадкова величина, критер1й якост! обслуговування (допустимая час чеканкя, допустима Имов1рн1сть втрати заяви 1 т.ш) 1 знаходиться ,зв'язск м!х параметрами системи 1 значениям критер^*, в. залежност1 в1д 1нтенсивиост1 "отоку.

'г Проте у випадку УПР ковяа закзка, в протилеипсть класччни* ТМО, мае счладний характер, оск!льки складаеться з окремих частик, ког!а з яких йотребус е1дпов1дяого о<5сл:гговування. Тпка . мнотакн1сть обслуговування заявки характерна - для процес1в обслуговування в системах УПР за рахунск уриваностг знятгя . ДнформацИ з Л1так1в. В1дом1 результата ТШ, в даному

' випадку, недостатньо в1добрзжатъ реальн! пронеси I ещшм методом досл1д*енвя под1бнях систем е метод статистичного юделвваяяя. Але пронес моделсеання тако! системи набагато -складн1ший, н1ж у випадку сдиночних заявок. Тому вкникае задача заи!ни система з! складники заявками екв1валентноп в розум1ня! того чи 1неого критер1я системоо одиночних заявок. У випадку, коли екв1валонтна за«1на неможлчва виникае необх!дн1сть в розробц! зручного матенатичнега ймов1рносного апарату описания I анал!зу систем касового обслуговування (СКО) з множинними заявками,': а такс* пошук мохливога спрацення формул I статистичних моделей для характеристик якост! обслугову! ання" при пор!внлйо калих Сар Характерно для процес!в в УПР) йков1рностяк пярекритгя 1кпупьс1в.'

Пета робот и. Розробка математичного принципу описг чня СМО з мнонинними заявками, а також метод¿в 1х статиотичного моделрвання для- п1двищення ефективност1 оцДнок пропускно! спроможноеп систем 1 засосЯв управляя пов1тряним рухом - на етапах 1х розробки 1 фуныионування. Наукова новизна робота полягае в настушюму: .

- розроблено комллексниЯ п1дх1д до розв'язання задач одХнгси пропускно! спроможност1 систем 1 засоб1в УПР на основ1 математичного принципу описания систем з множинкими заявками;

- розроблено метсди !> статистичного моделсвання;

- знайдено достатн1 умови заьини СМО а вхх.цниы потоком мноасинних заявок сЛльш простою СМО з вх^дним потоком одиночних заявок;

- формал1зовано величину втрати заявц! внаслхдок перекр>птя 1 скопления заявок в систем!;

- виьэдено верхнс 1 нимш оц!нки ьеличини втрати, розв'язано . практичн1 приклади, як1 демонстоують тсчнхсть цих оцхнок;

- виведено формул» для характеристики СМО з здвоеними заявками, з'ясовано умовь эргодячност! цих слстем;

- проведено статистичний експеримент з аналХтичнов перев!ркос результатов (виведених автором) для Система з здвоеними заявками;

- розроблено сташс-.'ичну модель СМО з мнохиннимк заявками х жорстким плануванням часу виконання операнд й.

Практична цхннХсть робота . прлягаа; в використанн1 - отриманих . автором результат^ у вигляд1 анал1тичних 1 статистг-них моделей, алгоритмов х програм в дослхджекнях по створенк- 1 . эастосуванню сизтем з мнокинними ¡заявками. Под1бн1 могелх характерн! для систем 1 засосПв УПР. В робот! • •- вигвлено ыазшив1сть значного спроцення прсиесу могешэвання СМО з мяожинними заявками у влпадку, коли зале»псть функдП втрати В1Д попередн1Х заявок дхе тхльки на 1нтервал1 часу не б1льшим за величину т;

- дано схематизацхо множиннох заявки, СМО з потоками псдЮних заявок, фуккцП втрати, що доз во л яе ыодеяивати багато систем за допоыогсю одного 1 того ж алгоритму 1 ройити оц1нки покааникхв 1х ефективност1; .

- для СМО з здвоеними заявками виведено формул» для сэреднього часу чекання операц1й;

я

- для деяких характеристик !мпупьсных потсяив виведен! форыули 1 нер!вност! для середньс! втрати, зв'язано! э перекриттям !мпульс!в, що моке бути ввкористано в практичних розрахунках пропускно! спромогяост! системи;

- розроблено алгоритм прискореного моделювання (без моделювання потоку) для оц1нки пропускно! спроможност^системи;

- розроблено алгоритм« 1 програми для систем з здвозними заявками I систем эг жорстким плануванням часу обслуговування;

- виведено оц!нки максимально! роз«1рност1 масив!в при моделвванн! систем з здвоеними заявками, до суттево при написанн1 I використанн! моделюючо! програми,

Методи досл!даень. Основн! результати робота ' отриман! з використанням теорН йков1рностей, теорП масового обслуговування, статистичного моделювання, теорИ !»дульсних поток!в, теорП мнохин. Для : демонстрацП 1 перев!рки ефективност! 1 практичност! отриманих теоретичных результат1в використовувалось числове моделювання.

АггроЗац1я робота• Основн! результати робота допов1 дались автором в 8-ми допов!дях на 6-ти науково-техн1чних конференц1ях 1 сем шарах.

Публ!к-щ11. По тем! дисертацП опубликовано 22 друксван! робота. Структура 1 оо'ек робота. Робота складаеться з вступу, п'яти роздШв, заключения, списку л!тератури С123 найменування) та двох додатк!в. Зм!ст робота викладено на 159 стор!нках машинописного тексту, вм!туе 20 рисунк!в, 2 таблиц, 8 схем.

ЗМ1СТ РОБОТИ V.: ■

У вступ! обгрунтовано актуальн!сть проблема, що розглядаеться, викладено яаукову новизну 1 практкчну ц!нн!сть отриманих резуяьтат!в, наведено короткий зм1ст дисертацП.

В першому роздШ розроблено математичну модель; по\ок!в з множинники заявками, яка основана- на закон! Пуассона для момент1Б . початку труп заявок 1. складному характер! 1ндив1дуально1 групи. Залропоновано такох зручний як для виводу формул, так 1 для статистичного моделювання ссос!б залданяя

ймоь1рносного закону 1ндив1 дуально! мнокинно! заявки розпод!лои числа * необхшшх операц1й, а також 1ит<эрвал!в С в яках

иоашиве ьиконання сперац!й.

Приведено алгоритм моделюваняя потоку заявок для роз1мкнено1 системи, розройлений автором. Припустимо, ио ЛСи=Лг(1)(Х,и ~ дв!ч1 реперервно диференцайована функць.. Ойчислимо значения И пох!дно! в точках 1п+кЬ/2, де надходхення п-о! заявки, Ь>О -пост1йкий крок, к=1,2,..., ! по формул! Шмпсона, використовуючи парабол гчну Стерло ляд;, б в кожному интервал! ип+кЬДп+Ск+1)Ь) по крайн1х 1 середнгй точкам, ойчислюемо значения тнтегралу

Лпк=/ХСШ1,

п

А саме,

Л =0; Л =Л . + ■+Ск-1)К)+и(1 .+Ск4)М*ла +кМ). пм п^ п,к-» О п п с п

Эазделегиь реал1зуемо за ялюмогоо давача виадкових айо

псевдовипадкових чисел деяк! ь>п з показниковим розпод1лом:

Р{оп>х>=е"*, х>0. ,

Для кожного к, починаючи з к-1, перев1ряеыо нер1вн1сть

Лпк>ол. Припустимо, що впершв вона рэал1зувалаоь для к, тойто

Л . £ы , Л . >ы . Тод1 визначаемо I за допоиогов л1н1йно!

1нтериоляцП: .■.',,•.•■

В наведених формулах формально 1о приймаеться як моые-лт початку пронесу, хача як иомент заявки 1о не враховуеться.

У другому роздШ даеться анал1тико-статистичза оценка ймов1рностей та середн1х значень, пов'язаних з перер!зом випэдкови* складшсс ыножиь (заявок). <

Головна задача роядхлу формулветься таким чином. Нехай маемо пуассон!бський пот!к одноргдних под!й-заявок. 3 кожнов заявкой виникае випадкова ыножина !мпульс1в. Мной ни !шульс!в р!зних заявок незалехн1. Можлив! 1Нфорка1ийН1 зтрати внасл!док перекриття заявок формал1зувться поняттям втрати Г, то вводиться в робот!. Втрата данхй заявц!, - в загальному зипадку, випадкова величина, що залехить в1д к1лькостГ 1кших заявок, що перетинасться з нес, 1 параметр!в 1х взаемного роамщення.

... ' ? .. НесхЗх1дна знайте , математичнв спод1вання величини втрати в

розрахунку на одну заявку.

Для розв'язання поставлено! задач! запропоновано алгоритми

статистичного коделованяя, як! основан! на розро<5леному автором

алгоритм! протяюси одн!е! множини через !ншу 1 автоматазацП

. розрахунку лебегово! м!ри мяохинй зсув!в, при яких мае м!сце

перер!з.

Нехай задано дв! числов1 множини 4 У1 = иСа( ,Ь4) !

V ^Й(о|с/1|е>, дв 0=а 0=с, <св<... <е!м, и.ц -

натуральн1 чи ла.

"1ктервалон пврвр!эу" кножин и ! V назвемо мнохпву тих чисел т будЬ-.ткого знаку, для яких множина и маг хоча <5 одну точку

перетяну э мнЙжпоп У+т=Д(с +т,с1 +т).

Алгорртк.отчисления н!ри, Тцу, 1нтервалу перер!зу С1.п.) полягае .8 нгступному. Позначно

'^.п.^у, Д у С гСа^З л Сс^+т.^+т) * 0 > СП роэглянеыо йудь-як! "задан! I та. к. Визначмю г, для яккх (а1,Ь4>пСвк+т,dj.fr) * 0» йавменш© значения т - те, при якому (с^-и-.^+т) пряцикае до Са1 ) эл!ва, най<3!льше - коли справа. Тод! иасмо с!|сжт»а1та с^+г»^. Таким чином г мае входити до !нтервалу *1к»Са)(-<1к,Ь(-ск); Довжина такого !нтервалу для т: • ^»(Ц-а^+Сс^-с,.). , (2)

Сумувчи С2) то Bci.ii 1 1 к, отрицаемо: • . . "

Тцу^Е^-а,)^ ^С^-с^. ' (3)

Яхщ,о лебегову ы!ру множини А псаначити |А|, то (3) мо^на переписатя так

(4)

Пот1и пропонуетьел алгоритм точного' отчисления Тцу.. Покладемо т^^т^вЬ,^ск; Розглянемо* '• множину

® !У,.|Д *ти:,т1к'>- Впорядкуемо ц! числа, перепозначими !х <хв1 .. . СОчевидно, х( - це якесь г1к, якесь т^).

Ягаю к^т^), покладею якао то Тод!

3

Tuv« T'cx *x )sgnC f> ). C5)

Js« 1 l:i ;

В практичних випадках часто вахливо знати uipy Интервалу nepepiay двох множин, коли початок и-1ипульсу попадав всередину„ У-1мпульс1в (Т0/у) i навпаки (Ту/Ц). У podoTi наводиться алгоритм oiuhkii Т0/у i TV/U> а к1нцевий результат мае вигляд:

W»V|. WmIUI. . (6)

Дано також алгоритм оц1нки м!ри 1 де Т,'^-

м!ра множини таких т, при яких хоча d для одвШ пари (i,lc) початок 1-го и-1мпульсу попадав ado на k-ий У-1мпульс, ado на в!дстань, ыеншу за L, зл1ва в1д нього на oci часу (.Т^-визначаеться вгдпоб1днЙ. Приймавчи практичну умову: dJc+A<clcii, отримано оцХнки

Т^<»С |V|+(d>. С7)

Пхсля визначення м!ри шюжини зсув1в можна ставити i

розв*язувати задачу про й»")В1рн1сть перекриття складних

випадкових множин. Розглянемо пуассон1ьський пот!к заявок з

параметром V. 3 кожною заявкою асоц1веться випадкова множина v

U^IKaj,^), де Ofat<bt<aa<...<by. Тут величина v.&l внпадков!: вони виэначавться загальнов еленентаряов под1ею ы € П, де fi - арост1р елементарних под!й. Елеиент и реал!зуеться по ulpi PC А) на деяк!й ст-глгебр! под!Я F. Ппотетичио завахавчу

заявку поаначимо V=fcCj Cck .dfc), де V випадкова Шохина. Ставиться задача про стинку амов!рностей: q=quv. 4=qu/v. Ч=ЧУ/и*

, де quy- >мрв1рн1сть перекриття хочь d рдного 1Иипульзу э одним \Нмпульсом; qU/y- 1мов1рн1сть початку хоча d одного и-1мпульсу п1д час V-iunynbcy; qV/U- iuobipuicTb початку хоча с одного У-1ыпуль;ау п!д час и-Шульсу; —. те саме,

що i qU/V (qV/u3. але з врахуванням продолжения на час Д.

В работ! отримано так! оц1нки: ■>

quv<XWTuv; ^и/,у£Ши/у; Чу/и=ХИГу/(;; q^SXffl^; Чу/и^^у/и1

Пот1м в роздШ викладено розв'язання задач! про знаходження верхньо! та нижньо! оц1нки ыатематичного спод!вання ве/жчини втрати. Позначимо

i=ftu.<vi>3 С 8)

6

випадкову величину втратй заявц1 з множиноп и, оо визначаеться сукупноп д1со вс!х множил , ио перерхзаються з II; Г*<в -максямальне можливе значения вхрати. В роздШ наведено алгоритм визначення оц!нки (8), який основано на алгоритм! протяжки одн!е! множини через !ншу ! визначенн! м1ри множини зсув!в (5). Инаевий результат таквй: /

М?< ХЯ.бт ♦ Г\«МСТ Т ,), С9)

<т:итЬт>*0> «V т

Для визначення точност! (9) виводиться нижня оц!нка М?. II вив!д грунтуеться на властивостях потоку Пуассона про функц!п роэпод1лу. часу м1ж моментами, заявок I властивост1 монотонност1 фуняЦоналу Г, А саме, прилускаеться, до. кожна . нова заявка, то завахав дан!й заяви!, мохе лише зб!льшити величину втрати. Нижня оц1яка мае вигляд '

' М?> \ Ш еА1т'гг(1т - Г*\4МСТиуТиу.) (10)

.-00

Таким чином, (9) 1 (10) оц!ншггь М* з двох стор!н, ко дозволяв судити про точн1сть оц!нкл. ,

У цьому х роздШ, гасгосовуючи розроблену. методику, розроблена модел! функц!оцування систем ! засоб!в УПР. Проведено чнслове модешоваяня.

У третьему рсздШ виявяено можлив!сть знатного спрощення процесу моделпвакня СМО з кноюяними заявками у випадку, коля залежн!сть функцИ втрати в!д попередн1х заявок д!е т1льки иа !нтерпал! часу, не большим за величину т. "У цьому випадку можлива зам!на систем» з складними заявками екв!валентнор скстемоо одиночках заявок.

На початку розд!лу давться означения ■ систем з т-обмеженоо п1сляд!ес. Нехай маемо СМО, яка характеризуется процесом УШ як оператором в1д в::!дного потоку- ХСЬЗ. Позначмо Ь закон . розпод!лу випадкового процесу НСО при задашй траекторИ процесу ХШ. . . •'. .; •■■■

Означения.. СМО назвемо системой я т-обме*еною шепяд^ю. якио для будь'Яких траектор1й. Х( Ш 1 ХаШ процесу УС13. як! сл!впадають при ^-т^ЬЗЦ, пае м!сце р!вн1оть Ц {N1=1^ ИЛ

для ск1нченновим1рних розподШв, щ> в!дносяться до значеНь процесу УШ на'э!др!зку-1о£1£Ц.

IfoTiu р-озгдядашъся СМО ? неск!нченним числом кш 1л1в, як! обслутовують пуассон!вський пот!к незв'даних !ыпульс!в. А саме, noTiK кодуеться пссл1довн1стю Ctn,jji), де tn~ момент надходження п-,01 заявки (початок n-го импульсу) , ч - довжина n-го !мпульсу (час обслуговування п-о! заявки). Для тако! система формулюеться 1 доводиться

Теорема 1. Нехай т;п2т з iuoBipHicTC одиниця. Тод! дана СМО е системой з т-обмеженои niauwUec.

Дал! ставиться i роэв'язуется основна задача розд1лу. . Нехай маемо noTiK незв'язних шохикних !мпульс1в. Для нього W(t3 мае якяйсь розпод!л LCWCL)]. Чи можна п!д!брати екь!валентний пот!к одиночних !мпульс!в, при якому L(W(t)l залишаеться не^м!нник?

Для ■ розв'язання поставлено! задач! визначаються ск!нченновим1рн! розпод!ли Импульсного потоку i вводиться поняття т-екв!валентних лоток1в. ..

Означения. Два !мпульсних потоки, ск!нченновим!рн! розпод!ли яких сп!впадають на !нгервалах довхини, меншо! ado р!вно! т, назвемо т-еквАйалвнтними.

Задача, поставлена вице, розз'язуеться за допомогос сформульованоХ. i доведено! автором тэореми про т-екз!валентн1сть потоку множинних 1мпульсав та потоку одиночних ,1Ш1уЛЬС1в.

Теорема 2. Нехай X - пуассонИвський з параметром X стац!онарний поИк множинних илульс!в. В кожному множинному iMnyjibci - щшадкова KinbKiCTb v одиночних !мЬульс!в 3i ск!нченним математичним спод!ванням v. ' Одиночн! !мпул?.ги починавться через !нтервали, (Ялым за т+т[, а час аснуванкя. кожного одиночного Импульсу 5т(.

Прм даних умовах .:oTiK X т-ёкв!валентний пуассон!вському потоку з параметром ХО одиночних iMnynbcib.; Функц!я . розпод!лу BCD пов'язана з характеристиками потоку ,X формулою:

де р^- iMOBipiiicTb даного значения v; B^Ct) - функад розпод!лу

довхини k-го одиночного iunynbcy в множинному iMnynbCi, що складаеться зу одиночних iMnynbciв.

В четвертому розд!л! розглянуто система 3i здвоениьш заявками. . :

■Л Футсц!онуваяня система описуеться таким чином. В одноканальну СМО надходить пуассон!вський я параметром Л noTiK заявок. Кожна .заявка потребуе двх операцП обсяугову^ання постiДно! тривалост1 т, але друга операЩя може початися нечран1ше^ His закончиться перша i не ран!ше, н1ж через час т+Д п1сля надходження заявки. Як т1льки заявка надШла, диспетчер планув час як для першо!, так 1 для друго! операцП, виходячи з вищезазначено! умови. Подр1<5нення виконаняя операций заборонено

При досл1дненн1- система було визначено умову ергодичност1, фуныЦп розпод!лу часу чекання здвоено! заявки, середн!й час чекання першо! i друго! операцП. Було проведено статистичне моделввання функи!онування системи.

Умова ергодячност! визначаеться сформульованими i доведенный автором теоремами.

Теорема 3. При 2Х.т£1 сумарний час чекання w^'+w^"' першо! i друго! onepaui.I. n-o! заявки прямуе до неск1нченкост1 за flMOBipHiCTB при п •» ю.

Теорема 4. При 2Хт<1 випадксвай гектор (чгп1,уИп>) мае ергодичний розпод1л.

Доведения осЗох теорем проводиться за iiqyKuieD за допомогою паралельного розгляду вищезазначено! системи i системи M|D|1 з пуассон1вським Tie! ж 1нтэксивност1 . потоком L часом обслуговування 2т.

Шсля з'ясуваяня уыови ергодивдоеп можна ставити питания про знаходженяя функц!! розшШлу часу чекання для першо! i другЯ операцП здвбено! зтявки. Розглянемо випадок ДСт.

Ана^Хз розпод^лу часу ' чекання заявки в!вся за доломогоо виртуального часу чекання Сметод,' розроблений Такачем) Нехай FCD - функцia розподхлу в!ртуального часу чекання системи. Тод! автор ьиводить р!вняння:

F'Cz)-mz>+F(z-2T)=0 при 2>2т+Д, ' СШ

F'Cz)-XF(z)=0 при 0<г<2т+Д. С1ЕЗ

Розв'язусчи (12), маемо ТСг)=С1-2т\)еХи~Ь при Oizia+Д. Tosi cep3/;nifl час чекання здвоено! заявки:-

а - jli3^- + Д - С1-е"ХД) С133

У випадку Д=0 С13) перетворсеться у в ¿дому формулу Хигшна.

Для функцП роэпод!лу часу чекання першо! F,Cx) 1 другоГ

С14) ' (15)

1 C15),.

С16) (17)

У випадку Д>т було застосовано статистичяе моделввання. Алгоритм моделввання складний, але по сво!й сут1 побудований на двох процедурах: розмщення i злиття. Процедура розм1«дення виэначае момент розм1ценкя операцП в!дносно вхе Юнуочих заЯнятих 1нтервал1в,а процедура злиття зливае фактично еайнят! !нтервали Mix якими в1льн1 1нтервали менш1, н1х т.

Дтя резервування пам'ят! виведено оц1нку розм1рност1 масив!в

at ,аа>..: ,at; bt .b^.... ,b1( де (^.b^, 1^1.....1 - 1нтервали

зайнятост!. При цьому l=d, коли 1 - к1льк!сть 1нтервая1в зайнятост! i момент надходження заявки, l=d+, l*d4\ коли J -KUibKicTb iHTepBaniB зайшггос.-т! в момент зак!нчення першо! 1 друго! операцП в!дповлдно.'. Оц!нка мае вигллд;

} 5 Уг]+г- {18)

Як показник ефективност! сястеми визначався чао чекання першо! i друго! операцП.

При Д^г була'досл!джена залежн1сть середнього часу чеканил першо; j ,друго! onepauil в!д величини: зазору i iнтенсивност! вх!дного потоку. Для кожного Х=0.1; 0.2; 0.3; 0.4 1 кожного Л в1д 1 до 20 з кроком 0.2 було проведено 10 реал!зац1й по 1000 заявок в KosHifl. Эагальна тендешЦя отриманих залегностей така. До моменту Д=т час чекання першо! onepauil зростае, друго!.-залишаеться практично постШним. Шелл моменту Д=т р1зко зменшуеться час чекання як першо!, так i друго! onepauil. Пот!м для першо! операцП час чекання починае зростати, для друго! г спадати, кожний пов!пьно прямуючи до свое! практично постШо! величини.

Fa(x) операцП можемо записати '

F (z)*P(wi <z>=F(z), Fa(z)=P{wa<z)*P(w<2+A>«F(z+A)

при z>0.'

ToaicepeHHifl час чекання, на основ! формул (14)

дор1внпе

* ^ * гяк * л -

00 .' •:■■ - Г

Mvfa= J(x-A)dF(x)

*

У випадку Д<т те* було проведено .'статистичне ысделювання, але по б!льт простону алгоритму.' При пор!внящЦ . анал!тичния результат!в (16), С17) ! результат!в <угатисткчного моделввання в!дносна похкбка робота программ не иёныа 1.12'/. 1 не бЬ-.ьша .4.675« .

В остаяньому параграф! розд!лу проанал!зоваво розпод1л в1ртуального часу чекавня здвоено! заявки.

Для функц!й Г(2кт+Д+х)=Г.(х) розглядаимо и(2,х)=> 2кГ.(х),

. к=о

|г|<1, 1 выводимо формулу

-г)

„ Ц(2,Х) = С<х<2т. (19)

1-ге ' н

Розкладавчи (19) по степенях г, отримаемо Рк(х) як коефШент

при гк: Рз(х)=(1-р)еХ1', Г1(х)-(1-р)еьСеР-Хх1,

ГаСх) = (1-р)ех*(еаРр-^еР + ^ ), ! т.д.

Тут всвди 0<х<2т. Або, роблячи зсув аргументу, маемо;

Р(х)=а-р)ех<х-л\ 0<х<гт+д,

Е(х)=(1-р)ех<х-,т-А>(ер-Х.Сх-2г-Д)), 2т+Д<х£4т*Д, (20)

Г(х)=(1-р)еХ(г-«т-Д)(егР-еРр-Х(х-4т-Д)еР+ £££^¿1").

4т+Д<х^6т+Д,

1 т.д.

У п'ятому розд!«! дослгдкувться система касс е. ого обсиуговування жорсткого планування з мнохинними яаявкаии методом статистичного моделввання.

Постановка задач! така. На обслугов/вчий канал надходить пуассон!вський пот1к заявок з параметром X. Копна заявка ыас пройти к операнШ обслугавуваяия на одйом;.' а току к канал 1. Час, необх!днмй для к-оГоперЗцП .¡-о! заявки, по.значимо -7 Вважьемо, що вс! т) незалежн! ■ в^падков! величини з функц!еь розпод!лу Bl£(t). В1д моменту нгаходження заявки як в1д початку в!дл!ку розглядаеться !ггервал, в якому мотаиве виконання к-оГ

11

операцП j-ol заявки, позначимо floro (tJ)c ,tJk). В загальному

випадку ц! 1нтервали(иожуть перекриватися нчв1ть при одному I тому х j, але tJk£tí Задаетьея . сум!сна функц!я

розпод!лу ССЦ ,t",... ,te,t¿) випадкового вектора

' н * • п

Ct.t,.....tx.t,).

Приймасться обмеження, як! назван! . умовою жорсткого планування. В момент над^оджекня j-ol заявки в!дом! '-"4jk»tjk.t^t. ■ l<k<*, i час обслуговуваяня кожно! . операцП плануеться таким чином, то використовуеться т!льки Ti 1нтервали часу, як! в!льн! в!д обслуговування J-1-o! i б1лыд ранн!х заявок. Перша операц!я з^ймае крайне лхве положения на oci часу з врахуванвям1 обчеженвя ,tj'fc3, друга - саке л!ве положения з врахуваннян обмеження

Сt-, . ■ ,t" . ' ), але т1лыси п!сля зак!нчення (ado переривання

• J t К J 9 К .

через нестачу часу) першо! операцП 1 т.д. Допускаеться под!л часу викснання операцП. ' .

Задача полягае в визначенн! • стац!онарьтге показник1в ефективност! система масового обслуговування, а саме:

1мов1рн1сть неповного виконания k-оГ oiiepanll випадково вибрано! заявки;

qo - !мов1рн!сть неповного вяконання випадково вибрано!

■ операцП; . ■. qjftp - iMObipHlCTb того. ííí.0 по випадково. вибран!й заяви! Йуде не

noBiiici'o вяконано' т або (Лльше операц1й; V - середн!й сумарний час лершЗуваннявсистем! одь!е! заявки; q¿k'- при заданому с С0<£<1) , 1мов!рн!сть того , до з аотр!бного " часу j)jk обслуговуванняк-о! операиН-випадково! заявки буде загублено хоча б £T]Jk часу; qe - !мов!рн!сть того, до сумарнийступ1нь недообслуговування

випадково вибрано! заявки будв не менше XOOet; 5 - cepesHl витрати часу по операциях випадково вябрано! заявки,

не враховусчи факти<!)кого часу обслуговуванЕя: рв - !мов!рн!сть в1льного стану СМО.

Нэгвемо в1льяии станом системи тахий стан, коли вс! заявки, до pwiue над!йшли, вже отлужен!. .

Перходом зайяятост! системи назвемо !нтервал в!д моменту

виходу эв1льного стану до моменту повзрнення в нього.

Час, зайнятий на попереднГ, все ще не обслужен! заявки до ¡юменту надходження дано! заявки, назврмо зайнятим 1нгервапсм. Визначимо величани, но характеризуЬть поточний стан СМО: - число зайнятих !нтервал!в часу в момент надходження 301 заявки в межах даного пер1оду зайнлтост1; Ст^.т^'р - к-ий зайнятий Интервал, в!драхований з моменту надходження .¡~о1 заявки; 6*~- те саме, що ! (т^.т^З, але П1сля видиення часу га обслуговування ^о! заявки.

Ведемо ще величина; Т1 - довжина 1-го периоду зайнятост!; >1 - число заявок, що над1йшли л!д час 1-го пер!оду заяйнятосП, В робот! викгадено алгоритм посл!довно!,реал1зац11 пер!од1а (айнятост!. За допомогов цього алгоритму, кр!м Т1 та м , (бчислпвться так! величини:

>1'*>- число заявок 1-го пер!оду зайнятост!,ш кожн!й з ' яко[

к-та операц!я не виконана повн!ств;. I - загальне чзсло не повн!ста викснаних операций по заявкам

!-го пер!оду зайнятост!; I загальне число заявок 1-го периоду зайнятост!, по кожн!й

з яких не повн1Ств виконано и ! б!льше операнд^; ' - загальний час перебування в систем! за.гвок 1-го перюду зайнятост!;

¡к£. - число заявок 1-го переду зайнятост! по хожн1й з яких

к-та операц!я не виконана коча б на ЮОс!«; 1 £ - число заявок 1-го пер!оду зайнятост!, по яких сумарне

недовиконання операиН складае не мечте ЮОсЯ; i - сумарШ н<,;виройнич1 витрати часу по заявках 1-го перюду зайнятост!.

Реал!зувчи И пер 1 од 1 в зайнятост!, СШЗО, з егенеративност: процесу, ао моделюеться, могна отримати так!

С1ЦНКИ:

I =» 1 => 1т 1=1

»* $V 5 V р0 * 5 V-'

£ I =1 * 1=1 * I :

Для описания пронесу nocniдовного плануваяня .обслуговування заявок на одному пер!од! заяйнятост! було розроблено алгоритм моделпвання поточного стану систеии, виведено початков! умови моделювання, розрахунков1 формули для переходу в!д m-1-oi операцП до ш-о! операцН, умови недовиконання onepauift. Тут хе змодельовано прийняття р1шення"про к1льк1сть заявок на пер!од! зайнятост! ! тз.ччет тривал!сть пер1оду аайлятост!.. В заключенн! наведено основн! результата робота. . Додатки м1стять в соб! документа, як! п!дтверджують практичне використання розроблених методик, алгоритмЦ ! програм, а такох текста програм.

' ОСНОВЫ! РЕЗУЛЬТАТИ РОБОТИ

Практика доел!дхень в галуз! ефективност! АС УПР, в тому числ! автора дисертац!!, показала, що Bi'OMi результата теорП масового обслуговування часто грубо в1добрахуе реальн! процеси, що досл1дху'оться, i единим методом розрахунку ефективност! системи масового обслуговування тако! складно! природа е метод ", статистичного моделвпвання. Проте гром1здк1сть. а)ггоритм1в, до ыоделспться, безкантрольнЮть точност!, можлив1сть методичних помилок в програм! часто роблять моделпвання неефективним.. Все це характерно для моделювання процес!в УПР. • ; . В дан!й робот!

- розроблено приндипи коделсвакня поток!в з мнохинними заявками; -розроблено принципи зведения класу задач ефективност! !нформац1йних СМО до схема втратк, що зв'язана з перекриттям складяих випадкових заявок;; ■■..■■-"

- виведено точн! формули ! нер!вност! для розрахунку ! оц!нки середньо! втрати, що срокувть практичн! розрахунки;

- розроблено алгоритм прискореного статистичного моделвванкя (без моделювання вх!дного потоку) для оц1нкл показвик!в ефективност! сйстеми;

- виявлено uojjiHBicTb анал!ти'Шого обчиолення характеристик СМО з мядхинними заявками при деяких спроценнях;

- на осноь! т-залехного потоку досл!дхено мохлив!сть зам!ни СМО

з множинними заявками еквхвалентноп СМО з одиночними заявками;

- для СМО з здвоеними заявками виведено' форыули для середнього часу чеканил операдШ I функцП розпод|лу часу чекання заявкл, виведено також умову ергодичност1;

- розроблено 1 реал!зовано алгоритм статистичного моделсвакня системи з здвоеними заявками, обчислено показники ефективност!;

- досл!дж.енп питания точност1 oiUhok статистичного моделсвання для визначення практично! придатнос-Ti розроблених алгэритм1в;

- виведено оценку po3MipHocTi масив!в, якх використовувться при ыоделвванн1 системи з здвоеними иаявками;

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

OCHOBHi Э ДРУКОВАНИХ Р0Б1Т:

1. Коба Е.В. О моделировании некоторых систем обслуживания со сложными заявками //Кибернетика и системный анализ, Киев, . Институт кибернетики АН Украины, 1993, Н2.

2. Koba E.V. On the simulation of queueing systems with multiple calls // ДоловШ АН Укра1ни, Кигв, 19ЭЗ, H5.

3. Коба E.В. Оценка вероятности наложения сигналов бортовых ответчиков методом статистического моделирования // .Повышение эффективности автоматизированных систем управления, Киев, 1ШИГА, 1992..

4. Демьянчук B.C., Коба.Е.В. и др. Автоматизированные системы управления воздушным движечием. Оценка надежности радиоэлектронных средств АС УВД ь процессе испытания и эксплуатации // Отраслевой стандарт. Система стандартов на АС УВД, ОСТ 54 71006-Si, . МГА, 1987.

5. Де.'&янчук Б. С., Коба Е. В. Об оценке эффективности ыногопоэичионных радиопеленггционных систем управления воздушным движением. // Авиационные тренажеры i системы управленил воздушным движением, Киев, KliHTA, 1989.

6. Дймьянчук В. С.Коба Е. В. Анализ распределенных систем обработки информации в АС УВД. // Прикладные вопросы нздеиюсти аппаратурного и.программного обеспечения вычислительных систем,

Киев, КИНГА. 1985.

7. Демьянчук B.C., Коба E.B. Принципы построек'« автоматизированных систем управления воздушным движением в нижнем воздушном пространстве. // Тезисы докладов Всесоюзной научно-технической конференции "Статистические методы в теории передачи и, преобразования информационных сигналов", Киев, 1988.

8. Демьянчук B.C., Коба Е В. Анаяитико-статистическая модель прогнозирования эксплуатационных показателей радиоэлектронных средств и систем УВД. У/ Тезисы докладов Всесоюзной научно-технической конференции "Статистические методы в теории передачи и преобразования информационных сигналов", Киев, 1983.

9.. Коба Е.В. 0.влиянии законов распределения на характеристики обслуживания потоков воздушных судов в системах УВД. // Тезисы докладов Второй Всесоюзной конференции "Управление воздушным движением", Москва, 1983. ' . .

гидписано дс друку II.02.94. Формат 60x84/16. Hanip дрткарський, Офсетний друк. Ум.фарбов1дб.5.. Ум.друк.арк.0,93.0бл.-виц.арк.1,0 Тираж 90 прим. Щна Вид. » 40/Ш. Зам-вл.- 40-1

Вигавниигво КПЩ. л

252058, Кихв-58, проспект Космонавта .Комарова,!