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

Общая характеристика рассматриваемой темы. Становление теори и массового обслуживания связывают с непрерывным расширением телефонных сетей в крупных городах Европы и Америки и необходимостью решения задач о задержке вызовов в этих системах . Такие задачи были описаны еще в 1907 г . Ф.В . Иоханнсенном , а первые шаги по их решению предприняты в 1909 г . датским математиком А.К . Эрлангом . Чьи работы стали ядром классической теории массового обслуживания . Скачок в развитии вычислительной техники за последние несколько лет привёл к появлению нового важного направления – теории управляемых систем массового обслуживания , а также способствовал применению результатов исследований к важным практическим задачам . Это направление , в современной теории массового обслуживания , является одним из актуальных и перспективных . Со г ласно определению , данному УСМО в работе \2\ , управляемая система массового обслуживания – это такая система обслуживания , в которой параметры составляющих ее элементов (входные потоки требований , дисциплина очереди , структура системы , длительности и дисциплины обслуживания ) допускают управляющее воздействие . Необходимым условием полноты описания такой системы является задание правила 'стратегии ' использования управляющих воздействий во времени . Основываясь на работах \3,4\ можно предложить след у ющую (довольно условную ) классификацию , вытекающую из понятия УСМО : Ш системы с управляемым доступом требований в СМО ; Ш системы с управляемой интенсивностью обслуживания ; Ш системы с управляемой структурой ; Ш системы с управляемой дисциплиной обслужи вания ; Ш системы алгоритмического управления потоками заявок. В настоящей работе поставлен вопрос об исследовании систем обслуживания с переменной структурой , представляющих собой математические модели поведения сложных реальных объектов с управление м входными потоками требований в условиях их конфликтности . Прежде всего , сюда следует отнести системы управления движением транспорта на перекрестках , системы управления микросварочными комплексами при сборке интегральных микросхем , системы управления воздушным транспортом в аэропортах с несколькими взлетно-посадочными полосами . Базовый подход к анализу и оптимизации систем обслуживания с переменной структурой изложен в докторской диссертации \5\ М.А . Федоткина. Особое место среди приложений теории систем обслуживания с переменной структурой занимают задачи о регулировании дорожного движения . Злободневность этих задач определенна неизменно возрастающим парком автомобилей во всем мире и возникающими в связи с этим весьма острыми экономическими , эк о логическими и социальными проблемами . Анализ процессов управления конфликтными потоками для нескольких классов однородных алгоритмов содержится в работах М.А . Федоткина . Обычно , задачи оптимизации систем управления транспортными потоками решаются при наличии гипотезы о том , что система работает в стационарном режиме . Любопытны , так же и ситуации , когда из-за непредвиденных обстоятельств возникают даже не очень продолжительные задержки в работе обслуживающего устройства . Восстановление стационарно г о режима , после таких задержек , может быть довольно долгим по времени процессом . Большинство работ , касающихся решения транспортных задач , основано на предположении , что длительности интервалов между последовательными поступлениями машин в систему распре делены по показательному закону . Это позволяет представлять входные потоки потоками Пуассона . Однако при плохих погодных условиях нельзя говорить о независимости движения машин . Из-за затрудненного обгона на дороге образуются автоколонны – транспортн ы е пачки . В этом случае транспортные потоки не являются потоками Пуассона . Для потоков такой структуры адекватной математической моделью является поток Бартлетта . Математическое описание потоков требований , используемое в данной работе , выполнено в рамк ах нового нелокального подхода к изучению потоков заявок \5,6\. Цель данной работы. Ставится вопрос об исследовании динамики системы управления тремя конфликтными потоками требований , функционирующих в случайной среде (в данном случае – состояние погоды ), определяющей вероятностную структуру входных потоков , а так же влияющей на процесс обслуживания требований . В настоящей работе сделана попытка вероятностного описания функционирования системы управления конфликтными потоками требований в классе алгор и тмов с упреждением. Математическое описание элементов системы . 1. Описание работы системы на содержательном уровне. Вопрос о применении алгоритмов с обратной связью (учитывающих наличие и размер очередей , скорости поступления требований , интервал ме жду последовательными требованиями , тип требований и т.д .) возникает при более детальном рассмотрении так называемых циклических алгоритмов , в которых используется только информация о входных потоках и потоках насыщения . Такой режим управления (в котор о м обслуживание потоков требований происходит строго по заранее определённому закону ) чаще всего применяется в системах обслуживания с большой загрузкой , когда интенсивности поступления требований по различным потокам практически одинаковы . Тем не менее, в случае появления в потоках разрывов (нет поступающих заявок ), циклический способ управления является не целесообразным : для некоторого потока обслуживающее устройство работает в холостом режиме , в то время как по другим потокам имеются очереди заявок н а обслуживание . В таких случаях рациональнее применять другие управляющие алгоритмы , использующие дополнительную информацию о структуре входных потоков требований . Однако , воплощение в жизнь подобных алгоритмов требует применения дополнительных техни ч еских средств , а это тотчас приводит к удорожанию и усложнению системы обслуживания . Появляется вопрос о разработки простейших алгоритмов с обратной связью , использующие некоторую минимальную информацию о системе и не требуют применения сложных техниче с ких устройств . В настоящей работе рассмотрен простой алгоритм с обратной связью , представляющий собой модификацию циклического алгоритма , при котором априори выделяются наиболее интенсивные входные потоки , потоки наиболее важные в смысле оперативно с ти обслуживания и потоки малой интенсивности . В процессе обслуживания такой алгоритм учитывает наличие очередей по некоторым потокам , требующим быстрого обслуживания. Назовём потоки конфликтными , если , во-первых , невозможно суммировать некоторые потоки и свести задачу к одномерному случаю , во-вторых , обслуживание заявок конфликтных потоков осуществляется в непересекающиеся интервалы времени , в-третьих , существуют интервалы недоступности , в течение которых потоки не обслуживаются. Рассмотрим несколько примеров современных систем массового обслуживания , обладающих указанными выше особенностями : 1. Транспортные системы управления , в которых к потокам наибольшей интенсивности относятся потоки внутригородского общественного транспорта , к потокам с приор итетом в обслуживании – потоки , по которым нежелательно образование длинных очередей и , наконец , к малоинтенсивным потокам – потоки въезда и выезда из города . 2. При организации работы областной клинической больницы потоки поступающих больных также мо жно разделить на три группы : приоритетным является поток экстренных больных (при неотложных состояниях ), группу малоинтенсивных потоков образуют больные из других областей , наиболее интенсивный поток это больные из данной области. 3. Система регулирован ия пешеходных и транспортных потоков светофорами , управляющимися вызывной кнопкой. Ф ункциональная схема системы такого типа приведена на рисунке . Входные потоки формируются в некоторой случайной среде (СС ), состояние которой определяет вероятностную структуру этих потоков . Если среда находится в состоянии , то входные потоки представляют собой потоки типа Пуассона (потоки отдельных требований ). При состоянии среды входные потоки яв ляются потоками типа Бартлетта (потоки пачек ). Заявки входных потоков поступают в накопители (очереди ) с неограниченными емкостями . Далее будем считать : Ш Пот ок является малоинтенсивным информативным приоритетным потоком ; Ш Поток пре дставляет собой малоинтенсивный поток ; Ш Поток – приоритетный поток наибольшей интенсивности . Информативность потока означает , что в динамике работы системы обслуживания учитывается наличие заявок в накопителе и поступление требований по это му потоку . Его приоритетность – необходимость оперативного обслуживания поступающих требований . Приоритетность потока означает , что при отсутствии требований по поток у (разрыв ) будет продолжено обслуживание по потоку . В соответствии с этими соображениями организована работа обслуживающего устройства (ОУ ), имеющего 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/ получим утверждение доказываемой леммы. Итак , ассимптотическое поведение одномерного распределения случайного векторного процесса при не зависит от начального распределения . Заключение. В конце этой (весьма краткой ) работы хочется подвести итог того , что нами было уже сделано : Ш Была дана общая характеристика случайной среды , системы управления , приведена её функциональная схема ; Ш На содержательном уровне дано определение конфликтности и потоков насыщения системы ; Ш Приведено математическое описание составляющих элементов системы и построен маркированный случайный точечный процесс , моделирующий динамическое поведение системы ; Ш Была доказана теорема марковости выделенной дискретной к омпоненты процесса . Ш Выведены рекуррентные формулы для одномерных распределений дискретной компоненты маркированного точечного процесса . Литература. 1. Куделин А.Н. Модель управления конфликтными потоками в случайной среде : “ Теория вероятностей и математическая статистика . Д иссертация на соискание уч . степени кандидата ф.-м.н ” . 2. Бронштейн О.И . Рыков В.В ., Об оптимальных дисциплинах обслуживания в управляемых системах // В сборн . "Управление производством ", Тр . III Всесоюзн . совещ . по автоматическому управлению . Техническая кибернетика .- 1965.- М .: "Наука ", 1967. 3. Р ыков В.В. Управляемые системы массового обслуживания // Сборн . "Итоги науки . Теория вероятностей . Математическая статистика . Теоретическая кибернетика . ВИНИТИ АН СССР ". 4. Файнберг М.А ., Файнберг Е.А. Управление в системах массового обслуживания // "Зар убежная радиоэлектроника ". 5. Федоткин М.А. Теория дискретных систем с переменной структурой обслуживания квазигенерирующих потоков : "Теория вероятностей и математическая статистика . Диссертация на соискание уч . степени доктора ф.-м.н .". 6. Федоткин М.А. Неполное описание потоков неоднородных требований . -"Теория массов . обслуж ." 7. Чжун К. Л . Однородные цепи Маркова . – М .: Мир , 1964. 8. Феллер В. введение в теорию вероятностей и её приложения . Т .1, - М .: Мир , 1967. 9. Кантарович Л. В., Крылов В.И . Приблежённые методы высшего анализа . – М . – Л .: 'ГИФМЛ ', 1962.