Содержание к диссертации
Введение
Глава 1. Построение процессов обслуживания конфликтных потоков 32
1.1. Классические подходы к построению моделей систем массового обслуживания 32
1.2. Функционально-статистическое задание системы обслуживания как управляющей системы 49
Глава 2. Предельные теоремы для циклических процессов обслуживания формируемых в случайной среде конфликтных потоков 61
2.1. Тандем конфликтных систем обслуживания как управляющая система 62
2.2. Итеративно-мажорантный метод получения условий существования стационарного режима в конфликтных системах массового обслуживания в случайной среде 89
2.3. Стационарные характеристики потока повторных требований 132
Глава 3. Изучение процессов загрузки и разгрузки конфликтных систем обслуживания 160
3.1. Система обслуживания в классе алгоритмов разделения времени с переналадками как управляющая система 161
3.2. Условия существования и некоторые свойства стационарного режима процессов обслуживания в классе алгоритмов разделения времени в случайной среде 176
3.3. Минимизация средней стоимости пребывания требований в системе за такт 214
3.4. Оценки загрузки системы, среднего времени и средней сто имости пребывания произвольного требования с помощью имитационной модели 222
3.5. Подход к формализации понятия загрузки на основе функ ционалов Чжуна 236
Глава 4. Процессы обслуживания неординарных рекуррентных потоков. Конфликтные режимы 270
4.1. Управляющая система обслуживания конфликтных потоков с зависимыми интервалами между требованиями 271
4.2. Итеративно-мажорантный метод получения условий существования стационарного распределения общих цепей Маркова 281
4.3. Обслуживание потоков несколькими конфликтными циклическими алгоритмами 297
Заключение 324
Библиографический список использованной литературы
- Функционально-статистическое задание системы обслуживания как управляющей системы
- Итеративно-мажорантный метод получения условий существования стационарного режима в конфликтных системах массового обслуживания в случайной среде
- Условия существования и некоторые свойства стационарного режима процессов обслуживания в классе алгоритмов разделения времени в случайной среде
- Итеративно-мажорантный метод получения условий существования стационарного распределения общих цепей Маркова
Функционально-статистическое задание системы обслуживания как управляющей системы
Научная новизна. Все результаты являются новыми и состоят в следующем:
1. Дано представление о системе массового обслуживания как о стохастической абстрактной управляющей системе. Идентифицированы основные блоки управляющей системы обслуживания. Проведено нелокальное функционально-статистическое описание блоков. Сформулировано типовое утверждение о достаточности и непротиворечивости функционально-статистического описания управляющей системы обслуживания.
2. Область применения так называемого итеративно-мажорантного метода доказательства предельных теорем для конфликтных процессов обслуживания расширена на модели в виде общих цепей Маркова и марковских процессов с непрерывным временем и модели систем обслуживания, функционирующих в случайной среде.
3. Для изучения выходящих потоков в стационарном режиме системы с циклическим обслуживанием с переналадками использовано нелокальное описание в предположении, что первичные входящие потоки формируются во внешней случайной среде.
4. Поставлены и решены некоторые задачи оптимального управления для рассматриваемых конфликтных систем обслуживания. Для системы с конфликтными режимами обслуживания задача сведена к оптимизации управления марковской цепью с доходами и разработана программа для решения задачи методом последовательного улучшения управления. Для систем обслуживания по алгоритму с разделением времени и ветвящимися вторичными потоками изучена задача о минимизации средней стоимости пребывания требований в системе за такт. На имитационной модели изучено влияние выбора управления из класса приоритетных, «жадных» и пороговых управлений на среднее время пребывания в системе произвольного требования и на загрузку системы.
5. Введён новый функционал в теории марковских процессов с непрерывным временем, связанный с моментом достижения процессом одной области фазового пространства при запрете посещения другой области. Установлена связь рассматриваемого функционала с оптимизационной задачей о разгрузке конфликтных систем массового обслуживания.
Теоретическая и практическая значимость. Дан ная работа содержит в основном теоретические результаты. К ним относятся: новый формализованный подход к построению математических и имитационных моделей конфликтных систем массового обслуживания, развитие итеративно-мажорантного метода установления существования стационарного распределения марковских процессов различной природы, исследование свойств нового функционала от траекторий марковского процесса. Данные результаты представляют интерес для теории вероятностей, теории случайных процессов и теории математического моделирования. Значимость для теории массового обслуживания заключается в новых классах моделей систем массового обслуживания и в применяемом в работе нелокальном подходе к описанию потоков. В то же время, некоторые результаты и выводы носят практический характер: выявлены структуры оптимального управления несколькими различными системами массового обслуживания, в частности, объяснена оптимальность некоторых известных по литературе алгоритмов управления конфликтными потоками требований.
Методология и методы исследования.
В данной работе в основе методологии лежит единый принцип изучения конфликтных систем массового обслуживания как стохастических абстрактных управляющих систем. С его помощью строятся математические модели и компьютерная имитационная модель. Также используется аппарат теории вероятностей, теории случайных процессов, теории массового обслуживания, теории управляемых марковских процессов, математической статистики, теории функций комплексного переменного, методы линейной алгебры и матричного анализа. Для исследования конкретных многомерных цепей Маркова использу 18 ется модифицированный автором итеративно-мажорантный метод, методы теории управляемых марковских цепей и приём цензурирования счётной марковской цепи.
Для проведения численных экспериментов используется среда математических вычислений Octave, язык программирования C++ и программные средства организации параллельных вычислений. Обработка результатов имитационного моделирования производиться методами математической статистики.
Положения, выносимые на защиту.
1. Функционально-статистическое задание конфликтной системы обслуживания в виде стохастической абстрактной управляющей системы.
2. Построение случайных процессов обслуживания и управления конфликтными потоками в рамках аксиоматической модели теории вероятностей.
3. Метод доказательства предельных теорем для многомерных марковских процессов с дискретным и непрерывным временем.
4. Алгоритм численного нахождения стационарного распределения вероятностей для числа повторных требований в тандеме циклических систем массового обслуживания.
5. Оптимизационные вероятностные задачи управления конфликтными потоками на основе свойств функционалов с запретами от траекторий многомерных марковских процессов.
Достоверность результатов работы обеспечивается строгим применением используемого математического аппарата, корректным выбором используемых методик исследования и проведения вычислений, проведением статистических экспериментов на основе компьютерного имитационного моделирования, а также согласованностью результатов диссертации с некоторыми более ранними результатами разных авторов при рассмотрении некоторых частных случаев.
Итеративно-мажорантный метод получения условий существования стационарного режима в конфликтных системах массового обслуживания в случайной среде
Сформулированные в предыдущей главе функционально-статистические свойства блоков конфликтной управляющей системы привели в результате к основному изучаемому объекту — многомерной однородной счётной цепи Маркова (1.22). В настоящей главе диссертации развивается метод доказательства предельных теорем для таких цепей Маркова, основанный на изучении динамики одномерных распределений. С целью демонстрации метода выделен подкласс конфликтных управляющей систем обслуживания, соответствующий тандемам СМО с несколькими конфликтными входящими потоками, циклическим алгоритмом обслуживания и переналадками в каждом узле, немгновенным перемещением требований между узлами и с суперпозицией просеянных выходящих потоков. Под переналадкой будем понимать здесь и далее те операции обслуживающего устройства, которые не связаны непосредственно с обслуживанием требований. Наличие переналадок, таким образом, призвано разрешить конфликтность входящих потоков требований, а также осуществить внутреннюю перенастройку обслуживающего устройства. Модели с циклическим алгоритмом обслуживания уже рассматривались ранее как для транспортных сетей [2], так и для локальных вычислительных сетей с маркерным доступом [87]. Для изучения процессов обслуживания в сетях необходимо иметь вероятностное описание выходящих потоков в некоторых узлах, так как эти выходящие потоки участвуют в формировании входящих потоков других узлов. Однако проблема выходящего потока в классической постановке до настоящего времени не решена. В настоящей главе найдено стационарное распределение для потока перемещающихся между узлами требований при его нелокальном описании.
В настоящей главе рассматривается класс управляющих систем, конкретизирующий детали функционально-статистического описания управляющей системы обслуживания из 1.2. Пусть задан индекс ] є {2,3,..., m-2}, m = m и задано разбиение множества Г = {Г(1), Гга,..., Г(п)} на непересекающиеся множества Г 1 , ji = О, 1, ..., j, )i = 0, 1, ..., га — ] — 1. Допустим далее, что множества Т, j = 1, 2, ..., m — 1 вида Схема управляющей системы при m = 5, m = 5, j = 2 и d = 2 изображена на рис. 2.1. Данная схема содержит следующие блоки: 1) внешнюю среду (ВС); 2) входящие потоки Пі - П5 и потоки насыщения Пнас - Пнас; вых ттвых 1 5 . 3) блоки очередей Oi - 05; 4) устройства 61 - 65 организации дисциплины очереди; 5) обслуживающее устройство (ОУ); 6) блок реализации алгоритма управления потоками (граф смены состояний обслуживающего устройства); 7) выходящие потоки ГТ
Схема управляющей системы для двух сообщающихся конфликтных систем массового обслуживания в случайной среде с управлением потоками в классе циклических алгоритмов с переналадками
Изложим содержательную постановку задачи, приводящую к данному функционально-статистическому описанию управляющей системы. Рассмотрим две системы обслуживания. В первую систему поступают входящие потоки требований Пі, Т\г, а во вторую систему — входящие потоки Пз, П4. Входящие потоки Пь П2, П4 формируются во внешней случайной среде с конечным числом d состояний г(}, г(1, …, e(d). Смена состояния случайной среды может произойти только в моменты смены состояния любого из обслуживающих устройств. Вероятность смены состояния ем на ет равна акД. При состоянии среды е[к, к = 1, 2, …, d, требования по потоку П}, j = 1, 2, 4, поступают группами, так что поток групп — простейший с параметром Л- [123], а размер группы равен Ъ с вероятностью f(b;j,k). Входящий поток П3 образуется из повторных требований потоков Пь П2. А именно, требования потока Пі после обслуживания направляются на об 65
служивание во вторую систему; совокупность этих требований составляет входящий поток П5 требований. Обслуживание требований из потока П5 будет заключаться в перемещении из первой во вторую систему обслуживания. Каждое требование потока П2 после обслуживания и независимо от других требований либо мгновенно с вероятностью ос, 0 ос 1 начинает перемещение во вторую систему обслуживания и добавляется к потоку П5, либо с вероятностью 1 - ее покидает сообщающиеся системы обслуживания и добавляется к соответствующему выходящему потоку. Таким образом, из двух потоков, поступающих во вторую систему обслуживания, один образуется из потока повторных вызовов из первой системы. Предполагается, что необходимо время для того, чтобы заявка из первой системы достигла второй системы. Перемещение заявки из первой во вторую систему осуществляется со случайной скоростью, распределение которой неизвестно. Более того, скорости перемещения разных заявок различны и имеют разные законы распределения. В силу этого предполагаем, что за акт обслуживания или переналадки каждая перемещающаяся заявка либо достигает второй системы обслуживания с известной вероятностью, либо не достигает её. Выходящий поток заявок, обслуживание которых заключалось в перемещении из первой системы во вторую систему, и является, наконец, входящим потоком Пз второй системы. Требования потока nj поступают в очередь Oj неограниченного объёма, ) = 1, 2, …, 5.
Обслуживание конфликтных потоков Пь П2 и П3, П4 в каждой системе осуществляется в классе циклических алгоритмов с переналадками c фиксированным ритмом переключения. Для разрешения конфликтности потоков после каждого акта обслуживания требуется акт переналадки. За акт переналадки обслуживания требований не происходит. Это значит, что обслуживающее устройство в первой системе имеет четыре состояния Г(1 1), Г(2,1), Г(з,1), Г(4,1), и длительность пребывания прибора в состоянии Г не случайна и равна Т5,ь В состоянии Г(1 ]) обслуживаются только требования потока Пь в состоянии Г(3 ]) обслуживаются только требования потока П2, а в состояниях ТЫ) и Г осуществляется переналадка и требования не обслуживаются. Порядок смены состояний имеет вид Г Г 1 1 , г = 1, 2, 3, 4. Бинарная операция 0 была определена ранее на стр. 62. Обслуживающее устройство второй системы имеет также четыре состояния Г ,2\ Г(2,2)) Г(з,2)) Г(4,2)) длительность пребывания прибора в состоянии Г(5 2) не случайна и равна TS)2. В состоянии Г обслуживаются только требования потока Пз, в состоянии Г(3 2) обслуживаются только требования потока ГЦ, а в состояниях Г 2 2 и Г 4 2 осуществляется переналадка и требования не обслуживаются. Смена состояний осуществляется в порядке Г(г 2) - Г(г01 2). Величины Ti;i, 12,1, , Ту предполагаются соизмеримыми.
В дальнейшем удобно два обслуживающих устройства рассматривать как одно новое обслуживающее устройство с некоторым числом п циклически сменяемых состояний Г(1), Гга, ..., Г(п) и фиксированным временем Тг пребывания в состоянии Гм,1 г п. При этом число п и длительности Тг, 1 т п однозначно определяются по начальным состояниям Г 1 , Г г" в момент времени 0 и длительностям Ті;і, ..., Ту следующим образом. Пусть Т — наименьшее общее кратное длительностей Г = Ті,і + Т2,і + Т3,і + Т4,і и 1" = Ті;2+Т2,2+Тз,2+Т4,2- Пусть целые числа ті] и П2 определены равенствами
Условия существования и некоторые свойства стационарного режима процессов обслуживания в классе алгоритмов разделения времени в случайной среде
Физический смысл неравенств (2.46), (2.47) заключается в том, что среднее число требований, поступающих по потоку TTj за цикл, не должно быть больше «пропускной способности» Ц для очереди Oj,) = 1, 2, 4. Более полно следствие доказанной теоремы раскрывается следующим утверждением.
Теорема 2.5. Для каждого j = 1, 2 или 4 стохастическая последовательность {(ГІ(Ш), Kj,i(a ),Xi(a ));i = 0,1,...} (2.52) является однородной цепью Маркова с периодом п. Условие (2.47) является достаточным для существования единственного стационарного распределения для цепи Маркова (2.52). Доказательство. Зафиксируем т0 Є {1,2,..., п}, п Є {1,2,..., п}, …, г{ є є {1,2,...,п}, ко є {1,2,..., d}, ki є {1,2,...,d}, …, \c{ є {1,2,...,d}, x0 є Є {0,1,...}, x\ Є {0,1,...}, …, xj Є {0,1,...}. По свойству счётной аддитивности вероятности можем записать:
Вычислим внутреннюю сумму по Xі в правой части (2.53). В силу счётной аддитивности вероятности, рекуррентных соотношений (1.20), (2.5), формулы (2.1) и вида условных распределений (1.21)
Отсюда следует марковское свойство последовательности (2.52). Периодичность и сообщаемость всех состояний устанавливается, как при доказательстве теоремы 2.2. Известно, что для счётной однородной цепи Маркова может иметь место ровно одна из двух альтернатив: либо существует единственное стационарное распределение, либо вероятность любого состояния стремится к нулю независимо от начального распределения. Предположим, что неравенство (2.47) выполнено, но стационарного распределения не су ществует. Аналогично теореме 2.3 можно доказать, что в этом случае по следовательность {MKj)i(cu);i = 0,1,...} неограниченно возрастает. Но это противоречит второй части теоремы 2.4. Доказательство завершено. Для изучения динамики состояния блока О5 внешней памяти установим рекуррентные соотношения для производящих функций i(z;г,к).
С учётом этого функционального соотношения между случайными величинами Л5,іМ и Л1,гМ преобразуем выражение для Mi(z,r,l,k,x), вычитая и прибавляя под знаком математического ожидания случайную величину откуда получаем второе рекуррентное соотношение из утверждения леммы. Наконец, допустим, что Г(г0І) Є 2Г. В этом случае из свойств потоков насыщения имеем равенство сходятся в круге z 1 +. Тогда последовательность {Мк5)і(ш);і = 0,1,...} ограничена по г.
Доказательство. Мы утверждаем, что производящие функции 5,i(r,r, к) ограничены по абсолютной величине некоторой константой М. оо в круге z 1 + р, где 0 р е, а константа М зависит только от р. Поскольку оценка (2.51) остаётся в силе также и для ) = 5, то математические ожидания вещественных случайных величин К5,І(Ш), і = 0, 1, … будут равномерно ограничены по г. Таким образом, теорема будет доказана.
Для 1 z 1 + выполняются неравенства: zXl+b — z 1"1-1 0 при 0 b + xi Ui,b (1 -cc+az)X2+b-(1 -a+oz) 1-2 0 при 0 b+x2 Г01,2 и, наконец, (1 -ot+otz)l 2 z 1 2 . Поэтому, обозначив
На содержательном уровне утверждение теоремы 2.6 можно пояснить следующим образом. Поскольку на каждом такте функционирования системы убыль числа требований в очереди О5 в среднем пропорциональна длине этой очереди, то приток транспорта из очередей Oi, О2 существенно изменяет длину очереди О5, если только длина очереди О5 мала. В то же время, приток требований в очередь 05 из очередей О] и 02 ограничен неслучайными конечными характеристиками Г)і, tr потока насыщения. Поэтому даже в случае, когда длины очередей О і и 02 неограниченно возрастают, за большой промежуток времени длина очереди О5 должна колебаться около «равновесного значения», для которого доля требований, покинувших О5, в среднем равна числу требований потоков насыщения Пнас, Щас.
Введём в рассмотрение частичные производящие функции W3)5)i(zhz2;r,k) = M ( zf3 lMz5 l((u)I({a : Г-(ш ) = ГМ,ХІК) = e(k)}) ) . Используя маргинальные распределения марковский цепи (2.6), определение данных частичных производящих функций может быть выполнено в виде степенного ряда по переменным Z], Z2 следующим образом:
Из вероятностных соображений этот ряд сходится при Z] = Z2 = 1. В частности, при этих значениях переменных имеют место неравенства и все члены ряда (2.55) ограничены, что гарантирует абсолютную сходимость ряда в поликруге {(zi, z2): zi 1, z2 1} [129]. Известно, что дополнительные условия типа ограниченности всех членов ряда не могут быть отброшены совсем. А именно, известная теорема Абеля об абсолютной сходимости ряда по степеням одной переменной не имеет место для степенных рядов с несколькими переменными [6]. Нам будет необходимо рассматривать ряды 3,5,i(zi,Z2;r,lc) при действительных значениях ъ\ 1 и ъ\ 1. В силу того, что коэффициенты
Итеративно-мажорантный метод получения условий существования стационарного распределения общих цепей Маркова
Найдём условия, при которых состояния (Г , е ,0), к = 1, 2, …, d, со общаются с другими состояниями. Для того, чтобы состояние {V[s\ e[l\ w) Є Є S было достижимо из достаточно, чтобы существовала це почка состояний, ведущая из (Гм, е[к\х) в некоторое состояние (Г ,е ,0) за конечное число шагов и затем из также за ко нечное число шагов, и чтобы переход по этой цепочке имел положительную вероятность. Рассмотрим вспомогательную однородную марковскую цепь {Si(cu);i = = 0,1,...} с тем же множеством состояний S = Г х х Х(т), что и у це пи Маркова (3.4), и следующими переходными вероятностями. Состояния (Г(п),ем,0), к = 1, 2, …, d объявим поглощающими. Пусть вероятность перехода из состояния (Г(п), е[к\х), х Є Хг и к Є Cv_b v = 1, 2, …, v, в состояние (ГМ eN w), w є X, І є CV, равна ak)lp(w - х + y«;r,k), а вероятность перехода из состояния (Г ,е ,х), х Є Х т, к Є Cv_i, в со стояние равна аісд. На физическом уровне такая цепь описывает систему без первичных входящих потоков. С математической точки зрения положительные переходные вероятности во вспомогательной цепи Маркова могут быть получены из переходной вероятности цепи Мар кова (3.4) следующим образом. Следует в переходных вероятностях (3.6) (3.8) брать только слагаемые, соответствующие отсутствию первичных тре оо m бований, и опустить в этих слагаемых сомножители J ] [(pj(0;k, t) dBS2(t) и ЛІФіІ0; ) ). Наконец, чтобы полностью определить вспомога 0j=1 тельную цепь Маркова, примем, что начальное распределение сконцентрировано на единственном состоянии (ГЧе(Чо) є S, то є {1,2,...,m}, w0GX(m)\{6}, koG{1,2,...,d}.
Обозначим Qi(s,k,x) вероятность равенства Е ш) = (Г ,к,х), s = 1, 2, …, п, х Є Xм, к = 1, 2, …, d. Из определения цепи Маркова { (ш): і = = 0,1,...} имеем: Qo(r0,ko,w0) = 1 и Q0(s,k,w) =0, если либо s r0, либо w w0, либо к ко. В частности, Q0(n,k,6) = 0 для всех к = 1, 2, …, d. Далее, имеют место рекуррентные по і = 0, 1, … соотношения для т = 1,
Ясно, что если вероятность Qi0(s,x,l) для некоторого io 1 положительна, то существует положительная вероятность перехода цепи (3.4) за io шагов из состояния (ГЧеЧ0) в состояние (V \e \w). Для (комплексного) вектора z = (zb z2,..., zj и целочисленного вектора w = (wi, W2,..., wm) Є X под символом zw будем понимать произведение z 1 х z2 х ... х zm, в котором члены 0 полагается равным 1. Будем в дальнейшем обозначать вектор (1,1,..., 1) є X символом Т. Для s = 1, 2, ..., п, т = 1,2, …,тик = 1,2, …,d введём частичные производящие функции
Доказательство. Предположим, что для точки z, указанной в условии теоремы, выполнено неравенство R(z;r, к) 1 для всех т = 1, 2, …, га и к = 1, 2, …, d, однако также для всех і = 1, 2, … имеем Qi(n, к, б) = 0. Напомним, что Qo(n, к, б) = 0 по определению. Из определения производящих функций Wi(z\r,к) и (zjr,к), используя соотношения (3.12)-(3.14) и сделанные предположения относительно величин Qi(n,к, 0), находим:
Следовательно, ряды (z; т, к), (z; п, к), (z; т, к) с положительными членами сходятся в точке z, указанной в условии теоремы. Далее, из условия нормировки что противоречит первоначальной оценке (3.17). Итак, одновременное ра венство нулю всех величин Qi(n, к, б), к = 1, 2, …, d и і = 0, 1, … не может иметь места. Доказанная лемма позволяет выделить классы существенных состояний цепи Маркова (3.4). Теорема 3.2. Пусть для всех т= 1,2, …, тик= 1,2, …, d имеет место R(z;r,k) 1 в некоторой точке z = (zbz2,... ,zj с zi 1, z2 1, …, Zm 1. Пусть также для каждого к существует номер f = 1, 2, …, га такой, что вероятность р(б;т, к) строго положительна. Тогда при нечётном числе d все состояния цепи (3.4) образуют единственный класс существенных состояний, а при чётном d — два класса существенных состояний.
Доказательство. Проведем доказательство для случая нечётного d. До казательство для чётного d проводится аналогично. Покажем, что из любо го состояния (ГЧ еМ х) Є S в любое состояние (r4eN,w) Є S существует конечная цепочка состояний, переход по которой имеет строго положитель ную вероятность. С этой целью мы построим цепочку состояний, которая ведёт из состояния в некоторое состояние из множества {(Гы,е(к) 6): s = 1,2,...,n, к = 1,2,..., d}, затем двигается в этом множестве, приготовляясь к переходу среды в состояние e , и на последнем шаге получая требуемое число w требований в очередях. Пусть s п, тогда по лемме 3.1 существует способ перехода вспомогательной цепи в некоторое состояние из множества {(Г , г \ б); к = 1, 2,..., d} за io шагов. Обозначим этот путь символом С Тогда условная вероятность перехода по пути С цепи Маркова (3.4) не меньше условной вероятности совершить переход по тому же пути С и отсутствия первичных требований на каждом шаге этого перехода. Аналогично, если s = п, то достичь множества некоторого состояния (Г , е ,0), и кі Є Су для некоторого у = 1, 2, …, d. Определим величину т условием: р(б;т,к2) 0 для к2 Є Су+]. Положительную вероятность будет иметь переход из состояния [Г п\е \0) Є S в (Гм,е(к2),б) Є S, а затем в (Г(п), е(кз),0), к3 Є Cv+2. Для этого достаточно, чтобы единственное первичное требование поступило в очередь Ог и после обслуживания оно не породило ни одного вторичного требования, и за время обслуживания и переналадки не поступило ни одного первичного требования.