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

ВИЛЬНЮССКИЙ УНИВЕРСИТЕТ

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

ХАЛАФ ЭХСАН ИБН МУХАММЕД

УДК 519.872

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

01.01.05 - Теория вероятностей и математическая

статистика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

ВИЛЬНЮС -1990

Работа выполнена на кафедре теорт вероятностей и математической статистики Белорусского государственного университета имени-В.2.Ленина.

Научный руководитель - . кандидат физико-математических

наук, стаций научный сотрудник Л7Д1Ш АЛ. _ .

Официальные оппоненты. : доктор физето-математических

наук, профессор ДАШШВ ЭЛ.

кандидат физия о-ыатеыатичб'ских наук, доцент • ЖПШОВСКИй Ю.В.

Ведущая организация - ораена Ленина Институт проблем

управления Мшшрибора и Ж СССР ' '

Защита состоится " * 1990 г.

в ±!> часов на заседании специализированного Совета Д 061.01.06 яри Вильнюссхоы университете по адресу: 232006 , г.Вильнюс, уз. Каугарйуко, 24.. Факультет Математики, ауд.101.

С диссертацией мозео ознактамться в научной библиотеке Зильнэсского университета (ул. Университете, 3).

Автореферат разослан " " . 1Э90 г.

7ченн2 секретарь специализированного совета Д 061.01.06

с^^^доц. П.С.ВАЙТК7С

TIEMüf?'

ОНЦАЯ ХА.РАКГЕРИСТЯКА РАБОТЫ

^куууцкосгь тонн. Системы массового обслуживания (С!Ю) тт широкой применение в различных областях науки и практи-сфоре обслуживания, при исследовании производственных процессов, описании функционирования систем управления, в ходэ исследования физических процессов, боевых действий и т.д. Значительный вклад в создание теории СМО и становление ее как математической дисциплины - прикладной ветви теории вероятностей -еносли ученые А.К,Эрланг,- А.Я.Хпнчил, Б.В.Гнеденко, И.Н.Коваленко, Г.П.Баварии, Г.П.Климов, Э.А.Даниэлян, Л.Кяейнрок, Дя.Кен-далл, В.Е.Бенеш, Дд.Козн, М.Ф.Ныэтс и др.

Развитие вычислительной техники, создание вычислительных .центров коллективного пользования и автоматизированных систем управления дали толчок появлению нового направления в теории кассового обслуживания - управлению с истомами кассового обслуживания. При управлении вычислительными системами, системами передачи информации, друтими системами массового обслуживания часто возникает необходимость оперативного изменения тех иm иных параметров системы с целы) оптимизации es работы. При этом выбор • параметров упрашения зависит, как правило, от состояния системы, а критерием качества является экономичность функционирования системы. Еще большую актуальность исследованию управляемых СМО придает бурное развитие микропроцессорной техники, позволяющей эффективно реализовать алгоритмы управления системами. Исследованию управляемых CMü (УСЬЗО} посвящены работы таких авторов, как В.В.Рыков, А.Ф.Герпутов, А.и.Гпрцев, А.А.Назг^ов, Н.А.Федогкин, С.Стидхем, К.Ссбел и т.д.

Одним из важнейших классов 7С1Ю янгявтся системы с переменной скоростью обслуживания требований, которые довольно адекватно описывают функционирование очень многих экономических систем и технических устройств. Довольно подробные обзоры работ по УСМО с переменной скоростью обслуживания сделаны В.З.Рыковым; Е.А. и М.А.Файнбергаш; В.Крэвиллоы; Д.Гроссом, Дж.Мэгэзином; Б.Т.Доши; Дв.Тегхемом. Системы талого вида рассматривались в работах И.Н.Коваленкэ, А.Д,Соловьева, А.з.Геряугова, Е.И.Рыжикова, Я.А.Когана, А.Н.Дудияа, Х.Тиймса, БЛСрэйбла, Б.Т.Доии, Дк.Тег-хема, Е.Гаялипа и др.

(ТЕМА

р

.Itimu

<«йсод

ТДЦИЙр

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

Цель рябдтн состоит в исследовании вероятностно-временны характеристик процессов функционирования'и оптимизации управяе ния следующими УСМО с изменяемый режимом работы:

1) однолинейные УСМО с произвольным распределением времен обслуживания требований во всех возможных режимах обслуживания;

2) двухскоростньа УСМО с учетом инерционности в переключении режимов; . '

3) многол:идейные СМО с удаляющийся на отдых прибором.

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

.Qcmffip.g. ,.дщдш та, даваты.ташща ж, дааш :

Получены в явном виде распределения вложенных, по момента« окончания обслуживания требований цепей Маркова для следуициг СЮ.

1. Система типа М/а /I с управляемой скоростью обслуживания при ыногопороговой и гистерезисной стратегиях управления;

2. Система типа Wа /I с управляемой скоростью обслуживания при пороговой и гистарезисной стратегиях управления, в которой переключение скорости проиоходит с запаздыванием относительно моментов принятия решений;

3. Система типа ЭД/М/а с удалявшимся на отдых прибором и рандомизированной гибрстной (из в -стратегий и Т-страте-гий) стратегией подключения прибора.

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

Ваттная новизна. Все.основные результаты диссертации являются новыми и впервые опубликованы или представлены к опубликованию в работах автора, список которых приведен в конце автореферата.

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

Глава I - модели передачи информации в зоне коммутации пакетов в режиме гибридной -коммутации с плававшим порогом или в режиме адаптивной коммутации при приоритете пакетов. Глава 2 -модели спутниковых сетей с предоставлением каналов по требовании. Глава 3 - модели оперативной динамической реорганизации баз данных в информационно-вычислительных сетях. Использование этих алгоритмов, как показали результаты численных экспериментов, проведенных на основе результатов данной диссертации, позволяет значительно повысить эффективность функционирования систем - на десятки и даже согни процентов.

Реализация рдэудьта.ТРТ>- Работа выполнялась в рамках-гос-бвджетной НИР "Вероятностный и статистический анализ случайных процессов и полей", Н госрегистрации 018700349285053, ее результаты использовались также при выполнении ряда хоздоговорных НИР по разработке систем и сетей связи различного назначения, проводимых в Белгосуниверситете.

Апрофнид работа. 0с1. ^шне результаты работы были долояе-нк на

-'ЯП Всесоюзной школе-семинаре по вычислительным сетям, Алма-Ата, 1988;

- I Всесоюзной конференции до информационным системам множественного доступа, .Минск, 1989;

- У-й Белорусской зимней иколе-семинаре по теории массового обслуживания "Методы исследования шформационно-вычисяитель-ных систем", Гродно, 1989;

- У1 Белорусской зимней школе-семинаре по теории массового

, .обслуживания "Математические методы исследования сетей связи и сетей ЭШ", Витебск, 1990;

- Республиканской научно-технической школе-семинаре ""Анализ

и синтез систем массового обслуживания и сетей ЭВМ", Одесса, 1990;

- научном семинаре кафедры теории вероятностей и математической статистики и научно-техническом семинаре отраслевой научно-исследовательской лаборатории штемати ;оского обеспечения коммутационных систаи о программным управлением Бел-госуниверситета.

Публикации. Основные иаучнш результат^ диссертации содержатся в 7 публикациях.

Структура л вддрзртавд. Диссертация состоит из введения, трах глав, списка литературы из 21 названия. Объем дисг сертащш 133 страницы,

СОДЕРШМЕ ДИССЕР1АДИЙ,

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

В главе I рассмотрена задача оптимизации стратегии выбора режима обслуживания в системах типа Ы/0/1 . Общая постановка 8адачи следующая. '

> .Имеется однолинейная СМО о ожиданием, на вход которой поступает стационарный пуассоновский поток с параметром Д . Прибор системы может работать в 5 , 5 & 2. режимах.' При работа в ( ~и режима время обслуживания"запроса имеет распределение В( >ФО*1" /, 5 с преобразованием .Лапласа-Стилтьеса (в) -

"ЫВ2&) и Двумя начальными моментами г * /, £ , - Предполагается, что изменение режима ра-

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

1-аУ+ 1с £ т М, т , (I)

где V - среднее время пребывания запроса в система, а -стоимость единицы времени пребывания запроса'в системе, Р( -средняя доля времени работы прибора в /~и режиме,, ¿у - стоимость единицы времени работы прибора в ¿-м режиме, -среднее число переключений с /"-го режима на т в едили-

6

цу времени, df стоимость одного такого переключения, f,m--f,s.

^ Считаем, что режимы перенумерованы таким образом, что if ••• > b(fS\ т.9. первый режим самый "медленный", ... ,

а 5-Й - самый "быстрый". Задача нахождения оптимальной стратегии выбора режимов является нетривиальной, если стоимостные коэффициенты" удоатетворяю? следующим условия»,):

которые будем считать выполненными. •

В § I рассмотрена задача, получакщаяся из общей задачи, сформулированной выше, в предположении d(t/n«0 , l.m'T^S . Для такой системы известно, что оптимальная з классе всех однородных марковских стратегий является монотонной, т.о. стратегией из класса шогопороговых, задаваемых следушим образом, фиксируются натуральные числа Jf} . . . , js.f , называемые порогами, О VoV-/* "' *Js-t *Js " 00 * Если число ¿' запросов э данный момент окончания обслуживания запроса удовлетворяет неравенству^ + /4 t >(Jt , следующий запрос обслуживается в /-м режиме, /» • Пусть i(in) -число запросов в системе в'момент окончания обслуживания п -го запроса. Процесс ¿(¿п) является дискретной цепьп Маркова. Обозначим

м- • (г)

Доказывается ' (Teopt а I)', что условием существования пределов (2), удовяетворящих условию нормировки, является выполнение неравенства J>s < / , где J>f i* t,S . Введем в рассмотрение производящую функцию

оо

/7(2)- Z JzJ*f.

Доказана г »О

Теорема 2. Производяпал функция fj(z) имеет следущий вид: • :. ;

■S'i (t)

Щ-К

' t'i >"'Jf-7' 1

О

z-b(X(f-D) ;,.

где X,

О S./ jt «Г

1+L Z ctm(fi-fs) (l) l'l m-Jl-,+*

а величины <лт подсчитываются по рекуррентным формулам,

С использованием (3), (4) получена явная зависимость величин V , Pt , t*/,S от порогов Jt • ,Js-f в-виде: s-/ £ aj „ s-r {t со

г Г/. • > 0 t'< 1 m"Jt-V t-f rfrsJ rnVt-t"_

J*I(j»->Js-f>--s^r—"7;-w--

_«)

v%e ß/ >. , £ - известные константы.

На основе (5) может быть реализована зффрктивная процедура нахождения оптимального набора порогов Jf , ... tjg.f .'

В § 2 рассматривается задача, получающаяся ¿а общей задачи главы I в предположении 5 = 2, dftS а ds f**d>0. Оптимальная отрастая ищется в классе гисто5езисных стратегий, определяемых. следующим образом, фиксируются натуральные числа j я А». Если число £ запросов в система в данный момент окончания обслуживания' запроса удовлетворяет неравенству ¿%J следующий запрос обслуживается в первом режиме, если t во втором режима, если же J < {«г k , то следущий запроо обслуживается в том же режиме, что и предыдущий, Нетрудно видеть, что процесс {, J , где ¿¿^ - число запросов в системе в момент iп окончания обслуживания запроса, а ^¿г -номер режима, который использовался парад моментом■ , является цепью Маркова. Обозначим ic » lim P{ij. »j, - fl

t* - /. , » -y t fi oo v fr/г ' tfl 1

n-i^Z 1' %t В** производящих функций Лffz) «

/-»t 2 & * V 09 g

получен явный вид. С использованием его получена явная зависимость критерия (I) от порогов ( J , & ) в виде:

r г „ -я;

-------—-—■-

где лтт) 4 „ //) А у {

К/; -.г ¿т<*;¿"л*,

^ г-0 ' -1 е'г/ /.¿7 1 '

С!) , СО

Мф"«*«/г£0ч '

ас,1 Г д1 /С/-г)/гШ/-2))

1 а дг1\

& и ф - известные константа. На основа (6) легко реализовать процедуру поиска оптимачь-ного набора порогов ( £*, Ь ).

Во второй глава рассмотрена задача, отяичакщаяся от задачи главы I тем, что £"2 и предположением, что функционирование системы имеет следующую особенность. После принятия"решения о переключении реггаша обслуживания еще к запросов обслуживаются в'старом режима и затем только происходит переключение на новый режим. Такой особенностью обладают, например, спутниковые сети связи с предоставлением каналов по требованию. Дет исследования свойств интаресушего пес процесса ¿¿п здесь рассматривается цепь Маркова/¿^ ,, }. где г^ - число запросов в момент ¿^ + О »- номер скорости, используемой перед моментом , ^ = если система не находится в состоянии ожидания реализации пршятого'решения о перок-тючении и

• , осли посла момента ¿п будет обслуживаться ^_\> -й

с момента принятия рекения о переключении запрос, А . Введем в рассмотрение вероятности

ж%) » Пт Р{и -I, П. «/,

а? (I) • (¿т р{и * с Г\ . г, Ь " $ Г и

производящие Функции

/7У (г) - Гг,0)а)г\ К* (г) - *

В § 2 главы 2 рассматривается гистерезисная стратегия тибора режима обслуживания, задаваемая парой порогов { )•

Теорема» Стационарное распределение вероятностей состоять системы задается следупдим образом:

1

^(гПрг&и-гЩ*''Кт(г), ' . '

Ка (г) = 2 (Лкн(г)-К,(г))12-£г (М1-г))), <7>

2) при 4-/ г :

<0 .. оЛ

3) при \ ^

• г с:, к)

Здесь величины оу - решение некоторой системы линейных алгебраииесккх уравнений,

с*) «£

1С

/»/ ' < лх+О

г

Г 7>. • -V л ■ Д - •/ ,С)7Ш) -ль п ,

С использованием результатов данной теоремы ищется явная

.10

»ависимосгь функционала (I) от порогов ( ^ , & ), которая имеет >тноситольно компактный вид и пригодна для организации эффектив-юй процедуры лоисна оптимального набора порогов. В § I данной •лавы рассматривается задача, получающаяся из задачи § 2 до-юлнительным предположением с1 - 0. Оптимальная стратегия вдется в классе пороговых.стратегий, получавшихся из гистере-исных при , Получено стационарное распределение вероят-

;остей состояний системы и ясная зависимость функционала (I) 'Т порога.у . В § 3 рассмотрена задача, аналогичная исследо-аяной'в § I, о одним дополнительным предположением, вытекаи-им из реальных постановок задач и судествэнно усложняющим за-ачу, а именно: при принятии резания о парэнлшении с меньшей корости на большую по истечении времени обслуживания Л зап-осов с меньшей сноростьв переключение происходит с вероят-остью ^ , 0< 1, ас дополнительной вероятностью ссгхра-яется меньшая скорость. В данной задаче такта получено ота-ионарноа распределение вероятностей-состояний СМО. Соответот-уодие формулы довольно близки к (7), (9), однако уравнения ил величин шеют более сложный вид, для их составления,

частности, трэбувтся использовать корни урашения /- (/-р)*

("Л (V-г})/г ) г » 0 в единичном круто комплексной юскости. Доказана

Теорема, Явная зависимость критерия (I) от порога имеет

ад:

I *

и /.) л (0 к (!)

* v»<7 ñt*i

ta lf0 , tT, , гГг s Om t - извеотныэ константы.

На основе (10) может быть построена процедура поиска ои-малького порога J . «

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

росов (уходит на отдых). В § I рассматривается обычная

п -стратегия подключения прибора, хорошо известная из теории систем с прибором, удашвдимся на отдых, развитой в литературе при с = I. Т.е. прибор возобновляет обслуживание запросов сразу, как только число запросов в очереди достигнет величины л, . Б § 2 рассмотрена болео сложная стратегия подключения прибора, введенная Я.А.Коганом и В.Г.Лигвиным (АВТ % 3, 1987 г.), задаваемая следующим образом. Зафиксирована вероятность р отключения прибора после попадания системы в свободное состояние и пороги п и k , k^-rt . Если отдых начался, говорив, что пошел период реорганизации. Этот цериод начинается с медленного цикла, длительность которого имеет произвольное распределение с функцией распределения //, (-¿) . Если за время медленноп цикла число запросов в системе превзошло величину п — / , после окончания медленного цикла заканчивается весь период реорганизации. Если то число пришедших запросов оказалось шяьие чем п , начинаются быстрые циклы реорганизации, имевшие длительность, характеризующуюся функцией распределения Нг (+) . При этом период реорганизации завершится с окончанием быстрого цикла, во время которого величина очере.;и достигла уровня k В обоих параграфах после этапов формализации задачи, наховдени переходных вероятностей состояний системы и составления систем управлений для стационарных вероятностей . 7гг • наличия t запро сов в системз в момент окончания обслуживания запроса, основную сложность составляет рекепие уравнений в конечны разностях, которые решаются следующим образом. С учетом специфики ко сффициенгов уравнений осуществляется переход от уравнений высо ких порядков к уравнению второго порядка. Для решения этих уравнений используется аппарат дискретных преобразований Лап-ласа-Стилтьеса (произведших функций). При этом задача сводится к решений линейных неоднородных дифференциальных уравнений, которые (с учетом необходимости последующего обращения преобразований Лаяласа-Стилтьеса) ищутся в виде сходящихся,степени* радов, В обофс параграфах с помощью такой методики найдено сгг цг.онарное распределение вероятностей состояний С?.Ю и первый мсмекг этого распределения, что позволяет решать задачу минимизации сре;яего времени пребывания запроса в системе при огрг Евзении на среднее число циклов реорганизации в единицу. времи

Основные результаты диссертации опубликованы в работах:

1. Дудин А.Н., Халаф Э. Оптимальное управление текущим порогом КП/ККН при адаптивной коммутации // Тринадцатая Всесоюзная школа-семь. "р по вычислительным сетям. Тезисы докладов. Ч.2.-М.: Алма-Ата, Г988. С.82-86.

2. Дудин А.Н., Халаф Э, Оптимизация предоставления каналов по требованию в спутниковой сети множественного доступа с временным разделением // Первая Всесоюзная конференция по информационным системам множественного доступа. Тезисы докладов. - Ми.: БелШШТИ, 1989. 0.67-71. • .

3. Дудин А.Н., Халаф Э. Двухскоростная система с инерционным переключением // Методы исследования информационно-вычислительных систем. - Тезисы докладов. - Мн.: Бел. уя-т, 1989. С.42-43.

4. Дудин А.Н., Халаф Э. Нахождение оптимальной гистерезисной стратегии .управления двухскоростяой системой массового обслуживания // Вестник БелгосуниЕврситета. Сер, I. 1989,

П 3. С.-35-38.

5. Халаф Э. Оптимальное управление многолинвйной сиотэмой массового обслуживания с выклгчавдиыся обслуживающим уот-ройстчЬм// Математические методы исследования сетей связи и сетей ЭВМ, Тезисы докладов. - Мн.: Бел. ун-т. 1990. С. 149-150.

6. Дудин А,н., Халаф Э. Оптимальное гистерззисноа управление двухскоростной системой массового обслуживания с инерцион-

. ным переключением // Анализ и синтез систем массовогб обслуживания и сетей ЭШ. - Тезисы докладов. - Томск, 1990.

7. Дудин А.Н., Халаф 3. Оптимизация динамической реорганизации баз данных в вычислительных сетях // Автоматика и вычислительная техника (в печати).