Модель управления конфликтными потоками в классе алгоритмов

Государственный комитет Российской федерации по высшему образованию.

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

Факультет Вычислительной Математики и Кибернетики.

Кафедра Прикладной Теории Вероятностей.

Курсовая работа:

“ Модель управления конфликтными потоками в классе алгоритмов с упреждением при влиянии случайной среды на структуру входных потоков и загрузку системы.”

Выполнил студент 843 гр.

Родин А.В.

1998 г

1999 г

Общая характеристика рассматриваемой темы.

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

Такие задачи были описаны еще в 1907 г. Ф.В. Иоханнсенном, а первые шаги по их решению предприняты в 1909 г. датским математиком А.К. Эрлангом. Чьи работы стали ядром классической теории массового обслуживания.

Скачок в развитии вычислительной техники за последние несколько лет привёл к появлению нового важного направления –теории управляемых систем массового обслуживания, а также способствовал применению результатов исследований к важным практическим задачам. Это направление, в современной теории массового обслуживания, является одним из актуальных и перспективных. Согласно определению, данному УСМО в работе \2\, управляемая система массового обслуживания –это такая система обслуживания, в которой параметры составляющих ее элементов (входные потоки требований, дисциплина очереди, структура системы, длительности и дисциплины обслуживания) допускают управляющее воздействие. Необходимым условием полноты описания такой системы является задание правила 'стратегии' использования управляющих воздействий во времени. Основываясь на работах \3,4\ можно предложить следующую (довольно условную) классификацию, вытекающую из понятия УСМО:

    системы с управляемым доступом требований в СМО;

    системы с управляемой интенсивностью обслуживания;

    системы с управляемой структурой;

    системы с управляемой дисциплиной обслуживания;

    системы алгоритмического управления потоками заявок.

В настоящей работе поставлен вопрос об исследовании систем обслуживания с переменной структурой, представляющих собой математические модели поведения сложных реальных объектов с управлением входными потоками требований в условиях их конфликтности. Прежде всего, сюда следует отнести системы управления движением транспорта на перекрестках, системы управления микросварочными комплексами при сборке интегральных микросхем, системы управления воздушным транспортом в аэропортах с несколькими взлетно-посадочными полосами. Базовый подход к анализу и оптимизации систем обслуживания с переменной структурой изложен в докторской диссертации \5\ М.А. Федоткина.

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

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

Большинство работ, касающихся решения транспортных задач, основано на предположении, что длительности интервалов между последовательными поступлениями машин в систему распределены по показательному закону. Это позволяет представлять входные потоки потоками Пуассона. Однако при плохих погодных условиях нельзя говорить о независимости движения машин. Из-за затрудненного обгона на дороге образуются автоколонны –транспортные пачки. В этом случае транспортные потоки не являются потоками Пуассона. Для потоков такой структуры адекватной математической моделью является поток Бартлетта.

Математическое описание потоков требований, используемое в данной работе, выполнено в рамках нового нелокального подхода к изучению потоков заявок \5,6\.

Цель данной работы.

Ставится вопрос об исследовании динамики системы управления тремя конфликтными потоками требований, функционирующих в случайной среде (в данном случае –состояние погоды), определяющей вероятностную структуру входных потоков, а так же влияющей на процесс обслуживания требований. В настоящей работе сделана попытка вероятностного описания функционирования системы управления конфликтными потоками требований в классе алгоритмов с упреждением.

Математическое описание элементов системы.

1. Описание работы системы на содержательном уровне.

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

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

Рассмотрим несколько примеров современных систем массового обслуживания, обладающих указанными выше особенностями:

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

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

    Система регулирования пешеходных и транспортных потоков светофорами, управляющимися вызывной кнопкой.

Функциональная схема системы такого типа приведена на рисунке.

Входные потоки формируются в некоторой случайной среде (СС), состояние которой определяет вероятностную структуру этих потоков. Если среда находится в состоянии , то входные потоки представляют собой потоки типа Пуассона (потоки отдельных требований). При состоянии среды входные потоки являются потоками типа Бартлетта (потоки пачек). Заявки входных потоков поступают в накопители (очереди) с неограниченными емкостями. Далее будем считать:

    Поток является малоинтенсивным информативным приоритетным потоком;

    Поток представляет собой малоинтенсивный поток;

    Поток –приоритетный поток наибольшей интенсивности.

Информативность потока означает, что в динамике работы системы обслуживания учитывается наличие заявок в накопителе и поступление требований по этому потоку. Его приоритетность –необходимость оперативного обслуживания поступающих требований. Приоритетность потока означает, что при отсутствии требований по потоку (разрыв) будет продолжено обслуживание по потоку . В соответствии с этими соображениями организована работа обслуживающего устройства (ОУ), имеющего 7 состояний образующих множество . ОУ в состоянии находится в течении времени . Обслуживающее устройство выполняет функции по обслуживанию требований, по управлению входными потоками, по формированию очередей в накопителях и по отбору требований из очередей с помощью некоторых механизмов (стратегий обслуживания) . Состояние для обслуживающего устройства соответствует обслуживанию требований потока . В состоянии для не обслуживаются требования ни одного из входных потоков. В состоянии обслуживаются требования потока . Граф изменения состояний (ОУ) представлен на рисунке. В соответствии с этим графом, при каждом состояние переходит в состояние . Состояние переходит в , а состояние переходит в при отсутствии очереди и непоступлении заявок по потоку и переходит в в противном случае. В состоянии система пребывает до момента поступления заявок по потоку, после чего переходит в состояние . Выходные потоки при работе системы с максимальной загрузкой, когда по любому потоку всегда есть очередь, а (ОУ) работает без простоев, назовём потоками насыщения и обозначим . Реальные выходные потоки в системе будем обозначать .

2. Описание входных потоков.

Все анализируемые далее случайные объекты, применяемые при построении математической модели и связанные с процессом обслуживания, будем конструктивно задавать на некотором полном вероятностном пространстве элементарных случайных событий с вероятностной мерой на - алгебре . Для описания входных потоков заявок будем использовать нелокальный способ. Т.е. нашему рассмотрению подлежит не конкретное требование, а весь их поток. Произвольный входной поток описывается векторной случайной последовательностью , где - число заявок типа, поступивших на промежутке времени по этому потоку. Тип заявок определен меткой (состоянием случайной среды). Поведение случайной среды, для простоты, будем описываеть однородной марковской последовательностью с двумя состояниями - хорошая погода, и вероятностями перехода . Такие ограничения означают, что смена погоды не слишком часта и что хорошая погода бывает чаще плохой. Подобные выводы позволяют считать, что за время , когда ОУ пребывает в состоянии погода не меняется. Известно, что случайные элементы связаны соотношениями:

(1)

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

3. Описание работы обслуживающего устройства.

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

(2) для .

Обозначим через длину очереди в накопителе по потоку в момент , . Для состояний ОУ предполагаем, что . Случайный точечный процесс при определяется рекуррентным соотношением

(3)

где - отображение множества на числовое множество такое, что . Будем называть длительностью фазы (состояния) обслуживающего устройства, а величину длительностью периода ОУ.

4. Потоки насыщения и выбор стратегии механизма обслуживания.

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

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

(4)

то есть некоторую стратегию механизма обслуживания. На выбор функции (4) естественно наложить следующие ограничения:

;

;

Откуда получим:

; (5)

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

Тогда зависимость (4) будет иметь вид:

(6)

Такая стратегия механизма обслуживания, учитывая (5), называется экстремальной.

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

Будем описывать поведение системы маркированным точечным процессом с выделенной дискретной компонентой , где - вектор длин очередей по потокам в момент . Для процесса основываясь на равенствах (1)-(3), имеет место следующее рекуррентное соотношение:

(7)

где , ,. Здесь векторное соотношение предполагает выполнение равенств при . Принимая во внимание выбранную нами экстремальную стратегию обслуживания , имеем:

Для изучения вероятностных свойств метки остановимся на некоторых свойствах условных распределений величин и . Полагаем что в этой модели при фиксированных значениях метки случайные величины и независимы и их условные распределения при любом и при удовлетворяют соотношениям:

; (8.1) (8.2)

(9)

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

6. Марковское свойство компоненты .

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

Теорема: Последовательности , и при заданном распределении вектора являются марковскими.

Доказательство: Докажем правильность утверждения для последовательности. Сообразно определению, данная последовательность будет марковской, если выполнено равенство

Где

Применяя формулу полной вероятности и принятые в данной модели основные свойства ее случайных элементов, получим:

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

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

Аналогично доказывается марковость последовательностей и .

7. Рекуррентные формулы для одномерных распределений дискретной компоненты маркированного точечного процесса .

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

Здесь начальное распределение считается заданным. Получим рекурентные соотношения вида , где - бесконечномерная матрица переходных вероятностей за один шаг процесса . Подробно рассмотрим вероятностные свойства последовательностей и . Из (7) нетрудно получить следующие, реккурентные по соотношения для этих последовательностей:

Заметим что исследование последовательностей и , проводятся аналогично.

Введём следующие обозначения:

На основании доказанного свойства марковости рассматриваемых последовательностей и формулы полной вероятности можно видеть что имеют место формулы:

(10)

где суммирование ведётся по

Теперь вычислим условные вероятности:

Окончательно формула (10) примет вид:

Здесь суммрование ведётся по всем точкам

Учитывая вид условных распределений для (8.1)-(9), нетрудно получить конкретный вид рекурентных формул для одномерных распределений дискретной компоненты . Подробно приведём только вывод формулы для вероятностей при .

Используя формулу (11), учитывая что при на интервалах времени ни один из потоков не обслуживается, получим для .

где полагаем при .

Вероятности , образуют матрицу

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

Поскольку при обслуживаются только требования потока ,

рекуррентные соотношения для вероятностей при получаются в виде:

(13)

(14)

Так как при происходит обслуживание требований только по потоку , то при получим, что при всех и , а при имеем:

(15)

а при любых :

(16)

Наконец для вероятностей имеем при любом , , .

(17)

а при любых , .

(18)

Заметим, что поскольку вероятности для , , то из (12) непосредственно следует, что при всех для , , .

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

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

Доказательство. Из того, что и для всех , следует что случайный процесс за некоторое конечное число шагов из произвольного состояния с положительной вероятностью по цепочке попадёт в состояние . Следовательно состояние является существенным. Согласно теореме 3.5 из /7/ совокупность состояний цепи, сообщающихся с также является существенным. Используя полученные нами рекурентные соотношения (12)-(18) и приведённые выше замечания нетрудно видеть, что множество

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

следует, что все состояния из будут непериодическими (/8/ стр. 408). Лемма доказана.

Лемма 2. При любом начальном распределении векторной цепи Маркова либо для всех :

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

такие, что , и всистеме существует стационарное распределение.

Доказательство. Из структуры множества и из того, что следует, что векторный случайный процесс из произвольного состояния с положительной вероятностью, не меньшей, чем , за один шаг может достигнуть множества . Обозначим через вероятность того, что рассматриваемая цепь Маркова исходя из произвольного несущественного состояния когда-либо достигнет некоторого существенного состояния из . Известно, что величины , являются решениями системы уравнений вида (8.6), приведённой в /8/ на стр. 392. Тогда, в силу неравенства и леммы 1, эта система является вполне регулярной и имеет ограниченное решение , . В этом можно убедиться непосредсвенной подстановкой. По теореме 11 из /9/ это решение будет единственным. Отсюда на основании эргодической теоремы в главе 15 из /8/ получим утверждение доказываемой леммы.

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

Заключение.

В конце этой (весьма краткой) работы хочется подвести итог того, что нами было уже сделано:

    Была дана общая характеристика случайной среды, системы управления, приведена её функциональная схема;

    На содержательном уровне дано определение конфликтности и потоков насыщения системы;

    Приведено математическое описание составляющих элементов системы и построен маркированный случайный точечный процесс, моделирующий динамическое поведение системы;

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

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

Литература.

    Куделин А.Н. Модель управления конфликтными потоками в случайной среде: “Теория вероятностей и математическая статистика. Диссертация на соискание уч. степени кандидата ф.-м.н”.

    Бронштейн О.И. Рыков В.В., Об оптимальных дисциплинах обслуживания в управляемых системах // В сборн. "Управление производством", Тр. III Всесоюзн. совещ. по автоматическому управлению. Техническая кибернетика.- 1965.- М.: "Наука", 1967.

    Рыков В.В. Управляемые системы массового обслуживания // Сборн. "Итоги науки. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. ВИНИТИ АН СССР".

    Файнберг М.А., Файнберг Е.А. Управление в системах массового обслуживания // "Зарубежная радиоэлектроника".

    Федоткин М.А. Теория дискретных систем с переменной структурой обслуживания квазигенерирующих потоков : "Теория вероятностей и математическая статистика. Диссертация на соискание уч. степени доктора ф.-м.н.".

    Федоткин М.А. Неполное описание потоков неоднородных требований. -"Теория массов. обслуж."

    Чжун К.Л. Однородные цепи Маркова. –М.: Мир, 1964.

    Феллер В. введение в теорию вероятностей и её приложения. Т.1, - М.: Мир, 1967.

    Кантарович Л.В., Крылов В.И. Приблежённые методы высшего анализа. – М. –Л.: 'ГИФМЛ', 1962.

1