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

-?

НИЖЕГОРОДСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. Н. И. ЛОБАЧЕВСКОГО

На правах рукописи УДК 519.873

КУВЫКИНА Елена Вадимовна

АНАЛИЗ И ОПТИМИЗАЦИЯ ОДНОРОДНЫХ АЛГОРИТМОВ УПРАВЛЕНИЯ КОНФЛИКТНЫМИ ПОТОКАМИ БАРТЛЕТТА

01.01.11 — Системный анализ и автоматическое управление

Автореферат

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

Нижний Новгород, 1992

/ '

Работа пыполпена в НИИ прикладной математики н кибернетики при Нижегородском государственном университете им. Н. И. Лобачевского.

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

Официальные оппоненты:

доктор технических наук, профессор Неймарк Ю. И.,

доктор физико-математических наук, профессор Рыков В. В.

Ведущая организация — Рижский институт инженеров гражданской авиации.

Защита состоится « » (Х^Ь^уС^Г_1992 г.

на заседании специализированного совета К 063.77.01 в Нижегородском государственном университете им. Н. И. Лобачевского но адресу: 603000, Нижний Новгород, ГСП-20, просп. Гагарина, 23, Нижегородский универ-

ситет.

С диссертацией можно ознакомиться в библиотеке ННГУ.

Автореферат разослан «_ 1Ь » ил

1992 г.

Ученый секретарь специализированного совета, кандидат фнз.-мат. паук, доцент

В. И. Лукьянов

L. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Гоорил управляемых систем массового обслугившшя (УСЖ) возникла в связи с созданием сло;?лых автоматизированных систем управления производством, сетей связи, вычислительных сетей и проч. Значительный вклад в развитие этого направления внесли работы Б.В.Гнеденко, Г.П.Башарина, А.А.Борэвкова, Г.И.Климова, Л.Н.Коваленко, В.С.Короляка, В.В.Рыкова, А.Д.Соловьева, а такяе ряда зарубежных авторов. Одним из перспективных разделов теории УСУО является исследование систем алгоритмического управления потоками заявок. Такие системы имеют широкий круг приложений в разнообразных областях практической деятельности, к ним относятся системы регулирования транспорта на перекрестках со ело;«!oi! геометрией переезда, системы диспетчерского контроля за последовательностью взлетов и приземлений самолетов в крутшх аэропортах, системы адаптивного управления технологическими и информационными сигналами микросварочного комплекса при производстве интегральных микросхем, системы обработки программ в локальных вычислительных сетях, системы управления потоками самолетов при прохождении таи пересекавшихся воздушных коридоров и др. Отличи-тзльннмн особенностями систем такого рода является: а) протекающие в них процессы носят существенно дискретный характер и рассматриваются либо на интервалах, либо в моменты, порожденные некоторым точечным процессом; б) обслуживающее устройство имеет насколько изменяющихся случайным образом режимов работы, причем, наряду с функциями по обслу.хлваяшо требований, оно выполняет и функции ориентации, переналадок, переключения режимов и др.,*' в) структура отдельных элементов системы может изменяться в процессе функционирования. Классические способы описания и исследования систем обслуживания не позволяют в полной мере отразить

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

Цель работы. Разработка и программная реализация алгоритмов проверки эффективности нелокального описания потоков специального вица, в которых требования по принципу близости моментов поступления условно объединяются в пачки, а интервалы между момонта.ш поступления статистически зависимы. Потоки такой структуры с некоторым заданным распределением числа требований в пачке называются потоками Еартлэтта. Исследование вероятностных свойств и оптимизация процесса управления конфликтными потоками Еартлэтта в классе циклических алгоритмов, в классе алгоритмов о упревдением, в класса алгоритмов с ориентацией и переналадками. Для решения этих задач били гспользованы элементы теории массового обслуживания, теории управляемых случайных процессов, эргоди-ческой теории марковских цепей, теории бесконечных систем алгебраических уравнений, теории функций комплексного переменного, методов имитационного моделирования и оптимизации.

Научная новизна.

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

2. Получены рекуррентные соотношения как для самих процессов управления конфликтными потоками Бартлетта по алгоритмам из указанных классов, так и для их одномерных распределений и производящих функций.

3. Для каадого масса алгоритмов исследовано. предельное поведение процесса управления, получены необходимые и достаточные условия существования стационарного решила.

4. Построены имитационные модели систем управления конфликт-

£

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

Практическая ценность. Результаты, полученные в диссертации, относятся к системам обслу;швания, в которых входные потоки конфликтны и переключение прибора с обслуживания одного потока па другой происходит не мгновенно, а за конечное время. В работе разработаны алгоритмы определения моментов поступления пачек в систему, которые целесообразно выбрать за моменты принятия решений о разрешении или запрещении обслуживания. При анализе указанных систем (теоремы 2.1-2.4, 3.1-3.4, 3.6, 4.1-4.6) получонн простые ограничения на интенсивности поступления, интенсивности обслуживания и параметры однородных алгоритмов управления, которые позволяют существенно сократить число возможных вариантов при решении задачи оптимизации. На основании аналитических и численных исследований систем управления конфликтными потоками выработан рдц практических рекомендация (о необходимости коррекции параметров алгоритмов при изменении вероятностной структуры входных потоков, о целесообразности использования алгоритмов из того или иного класса и др.), которые проинтерпретированы на задаче регулирования дорожного движения на перекрестках. Разработанный комплекс имитационных программ мотат быть использован при создании учебных лабораторных работ для анализа, синтеза и оптимизации систем обслуживания с переменной структурой.

3

Апробация работы. Основные результата работы докладывались на 5-ти Всесоюзных конференциях и совещаниях, на 3-х Всесоюзных школах, на 4-х конференциях молодых ученых Волго-Вятского региона, на 8-ми итоговых научных конференциях Ш1ГУ.

Публикации, структура и объем работы. По теме диссертации опубликовано 19 работ. Диссертация состоит из введения, четырех глав, заключения, приложения, содержащих 9 рисунков и 7 таблиц, и списка литературы, включающего 128 наименований. Общий объем работы 215 страниц.

П. СОДЕРЛШЕ РАБОТЫ

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

Первая глава диссертации включает два параграфа. В § 1.1 дается общая постановка задачи об управлении т>2. конфликтными независимыми потоками Г^^..,Пт в соответствии с некоторым однородным алгоритмом при неограниченном объеме бункеров-накопитв-лей очередей (система с оквданиеы). Под конфликтностью входных потоков на содержательном уровне понимается еле,дующее: во-первых, обслуживание заявок конфликтных потоков допускается лишь в непересекающиеся промежутки времени, чем обусловлена невэзмо;шость суммирования некоторых потоков но условши ах-обслуживания и сведения задачи к одномерному случаю; во-вторых, имеются интервалы недоступности обслуживающего устройства (07), когда потоки не обслуживаются, а система осуществляет ориентацию, порепаладки, разогрев и т.д. Порядок обслуживания потоков определяется процессами поступления и обслуживания заявок сразу по всем потокам. Моделью системы, которая отракает указанные характерные особенности, является система обслуживания с переменной структурой, задаваемая через ма-

¥

тематическое описание своих составляющих элементов: векторного входного потока Г1 = (П_(1Па,1..,Пт') , структуры £(г) обслушшающе-го устройства, алгоритма , управляющего структурными изменениями ОУ, векторного потока насыщения П , Г^Ю , стратегии 5* механизма обслуживания. При этом существенно используется новый принцип нелокального описания отдельных элементов. Это означает, что описывается поведение на каждой отдельной заявки, а целой группы заявок в некоторые специальные моменты времени. Будем подразумевать, что с системой управления потоками связало вероятностное пространство Р) элементарных исходов <х> е Й с вероятностной мерой РО) на Г -алгебре 1 , и всо случайные элементы задаются на (|м!,Т)Р) .

Векторный входной поток П описывается нелокально с помощью точечного процесса -[("с- ^0 выделенной дискретной

компонентой >7т г ^ • Здесь ~

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

г \ 4

на 1-ом интервале наблюдения ич/^ч-!,) и принимает, значения у ^

из множества М-1°,-'!,5-, 'С^"-•

Структура обслуживающего устройства определяется мно-

жеством Г его состояний 6 . Множество Г разбивается на п. подмножеств Г , •"=-!,к. , однотипных состояний, которые назовем режимами работы прибора, т.е. Г= Ц^Г^, -Г^^к* ^к-СгД,

к.(г) _ целое положительное, Смена состояний ОУ происходит

в моменты Пусть при случайное отображение ГО и

случайная величина 'эе^- ^ характеризуют состояние ОУ на интервале [т- и размер очереди по ГЪ а момент т:^ и принимают зна-

чения ёеГ и гс^&М . Если Х^С^ь^гЛ'-■ > ^'тцО » тогда алгоритм г/. , управляющий переключенном состояний ОУ, имеет вид

5

и

Векторный поток насыщения и представляет собой совокупность выходных потоков системы, если очередь по каждому из потоков бас-конечна' и ОУ работает некоторым экстремальным образом. Поток насыщения ПН описывается нелокально с помощью векторной случайной последовательности -{(З^, Е^ ) о\ о выделанной дискретной компонентой - Случайная величина ^принимает значения 2:6 М й определяет максимально возможное число í

требований потока ГЬ , которые могут быть обслужены на \ -ом интервале [х^ . В работе рассматриваются независимые потоки насыщения специального ввда. При этом , где ^ - це-

лое положительное и • алеет следующее распределение 'в»

если А 6еГ-)\/Ц=0 & ,

л

где Г. - множество состояний ОУ, которые соответствуют обслуживанию требований потока П^ .

Под стратегией 5" механизма обслуживания понимается правило, согласно которому заявки отбираются из очереди на обслуживание и которое имеет ввд функциональной зависимости мезду случайным числом • ^ реально обслуженных на интервале Ст^т^О трабова-ний ^ -ого потока и случайными величинами 'эе^ ^ ,*} ¿ \ , В работа рассматривается экстремальная стратегия 5*0 вида

н.. = ттЛ"*'.+п .. , ^.. V .

(3)

Поведение системы обслуживания описывается векторной последовательностью К >/ с выделенной дискретной компонентой Задача сводится к изучению вероятностных свойств последовательности ; О }- , которая определяется не-

' V '

е

локальным описанием входных потоков П^П^,,,,, ПГп , структурой а также соотношения!.«! (I - 3)й задает динамику состояний 07 и флуктуацию длин очередей по потока!.!. Для имеет место

рекуррентное соотношение

Параграф 1.2 посвящен проблеме нелокального описания потоков пачек. Нелокальное описание {Сч,^)^ предполагает выбор

случайной последовательности о}- моментов наблгадеш«.

Для отдельно взятого потока П (ради простоты индекс j здесь опущен) в качестве т^ iо , следует выбирать моменты постулле-шщ первых требований в пачках. При этом случайная величина ^ ^ определяет длину (число требований) i -oi'i пачки, и rj^vso, полагаются условию независимыми в совокупности. Если в качество математической модели формирования пачки принять систему М1И\,1\00 то распределение числа ^ требований а пачке совпадает с некоторой модификацией геометрического распределения, описывающего флуктуацию длины очереди при функционировании системы в стационарном рекиме, и тлеет вид

, , (5)

где r j - параметры распределе;шя,СК . Под потоком Бартлет-

та будем понимать поток пачек, для которого в качестве моментов Т| f впбрани моменты поступления первых требований в пачках

и величины ^. , распределены по закону (5). Нелокальное

описание апробировано па раде известных реальных потоков пачек, в том числе, на потоках транспорта на магистрали, па потоке вызовов

на пункт скорой помощи, на потоке импульсов вдоль нервного золок?

на, на потоке ошибок при передаче двоичной информации по телефону и др.

В работе предложены некоторые эвристические алгоритмы выбора х при нелокальном описании потоков пачек. Пусть входной поток П задан в виде последовательности 4. У моментов поступ-

ления требований. Анализ статистических данных включает два этапа. На первом этапе применяется простейший алгоритм выбора и формирования пачек, который является формализацией графического анализа моментов поступления заявок по принципу их близости и имеет вид гтОп. : >СЦ У ,

, 1\ = Ч+ГЧ , , ,

где >0 ,-1 ^0.^о"^^ ^ А • Это означа9т1 чт0

длительность интервала мезду моментами поступления -ого и (у*"^) -ого требований строго меньше сц , то обе заявки принадлежат одной пачке, в противном же случае,(И"0 -ал заявка является первой заявкой следующей пачки и момент ее поступления принимается за момент наблюдения. На втором этапе к полученной первоначальной последовательности -{(Т^, применяются некоторые алгоритмы укрупнения пачек, которые разработаны на основе анализа динамики потока указанной структуры. Алгоритмы апробированы на примерах и показали хорошую работоспособность.

Пусть теперь независимые входные потоки яв-

ляются потоками Бартлетта и последовательности поступления первых требований в пачках по всем потокам совпадают. Из условия независимости потоков и определения потока Бартлетта следует независимость в совокупности случайных величин ^ • ^,>>0, э

6 *

распределение которых не зависит от реализации т и имеет вид

, р^Ч^И^Г, у.>А , (6)

Вторая глава диссертации включает три параграфа и посвящена изучению асимптотических свойств циклического алгоритма управления конфликтными потоками Бартлетта. В § 2.1 рассмотрена работа системы'на содержательном уровне, а также дано математическое описание данной системы как системы обслуживания с переменной структурой. Множество Г состояний ОУ тлеет вид-^^Г^:^^¿кО), и разб1шается на п-г.га режимов

Пусть = . Смена состояний ОУ происходит в со-

гы

ответствии с циклическим алгоритмом

Г , если Г^Г^'*^ ,

= < , если =

, еслиГ^Г^, иг«^

Отображение Ц С" ) и всевозможные наборы значений величин К(г"),

определяют класс А^ однородных циклических алгоритмов. Из (7) непосредственно следует, что величину к (г') можно интерпретировать как время пребывания ОУ в режиме Г , где г^п. Пусть

имеют место все предположения относительно свойств потоков иасы-

ПН ПН -«н ,

,,'и II , которые были сделаны в § 1.1. При этом

распределение (2) с учетом равенства П •= Г ° имеет следующий ввд , если(г, = (и:^5вГСг»~и> V(г^ = О <£ Ее Г \ Г ^« ') . в качестве стратегии механизма обслуживания примем экстремальную стратегию &0 , которая имеет вид (3).

В дальнейшем будем предполагать, что входные потоки П.,.

Г, г,"

11^ и потоки насыщения П^ условно независимы, т.е.

если х определена как последовательность 'поступления первых

требований в пачках, то случайные величины > условно

назависима в совокупности, а такта имеет место равенство

ЧЛ- ""(¡А 4 й 1 ' *

*\Г^8. V.... Р(£Г^) .

В § 2.2 приведено основное рекуррентное соотношение вида (4) для {(г!^!))^0.)" при циклическом (7) алгоритме управления. Доказано (леша 2.1), что случайные последовательности

01»т- > являются однородными марковскими цепями. Б дальнейшем подробно были изучены лишь вероятностные свойства последовательности {(Г^'Х^); о}- . Свойства же последовательностей {(Г^'а^ ¿=2Д>г , а тем самым и свойства "КО.'/^!.)? ^ могут быть исследованы аналогично в силу симметрии системы относительно входных потоков П^,,., . Далее рассмотрены свойства пространства X' состояний однородной марковской цепи Кг!,«^); ч-^О У . Показано (леммы 2.2, 2.3), что условна } является необходимым и достаточным для того, чтобы Х-иХ^ где Х^ - минимальное замкнутое множа ство существенных периодических состояний с периодом с1-к. , Х0 - незамкнутое множество несущественных состояний, Х'^ 0 , Здесь С& 1 - целая часть числа й- . Получены рекуррентные соотношения для одномерных распределений и соответствующих им производящих функций однородной марковской цепи {(Д' ^йУ . Если (^(йж^РС^С^гОс,) дощ всех -и"? о , С^х^е X1 , то имеет место

Лемма 2.4. Пусть для однородной марковской цопи 1>о} имеет место условие »(к(л V) 1 А , тогда при любом начальном распределении

{а'Дх^Сё^еХ1 V либо 10

для всех (Дх^е X' и не существует стационарного распределения/ либо для всех ) <? X '0 и ^¿й'^яС^)-

= О! (/,«>0, причем, ^.ОЧ^Ь"!

В последнем параграфе исследовали асимптотические свойства циклического управления конфликтными потоками Еартлетта при С помощью итеративно-мажорантного метода доказаны теорочы 2.1-2.3 о предельном поведегаш цепи т^ ^^ 0• < которые допускают следующее обобщение.

Теорема. Для существования единственного стационарного распределения -^'(^х^гС^гс^еХ.' \ однородной марковской цепи {(Д.,^^;*>0V такого, что дм всех (^)еХ;, ^^^^^'(«.х^о для ^ ¿^О. (6^)^= 4. , необходим и достаточно, чтобы +

Аналогичные условия мо1ут быть получены и'для остальных потоков.

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

Третья глава включает четыре параграфа и посвящена анализу и оптш.газадии процесса управления конфлшстшши независимыми потоками Бартлетта в классе однородных алгоритмов с упрощением. Параграф 3.1 содержит постановку задачи. Предварительно работа системы описана на содержательном уровне. Обслу;.гавающео устройство

имеэтфьъ-м) рекпмов Г^г=1,гт+1. При этом Г^, ¿ = - ре-

г-1аД- О

жимы ориентации и переналадок, 1 соответствует обслужива-

п • --„(2тм)

ншо требований потока 11^=1,пг} и, наконец, I - дополни-

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

И

определяется структурой 5(Г), а также процессами поступления и обслуживания требований в потоке П^, названном информативным. Следует отметить, что алгоритм с упревдением целесообразно применять в том случае, когда входные потоки условно можно разбить иа три группы: приоритетный поток П., , группа малоинтенсивных потоков , интенсивный поток Пт.

Определим теперь структуру ОУ. Множество Г состояний ОУ разбивается нап-=2т+л поданожеств Р \ ^ к (г VI у = _ гт агк-^ '

=и,гг. Пусть л = , к^-кСгт-

Используя введенные ранее обозначения, алгоритм Л с упреждением запишется в виде

' , при г£=гсг'*\ , 4 6 ,

Г^ , при = ,

, при Г^Г^'*^,

Г(2т+4'1), при (г^Г®"1-4^"1-0^ ы) V

, приСг-=гС1т^кат-1\

* V Мд

где Ы- целое положительное, _ Величина N может ин-

терпретироваться как показатель приоритетности потока П^ . Отображение и совокупность всевозможных наборов значений величин к.0"), определяют класс А г однородных алгоритмов с упреждением.

Для алгоритма с упревдением распределение (2), которое описывает семейство потоков насыщения специфической структуры, при-

и

нимает следующий конкретный вид ~ 2-1 при |и & бе Г^Мг.^ое Г \Г ^4*) для каадого!=-»,т-1

\ « е Г\(г11т~°и Г&т+1>)) .

Все остальные предположения относительно свойств исходных составляющих элементов системы обслуживания с переменной структурой, сделанные в предыдущих главах, имеют место и в данном случав. Процесс управления т>1 конфликтными независш.шми потоками Бартлетта по алгоритму с упревдениеи описывается случайной последовательностью {(г!,^;); о У.

Перейдем далее к § 3.2. Основное рекуррентное соотношение для процесса управления потока),ш по алгоритму с упревдениеи получается из (4) путем замены отображения "и(Г«,,'*Ч> 11 ^ на и, СГД'^ •, ^ • ^ - представляет труда показать (лемма 3.1), что случайная послодовательность {(Г-' о^ а также последо-

вательности . 1),1>о})^-ГТ^ , являются

однородными марковскими цепями. Ограничимся изучением вероятностных свойств цепи ь^т V • ¿на-™3 же , -{(Г^./зе' . ^Х- »- 5 может быть проведен аналогично.

В виде итеративных формул получены выражения для одномерных распределений и соответствующих им двойных производящих функций цепи {(Г;1 зе' . •ае.' .); (> О\ . В леммах 3.2-3.5 исследованы

> ' 1^1» ^ ГП Д |

свойства пространства X состояний однородной марковской цепи ^-зе^^^о}- , которые могут быть обобщены следующим образом.

Лемма. Пространство X1 распадается на минимальное замкнутое множество X, существенных непериодических состояний и не-

I

замкнутое множество Хо+0 несущественных состояний тогда и только тогда, если, взаимно просты. Полученные условия играют существенную роль при изучении

УЗ

асимптотического поведения 0 ^ при i-*-.

Пусть AA^Cß,^ x^ex'V , <->0 - одномерные рас-

пределения цепи {(Г;^ 0 } . тогда предельные

свойства этих одномерных распределений определяет

Лемма 3.7. Если выполняются условия tu*»:,1! }

(U. * , К. fcr-- взаимно простые, то при любом начальном

ill \

распределении для {(Д либо <n)~°

для воэх (б^^х^^Х и стационарного распроделешш не существует, либо {im a\(ß

>0 дал ,

1 Параграф 3.3 посвящен изучению предельных свойств однородной марковской цепи {(Д',^ Oi^0^ • ^ помощью итератив-ио-мажоролтного метода получены необходимые и достаточные условия существования стационарного роима. Необходимые условия сформулированы в следствии 3.8, которое является обобщением теорем 3.1-3.4, а достаточные условия - в теореме 3.6.

Следствие 3.8. Для существования пределов

при всех 1

таких, что Z^Q , т.е. .для существования

стационарного распределения однородной марковской цепи {(Г)1'ге1 . 'Эе.1 ■ необходимо выполненио следующих условий:

i 5 ■(ji ^ пц-t '

fc j Ks - взаимно простые числа.

Теорема 3.6. Для того, чтобы существовало стационарное распределение однородной марковской цепи i^o} , то есть , С^,^,xvn) £ х'0 ,

достаточно потребовать выполнения условий кО+^О-^Т1)""

, взаимно простые числа.

При доказательстве этой теоремы попользована теорема 3.5, которая выясняет предельные свойства цепи 10 ^''¿е' -У, i- > о Y .

* Л"

В последнем параграфе третьей главы с помощью метода имитационного моделирования решена задача оптимизации параметров алгоритма с упреждением по условию минимума средних задержек произвольного требования в системе. Кроме того, разработанная имитационная модель на примере входных потоков Пуассона и Бартлетта позволила установить, что вероятностная структура входных потоков существенно влияет па выбор оптимальных параметров алгоритма. Этим фактом объясняются, например, сбои (резкий рост задержек произвольной машины на перекрестке) в работо транспортных систем при изменении вероятностной структуры транспортных потоков, которая, как известно, зависит от погодных условий.

Четвертая глава диссертации посвящена изучению вероятностных свойств процесса управления конфликтными независимыми потоками Бартлетта в классе однородных алгоритмов с ориентацией а переналадками. Не ограничивая общности, будем считать, что сис-» тема имеетт= а. входных потока. В § 4.1 подробно рассмотрено описание S(c) и управляющего алгоритма cL . Математическое описание, структура и свойства других исходных составляющих элементов системы обслуживания с переменной структурой полагаются теми же, что и в первой и второй главах. Обслу-лшашцее устройство имеет h. решмов работы Г ^j1 г = ЙТТи , каадый из которых разбивается на четыре фазы к(гД>

целое положительноеЛ , к От,СотЛ 5 к <7-/1)-= k- сои>Л . Тогда,Г^г)-^и Г-Отмекш, что для данной системы в отличие от общей постановки состояние $ обслуживающего устрой/3'

ства обозначено символом , где (гу&).

При каждом г=ТТ[ состояния % е соответствует обслужи-

ванию требований потока П^ , в состояниях 8е обслужи-

вающее устройство осуществляет ориентацию и переналадки, ^ = ^а.. Пусть и 5

где к.0 - целое положительное, г=7Тгм , так что

___Л-*

=соги,1.Переключение режимов Г4 , г= ^п, работы ОУ определяется

процессами поступления и обслуживания требований по потокам П^, . Зададим некоторое разбиение пространства

И® М значений векторной очереди . Тогда алго-

ритм с/, о ориентацией и переналадками определяется отображением VС",*,0 следующего вида

г^=и (г; Уь(у1 у, -

' Г^ , если (Г^Г^Че^Ш^ Г^И) , если

, если С^Г^И,

, если Г^Г0^, ^¿кСу-Д^ V?, >-=; , если г^Г^'*^ , ^ ;

.ешГ^Г^,^.'

Распределепие (2) для потоков насыщения П.' с учетом равенства Г-О примет вид ^ \г£= 6 >= 1

при Л вей 8еГ\С0 г^"4^,*.

В § 4.2 получены основные рекуррентные соотношения как длн самой последовательности ь^зЛ-Н^''0^" аналогичные

(4), но с учетом конкретного вида отображения иС*/,') ■ так 11 доя ее одномерных распределений и соответствующих ям производящих функций. Последовательность .является однородной марковской цепью (лемма 4.1). Пусть СЦС^,'^ = Р(Г^= СДля всех х' , где X1 - пространство состояний цепи {(^»^^¿ч))^0^' Исследованы свой-

I ' '

ства X (леммы 4.2-4.4) и получены необходимые и достаточные

условия^ .при которых пространство л

распадается на минимальное замкнутое множество Х< существенных периодически состояний с периодом, равны;,! к , и незамкнутое мно;кество Х.^0 несущественных состояний. Показано,чтс при этих условиях имеет место следующее утверждение (лемма 4.5): независимо от начального распределения однородной марковской цепи ь^л либо -¿¿Иг^^С^х^ для всех

((Ь^ X' и стационарного распределения не существует, либо йЧ^'^ъ^-О для («.х^адех'о и

= ^ ,<)>о для (в,*, , ^й1 (в,*н = ! .

Ац

В § 4.3 с помощью итеративно-мажорантного метода изучено асимптотическое поведение цепи ^(Г^^^^^оо} при 1—°°. Необходимые условия существования стационарного режима в системе сформулированы в теоремах 4.1-4.5, которые обобщены в вида следующего утверждения.

Следствие 4.6. Для того, чтобы существовало единственное стационарное распределение {О. (¡8 х^; еX1 \

однородной марковской цепи {(Д-)'3^; > 0 У необходимо выполнение условий кО+^С!-^)"1)-^»^^0, к^+г^-^У*)-

У7

Достаточные условия получены в теореме 4.0.

Теорема 4.0. Для того, чтобы существовало единственное стационарное распределение однородной марковской цепи

5^-'г, О»^0 ^ достаточно потребовать выполнение следующих условий Ус^+г^О-^")<)- К^а^О, К <3 + г'О - з ^1) - * (п О.

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

В заключении кратко сформулированы основные результаты диссертационной работы.

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

и

Ш. ЗАКЛЮЧЕНИЕ

Основные выводы диссертационной работы:

1. IIa примерах известных реальных потоков показана целесообразность применения для них нелокального описания.

2. Предложен способ построения моделей систем управления конфликтными потоками Бартлетта.

3. Разработан метод анализа систем управления конфликтными потоками Еартлотта.

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

По теме диссертации опубликованы следующие работы:

1. Народицкая Е.В. Исследование методом имитационного моделирования управления конфликтными потоками в классе однородных алгоритмов с упрездением // Третья Всес. школа по автомати-зир. системам массов.обслун.: Тез. дом. - !Л. ,1981.0.94-95.

2. Федоткин U.A., Народицкая Е.В. Управление потоками по информации о моментах поступления требований и нелокальное описание потоков // У Всас.совещ. по статистическим методам в .процессах управления: Тез. докл. - М., 1981. .

3. Народицкая Е.В., Федоткип М.А. Выбор последовательности моментов наблюдения при нелокальном описании потоков Бартлетта // Всес. совещ. по автоматизир. систем массов.обслуж.: Тез. докл. - U., 1982. - C.I76 - 177.

4. Народицкая Е.В. Структурная адаптация одного, класса алгоритмов управления конфликтными потоками заявок. // Науч.коиф. молодых ученых Волго-Вятского региона, посвященная 60-летию образования СССР: Тез. докл. - Горький, 1983. - С.93-94.

5. Народицкая И.В. Выбор последовательности моментов наблюдали

при нелокальном описании потоков Бартлетта. Труды Ш конф.молодых ученых НИИ ШЖ и ф-та ВМК ГГУ, 1984. - Деп. в ВИНИТИ. С.152 - 187.

6. Федоткин М.А., Народицкая Е.В. Моделирование алгоритмов с поиском разрыва, управляющих потоками самолетов // Вторая Всес. научно-пракг. конф. по управлению' воз,душным двнк. : Тез.докл. - Ы., 1983. - С.97 - 99.

7. Иванова Е.В. Математическое моделирование процесса управления конфликтными потоками требований. // Всес.конф. по теоретич. проблемам кибернет. - Саратов, 1983. С.

8. Федоткин М.А., Народицкая Е.В. Адаптивное управление конфликтными транспортными потоками при изменении погодных условий // Координационное совещ. и ХП Всес. школа—семинар по адаптивным системам. - Шнек, 1984. - С. 96.

9. Иванова Е.В., Федоткин М.А. Управление транспортом на перекрестках в классе алгоритмов с упреадением, реагирующих на интервалы поступления машин в информативном потоке // Прикладные проблемы управления макросистемами. - .',1., 1985. - С. А А 9-AM..

10. Кувыкипа Е.В. Сравнение алгоритмов управления конфликтными потоками Пуассона и Бартлетта.//Исследование путей повышения эффективности сетей связи и сетей ЭВМ.-Минск,1985.-С.124-125.

11. Федоткин М.А. .Кувшшна Е.В. Динамика транспортных потоков и управляющие системы.// УП Всес.конф. по проблемам теоретич. кибернет.: Тез. докл. - Иркутск, 1985. - C.III-II2.

12. Кувыкина Е.В..Федоткин М.А. Управление конфликтными пуасоонов-скими потоками по алгоритму с уприданием// Межвуз.сб."Повышение эффективности использования вычислительной техники и АСУ

в гражданской авиации".- Рига, ШИТА, 1986. - С. Д02.-40Ч.

13. Кувыкина Е.В. Исследование простейшего алгоритма управления конфликтными транспортными потоками типа Бартлотта. Материалы

ZD