Содержание к диссертации
Введение
Часть 1. Марковские сети массового обслуживания. 18
Глава 1. Основные определения и леммы. Характеристики сетей массового обслуживания.
1.1. Основные определения. Зі
1.2. Основные леммы. 2
1.3. Основные характеристики сетей массового обслуживания и способы их определения.
Глава 2. Сети массового обслуживания Джексона. 5Ь
2.1. Постановка задачи.
2.2. Стационарные вероятности состояний сети Джексона. ^°
2.3. Нестационарное распределение вероятностей состояний сети Джексона
2.4. Нестационарное распределение вероятностей состояний сети Джексона с зависимыми от времени параметрами потока и обслуживания.
2.5. Нахождение нестационарного распределения вероятностей состояний сети Джексона методом итераций.
2.6. Стационарные вероятности для замкнутой сети Джексона. i
2.7. Нестационарные вероятности состояний замкнутой сети Джексона. 64
2.8. Нахождение нестационарного распределения вероятностей состояний замкнутой сети Джексона методом итераций. ?6і
Глава 3. Марковские сети с параметрами, зависящими от их состояния. гг
3.1. Постановка задачи. 2І
3.2. Стационарные вероятности состояний марковской сети с параметрами, зависящими от их состояния.
3.3. Марковские сети с зависимой циркуляцией. 2 *
3.4. Замкнутые марковские сети с зависимой циркуляцией. іс>3
3.5. Определение нестационарных вероятностей состояний обобщенной схемы обслуживания в простейших предпосылках методом итераций. \ os
Определение нестационарных вероятностей состояний марковских сетей с зависимой циркуляцией методом итераций.
3.7 Выражение характеристик сети через стационарное распре-деление вероятностей состояний. ^*
Глава 4. Марковские системы массового обслуживания с разными классами требований и параметрами, зависящими от их состояния.
13А
4.1. Постановка задачи. і д, 5"
4.2. Стационарные вероятности состояний марковской СМО с параметрами обслуживания, зависящими от ее состояния.
4.3. Стационарные вероятности состояний марковской СМО с параметрами входящего потока, зависящими от их состояния.
4.4. Стационарные вероятности состояний марковской СМО с разными классами требований и параметрами, зависящими от і за ее состояния.
Глава 5. Марковские сети с разными классами требований и параметрами, зависящими от их состояния.
5.1. Разомкнутая марковская СеМО. Постановка задачи.
5.2. Стационарное распределение вероятностей состояний для разомкнутой СеМО.
5.3. Марковские сети с разными классами требований и зависимой циркуляцией.
5.4. Нестационарный режим для СеМО с разными классами требований.
5.5. Замкнутая СеМО с разными классами требований.
Глава 6. Марковские сети массового обслуживания с различными каналами в узлах.
6.1. Многоканальная СМО с различными каналами. ^
6.2. Замкнутая марковская СеМО с обобщенной дисциплиной разделения процессора и различными каналами в узлах.
6.3. Замкнутая марковская СеМО с обобщенной дисциплиной разделения процессора и различными неравнодоступными каналами в узлах.
Глава 7. Другие марковские сети. 22^
7.1. Марковские сети с возможностью обхода узлов требованиями. % %»
7.2. Частные случаи. ^3
7.3. Замкнутые марковские сети с возможностью обхода узлов требованиями.
7.4. Разомкнутые марковские сети с возможностью обхода узлов требованиями и зависимостью интенсивности обслуживания от состояния сети. -2 $9
7.5. Марковские сети с ненадежными каналами обслуживания. А^4
7.6. Марковские сети с ненадежными каналами обслуживания и зависимостью интенсивности обслуживания от состояния сети. * 1
Комментарий к части 1.
Часть 2. Кусочно - линейные сети массового обслуживания. -2^
Глава 1. Сети со случайным выбором канала в узле и обобщенным разделением процессора.
1.1. Вступительные замечания. " "
1.2. Разомкнутая сеть случайным выбором канала в узле идисциплиной "обобщенное разделение процессора".
1.3. Стационарное распределение вероятностей состояний замкнутой СеМО.
1.4. Разомкнутая КЛСеМО с дисциплиной "обобщенное разделение процессора" и зависимостью скорости обслуживания от ее состояния.
1.5. Разомкнутая КЛСеМО с дисциплиной "обобщенное разделение процессора" и зависимостью параметров обслуживания и циркуляции от ее состояния.
1.6. Разомкнутая КЛСеМО с зависимостью параметровобслуживания, циркуляции и распределения требований по каналам от ее состояния.
1.7. Частный случай разомкнутой КЛСеМО с зависимостью Л параметров обслуживания и распределения требований по каналам от ее состояния.
1.8. Замкнутые КЛСеМО с зависимой циркуляцией. &ЗЇ
Глава 2. Кусочно - линейные сети с дисциплиной "обоб-щенное разделение процессора" и разными классами требований.
2.1. Разомкнутая сеть с дисциплиной "обобщенное разделениепроцессора" и разными классами требований.
2.2. Разомкнутая КЛСеМО с разными классами требований и параметрами потока, обслуживания и циркуляции, зависящими от ее состояния.
2.3. Стационарное распределение вероятностей состояний замкнутой КЛСеМО с требованиями разных классов.
2.4. Стационарное распределение вероятностей состояний зчо замкнутой КЛСеМО с требованиями разных классов и
зависимой циркуляцией.
Глава 3. Сети однолинейных систем массового 3^3
обслуживания требованной разных классов с абсолютным приоритетом поступающего требования и дообслу-живанием.
3.1. Однолинейная СМО с требованиями разных классов и *ч3 абсолютным приоритетом поступающего требования и дообслуживанием.
3.2. Разомкнутая СеМО однолинейных СМО. SS^
3.3. Разомкнутая СеМО однолинейных СМО с зависимой циркуляцией.
3.4. Замкнутая кусочно - линейная СеМО однолинейных СМО. 3?3
3.5. Замкнутая кусочно - линейная СеМО однолинейных СМО с зависимой циркуляцией.
3.6. Замкнутая КЛСеМО однолинейных СМО с зависимой 39i циркуляцией и сменой класса требования при переходе.
Глава 4. Сети однолинейных систем массового обслуживания с разделением процессора и обобщенным групповым обслуживанием (LBPS).
4.1. Система массового обслуживания с разделением процессора и 33 обобщенным групповым обслуживанием (LBPS).
4.2. Система массового обслуживания с дисциплиной LBPS и ЧЮ зависимостью параметров от дополнительных непрерывных компонент.
4.3. Разомкнутая сеть однолинейных систем массового обслужива- Ч і5 ния с разделением процессора и обобщенным групповым обслуживанием (LBPS).
4.4. Замкнутая сеть однолинейных систем массового обслужива- *ijL6 ния с разделением процессора и обобщенным групповым обслуживанием (LBPS).
Комментарий к части%., 43 2-
Часть 3. Кусочно - непрерывные сети массового Н З 5Г обслуживания.
Глава 1. Проблематика кусочно - непрерывных сетей ЧЪмассового обслуживания.
1.1. Краткое описание кусочно - непрерывной сети массовогообслуживания.
1.2. Актуальность исследования кусочно - непрерывных сетей массового обслуживания.
1.3. О мультипликативной форме. 433
1.4. Однолинейная система обслуживания с ограниченной емкостью для содержания требований.
Глава 2. Кусочно - непрерывные марковские процессы. Чнб
2.1. Краткое описание кусочно - непрерывного марковского процесса.
Простейший кусочно - непрерывный марковский процесс. ^
Определение характеристик потока событий, порожденных кусочно непрерывным марковским процессом.
О связи стационарных вероятностей состояний кусочно - 4 б?2
непрерывного марковского процесса в моменты произвольный, поступления и ухода требований.
Глава 3. Сети с дисциплиной обслуживания "обобщенно разделение процессора".
Система с дисциплиной обслуживания "обобщенное 4g
разделение процессора".
Разомкнутая сеть массового обслуживания с дисциплиной "обобщенное разделение процессора".
Стационарное распределение вероятностей состояний замкну- той СеМО.
Разомкнутая сеть с дисциплиной "обобщенное разделение процессора" и зависимостью скорости обслуживания от ее состояния.
Разомкнутая сеть с дисциплиной "обобщенное разделение про-цессора" и зависимостью параметров обслуживания и цирку» ляции от ее состояния.
Глава 4. Сети с дисциплиной обслуживания "обобщенноеразделение процессора" и разными классами требований.
Система с дисциплиной обслуживания "обобщенное разделение процессора" и разными классами требований.
Разомкнутая сеть с дисциплиной обслуживания "обобщенное разделение процессора" и разными классами требований.
Разомкнутая сеть с разными классами требований и пара-метрами потока, обслуживания и циркуляции, зависящими от ее состояния.
Стационарное распределение вероятностей состояний замкну» той сети с требованиями разных классов.
Стационарное распределение вероятностей состояний замкну-той сети с требованиями разных классов и зависимой циркуляцией.
Глава 5. Сети однолинейных систем массового обслуживания требований разных классов с абсолютным приоритетом поступающего требования и дообслуживанием и зависимостью параметров СеМо от их состояния.
5.1. Однолинейная СМО с требованиями разных классов абсолют- 6і-о
ным приоритетом поступающего требования и дообслужи-ванием.
5.2. Разомкнутая СеМО однолинейных СМО. 13
5.3. Разомкнутая СеМО однолинейных СМО с зависимой цирку- 33 ляцией.
5.4. Замкнутая СеМО однолинейных СМО. Q4&
5.5. Замкнутая КНСеМО однолинейных СМО с зависимой цирку- й$Н ляцией.
5.6. Замкнутая КНСеМО с зависимой циркуляцией и сменой класса требования при переходе.
Глава 6. Сети массового обслуживания с конкретными ви- дами зависимой циркуляци.
6.1. Замкнутая звездообразная сеть массового обслуживания при зависимости вероятностей перехода от состояний узлов.
6.2. Замкнутая звездообразная СеМО с зависимой циркуляцией,обобщенной дисциплиной разделения процессора и различными неравнодоступными каналами в узлах.
Разомкнутая сеть однолинейных систем с потерями.
Глава 7. Сети массового обслуживания с различными ка-налами в узлах.
7.1. Многоканальная СМО с потерями. 7^ з
7.2. Замкнутая СеМО с обобщенной дисциплиной разделения чгц процессора и различными каналами в узлах.
7.3. Замкнутая СеМО с обобщенной дисциплиной разделения процессора и различными неравнодоступными каналами в узлах.
Комментарий к части 3.
Заключение 75^
Литература
Введение к работе
В настоящее время в связи с развитием процессов информатизации в большинстве стран, информационно-вычислительных систем, систем связи и передачи данных, глобализацией экономических связей и структур, международным разделением труда в процессе производства значительной части промышленной продукции, транспортных систем для обслуживания этого разделения труда, усложнением самого процесса производства этой продукции и т.п. весьма актуальными становятся сетевые модели, с достаточно высокой степенью адекватности описывающие эти процессы и помогающие тем самым находить рациональные решения для таких сложных систем.
Одними из наиболее часто применяющихся сетевых моделей, связанных с взаимоувязкой во времени процессов функционирования множества разнородных подсистем, из которых состоят вышеуказанные сложные системы, являются сети массового обслуживания.
Сети массового обслуживания являются достаточно адекватными моделями самой ЭВМ, локальных сетей ЭВМ и ПЭВМ, информационно-вычислительных сетей, сетей связи и передачи данных, транспортных сетей, производственных сетей и т.д.. Возникнув как модели ЭВМ и сетей ЭВМ, они интенсивно расширяют области своего применения.
Сети массового обслуживания состоят из конечного числа узлов и характеризуются входящим потоком требований, нуждающихся в обслуживании в узлах, дисциплинами обслуживания в узлах, характером циркуляции требований по узлам, распределениями длительностей обслуживания в узлах и т.д.
Первая работа по сетям массового обслуживания появилась в 1957 г. Это знаменитая статья Джексона по разомкнутым экспонен циальным сетям массового обслуживания ( с входящим пуассонов-ским потоком и экспоненциально распределенной длительностью обслуживания), в которых закончившее обслуживаться требование направлялось в другой узел с определенной вероятностью (марковская маршрутизация). Гордон и Ньюэлл получили соответствующие результаты по таким же, но замкнутым экспоненциальным сетям массового обслуживания через 10 лет в 1967 г. В 1968 г. Познер и Бернхольц обобщили эти результаты на случай разных классов требований. В 1972 было опубликовано 3 работы. В 1973 г. - одна (Бьюзен, 1973 г., по алгоритмам расчета нормирующих констант). В 1974 г. - 5 работ, в 1975 г. - 11 работ ( по данным, доступным автору) В этом же году была опубликована знаменитая теорема ВСМР
( Baskett, Chandy, Muntz, Palacios) по сетям массового обслуживания с разными дисциплинами обслуживания, длительностями обслуживания, преобразования Лапласа которых являются дробно-рациональными функциями, и марковской маршрутизацией. В этом же году была опубликована статья Келли по сетям массового обслуживания с детерминированной маршрутизацией, т.е. маршрут движения требования по узлам задавался детерминировано. С тех пор оба этих направлений стали интенсивно развиваться и количество публикуемых ежегодно статей стало исчисляться десятками и сотнями. Появились обзоры работ по сетям массового обслуживания. В СССР первый такой обзор под названием " Сети массового обслуживания и их применение в ЭВМ " был опубликован автором в 1977 г. [14 в лит. к ч. lj. Затем в 1983 г. был опубликован Башариным Г. П. и Толмачевым А.Л. обзор под названием " Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислит В 1979 г. появилась первая монография по аналитическим методам расчета характеристик сетей массового обслуживания (с детерминированной маршрутизацией). Она принадлежала Келли. В этом же году появилась монография по расчету характеристик сетей массового обслуживания методом статистического моделированию с помощью регенерирующих случайных процессов. Ее авторами были Иглхарт и Шедлер.
К настоящему времени по сетям массового обслуживания имеются уже тысячи публикаций, изучены самые разнообразные сети с различными особенностями, присущими реальным сетям. Опубликовано 13 монографий. Получено много прекрасных результатов. Вместе с тем целесообразна выработка единого подхода к методике аналитического исследования характеристик разнообразных сетей массового обслуживания.
Такая попытка и предпринята в настоящейработе. В ней выработан единый подход к методике аналитического исследования характеристик разнообразных сетей массового обслуживания, базирующийся на:
- формировании для каждой рассматриваемой сети массового обслуживания посредством расширения пространства состояний соответствующего марковского процесса,
- составлении системы линейных дифференциальных уравнений для нестационарного режима или линейных алгебраических уравнений для стационарного режима для вероятностей состояний марковского процесса ( для марковских сетей ), составлении системы дифференциальных уравнений в частных производных в стационарном режиме для функций распределения вероятностей состояний марковского процесса ( с добавлением непрерывных переменных, эти состояния марковского про цесса называются микросостояниями ) для кусочно-линейных сетей массового обслуживания. Эти непрерывные переменные уменьшаются по кусочно-линейному закону, т.е. скорость обслуживания является кусочно-постоянной функцией от них, поэтому такие сети называются кусочно-линейными сетями массового обслуживания, составлении системы дифференциальных уравнений в частных производных в стационарном режиме для плотностей распределения вероятностей микросостояний марковского процесса для кусочно-непрерывных сетей массового обслуживания. Эти непрерывные переменные уменьшаются по кусочно-непрерывному закону, т.е. скорость обслуживания (их уменьшения ) является кусочно-непрерывной функцией от самих непрерывных переменных, поэтому такие сети называются кусочно- непрерывными сетями массового обслуживания,
- получении аналитического решения (точного или приближенного) для системы линейных дифференциальных уравнений для нестационарного режима или точного аналитического решения для системы линейных алгебраических уравнений для стационарного режима для вероятностей состояний марковского процесса ( для марковских сетей ),
- получении точного аналитического решения для системы дифференциальных уравнений в частных производных в стационарном режиме для функций распределения вероятностей микросостояний марковского процесса для кусочно-линейных сетей массового обслуживания, а затем по ним и распределения вероятностей состоя-ний марковского процесса в части дискретных компонент (которое называем для краткости распределением вероятностей состояний марковского процесса),
- получении точного аналитического решения для системы дифференциальных уравнений в частных производных в стационарном режиме для плотностей распределения вероятностей микросостояний марковского процесса для кусочно-непрерывных сетей массового обслуживания, а затем по ним и распределения вероятностей состояний марковского процесса с учетом сказанного выше,
- нахождении необходимых и достаточных условий на исходные данные сетей массового обслуживания для представления вышеуказанных распределений в полученном аналитическом виде,
- нахождении достаточных условий на исходные данные сетей массового обслуживания для регулярности и эргодичности рассматриваемого марковского процесса.
Основное внимание уделяется нахождению аналитического вида распределений вероятностей состояний исследуемой сети, так как по этому распределению можно определять наиболее употребительные основные характеристики сетей массового обслуживания как моделей реальных вышеуказанных сложных систем.
Сети массового обслуживания как обобщения систем массового обслуживания позволяют найти простые объяснения некоторым феноменам систем массового обслуживания, которые казались загадочными . В качестве примера такого феномена приведем любопытный факт - доказанную рядом авторов ( Абольников [1 в лит. к ч.і], Ивницкий [13 там же]и др.) инверсность системы М/G/l с ограниченной очередью и резервированной системы типа G/M/1. Приведем соответствующее утверждение без формульных записей.
Утверждение состоит в следующем: если для системы М/G/l с ограниченной очередью и резервированной системы типа G/M/1, могущих содержать одинаковое максмальное количество требований, инверсны последовательности начальных условий и исходных данных, то инверсны и последовательности их выходных характеристик - распределений числа требований в системах.
Эта инверсность находит очень простое объяснение, если рассмотреть замкнутую сеть массового обслуживания, состоящую из двух узлов, один из которых имеет произвольное распределение длительности обслуживания, а второй - экспоненциальное распределение длительности обслуживания.
Рассматриваются сети массового обслуживания в следующих предпосылках:
1. Входящий в сеть поток требований является входящим потоком марковского типа, т.е. пуассоновским потоком с интенсивностью, зависящей от состояния сети или ее агрегированных показателей.
2. Осуществлялось стремление к максимальному учету зависимостей параметров входящего потока, дисциплины обслуживания, распределений длительностей обслуживания, циркуляции требований по сети (переходных вероятностей) от состояния сети или ее агрегированных показателей в рамках получения аналитических решений соответствующих систем уравнений.
3. Рассматриваются в возможно более общих предпосылках сети массового обслуживания в математическом аспекте. Вопросы интерпретации и применения полученных результатов с учетом реальных особенностей к конкретным сетям, моделирующим функционирование вышеуказанных сложных систем, остаются прерогативой специалистов в этих областях.
4. Необходимые и достаточные условия для представления полученных результатов в представленном аналитическом виде формулируются для известных исходных данных исследуемых сетей массового обслуживания, что позволяет их легко проверить.
5. Вводится и широко используется для доказательства необходимости понятие "взаимной независимости" исходных данных, что имеет достаточно прозрачный смысл: изменение одних исходных данных никак не сказывается на значениях других исходных данных сети массового обслуживания.
6. Вводятся в рассмотрение сети массового обслуживания, у которых скорость обслуживания требования ( скорость уменьшения оставшегося количества работы по обслуживанию требования ) зависит от оставшегося количества работы по его обслуживанию, что существенно расширяет класс сетей массового обслуживания, поддающихся аналитическому исследованию.
7. Как правило, изложение начинается с рассмотрения соответствующей системы массового обслуживания, на примере которой проявляются определенные закономерности, которые затем развиваются и обобщаются на сети массового обслуживания данного класса. Сами же сети исследуются в естественном порядке нарастания сложности и общности.
Диссертация состоит из J частей. В первой части приводятся основные определения и леммы и рассматриваются марковские сети массового обслуживания. Сначала рассматриваются сети Джексона, в том числе, и в нестационарном режиме, для которого получены точные (для определенных начальных условий) и приближенные
( для произвольных начальных условий) решения. Далее исследуются марковские сети с параметрами, зависящими от их состояния, марковские сети с разными классами требований. Здесь уже существенно используется известное условие Коваленко, обобщенное в требуемой степени. Затем рассматриваются марковские сети с различными каналами в узлах, с возможностью обходов узлов требованиями, с ненадежными каналами обслуживания.
Кусочно-линейным сетям массового обслуживания посвящена вторая часть. Исследуются разомкнутые и замкнутые сети со случайным выбором канала в узле, обобщенным разделением процессора и марковской маршрутизацией, что является в определенной степени обобщением сетей BSMP. Затем рассматривается зависимость параметров обслуживания и циркуляции требований по узлам от состояния сети. Далее исследуются такие же сети, но с разными классами требований и учитывается зависимость параметров входящего потока от наполненности сети требованиями разных классов. Здесь также существенно используется обобщенное условие Коваленко, для установления инвариантности стационарного распределения вероятностей состояний.
Затем рассматриваются сети однолинейных систем массового обслуживания требований разных классов с абсолютным приоритетом поступающего требования и дообслуживанием, причем как параметры потока, так и параметры обслуживания зависят и от непрерывных компонент состояния узла кроме обслуживающегося требования. Исследуются также сети однолинейных систем массового обслуживания требований разных классов с разделением процессо-ра и обобщенным групповым обслуживанием ( last-batch-processor-sharing ), введенным Ноетзелом. Эта дисциплина обобщает ряд известных дисциплин обслуживания.
Кусочно-непрерывным сетям массового обслуживания посвящена третья часть. Дается кратко проблематика кусочно-непрерывных сетей массового обслуживания, краткое описание кусочно-непрерывных марковских процессов, используемых далее для исследования таких сетей. Определяются характеристики потока событий, порожденных кусочно-непрерывными марковскими процессами, связи стационарных вероятностей состояний этих процессов в моменты произвольный, поступления и ухода требований.
Кусочно-непрерывные сети массового обслуживания являются совершенно новым объектом математического исследования. Для них скорость обслуживания требования зависит от оставшегося количества работы по обслуживанию этого же требования. В силу этого приходится составлять дифференциальные уравнения в частных производных для плотностей вероятностей микросостояний и они в известной степени усложняются. Однако при определенных условиях на исходные данные можно получать аналитические решения этих уравнений. Они и приводятся в этой части.
Исследуются кусочно-непрерывные сети массового обслуживания с дисциплиной "обобщенное разделение процессора" и зависимостью параметров обслуживания и циркуляции от их состояния в части дискретных компонент. Затем эти результаты обобщаются на случай требований разных классов.
Рассматриваются также разомкнутые и замкнутые кусочно-непрерывные сети однолинейных систем массового обслуживания требований разных классов с абсолютным приоритетом поступающего требования и дообслуживанием, причем как параметры потока, так и параметры обслуживания зависят и от непрерывных компонент состояния узла, в том числе и от непрерывной компоненты обслуживающегося требования.
Затем рассматриваются замкнутые звездообразные кусочно-непрерывные сети массового обслуживания с конкретными видами зависимой циркуляции, с обобщенной дисциплиной разделения процессора, различными неравнодоступными каналами в узлах, разомкнутые кусочно-непрерывные сети массового обслуживания однолинейных систем с потерями. Далее исследуются замкнутые кусочно-непрерывные сети массового обслуживания с обобщенной дисциплиной разделения процессора и различными каналами в узлах, в том числе и неравнодоступными.
Нумерация формул отдельная в каждом параграфе. При ссылках иц теоремы и формулы из других параграфов, глав, частей указывается номер части, номер главы и номер соответствующего параграфа.
