Содержание к диссертации
Введение
Глава 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
Библиографический список использованной литературы
- Функционально-статистическое задание системы обслуживания как управляющей системы
- Итеративно-мажорантный метод получения условий существования стационарного режима в конфликтных системах массового обслуживания в случайной среде
- Условия существования и некоторые свойства стационарного режима процессов обслуживания в классе алгоритмов разделения времени в случайной среде
- Итеративно-мажорантный метод получения условий существования стационарного распределения общих цепей Маркова
Функционально-статистическое задание системы обслуживания как управляющей системы
В работах [111, 112] был впервые предложен новый подход к построению моделей систем массового обслуживания. Согласно этому подходу систему массового обслуживания следует рассматривать как абстрактную управляющую систему [84] при наличии случайных факторов. Напомним, что понятие управляемой системы массового обслуживания, данное в [94], никак не связывалось с понятием управляющей системы из [84]. Впервые связи абстрактных управляющих систем и управляемых систем массового обслуживания были выявлены в [111]. В управляющей системе массового обслуживания выделяются семь стандартных блоков: внешняя среда, входные блоки, очереди, блоки стратегии механизма обслуживания, обслуживающее устройство, блок реализации алгоритма управления, выходные блоки. При рассмотрении системы массового обслуживания следует исходить из следующих принципов: 1) функционирование управляющей системы обслуживания происходит в дискретной временной шкале; 2) управляющая система обслуживания имеет схему со стандартными блоками, а при задании блоков системы следует использовать нелокальное описание [108], содержащее минимальную достаточную информацию; 3) следует выявлять как статистические, так и функциональные связи между блоками системы при её функционировании во времени. Для анализа и оптимизации построенной модели исследователь выбирает характеристики некоторых блоков системы. В настоящее время имеется положительный опыт применения такого подхода при построении математических и имитационных моделей управляющих систем массового обслуживания [59]. Преимущество данного подхода заключается в едином взгляде на управляющие системы. Более того, составные части реальных систем обслуживания могут рассматриваться как управляющие системы сами по себе. На этом пути в работах [117, 154] была построена адекватная модель процесса формирования транспортных «пачек» на автомагистралях. А в работах [92, 116] были построены и изучены математические модели нелокального описания выходящих потоков циклических систем массового обслуживания конфликтных пуассоновских потоков, либо потоков Гнеденко–Коваленко. Счи 14 талось, что входящие потоки не меняют своей вероятностной структуры во времени. Отметим, что в этих работах для исследования распределений вероятностей был использован метод производящих функций и отсутствовали численные примеры на нахождение соответствующих распределений. Функционально-статистическое задание применялось в работах автора [32, 34, 39, 41, 42, 44–48, 57, 59, 60, 62, 213, 217] для построения моделей следующих конфликтных управляющих систем массового обслуживания: 1) системы обслуживания формируемых в синхронной среде неординарных конфликтных потоков в классе алгоритмов с разделением времени и переналадками; 2) системы обслуживания формируемых в синхронной среде неординарных конфликтных потоков в классе циклических алгоритмов с продлением; 3) системы обслуживания неординарных рекуррентных потоков в классе циклических алгоритмов с переналадками; 4) тандема двух систем массового обслуживания с немгновенным перемещением требований между системами. Таким образом, можно заключить о том, что начинает развиваться новое направление в теории массового обслуживания, связанное с моделированием, анализом и оптимизацией неклассических управляющих систем обслуживания конфликтных потоков. Поскольку конфликтные управляющие системы обслуживания являются идеализацией многих реальных процессов обслуживания в условиях изменяющихся стохастических факторов, данное направление представляется актуальным.
При анализе построенной математической модели прежде всего возникают задачи явного вычисления основных характеристик системы на переходном процессе или в установившемся, стационарном режиме. В связи с этим ценность представляют методы отыскания необходимых и достаточных условий существования стационарного режима. Кроме того, такие условия представляют практический интерес сами по себе, если решить соответствующие уравнения и не удаётся. Ограничиваясь классом марковских моделей, можно сказать, что имеющиеся методы установления условий существования стационарного распределения у счётных цепей Маркова сводятся к следующим: 1) прямое решение уравнений стационарности и исследование условий, когда формальное решение имеет вероятностный смысл; 2) использование критериев, связанных со свойствами решений специально построенных систем линейных алгебраических уравнений или неравенств [19,119,156,185]; 3) изучение процесса «сноса», связанного с движением марковской цепи [68, 184]; 4) итеративно-мажорантный метод, связанный с изучением динамики одномерных распределений счётной цепи Маркова [109, 110]. Чаще всего в публикациях используется второй метод из перечисленных в форме «критерия Мустафы» [156, 185]. Однако для его применения необходимо «угадывать» решение соответствующих уравнений и неравенств, и этот процесс не алгоритмизирован. Некоторые рекомендации по построению функций Ляпунова для цепей Маркова типа случайных блужданий на целочисленных решётках малых размерностей приводятся в монографии [148]. В противоположность этому методу, итеративно-мажорантный метод носит алгоритмический характер и позволяет находить достаточное условие полуавтоматически. Поэтому видна насущность обобщения и распространения итеративно-мажорантного метода на широкие классы марковских цепей, на общие цепи Маркова с произвольным пространством состояний и процессы Маркова с непрерывным временем (скачкообразные процессы).
Цели и задачи диссертационной работы. Кцелям диссертационной работы относятся: выработка нового неклассического подхода к моделированию конфликтных управляющих систем массового обслуживания; развитие методов анализа и оптимизации таких систем, изучение новых целевых функционалов в теории управляемых случайных процессов. Для достижения целей решаются следующие задачи: 1. Выявление схемы конфликтной управляющей системы обслуживания, функциональных и статистических связей между блоками системы. Установление непротиворечивости функционально-статистического описания, достаточности и согласованности при построении соответствующего математического стохастического процесса. 2. Развитие методов получения условий существования стационарных распределений вероятностей многомерных стохастических процессов массового обслуживания.
Итеративно-мажорантный метод получения условий существования стационарного режима в конфликтных системах массового обслуживания в случайной среде
Понятие абстрактной управляющей системы было предложено в работе [84]. Данное понятие является первичным и призвано выявить общие закономерности строения и протекания процессов управления в реальных объектах. Сопоставление процессов обслуживания и управляющих систем впервые проведено в работах [111,112]. В данной диссертационной работе развивается точка зрения, согласно которой любая система массового обслуживания является управляющей системой.
Поблочное строение управляющей системы обслуживания удобно представить в виде наглядной схемы, содержащей следующие типовые блоки: внешняя среда, входные блоки, блоки очередей, блоки стратегии механизма обслуживания, блок обслуживающего устройства, блок реализации алгоритма управления потоками, выходные блоки. Примеры схем содержатся в следующих главах диссертации.
Рассмотрим последовательно составные блоки для произвольной системы массового обслуживания с точки зрения их описания. При этом будем считать, что уже выбрана дискретная временная шкала моментов {то, Т],...} наблюдения за системой. Часто в качестве моментов ть і = 0, 1, … выбирают моменты поступления требований в систему, либо моменты окончания обслуживания требований, либо моменты смены состояния обслуживающего устройства и т.д.
Блок внешней среды определяет вероятностную структуру входящих потоков системы. Пусть = { e Va ... } — множество возможных состояний внешней среды. В классических работах Эрланга, Хинчина, Гнеден-ко, Кендалла, Поллячека и др. фактически предполагалось, что внешняя среда имеет единственное состояние и вероятностная структура входящих потоков остаётся неизменной. Позднее, например, в работах Ньютса [187], считалось, что параметры входящих потоков зависят от состояния внешней среды. При этом состояния внешней среды могли меняться случайным образом, а именно, быть связанными в цепь Маркова с непрерывным временем. В настоящее время такие потоки изучаются в рамках теории дважды стохастических потоков [160]. При этом вопрос о том, как именно внешняя среда воздействует на пространственно-временную структуру входящих потоков, исследователями долгое время не ставился. В последнее время в некоторых работах (например, [93,113]) рассматриваются различные механизмы формирования потоков во внешней среде. Таким образом, внешняя среда может менять не только параметры входящих потоков, но и их вероятностную структуру. Группу входных блоков образуют входящие потоки системы обслуживания и потоки насыщения. Наиболее подробное описание потока требований П относится к наблюдению потока в любой момент времени t 0 и имеет одну из следующих эквивалентных форм [22,123]. 1. С помощью неубывающей случайной последовательности T TJ ... (1.15) Здесь величина т[ соответствует моменту времени (точке на оси времени Ot), когда поступает г-й вызов. Равенство вида т[ = т(+1 означает, что г-й вызов и (г+ 1 )-й вызов поступили одновременно. Таким образом, допускается поступление более одного вызова в один и тот же момент времени. Для фиксации вероятностных свойств потока при таком способе необходимо задать все конечномерные распределения последовательности (1.15). 2. С помощью стохастической последовательности {(т.",г,.");г = 1,2,...} (1.16) Здесь последовательность т { т { ... задаёт моменты поступления групп вызовов, а величины rf, і = 1, 2, … задают размеры групп. Для описания потока ГТ вида (1.16) требуется задать все конечномерные распределения последовательности (1.16). 3. С помощью случайного процесса {a" (t);t 0}, (1.17) где величина л "! -) задаёт число вызовов потока ГТ, поступивших за полуинтервал [0,t). В этом случае требуется указать все конечномерные распределения процесса (1.17). Для известного числа задач описание потока вида 1-3 получить не удаётся. Поэтому в работах [107,114] было предложено так называемое нелокальное (неполное) описание потока требований. Процитируем здесь соответствующее определение.
Определение 1.1. Пусть 0 = тн тн ... — последовательность точек на оси Ot (верхний символ «н» означает «наблюдение»), не обязательно совпадающая с (1.15), r\н — число требований потока П, поступивших на полуинтервале (тн,тн+1], и vt — некоторая характеристика (метка) требований, поступивших на полуинтервале (тгн,тгн+1]. Векторная случайная последовательность {«,Лгн г);г = 0,1,...} называется потоком неоднородных требований при его неполном (нелокальном) описанием.
Часто полагают, что метки V суть случайные элементы со значениями в некотором измеримом пространстве (М,М). При необходимости будем считать, что М — полное метрическое сепарабельное пространство, аМ — ст-алгебра его борелевских подмножеств. Пусть в системе обслуживания имеется 1 m оо входящих потоков требований Пь П2, …, Пд. Обозначим ци число требований, поступивших по входящему потоку nj на полуинтервале (ТІ, ТІ+І] , а v i — метку этих требований. Будем рассматривать входящие потоки Пь П2, …, Пд требований при нелокальном описании в виде маркированного точечного процесса Для задания свойств процесса обслуживания используются потоки насыщения nн ас, nн ас, …, П ас системы [109]. Содержательно, потоки насыщения суть виртуальные выходящие потоки системы массового обслуживания при неограниченном запасе ожидающих требований и максимальном использовании ресурсов обслуживающего устройства. Необходимость введения потоков насыщения возникает в силу того, что длительности обслуживаний различных требований могут определяться состоянием системы обслуживания и, как следствие, быть зависимыми и иметь разные отличающиеся законы распределения. Обозначим число требований по потоку nн ас на полуинтервале (тьті+і], а у — метку этих требований. Потоки насыщения рассматриваются ГТнас, Пн ас, …, П с при их нелокальном описании в виде маркированного точечного процесса
Условия существования и некоторые свойства стационарного режима процессов обслуживания в классе алгоритмов разделения времени в случайной среде
Вид рекуррентных соотношений в теореме 2.1 позволяет провести классификацию состояний цепи Маркова (2.6). В дальнейшем предполагаем, что состояния случайной среды образуют единственный апериодический неразложимый класс. Будем также считать, что 0 f(1;j,k) 1 для всех ) = 1, 2, 3, 4 и к = 1, 2, …, d, то есть существует положительная вероятность поступления одиночных требований по каждому потоку при каждом состоянии случайной среды. В дальнейшем будем использовать также величину Ц = 21ГЄІГ Т,І, выражающую максимально возможное число требований из очереди Oj, которое может быть обслужено за один цикл Г - Г - - ...- Г функционирования обслуживающего устройства.
Теорема 2.2. Множество Г х х Х(5) состояний марковской цепи (2.6) есть объединение незамкнутого множества S\ несущественных состояний и замкнутого множества Si U S2 U S3 существенных сообщающихся периоди 88 ческих состояний с периодом п. Доказательство. Заметим, что рекуррентные по і = 0, 1, … соотношения (2.7)-(2.34) являются прямыми уравнениями Колмогорова - Чепмена для счётной цепи Маркова (2.6) и содержат в себе, в частности, переходные вероятности этой цепи. Из соотношений (2.8), (2.17), (2.27) заключаем о том, что каждое состояние Ь не следует ни за каким состоянием из поэтому S\ — множество несущественных состояний.
Из предположения f(1;j,lc) 0 и разложения в степенной ряд в окрестности точки z = 0 вида заключаем о том, что величины cpj(b;k, t), b = 0, 1, … строго положительны. Поэтому все выписанные явно коэффициенты перед вероятностями Qi(r,k,xi,Х2,Хз,Х4, ) в равенствах (2.7)-(2.34) отличны от нуля. Обозначим О = {0,0,...,0) Є Xм нулевой вектор размерности т. Докажем, что все состояния из множества Si U S2 U S3 существенные. С этой целью установим, что состояние (Г ,е ,0) достижимо из любого состояния (rW,e ,w) Є Si U S2 U S3 и что, наоборот, произвольное состояние (Г ( w) Є Si US2US3 достижимо из (Г е О). Зафиксируем произвольное состояние (rw,eM,w) (Г(1), е(1),0) из Si U U S2 U S3, w = (wi,W2,W3,W4,w5). По предположению, марковская цепь {Хі{( ) Л = 0,1,...} эргодическая, следовательно, существуют такие нату-ральное t и состояния е , е , …, е 4 что положительна вероятность cik, akl)k2 х ... х akt)i перехода по пути e(kl e(k ... e(kt . Не уменьшая общности, можно считать, что t (j)_1WjTi для всех j = 1, 2, 3, 4 и что г 0 (t + 1) = 1. Веро ятность одновременного осуществления следующих событий оказывается положительной: а) все требования, поступающие в очередь 05, покидают её на следующем такте; б) требования потоков Пі, 1І2, ГЦ не поступают в течение t + 1 шагов цепи (2.6); в) все обслуженные требования из очереди О2 покидают систему, а не присоединяются к потоку ГТ5. Выбор значения t гарантирует, что все очереди через t + 1 шаг станут пусты. Чтобы достичь состояние (rw,e(k),w) (Г(1),е(1),б) из (Г(1),е(1),0), достаточно, чтобы тре бования из очереди О5 не уходили, а накапливались.
Итак, математической моделью тандема конфликтных систем массового обслуживания в классе циклических алгоритмов с переналадками в случайной среде является многомерная стохастическая последовательность (2.6) с пятью счётнозначными компонентами. Получение условий существования стационарного режима в таких процессах представляет собой нетривиальную задачу. В следующих разделах будет проведено исследование предельных свойств цепи Маркова (2.6) с помощью модифицированного итеративно-мажорантного метода.
Для получения условий существования стационарного распределения периодической многомерной цепи Маркова (2.6) нами будет использован итеративно-мажорантный метод. Особенностью применения данного метода к рассматриваемой системе является необходимость учитывать флуктуации интенсивностей входящих потоков, вызванные наличием внешней случайной среды. Одновременно будут найдены условия существования стационарных распределений для случайных процессов, получаемых рассмотре 90 нием только части компонент многомерных векторов (2.6). Установленная теоремой 2.2 классификация состояний цепи Маркова (2.6) позволяет доказать следующее важное утверждение. Теорема 2.3. Для существования единственного стационарного распределения у цепи Маркова (2.6) достаточно, чтобы последовательность {М(к1}і(ш) + К2,І(Ш) + К3,І(Ш) + К4,І(Ш) + К5,І(Ш));І = 0,1,...} (2.40) была ограниченной. Доказательство. Пусть последовательность (2.40) ограничена. Поскольку счётная цепь Маркова (2.6) имеет единственный класс сообщающихся состояний, только одна из двух альтернатив может иметь место [127]: либо существует единственное стационарное распределение, либо независимо от начального распределения выполнены предельные соотношения
Итеративно-мажорантный метод получения условий существования стационарного распределения общих цепей Маркова
Наряду с циклическими алгоритмами управления потоками неоднородных требований широко применяются алгоритмы динамического переключения обслуживающего устройства с учётом текущего состояния системы обслуживания на момент принятия решения. В этой главе внимание сконцентрировано на анализе и оптимизации моделей конфликтных систем обслуживания дважды стохастических конфликтных потоков в классе алгоритмов разделения времени с переналадками. Такие алгоритмы находят широкое применение в реальных системах передачи и обработки информации. С использованием развитого в предыдущей главе итеративно-мажорантный метод здесь устанавливаются предельные теоремы для изучаемого процесса обслуживания. Обращаясь к задаче выбора управления отметим, что возможно учитывать интересы единичных требований либо точку зрения обслуживающего устройства. В первом случае на практике рассматривается средняя стоимость пребывания всех требований в системе в единицу времени или за такт работы системы. Такая характеристика изучается в данной главе. Во втором случае основная характеристика — загрузка системы, понимаемая как доля времени, в течение которого обслуживающее устройство занято актами обслуживания и актами переналадки и управления. Найти явное выражение загрузки через параметры системы не удаётся. Здесь исследован вопрос о приближённом вычислении загрузки. В качестве альтернативы понятию загрузки в настоящей главе предлагается новый подход, основанный на свойствах некоторых функционалов от траекторий системы массового обслуживания, близкий по духу к задачам на быстродействие в классической теории оптимального управления.
В этой главе мы сохраняем обозначения 1.2. Пусть 1 d оо, 1 m оо m = 3m, n = m + 1. Схема управляющей системы обслуживания в классе алгоритмов разделения времени с переналадками приведена на рис. 3.1. На схеме присутствуют следующие блоки: 1) внешняя среда (ВС) с конечным числом d состояний; 2) входящие потоки Пі, П2, ..., П2т первичных требований, входящие потоки П2т+ь П2т+2, ., П3т вторичных требований и потоки насыщения nfac, nfс, ..., П ас; 3) блоки очередей О], 02, ..., От; 4) устройства 6Ь 62, ..., 6т по организации дисциплины очередей; 5) обслуживающее устройство (ОУ); 6) блок реализации алгоритма управления потоками (граф смены состояния обслуживающего устройства); 7) выходящие потоки ГТ ЫХ, 1І2ЬІХ, .. -П 1Х. при S = TL, X = с = 1, 2, … и b = в остальных случаях при нимает значение 0. Для описания блока реализации алгоритма управления введём отображение h(-): Х(т) - {1,2,..., т + 1} целочисленной неотрицательной решётки Xм такое, что прообразом точки n = m + 1 является только нулевой вектор б Є X. Определим отображение описывающая динамику изменения состояния обслуживающего устройства и внешней случайной среды, а также флуктуации длин очередей, при заданном распределении вектора (Г0(ш),хоМ, к0(ш)) является однородной марковской цепью.
Перечислим те физические предположения, которые приводят к только что сформулированным свойствам функционально-статистического описания. Пусть m оо конфликтных потоков П{, Щ, …, П формируются в случайной среде с d оо состояниями е, е«, …, е . Требования этих потоков будем называть первичными. При состоянии среды е к, к = 1, 2, …, d, требования по потоку П, ) = 1, 2, …, га, поступают группами, поток групп — пуассоновский с интенсивностью Л- , размеры групп суть независимые случайные величины. Группа содержит b требований с вероятностью f(b;j,k), b = 1, 2, …. Требования потока П помещаются в накопитель Oj неограниченного размера, Nj = оо. Требования обслуживаются поодиночке. Длительность обслуживания произвольного требования из накопителя Oj (обслуживание типа )) есть неотрицательная случайная величина с функцией распределения Bj(t). После каждого акта обслуживания прибор осуществляет внутреннюю переналадку с целью управления потоками и разрешения конфликтности. Длительность переналадки после обслуживания требования из очереди Oj также есть неотрицательная случайная величина с функцией распределения Bj (t). Если после переналадки очереди пусты, то на обслуживание выбирается первое вновь поступившее требование. Если, напротив, длины очередей составляют ненулевой вектор х = (хь х2,..., хт), то на обслуживание выбирается требование из очереди с номером ) = Н(х). После обслуживания типа ) требование порождает вторичные требования, которые образуют потоки TTJ , Щ, …, П. Вторичные требования потока П-" поступают в очередь Oj. При состоянии среды е совместное распределение числа порождённых вторичных требований задано многомерным распределением {p(y;j,k);y Є Xм}. Здесь для у = [yhy2,... ,ут) число p(ij;j,k) есть вероятность того, что в очередь Oi поступят у] требований, в очередь О2 — 1)2 требований и т.д., и наконец, в очередь От — ут требований, если состояние среды есть ем. Таким образом, входящие потоки системы складываются из входящих потоков первичных и вторичных требований. Смена состояний случайной среды может происходить только в моменты окончания обслуживания требования или окончания переналадки. Вероятность перехода среды из состояния е к, к = 1, 2, …, d, в состояние e[l, I = 1, 2, …, d, равна акД. Последовательность состояний случайной среды образует неразложимую марковскую цепь.
При переходе от содержательной постановки к формализованному функционально-статистическому заданию блоков учтены следующие соображения. Во-первых, реальный входящий поток П{ представлен в виде суперпозиции потоков nj и nm+j: поток nj содержит первую по окончании переналадки группу требований из Ш, когда очереди системы пусты, а поток nm+j содержит требования, поступившие по потоку П{ за акты обслуживания и акты переналадки и управления. Входной блок потока П2т+) есть