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

р г Б ДД,

СЬКИИ УН1ВЕРСИТЕТ 1МЕЩ ТАРАСА ШЕВЧЕИНЛ

На правах рукопису

ДОЦЕНКО СврПй 1ванович 0ПТИМ13АИ1Я СИСТЕМ МАСОВОГО ОБСЛУГОВУВАННЯ 01.01.09 - математична к1бернетика

АВТОРЕФЕРАТ

дисэртацП на здобуття наукового ступеня кандидата ф1зико-матвматичних наук

Ки1в - 1994

Робота виконана в КМвському ун1верситет! 1мен1 Tapaci Шевченкв.

Науковий квр1вник« -доктор ф!зико-матвматичних наук, професор ЗАКУСИЛО O.K.

0ф1ц1йн1 опонентм« доктор ф1зико-математичних наук, профосор Карташов М.В.

кандидат ф1зико-математичних наук, доцент Майдаюок Р. Я.

Цров1дна установа« - 1нститут кЮернетики

1м. В. М. Глушкова АН Укра1ни

Захист в!дбудеться -]2&" Ълф&И^А 1994 р. о 14.00 hi зас!данн1 спвц1ал1зовано1 радиД' 068.18.16 при Ки1вськом; ун1верситет1 1мен1 Тараса Шевченка за адресов« 252127, м.Ки1в-127, проспект Академ1ка Глушкова, 6, факультет к1бернетики, ауд. 40.

3 дисертацЛею моана ознайомитися в 01бл1отец1 Ки1вського ун!верситету 1мен1 Тараса Шевченка.

Автореферат роэ1сланий •• J2?- 199V р.

Вчений секретар спвц1ал1эованоХ ради

Кузьм1н А.В.

ЗАГАЛЬНЛ ХАРАКТЕРИСТИКА Р030ТИ Актуальн!сть теми»-Сорэд р1зномин1тшк задач прикладно! матема-гики проблема досл1д>:юшгя систем масового обслуговування е одном з 1айб1льи валивших. Модел1 масового обслуговування вшмкають при эозвязанн! р!зних практачних задач. При цьоку поряд з проблемам, та! мають безпосеродне в!дношшя до обслуговування населения або эброки вантаж!в, проблема, як1, здавалося б, но мають в!даошешя до ласового обслуговування собробка рад!осигнал!в, дояк! б!олог!чн! зистеми, 1 т.д.) таксик моауть бута розглянут! за допомогою теорП ласосого обслуговувашш. Сород задач масового обслуговування экреме м1сцо пос1дають оптам1заЦ1йн!. Для кожно! тако! задач! зибирайться критерий оптим!зац1* та множима допусг.ашх розв-язк!в, ш як!й в!дшукуеться оптимальней за дашел критор!ем. Сл!д в!дзна-тата, що оптим!зац1я в б!льшост! вииадкХв проводиться не за раху-яок притягнення додаткових pocypcls, а за рахунок рацЮнальиого використання pecypciB, ио в у системах. Проблема оптим1зац!1 СМО розглядаеться внео протягом досить тривэлого часу. Найб1льш повний терсл!к poölT стосовно дано! тематики, який м1сгать дек!лька сот. иайменувань, був приводоний Т. Крвб1лом та Д. Магазином. В основу тершо! глави-покладено результата, що одержан! O.K. Закусило, цруго!- Л.Шраге та A.B. Макар!чевим ,тротьо1- Д.Джонсоном та Я.Клейнроком, додатку- Т. Ролек! та Д. ШтоЯяном.

Мета роботш досл1дження та оптим1зац!я широкого класу систем часового обслуговування за р!зними критер!ями.

Наукова новизна результат!в дисертацИ полягав у розгляд! якЮно нових постановок оптим!зац1йних задач для СМО.

Метода досл!дження. Математичним апаратом, що використовуеться в дисертацИ, в теор1я ймов!рноствй «зокрема теор1я випадкових процес1в), теор!я даференц1йншс р1внянь, элемента дискретно! математики.

Практична ц!нн!сть. В дисертацИ наведен! результата як1сного досл!даэння широкого Класу конкретних СМО. ' Кожна з розглянутих систем в математичною моделях) для деякоХ конкретно! реально !снуючо! система або водночас одразу дек1лькох систем. Б!льш того, завдяки ун!версальност! моделей, що розглядаються ц! модел! будуть корисн! при розв-язанн1 практачних оптим1зац!йних задач, як! будуть виникати вадал1.

. Апробац!я роботи. Рэзультата дисертацИ допов1дались 1 обгово-рголись аа таких конферешЦях та сем!нараХ| науковому сем!нар!

1нституту математики ЛК Укра1ки «н.к.-акад. Королкк В.В.,1994 р.>, .науковому сем!нар! кафедри прикладное статистики КиХвського . ун!верситету 1мен! Тараса Шэвчеккз <н.к.- проф. Ан!с!мов B.B., 19S3 р.>, десят!й схмов!Я вкол!-сем!нар! 'иАнал1з та застосування систем та мерек масового обслуговування" <н.к.-проф. Медведев Г.А., Б!лоруськкй двржун!верситат, м. М1нськ, 1994.), науковому сем!нар! !нституту К1бернетики АН Укради <м. Ки1в, 1994 р.>

ПубДхкацП. Основн! результата дасертацП опубл!кован1 у 3 роботах.

Структура та обсяг роботи. Дксертац!я обсяго.м 7в стор1кок складаеться з! вступу, класкф!кац!йно1 схеми, трьох глав, додатку та .списку л!тератури з 71 найменувань.

SMICT РОБОТИ

В дан!Й робот! розглядаються задач!, як! об-еднан! едшою метой - сптж1зац1я систем масового обслуговування. Для кожноЗ звдач! формулюоться критер1й оптим1зац!1, за яким знаходиться оптимольнкй. розь'язок на мноакн! допуеттаих розв'язк!в.Розгляну^ задач! в!др1зняються в1д б!льшост1 задач масового обслуговування там, ко еони не т!льки описуать ту чи 1шу систему <мох;е , знаходитись стац!онарний розпод!л черги, стацЮнарна ймов!рн1ст1 загублення вимоги I таке 1нше> , о й розглядають штання, щодо пол!шенйя ситеми за тш чи !ншм кр1тор1ем оменшекня довжини черги, змашення стацЮнарно! ймов!рност1 втрати вимоги, зб1ль-шення функц1оналу прибутку 1 таке 1нше>.

За основу класиф1кац!1 розглянутих задач масового обслу-говування взято класкф!кац!ю, запропоновану Т. Краб.'.лом та Д. Магазином та модиф!ковану автором. Запропонована класкф!кац1я но претеидуе на повноту 1 коже розширюватись як за рахунок виникнення ноеих. п!дклас1в у рамках !снуючих клас1в, так 1 за рахунок новиа клас!в, як1 не вкладаються у рамки дано! класиф!кац11. Кр1м того, означен1 класи та Шдкласи опткм!зац1йних задач можуи перетинатися, оск1льки одна задача ыожэ бути в!днесена до р1зша 1слас!в та п1дклас1в.

У ПЕРШ1И ГЛАВ1 дасертацП розглядаються системи, як1 зг!днс нсЕедено! в с Ii класиф!каа11 належать до статичних «або систек проектувягшя), оск1льки Ix оптим!зац!я полягав у знаходженн] оптимального порядку прилад1в або буфер1в перед приладами, оптямольнкх розподШв !нтенсивностей обслуговування м1ж прилада-ivc;, як! надал! кэ зм!нюються у процес! обслуговування.

1.Оптимальней розпод!л неоднор!дних обслуговуючих прклод1в у систем! з вп!дзпорядкоззнкм входом.

НохаЛ е багатоканальна система з окспокенцИ'йппя розпо-д!лгс,я час!в обслугозаштя капал!в з !ктонсизнссткми ОбСЛуГОВуВЭШМ <ц1 ,и2>.. ,цп>. Вимога, л;са подходить у систему, проглядаа вс! приладк у порядку, цо задасться деякою перестановкой та. надходшъ на обслуговування на портнй зпоИдезий гЛлыпм прилад. Якщо вс1 прклэди зайнят!, то вииога загубховться.

Зстаковлопо, що оптимальна перестановка, яка •■м1н1м1зуе" пот1к загублених втаог, визначзеться умоЕод спадання !нтонсивнос?ей обслуговування п?'ллад!в, цо розглядгються по черз!. Ваявляеться, ¡до такою перестановкою е розпод!л прилзд!в у порядку спадання 1нтенсивностей обслуговування. Ця перестановка стохаст;;чно м1н!м1зуе пот!к загублених вимог на мноазш! вс 1х мозлирих перестановок. 0шчз.:альн1сть за дапим критер!ем оз.чачав оптимальнЮть за багатьма !ншми критор!ями, але цей результат номокливо виразити к!льк!сно, тобто в!дпов!сти на загктакня,наск!лыш система,яка задасться оптимальною перестановкою, краще, н!а система, яка задаеться дежою Испою перестановкою за деяккм критер!ом. Розглянута задача, як 1 II узагальнення, як! будуть розглянут! падал!, належать до талу 1.

В с23 формулювтьоя задача, яка з узагальненням дано! у тому знамени!, цо часи обслуговування мають доз!льний розпод!л, та робиться висновок, що розпод!л прилад1в у порядку спаданння потужностей обслуговування <тобто у порядку спадання соредн!х час!в обслуговування» м1н1м1эув ймов1рн!сть втрати вимоги у стац!онарному режим!. Цв твврдаення справодливе для б!льшост! практичних задач ,але справедлива не завжди «мокна навести контрпршслад).

Одержано деяк! результата в!дносно розпод!лу прилад!в у багатоканальн!й гетерогенн!й систем!. Для ц!в! система: доведено таку теорему«

Теореиа 1.1. Якщо £к- стар!юча, £к+1- молод1юча,а слабо молод!юч1 випадков! воличини <або -новий г!ргае старого"», то пот!к загублених вимог системи, який породжувться перестановкою (1,...,п>, е стохастично вкладеним в пот1к загублених вимог, який породкуеться перестановкою и,..,к-»,к>1,к,к+2,..,п».

2. Безгосередн1м насл1дком задач! оптимального розпод1лу прилздЬ в багатоканалыПй гзтврогенн!й систем! з експ6нвнц!йнпма часами

обслуговувашм е задача про оптималыпй розпод!л Оуфер1в в багато-канвльн!й гомогенн!й <п¡о) систем! з експонец1Яними часами обслуговування, яка м1сткть в сс<51 к буфер1в, кожен з яких мозкпа встаковити перед одним з прилад!в,'ало перед комол/ приладом може бути встановлбно но б!льше одного буферу. Якщо вимога загублксться на I-му прилад! а<л>, то якщо прилад не мае буферу або буфер зайнятий ¿стою бимогою, Бона намагаеться нэд1йти на <1+1>-й прилад. Якцо вимога намагаеться надХйти на доякий прилад, який мае буфер, 1 в момент надходкення еимоги прилад зайнятий, але буфер в1лышй, вимога надходить у буфер, 1 знаходаться там, доки зак!нчкться обслуговування на в1дпов1дному прилад!, пХсля чого негайно зв!лыше буфер та надходить на обслуговування на цей прилад. Введено в!дношешш частшшого порядку на множил! вс!х моиливкх розпод!л!в буфер1в у систем1. Нехай (1 .. ,»к>п. 11<12<..<1к<п- вектор, який задав розпод!л буфер!в на в!дпов!д-шк позкЦях систем, до 11,..,1к- номери прилад!в, перед якими розсташован! буфери. Розпод!л <»{1 '> будемо називати

"61ЛЫЗИМ", н!ж (I,'21.....4к2))п

<1 позначати (1<1 . 1<2).--• як®0

11(1Ы1(2), .. дано! системи доведено такий результат»

Теорема 2.1. Для доз!льного вх!дного потоку б0, пот!я

загублегаос вимог б'система и'1 Ь буде стохвстично

вкладений в потХк загублених вимог системи а 1(2\.. ,1^г)>п,якщо ■>п2<*1{2).---л£г)>п. Таким чином, пот1к загублених вимог буде стохастично мШмальним при розпод1л1 буфер1в на останнлх к П03ИЦ1ЯХ (п-к+1,..,п)п, 0СК1ЛЬКИ р03п0д1л (п-к+1,..,п>п

-б1льше" вс!х 1нших зг!дно з визначенням.

3. Розглянуто багатоканальну марк!вську гетерогенну систему з необмеженою к1льк!стю м1сць в черз1, проведено пор1вняння двох <б|м|п |оо> систем та одержано дэяк! достатн! умови оптимальност1.

Теорема 3.1. Нехай в порш!й систем1 б^, а в друг!й кг при-лад!в. Для поршо! системи випишемо 1нтенсивност1 обслуговування лрилад!в у зростаючому порядку, а для друго!- в спадаону порядку!

(тут 1ндоксяц!я пов'язана з вп1дпорядкуванням прилад!в зг!дно э

1нтенс1гон1стю обслуговувоння 1 п!як но повязана з порядком розпод!лу прилад!в в системах <1>, <2> >. Нехай виконуються

нор1вност1| ц1(1)>|а|г) та 1'^ц}2' <»*> .Тод! для дов!льного

вх!даого потоку мае м!сце нер!вн!сть х1ч> йЧ<2 <ы, до озна-

чав к!льк1сть вимог в 1-й систем! в момент часу Касл!док 1. Якщо в деякХй готорогенн!й <о|п|со> систем! зробити -злиття" ,тобто зам!нити два або дек1лька ••сус!дп1х" прилад1в на один, !нтенсивн!сть обслуговуваштя якого дор!шгоз сум! 1нтенсивностей прилад'в, що замИпоються, то система -покращуеться" зг!дно доного критерию, 1 навпаки, якщо рооити "роздр Юления", тобто зам!няти одшг прклад на дск!лька прилад!в з такою ж самою сумарпою !нтенсквн!стю обслуговуватшя, то в!д цього система "лог1ри'уе;ться" зПдно задэного критор1ю.

Касл!док 2. Якщо розглянути да! гомогвнн! с б [м Iг*!00> системи стоОто !нтенсивност! обслуговувзння в кокн1й систем! р!вн!> з р1вкими сумарними 1нтенсивностями обслуговувоння < тобто пехай перша система м!стить п , а друга п_ прилад1в, .ц,2'^

1 С* X Г) ^ л П^

" то нер!вност1 <**> б справедливими.

Якщо провести пор!вняшш двох гомогенних <<з |м |п> систем, для таи часи обслуговуваипя експононц!Лн! та мають однпковий параметр в межах кокно! системи, перша система м!стить п1, а друга

п2 прилад!в,до Скп.,<пг 1 п2 д1литься на п^ !итенсивност1 обслу-говування порто! та друго! систем дор!газготь '= У- ,ц<г)=

1 о ^ х п2

то виявляеться, що для дов1лыюго вх!дного потоку потоки

загублених вимог зв-язан! сп!вв!дношенням« в<1) яВз(г) ).

Пор1внясмо одержан! розультати з результатами, одержашми для <о|п|п |<*» системи. Якщо для <с|м[п|со» систеш "злиття" приладТв призводить до "сокращения" (тобто до стохастичного зменшення довкини черта у кокен момопт часу», а "роздр1блвш:я" до "поПршення" системи, то для <п|м|п> навпаки, "роздр!блеш1Я" призводить до -покращення- <тобто до стохастичного зменкошя штоку загублених вимог», а "злиття--до нпог1рзо1шян системи.0

4. Розглянуто марк!вську систему з груповим нпдходоэшгям. Тяка система м1стить в соб! п прилад!в, як1 мають окспоненц1Ян1 часи оослуговування. В систему вимогп надходять грулами по п одшщь.

Необслугован! вимоги загублюються. Необх1дно м1н1м!зувати (за деяким критар!ем> к!льх1сть загублених вга/ог шляхом розпод!лу 1нтенсиыюстей Mia; приладами, явдо суыарну 1нтенсиви1сть обслуго-вування задано <Hj+ (i2+...+ с = const).

Опечатку розглянуто частиший випадок, коли вх1дний пот!к-пуасон1Бський з параметром X та п=2. Критер1ем оптим!зац11 у цьому випадку вкбрано м1н1м1зац15о математячного сподХвакня к!лькост! загублешпе вшог у стац!онаркому режим!»

min| с| ,да |<t1tt2>- к!льк1сть загубле-

них вкког на 1нтервал1 часу ctt,t2a .

У цьому вападку д!аграма 1нтенсшзностей переход1в м!ж станами система мае простий вдгляд:

—------* '■ "■1 - 1

tx ii

4Иа л

(0;1) Т

h

Користуючись даною д!аграмою, виписувться фомула для м«

,2 ( \с+ с2- 7Ц Л1 1

«"тг- —5-. зв!дки безпосередньо вишшвав, що

значення м буде мШмальним при ц.,= ц2= с/2 ,тод1

м - -И2 + •

Для дов1льного п доведено результат, який в узагвльненням попереднього!

Теорема 4.1. Для дов1льного вх1даого потоку мае м!сце аналог1чниЗ результат «який в узагальнонням попереднього, але його не можно сиразлта к1льк1сно>, а сома» у момопт надходаошш кожно! еилогл при розпод!л! 1нтенсивностей нар!вно загублшться стохас-тично моше ею,юг, н!к при будь-якому 1ншому розпод!л1 1нтонс;пзпостеЯ.

Заусалспня. Якщо розглянути задачу з груповим надходаенням та ср.панг1всъккми ЧОСОМИ ОбСЛуГОЕУВШШЯ < ЕгС^.к), 1-1,п , ц =с>, то не 1снуе оптимального розпод1лу 1нтенсивнос-

той/'жий стохасгачко м!и1м1зував би пот!к загублоних вимог, як у

попередньому випэдку. Однак, мояливо розгляну.ти системи, як1 призводять до м1н!м1зац1! осташього моменту обслуговування у rpynl для задач1 з груповим надходжонням. Розглянуто дв! постановки»

1) Трупа вимог, що подходить на обслуговування, займаз ус! прилади. Якщо у черговий момент надходаення у попередн!й rpyni не встиглэ обслукитися принайми! одна вимога, то система сплачув одшшчний штраф, а вимзги, що не встигли обслуамтися, вит!сняються.

2) Якщо у черговий момент надходаення у попередн!й rpynl на встиг-ла обслужитися принайми! одна вимога, то система сплачус одиничний штраф, а вс! итоги, що сойно шуЦйшш, загублюються.

Очозидно, що для того, цоб м!н!м1зупати функц!ю штрафу у обох випадках, нвобх!дно стохастично м!н!м!зувати максимальней час обслуговування у rpynl. Для даних випадк1в доведено аналог теореми 4.1. «тобто розпод1л !птенсивностей обслуговування м1* ус!мз приладами нар1вно в обох випадках 8 оптим&лышм розв-язком дано! задач!. В

5.Розглянуто задачу оптимального складання вироб!в з дек!лькох 1кгред1ент!в. Нехай в систему надходять пуасон1вськ! потоки 1нгред1ент!в <1,...,п> з 1нтесивностями ц,,...,^ , ц^...+ja-с» =cor,5t. Нехай система моке збер1гати не б!льше одного елементу кокного типу. Складання виробу вважавться зак1нченим в момент часу, коли система м!стить в соб1 1нгред1енти вс1х тип1в.

Задача полягае у тому, як розпод1лити 1нтенсивпост1 ^.....цп

так, щоб максим!зувати процес складання вироб!в.

Позначимо вшадкову величину, яка розпод!лена за зако-

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

\ = »-«<е(1,<^>,е(г)(>12),....е(п)<м.п>> -

Доведено, що f<ц1____,цп> буде стохастично м!н1малъною при

отже мае мЮцв такий результат« Теорема 5.1. Пот!к вХдновлеяня, який породаено випадковою величиною 5 при ^ ••^ буда зв-язаний з потоком в1дновлення, який породаено \ при будь-якому 1шому розподШ 1нтенсивностей Ц,i•••.Цп таким чином»

.....IV 8

Для ерл&нг1всышх та детерм1нованих вх!дних поток!в 1нгред1ент1в мае м!сцв аналогична теорема.

Розглянуто вкладок, коли система мае можливХеть зберХгати 1нгред1внти кожного типу у нео0можии1й к1лькост1:

—. — — —

—

— — —

__ -

Г г I

1нгред1ент кожного Т1шу п1сля надходаюння а систему в!дразу нылагаеться над!йтп на склздальну л!н1ю.. Якщо на складальн!й л!н11 вке е 1нгред1ент такого т;шу, то слемент, що щойно над1йшов у систему, надходать на склад. Складання зак1нчуеться та готовий вироО залшае систему у перший момент, коли на складальн!Й л!нП е ва1 1нгрод1енти. У той же момент часу з! складу на складальну л1н!ю надходать г;о одному 1пгрод1енту кокного типу шсщо вони е у наивность. НеоСх1дао максим1зусати вихХдний пот!к готоеих вироб!в.

Нехай -пуасон1всъкий процес з параметром ц. Тод! у момент

часу 1. буде складено тт1 <1> ><t),... <^> > впробХв. Доведено, що 1 в цьому випадау розпод!л Хитенсивностей нарХвно максимХауе кХлысХсть готових виробХв для будь-якого моменту часу

У ДРУИИ ГЛАВ1 розглянуто результати, як! було одержано для систем з дисциплХною Шраге <с7],саэ>, де даеться таке II визначегшя:

1.Вьажавться, що швидкХсть обслуговування дор1внюе одшшц1.

2.Ввакаеться, що обсяг роб!т, що в необх1дний для обслуговування кожно! вимоги.стае вХдомим у момент надходаення ц!е! втюги.

• з.Водночас може обслуговуватись дек!лька вимог.алв сумарнв твида!сть будо дор!внювати одишц!. Обслуговування будь-яко! вимоги моке бути перервано у будь-який момент часу.

бдрт -да дисдш1л!на, яка характеризуемся там, що в кокен

ломонт часу обслугопуеться вимога, яка мае наймонший залишковий збсяг роб! т.

Ка в!дм1ну в!д систем, розглянутих в пера!й глав!, дан! жстеми належать до данам!чллх <або систем кэрування), оск!льки Ксения про зм!ну дояк!х парамотр1в систе?д1 гложа пр/^атнсь у трсцес! обслугоьулшшя.

Лля данях систем одержано так! результата

Для випадкових вх!днкх поток'в та вмпадкових обсяг1в роб1т лають м1сцз сп!вв!дноыокнл стохастичного порядку s для

lotokld ВИМОГ,ЩО ОбСЛуУМЛИСЯ <тут s srpt- ВИХ!ДНИЙ ПОТ!К системи иш дксцишШш srpt, s ~вих1дни,1 itotík вимог для будь-яко! 1ншо1

тисципл!ни> та о it) !^tn<t) для к!лькост! вимог, що ^находиться в

м1стем1 в будь-яккй момент часу t.

"окна розглядати задач!,в лккх обсяги роб!т,що надходять на )бслуговува1шя,залишают1.оя пеШдокши до к!нця обслуговування. У аьому виподку аналогом srpt е диснипд1нн, яка полягав у тому, що в южен момент часу обслуговуеться вимога з! стохэсткчпо м1н!маль-им залишковим обсягом роб!т <якщо розпод!л часу обслуговування :тар!ю'П1й,то означено» диснигглШо» Суде • будь-яка дисципл!на без тереривзнь, наприклад tifs aöo fils, якщо молод1ючий -то означеною шситл!пою буде обслуговування у кожан момент часу вимога,або -рули пю/ог,як! до цього одержали м!н!мальну к!льк!сть обслугову-эання>, при цьому також мають м!сце сп!вв!дноиошя стохастичного горядку s3rpt^ts для потокin вимог, що обслужилися).

Сл!д в!дзначити, що тривал!сть пср!од!в простою та пер!од!в шйнятост! не заложить в1д вибору дисциплйи обслуговування у слас1 ycix консервативних дисцшл!н, отжэ srpt не даз н!яких юре ваг у цьому план!. Сл1д також в!дзначити, цо переваги srpt г (q|b|i|oo) проявляються тем б!льше,чим б!льше дисперс!я часу >бслуговування «зокрема.у cq|d|i|oo> srpt но моз н1яких пероваг юред firs або fils>.

ЬРозглянуто дисципл!ну, яка в коиен момент часу обслуговув шмогу з найб!льшим залишковим обсягом роб!т (тобто в протилекною ю в!;шошенню до srpt у деякому значекн!). Природньо назвати таку

^ИСЦИПЛ1ну LRPT (Longest Remaining Proceaning Time). ВзавМОЗВ'ЯЗОК

il» srpt та lrpt мокна розглянути на такому приклад!»

гехай s <g|0|i|co> система з перериванням, в як!й обсяги. роб!т по

>бслуговуванню kojkhoï влмоги стають в!домими в момент надходжекня.

Нахай кожна вимога, що знаходиться в систем!, в кожен момент часу створюз 1й "нозручШсть", яка е функц!ею в!д залишкового обсягу роб!т по обслуговуванню ц1е! вимоги: ук- * <ик> , до f- неперервна зростаюча фуикц!я та *(О) Як 1 в поперодньому випадку вваиаеться, що -незручнЮть", що створюеться групою вимог,дор!внюв сум! незручностей, що створюються ножною вимогою окромо.

- Позначимо через *k<t > залишковий обсяг роб!т по обслуговуванню k-i БИМОГИ. Якщо , т.^,- в1дпов1дно момента надходжоння к-1 вимоги в систему та зак!нчення II обслуговування, то ?k<t)=0 ,t« tt^^ та «к<\> = Тод! платня за незручн!сть визначаеться як !нтег-рал в1д сумарно1 незручност!, яка спричиняеться систем1, по часу»

t

•il

S(t) = | ) f (xk(u> )du.

Задача поллгае у зкаходженн! дисцишШга у клас! yclx консервативных дисципл1н, яка б м1н1м1зувала s<t>. Для дано! системи одержано такий результат!

Теорема 1.2. Якщо *-л!н!йна функц!я, то s(t> не заложить в!д вибору дисцшхл1ни обслуговування у клас1 консервативних дисципл1н, якщо *-вв1гнута функц1я, то тод! оптимальною дисцишШюю обслуговування буде srpt, ящо *-опукла, то тод! оптимальною дисципл!ною обслуговувшшя буде lrpt.0

Розглянемо деяк1 к1льк!сн1 результата для lrpt «майке у вс!х статтях, як! розглядають srpt, в!дзначавться, що отримати к1ль-к!сн! характеристики для не! дуже важко або немокливо). Отже, будемо розглядати систему <m|g|i|<»|lrpt). Нехай n«t>-к1льк1сть вимог, що знаходяться в систем1, wit)- сумарний обсяг невиконаних роб!т для вс1х вимог в момент часу t, pJ,(v,t> -p{Ntt)-i,witxv), f -функц!я розпод1лу обсяг1в роб!т, що надходять на обслуговування, pQ<t)- ймов1рн1сть того, що система в в1льною у момент часу t <вона така ж, як 1 для <h|bIi|oo) системи». Тод! р!зницеве р1вняння Колмогорова для Pk<v,t) мае вигляд!

~8F ~ 3v "--к-^к + *<pk-i*F) '

У стац1онарному режим! маемо«

dP

■d^ - АРк + Р^<0) - , к>1 (1)

со

р0= х-р , де p=^jW<t> - завантаження системи.

00 oo Якщо u>ri<s> « Pn, ф,<*> » JV~"Ui4P <u> , ф<«> = Je"UdF <u> ,

0 ° k O O

<5<e,z>- ) ф <s)zk - TBlpua функц1я ДЛЯ ПОСЛ1ДОВНОСТ1 ф,,е»>.

й=ок к

»*<*> - KOplHb р1вняння а—\«-Хгф<я) =0 ,ТО

Р0\гф(ч*(2)> + Р0(*-Ъ

í(s,z)

<5 - X +

У частинному випадку, якщо обсяги роб!т, що надходять на обслуговування, мають експонетЦйний розпод!л з параметром ц <ц>А.> .маемо«

$<z> - Ф(И z> - ^ Ц-\-/(Л.>Ц)2- *Ац» = ^ Ц-Ь-/(Ц-Л>2- 4^(z- ■> ' Ц 2\(z —1> Ц 2MZ-1J

Серодня к!льк1сть. виког у стац1онарному режим1 дорШгов

м = Ф' 11) ^ - *** - —Р— .

(l-p)^

Граничний розпод!л довжини черги в стац1онарному реким1 при р*1 мае вигляд» якщо *-довжина черги, то перотворення Лапласу гранично!

величина (1-р)гх мае вигляд« ^1 ^ - з^1**" -t. Зображешго в1дпов1дае такий ориг!нал|

/ТТ^-t . e"t/4 . .1 . _ 2 «S -t2

2и т уирг ' т ■ ......-..... |в

2.Для 1«|о| 1 |5т=>г> системи з вибиванням одержано так1 результата! 1>.Якщо в<к> — функц1я розпод!лу обсяг1в роб!т, що надходять на

обслуговування, «р^<к>-е><р|\|в<у>с1у] , то Ямов!рн1сть того, що в стац!онарному ре«им1 система в в!льною, дор!внюв %0-—-.

2>. Якщо ДЛЯ ДВОХ систем В,'!^, /кйв1<к)-^иавг(н> ТО

з). Для (м|о|1|бкрт> системи <тобто результат сп!впадаа

з в1дпов!дним результатом для <м¡о)»> системи».

4>. 1С0>в для будь-яко! фугасцП в<м> <якщо нов1ть в(«>«1 для деяко-

ГО СК1НЧОНОГО х>.

б>. Для < м | к | г | srpt > система xq=-—-.

а

3. Розглянуто комерц!йн! задач!,безпосередньо поз'язан! з srpt. 1). Нехай е <g|g|i|w> система, яка несе витрати за перебування в н!й кокко! вимоги, пропорц1йн! повному часу перебувення (в!д моменту надходжешш до моменту зак!нченля обслугозуваши). Доведено, що у клас! ycix консервативних дисциплш з перериванням srpt м!н!м!зуе сумарн! витрати системи.

Розглянуто вкладок, коли обсяга роб!т,що надходять на обслуго-вування, залишаються нев!домими до зак!нчення обслуговувашш, витрати системи в!д перебування в н!й кокко! влмоги не е л1н!йниго по часу перебування, а оптимальна дисципл1на шукаеться у клас! bc!j консервативных дасцкпл1н без пореривышя. Для цього випадку доведено тзкий результат:

Teopeira 2.2. Нехай для означено! системи f-неперервнг монотонна функц!я, яка задав залежн!сть витрат системи в!д час: перебування в н!й кокно! вкмога. Тод! якщо i -л!н!йна фушсц!я,то : клас! дисиипл!н, що розглядамться, порядок обслуговувашш вимог н< мае значения, якщо f-опукла функд!я, то оптимальною дасцшШною буде fifo, якщо -f- вгнута функц!я, то оптимальною дисципл!ною буде lifo.

У ТРЕТ1И ГЛЛВ1 досл!дауються окрем! тандемн! СМО.

1. Було проанал!зовано систему, яка складаеться з двох прила-д!в з експоненц!йними часами обслуговувашш з параметрами ц1 та ц2, як! кожна вшога мае пройти посл!довно. В систем1 присутн!: один роб!тшк, який обслуговуе вимоги на обох приладах !, таки чипом, водночас в!дбуваеться обслуговування лише на одном прилад!. Перед кокним приладом в необмежена к1льк1сть м1сць черз! <див. мал.)

1.11111

00

Прилад N©1 <ц,>

11111111

Прилад N02 <112>

Для дйпо! системи робиться пор!вияння р!зних дасципл1н обслу гсвувышя та анал!зуються результата модолювоння на ЕОМ, яке 6yj проведано М. Табу-Нетто. Доведено, що для дов!льного вх!дног

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

2. Л.Клейнроком була розглянута пр1оритетна системе, в як1й вимоги мають можлив!сть купляти пр!оритет. Вважаеться, що 1снуэ иадм!н1стратор черта-, який берв -хабар- в1д кожно! вимоги, що надходить у систему, та розм1щуе вимоги в черз! зг!дно з сумами одержаних ихабар1вп наступним чином« у момент надходження вимога, яка запропонувала деяку суму адм1н!стратору, ставиться в чергу попереду yclx вимог, що запропонували меншу суму,та позаду yclx вимог, що запропонували б1льшу суму адм!н!стратору. Нехай А. - !нтенсивн!сть надходження,

f (т) - функц!я розпод!лу часу обслуговування, в<х) - функц1я розпод!лу суми -хабару". Сума -хабара" та час обслуговування в незалежними випадковими величинами. Тод1 математичне спод!вання часу перебування в систем! вимоги, яка запропонувала адм1н1стратору -хабар" * , дор!внюв

и

w<х> --2-=■ <»> , де

<1-р+рв<х) > „

р » \ft dF <1) - завантаження системи» ~~ J42 dF <т>

о о

Нехай в стаЩонарному режим! в систему надходить вимога, яка

може запропонувати суму -хабару* за власним розсудом , а не зг1дно

з функц!вю розпод1лу f со. Для ц1е! вимоги м!н1м1зуеться ц!льова

функц!я витрат,яка являв собою суму -хабара- та витрат, пов-язаних

з перебуванням у система в<й> - н+ав<*> ■* min , де а - так званий

коеф!ц!внт нетерп1ння - витрати вимоги при перебуванн! у систем!

кожну одиницю часу.Розглянута система в системою з неперервними

пр!оритетами, i таким чином в узагальнвнням пр1оритет1шх систем.

Кр1м того,сл1д в1дзначити, що в системах, що розглядалися ран1ше,

вимоги не мали права вибору, до якого класу пр1оритет1в

приедпуватися.

У дисертац!йн1й робот! розглянута задача, яка в модиф!кац!ею дано!| нехай в стец1онарному режим! для дано! вимоги треба пройти посл1довне обслуговування на двох або 01лып1й к1лькост1 однотипних прилад1в. Ця вимога мае даяку суму к, яку вона може витратити на хабари. Необх!дао розпод!лити цп суму м!к адм!п!страторами

прилад1з так.щоб математичпо спод!вання сумарного часу пересЗування у bcíx системах було б м1111мальж:м:

^ i-J <х •» minl»;^ С, ^ Xj= х |

Для дпко! системк доведено такий результат: Тесрела 1.3. Якщо в- вгиута fVüKutn, то для дов!льно! к!лькост! щшадЛв' розпод1л суми Mi::t адм!н!страторами нар1вно м!н!м!зув сумарний час перобування у bcíx системах. П

. Для задач! Джонсона, яку було розглянуто в , одержано таг«! результате:

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

1 i, i, i2 lk_1 n J

(Для к!лькост1 стащив, 0!лы1!о1 двох, задача не вир!шена, 1 дана формула' мозке бути корисною для"' побудови чксельного алгоритму ро.зв'язку на Е0.\!>.

2). Рсзглянуто аналог зодач1 Джонсона для системи з двох станк!в, якл;о промйкня черга м!ж станками в!дсутня, тобто якщо i-a деталь зао обсдукилася на i-му станку, а u-n-ша на 2-му - н!, то i-а деталь зкаходиться на 1-му станку «блокуючи доступ до нього

>-1 детал! до моменту зак1нчешш обробки u-n-l детал! на 2-му станку. Доведено, цо у загальному вшадку неможливо побудува-ти алгоритм, аналог!чний алгоритму Джонсона, але для частинних Е1шади!в одержано так! рэзультати:

Якщо <V i, j) ía^Bj), то при будь-якому порядку обробки деталей для bcíx значень i у момента зак!нчення обробки i-l детал! на 1-му станку (1-1)-ша деталь на 2-му станку вже оброблена 1 у жоден момент часу не виникае "блокування- 2-го станку, тому сумарний час

обробки буде такий самий.як 1 в задач1 Джонсона, а саме > а.+ в ,

iSi 1 п

тому оптимальним буде порядок обробки, при якому на останньому м!сц! буде стояти деталь, у яко! час обробки на 2-му станку м!н1мальний, порядок обробки !нших деталей не мае значения, якщо (V i.jHA^j) то при будь-якому порядку обробки з моменту над-ходаення 1-1 детал! на 2-й станок 1 до моменту зак1нчення обслуговування п-1 детал! на 2-му станку 2-й станок не буде аростоавати, тому сумарний час обслуговування на двох станках буде

дор.'ляювати V в.. Зв1дси вшливав, ко для того, щоб сумарний 1=1

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

У ДОДАТКУ наводяться визначення, основн! властивост! стохастичних нер1вностей та "хне застосування у оптим1зац11 систем масового обслуговування, а також три теореми, як1 було доведено Т. Ролек!. Деяк! з розглянутих властивостей ран!ше не розглядалися. Доведения цих властивостей дозволяв розширити мокливост1 застосування означених теорем до конкретних систем массозого обслуговування.

Основн! результата дасертацП викладено у таких роботах«

1. Доценко С.И. .Закусило O.K. Оптимизационные задачи в системах массового обслуживания. Тез. докл. Десятой Белорусской школы-семинара -Анализ и применение систем и сетей массового обслуживания». Минск, 1994, с 47.

2. Доценко С. I. Оптимальний розпод1л Хнтенсквностей обслуговування в багатоканальних марк1вських системах масового обслуговування. ПрепрХнт ГТФ-94-б*-^, КШв.1994 р., 7 с.

3. Стохастичн! нер!вност1 та 1хнв застосуващю для оптим1зац!1 однокакальних систем з необмеженою к!льк!стю м1сць в черз1. Препр1нт 1ТО-94-Л-У, Ки1в,1994 р., 9 С.

СерНй 1ванович Доценко

0птим1зац1я систем масового обслуговування

Зам. 7/ Формат 60x84/16. Обл.-вид.арк. 0,93

Птдписпно до друку 13.0».9»Р. Тираж. 100.____

Полтгрпфтчна д}льниця ТТФ }м.М.М.Боголюбова МЛ УкраГни