RSS    

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

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

Дата добавления: март 2006г.

Государственный комитет Российской федерации по высшему образованию. Нижегородский Государственный Университет им. Н. И. Лобачевского

    Факультет Вычислительной Математики и Кибернетики.
    Кафедра Прикладной Теории Вероятностей.
    Курсовая работа:

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

    Выполнил студент 843 гр.
    Родин А. В.
    Общая характеристика рассматриваемой темы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Страницы: 1, 2


Новости


Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

                   

Новости

© 2010.