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


головна сторінка Реферати Курсові роботи текст файли додати матеріалПродать работу

пошук рефератів

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

завантажити
Знайти інші подібні реферати.
подібні якісні роботи

Розмір: 137.69 кб.
Мова: російська
Розмістив (ла): FreeDom
11.03.2011
1 2 3 4    

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

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

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

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




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

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

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

Родин А.В.




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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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







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

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

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

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

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

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

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

(1)

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

    продолжение
1 2 3 4    

Добавить реферат в свой блог или сайт
Удобная ссылка:

Завантажити реферат безкоштовно
подобрать список литературы


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


Постійний url цієї сторінки:
Реферат Модель управления конфликтными потоками в классе алгоритмов


Разместите кнопку на своём сайте:
Рефераты
вгору сторінки


© coolreferat.com | написать письмо | правообладателям | читателям
При копировании материалов укажите ссылку.