Содержание к диссертации
Введение
Глава 1. Обзор основных результатов по сетям массового обслуживания с управлением потоками 9
1.1. Оптимальное управление интенсивностями обслуживания . 9
1.2. Оптимальное управление маршрутизацией 14
1.3. Оптимальное управление потоками 20
Глава 2. Оптимизация потоков в сетях массового обслуживания . 27
2.1. Определение векторов относительных интенсивностей потоков для открытых сетей обслуживания 28
2.2. Определение векторов относительных интенсивностей потоков для замкнутых сетей обслуживания 36
2.3. Построение множества векторов относительных интенсивностей потоков 43
2.4. Метод формирования маршрутных матриц 48
Глава 3. Динамическое управление потоками в сетях массового обслуживания 51
3.1 Открытые сети обслуживания 51
3.2. Открытые сети с параллельными системами массового обслуживания . 55
3.3. Замкнутые сети обслуживания 59
3.4. Стационарное распределение сетей обслуживания с управлением потоками 65
Глава 4. Исследование сетей массового обслуживания с управлением потоками 73
4.1. Исследование открытых сетей обслуживания 73
4.2. Исследование эффективности метода динамического управления потоками 81
4.3. Исследование замкнутых сетей обслуживания 88
Заключение 95
Список литературы 96
- Оптимальное управление маршрутизацией
- Определение векторов относительных интенсивностей потоков для замкнутых сетей обслуживания
- Открытые сети с параллельными системами массового обслуживания
- Исследование эффективности метода динамического управления потоками
Введение к работе
Характерной чертой современного этапа развития общества является все более широкое распространение и использование больших сложных систем с сетевой структурой и стохастическим характером функционирования (БСС) (примерами систем этого класса могут служить информационно-вычислительные сети, сети передачи данных, гибкие производственные системы). Структурная и функциональная специфика систем этого класса и использование в этих системах развитых подсистем управления со сложными алгоритмами управления существенно затрудняют решение задач анализа, синтеза и оптимизации систем этого класса, возникающих при их проектировании и эксплуатации. В связи с этим в значительной степени возрастают требования к используемым при решении этих задач математическим моделям и методам. Практический опыт решения этих задач показал перспективность и эффективность использования сетей массового обслуживания (СеМО) в качестве математических моделей сложных стохастических систем с сетевой структурой.
Отображение в модельных СеМО средств и методов управления БСС приводит к построению сетей обслуживания с управлением, которые фактически являются подклассом сетей массового обслуживания. СеМО с управлением обеспечивают не только принципиальную возможность решения целого класса задач анализа и синтеза БСС, но и возможность решения ряда задач, связанных с повышением эффективности управления БСС.
Большой вклад в развитие теории, методов анализа, оптимизации и синтеза сетей массового обслуживания внесли А. А. Боровков, Г. П. Башарин, В. М. Вишневский, П. П. Бочаров, В. А. Ивницкий, В. В. Рыков, Ю. В. Солодянников, А. В. Печинкин. Среди зарубежных специалистов необходимо отметить таких ученых, как Дж. Джексон, Л. Клейнрок, Ф. Келли, К. Чэнди, А. Лазар, Д. Тауслей.
Среди задач управления сетями обслуживания можно считать одной из наиболее приоритетных в теоретическом и прикладном отношении задачу оптимального управления потоками требований в сетях в силу существенного влияния потоков на характеристики качества функционирования сетей.
В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном университете по темам, включенным в план НИР СГУ: «Математическое моделирование сетей передачи данных и информационно-вычислительных сетей» (шифр «Сеть», гос. per. № 01930007385), «Управление сетями массового обслуживания» (шифр «Контур», гос. per. № 01930007386), «Теория и методы управления сетями массового обслуживания» (шифр «Звено», гос. per. №01960007744), «Синтез сетей массового обслуживания с управлением» (шифр «Такт», гос. per. № 01200001098), раздел «Математические задачи синтеза сетей массового обслуживания с динамическим управлением» госбюджетной темы «Разработка и применение фундаментальных методов исследования задач математического анализа, дифференциальных уравнений, дискретной математики, теории упругости и газодинамики» (шифр «Интеграл», гос. per. № 01200002986).
Целью диссертационной работы является развитие теории сетей массового обслуживания с управлением и методов их анализа и синтеза, разработка эффективных методов статического и динамического управления потоками в сетях массового обслуживания.
Основными задачами, решаемыми в диссертации, являются следующие.
Разработка методов оптимального управления потоками в сетях массового обслуживания.
Разработка методов оптимизации маршрутных матриц сетей массового обслуживания.
Анализ сетей обслуживания с управлением потоками.
В диссертационной работе использовались результаты теории вероятностей, теории марковских процессов, теории массового обслуживания, теории сетей массового обслуживания.
В диссертационной работе получены следующие основные результаты.
Разработаны методы оптимального управления потоками в сетях массового обслуживания.
Разработаны методы оптимизации маршрутных матриц сетей массового обслуживания.
Получены основные характеристики сетей массового обслуживания с управлением потоками.
Постановка задач, методы решения и полученные результаты являются новыми.
Практическая значимость представленных в диссертационной работе результатов заключается в возможности применения рассмотренных методов оптимального управления потоками в сетях массового обслуживания, методов анализа и синтеза сетей массового обслуживания с управлением в математических моделях больших сложных систем а сетевой структурой и стохастическим характером функционирования. Использование моделей этого вида позволит расширить круг задач анализа и синтеза систем этого класса и повысить эффективность их решения.
Научные положения и методы, разработанные в диссертации, используются в учебном процессе Саратовского государственного университета.
Основные результаты диссертации опубликованы в работах [28-31, 41-44]. Результаты докладывались и обсуждались на научных семинарах кафедры системного анализа и автоматического управления Саратовского государственного университета, Первом и Втором Всероссийских симпозиумах по прикладной и промышленной математике (1-6 июня 2000г., г. Петрозаводск; 1-6 июля 2001г., г. Самара), представлены и обсуждались на Четвертой международной научно-технической конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (10-12 декабря 2001г., г. Ульяновск), Международной научной конференции «Компьютерные науки и информационные технологии» (14-18 мая 2002г., г. Саратов).
Результаты диссертационной работы получены автором самостоятельно. Научный руководитель — доктор технических наук, профессор
Ю. И. Митрофанов, соавтор совместных публикаций [28-31], принимал участие в постановке задач, решаемых в диссертационной работе, в разработке концепций оптимального управления потоками в сетях массового обслуживания, в формировании идей доказательств некоторых утверждений.
Диссертация состоит из введения, четырех глав, заключения, списка литературы. Объем диссертации 103 страницы. Диссертация содержит 17 таблиц. Список литературы включает 79 наименований.
В первой главе представлен обзор основных результатов по теории сетей массового обслуживания с управлением интенсивностями обслуживания, сетей обслуживания с управлением маршрутизацией, а также методам анализа и синтеза сетей обслуживания с оптимальным управлением потоками. В работах [9, 10, 21, 35, 37, 40, 45, 48, 53, 64, 65, 69, 70, 76, 78] рассматриваются методы управления интенсивностями обслуживания и методы построения оптимальных правил выбора интенсивностей обслуживания в сетях массового обслуживания. В работах [1, 11, 15, 18, 20, 22, 32, 33, 36, 47, 49, 51, 55, 59, 62, 67, 72, 74] изучаются методы управления маршрутизацией в сетях обслуживания, исследуются характеристики сетей обслуживания с различными методами маршрутизации, разрабатываются методы оптимальной маршрутизации потоков требований. В работах [14, 19, 23, 52, 75] доказывается существование стационарного распределения вероятностей состояний сетей массового обслуживания с управлением маршрутизацией в мультипликативной форме. В работах [63, 66, 68, 71, 73, 77] предлагаются методы построения оптимальных стратегий управления маршрутизацией и (или) интенсивностями обслуживания в сетях массового обслуживания и исследуются свойства сетей данного класса.
Во второй главе рассматривается метод оптимизации маршрутных матриц сетей массового обслуживания с одним классом требований. Критерии оптимизации, используемые в данном методе, обеспечивают достижение необходимого качества функционирования сетей. Обсуждается метод определения относительных интенсивностей потоков требований в открытых и замкнутых сетях массового обслуживания, который используется при реше- ний трех задач: нахождении минимальной средней длительности пребывания требований в открытой сети обслуживания при ограничении на средний доход в единицу времени от функционирования сети, нахождении максимального среднего дохода в единицу времени от функционирования открытой сети обслуживания при ограничении на среднюю длительность пребывания в ней требований [41, 44], нахождении максимальной пропускной способности замкнутой сети обслуживания при ограничении на значения компонент вектора относительных интенсивностей потоков требований. Рассматривается метод формирования маршрутных матриц сетей массового обслуживания при заданном векторе относительных интенсивностей потоков требований [28].
В третьей главе рассматриваются методы оптимального динамического управления потоками требований в сетях массового обслуживания с одним классом требований. Для открытой экспоненциальной сети массового обслуживания с маршрутной матрицей, зависящей от состояния сети, ставится задача определения для каждого состояния сети маршрутной матрицы, обеспечивающей минимальное значение средней длительности пребывания требований в сети. Предложен метод оптимального управления потоками требований в открытых сетях обслуживания с параллельными системами обслуживания, обеспечивающий решение этой задачи [42]. Рассматриваются свойства открытых сетей обслуживания с более общей топологией и с использованием метода оптимального управления потоками. Предложен метод динамического управления потоками в замкнутой экспоненциальной сети массового обслуживания [29, 31], обеспечивающий оптимальную траекторию эволюции сети из произвольного состояния в некоторое заданное состояние. Получены выражения для стационарного распределения вероятностей состояний открытых и замкнутых сетей массового обслуживания с динамическим управлением потоками [43].
В четвертой главе полученные в главах 2 и 3 результаты прилагаются для исследования гипотетических однородных открытых и замкнутых сетей обслуживания с оптимальным управлением потоками. Для открытых сетей обслуживания построены оптимальные маршрутные матрицы и установлена зависимость маршрутных вероятностей от ограничений на средний доход от функционирования сетей обслуживания и от ограничений на среднее время пребывания требований в сетях обслуживания. Приведены примеры использования метода формирования маршрутных матриц для замкнутых сетей обслуживания с максимальной пропускной способностью, а также для замкнутых сетей обслуживания с оптимальным управлением потоками. Проведено исследование эффективности методов оптимального динамического управления потоками в открытых и замкнутых сетях массового обслуживания.
Оптимальное управление маршрутизацией
В работах [36, 47, 49, 51, 72], а также обзорах [67, 74], предлагаются методы маршрутизации потоков требований, обеспечивающие оптимальное функционирование сетей массового обслуживания. Рассматривается открытая двухсистемная сеть массового обслуживания с системой С, типа МЛ/ Kj С потерями и интенсивностью обслуживания щО), где индекс j соответствует состоянию системы С2 и принимает два значения: 1 или 2. Длительность пребывания системы С2 в состоянии п2, п2 = 1,2, есть случайная величина, распределенная по показательному закону. На вход системы Q поступает пуассоновский поток требований с интенсивностью X. Требования, поступившие в систему Cj в момент, когда все приборы заняты, теряются и потеря одного требования оценивается величиной h. Стоимость работы прибора с щО) в единицу времени равна r{, j = 1,2; гх гх . Пусть щ и щ - число требований в Сх, поступивших во время пребывания С2 в состоянии соответственно п2 — 1 и п2 = 2. Функционирование данной сети можно описать марковским процессом с пространством состояний п2-\ возможны два решения: 1) поступившеє в систему Сх требование выбирается на обслуживание этой системой; 2) требованию отказывается в обслуживании. Вероятности принятия этих решений обозначим через а+(л) и оГ(и), можно принять в случае п2 = 2. Вероятности принятия этих решений обозначим Р (я) и Р (л), Р+(«) + Р» = 1. Пусть р(п) - стационарная вероятность пребывания сети обслуживания в состоянии п. Полные потери в сети обслуживания Задача оптимизации функционирования сети обслуживания формулируется следующим образом.
Необходимо найти такую стратегию управления сетью обслуживания в стационарном режиме, чтобы минимизировать суммарные потери в ней в единицу времени. Под стратегией управления понимается последовательность управляющих решений, которые на основе информации о состоянии сети обслуживания определяют, назначить ли поступившее в систему Cj требование на обслуживание или отказать ему в этом. Теорема 1.2. Необходимая стратегия управления сетью обслуживания существует тогда и только тогда, когда существует решение следующей задачи математического программирования: найти при ограничениях на систему уравнений, которой удовлетворяют стационарные вероятности состояний, и Для решения задачи могут быть использованы методы линейного программирования, т.к. в каждом состоянии п только один из управляющих параметров положителен, а другие равны 0. Работа [36] является примером рассмотрения данной задачи. В работах [49, 51] проводится исследование методов маршрутизации с целью выравнивания нагрузки в открытых сетях обслуживания. В работе [47] рассматривается задача оптимального управления маршрутизацией, обеспечивающая минимальную стоимость функционирования открытой СеМО. В работе [72] рассматривается сеть с коммутацией пакетов, имеющая I+J типов передаваемых по сети пакетов. Множество Sx = {і,...,/} содержит неинтерактивные типы, множество S2 = {/+1,...,/+ j} - интерактивные. Пусть Е = Sx U S2 - множество всех типов пакетов, которые могут находиться в сети. Для таких сетей требуется, чтобы среднее время задержки интерактивных типов пакетов в сети не превышало заданного значения. В качестве математической модели сетей с коммутацией пакетов рассматривается сеть обслуживания типа сети Джексона с L системами обслуживания. При этом каждое требование имеет пометку принадлежности к конкретному типу пакетов. В дальнейшем обозначения множеств Slt S2 и Е используются для обозначения соответственно множеств неинтерактивных, интерактивных и всех типов требований в сети массового обслуживания. Вводится управление у, которое используется для составления расписания очередности обслуживания требований в каждой СМО сети обслуживания.
Оно зависит от текущего и прошлого состояния сети. Пусть Х(к) - интенсивность входящего потока требований к типа в сеть; с(к) — стоимость пребывания одного неинтерактивного требования к типа в сети обслуживания в единицу времени; й{к) - заданная верхняя граница среднего времени пребывания интерактивного требования к типа в сети; й(к;у) - среднее время пребывания требований к типа в сети при управлении у. Задача заключается в нахождении такого управления у очередностью обслуживания требований, которое минимизирует среднее время пребывания неинтерактивных типов требований в сети обслуживания и в то же самое время обеспечивает среднее время пребывания интерактивных типов требований в сети ниже заданной границы. Управление у будет возможным, если будет оптимальным, если минимизировать по всему классу возможных управлений. Теорема 1.3. Возможное управление существует тогда и только тогда, когда существует возможное решение следующей задачи линейного программирования: найти где U - множество типов требований, находящихся в сети обслуживания, которым управление у предоставляет абсолютный приоритет в обслуживании; n{U) - среднее число требований, имеющих абсолютный приоритет в обслуживании; п(Е) - среднее число требований в сети обслуживания. Теорема 1.4. Для данной задачи линейного программирования управление у будет оптимальным тогда, когда й(-;у) будет оптимальным решением задачи линейного программирования. В работе [72] показывается, что оптимальное решение будет получено, если все типы требований разделить на I + j (О j ,/) упорядоченных групп и применить к ним правило абсолютного приоритета. В работе [62] решается задача определения маршрутов требований, максимизирующих прибыль от функционирования сети с коммутацией каналов в единицу времени. В качестве модели сетей с коммутацией каналов используется сеть обслуживания с потерями. В работе [55] исследуется влияние добавленной дуги, и, следовательно, нового маршрута требований на среднюю длительность пребывания требований в открытой СеМО. Важным результатом теории СеМО с управлением потоками является определение стационарных распределений вероятностей состояний данных СеМО. В работах [14, 19, 23, 52, 75] для сетей обслуживания с маршрутизацией, зависящей от состояния, доказывается существование стационарного распределения в мультипликативной форме.
Определение векторов относительных интенсивностей потоков для замкнутых сетей обслуживания
Рассмотрим теперь замкнутую экспоненциальную сеть массового обслуживания Г [5, 60], которая отличается от сети Г0 отсутствием источника требований С0. Сеть содержит N требований одного класса, переходы которых между системами в процессе эволюции сети определяются неприводимой маршрутной матрицей 0 = (0,-,), i,j = 1,2,...,L. Обозначим: nt - число требований в системе С,., / = 1,2,...,L; /? = («,) - вектор, определяющий состояние сети Г; Щщ - м.о. числа требований, находящихся в системе С, сети Г; 7Т/д _1 - м.о. числа требований, находящихся в системе С, сети обслуживания, которая отличается от сети Г только тем, что в ней содержится N-I требований; S(N,L) — множество состояний сети Г. Определим разбиение x SiN L)} множества S(N,L): b{S{N,L)} = {S?(N,L), S}{N,L),..., Sf (N,L), r.,S?{N,L)}, S {N,L) = {n = (1.....)nєS{NtL),л, = k,j=1 y =N), k = 0,1,2,..., . Известно [60], что нормализующая константа G(N,L) определяется выражением т.е. G(N,L) является функцией вектора со = (со,), j = 1,2,....L. Из приведенного в [25] выражения для математического ожидания числа занятых обслуживающих приборов в системе С, используя выражение ht = А /ц.,, которое верно только для систем обслуживания с одним прибором, получим Рассмотрим функцию которую, учитывая (2.16), запишем в виде как известно [25, 26], эта функция называется пропускной способностью сети Г. Покажем, что Л(оо) является вогнутой функцией от вектора со. Предварительно приведем из работы [79] некоторые результаты, представленные в виде замечаний 2.1 и 2.2. Замечание 2.1. Пусть r,se Rn, R = (-00,00).
Пусть также и Мажорантное упорядочение r m s определяется как Замечание 2.2. Пусть /: Т" - R{T a R). Функция / определяется как вогнутая функция, если х тх , х ,х e F" = f(x) f(x ). Если функция f непрерывно дифференцируемая и симметрическая в Тп, то она df df С/Лі ОлЧ является вогнутой, если и только если Ґ (х1-х2) о, для всех х є IF", где х = (х{), xt = (dj/iij, z = 1,2,...,L. Обозначим через Gt(N-k L-X) - нормализующую константу сети обслуживания, полученную из исходной сети путем исключения системы Cj, / є X, и к требований. Используя базовые функции сети Г [5] L COy w Л У gj(N-k,L-\)= X П neSf(N,L)J=1 получим L U/J gi(N,L-\) = Gi(N,L-\) = X П \»JJ neSf(N,L)J=l (2.17) Сформулируем результат, представленный в работе [79], в виде леммы 2.1. Лемма 2.1. Л(со) является неубывающей функцией от N, т.е. для любого положительного целого N G(N-l,L) G(N-k-l,L) k = ia_N G(N,L) G(N-k,L) Определим теперь частную производную dG{N,L)jda)i, / = 1,2,...,1. Лемма 2.2. Частная производная функции G(N,L) по переменной со( определяется из выражения (2.18) dG(N,L) _ni]NG(N,L) dco, , 1 = 1,2,...,1. со. Доказательство. Используя свойства базовых функций g{N,L) = Yjgi{N-k,L), k=0 gi(N-k,L) = а также выражение (2.17), получим V /V g,(N-k9L), "V G(N,L) = X Gt{N-k,L-\). (2.19) Следовательно, dG(N,L) д dco. 6co, N r CO. (.. \k k=0\ Pi J G N-KL-l) 0), .Ml J W Л, Л " G,(tf- ,L-1) = W-l і v—1 M; =0 G V Mi J Jfc-1 G,(W-A:-1,L-1) = M, , xft-1 CO, M,J //-1/_ л G,.( -l,L-l) + -p -l G,(JV--l,L-l) = «л /У 3co, ДІ Используя рекурсию по ЛГ, получим выражение ш.Л dG(N,L) G(N-k-\,L), Гл /„ со. Заметим также, что dG(N,L)= д Зсо, дсо. G,{N-k,L-l) N 1 iV —і M, =1 Jt— G,(tf-M,-1) = N Ui Ґ \k чу Q(tf- ,L-1) = %G( ) со,. Обозначим со и со - векторы относительных интенсивностей потоков требований. Тогда справедлива следующая теорема.
Теорема 2.3. Пропускная способность Л(со) замкнутой сети массового обслуживания Г является вогнутой функцией. Доказательство. Используя известное из [54] равенство G(0,L) = 1, найдем a», G2(N,L)\ асо,. а,. G\N,L) »-2ґп ]Г -L [G(N,L)G(N-k-2,L)-G(N-1,L)G(N-Je-IL)] k=0 \»IJ ч .Mj N-\ G(N-\,L) Тогда аЛ(со) дЛ(со) ScOj 5co2 \ix\i2G (N,L) N-2 z A:=0 f V 1 V Л J [G(N-\,L)G(N-k-\,L) со, со G(N-l,L) (2.20) 2 -G(N,L)G(N-k-2,L)] + .Ъ) J №. Выражение в прямоугольных скобках согласно лемме 2.1 является неотрицательным и неравенство
Открытые сети с параллельными системами массового обслуживания
Рассмотрим сеть обслуживания Гс, состоящую из L параллельных систем обслуживания с интенсивностями обслуживания ц(, маршрутными вероятностями 0О/ 1, («,.+1)/ц;.=тіп +1)/ }, є.с (3.2) О, в противном случае, где ni - число требований, находящихся в системе Q, / = 1,2,...,/, в момент поступления очередного требования из источника. Средняя длительность пребывания в системе Ck, k = \,2,...,L, вновь поступающего из источника требования равна {пк + 1)/цк . Определение 3.5. Нагрузкой системы С,, / = 1,2,...,/,, называется отношение числа требований ni к интенсивности обслуживания в этой системе. Покажем, что правило (3.2) управления вероятностями 0Ш, / = 1,2,...,/,, обеспечивает минимальное значение математического ожидания т0 длительности пребывания требований в сети Гс [42]. Теорема 3.1. Пусть дана сеть обслуживания Тс с L параллельными системами обслуживания, интенсивностями обслуживания ц,, /=1,2,...,/, и маршрутными вероятностями 0 0О/ 1 и 90 = 1. Тогда для любого состояния сети п = (/?j,//2,...,) правило (3.2) управления потоками требований, поступающих из источника С0, обеспечивает минимальное значение математического ожидания т0 длительности пребывания требований в сети Гс. Доказательство. В соответствии с правилом (3.2) средняя длительность пребывания вновь поступившего требования из источника в систему С, будет наименьшей по сравнению со средними длительностями пребывания его в других системах сети. Таким образом, это правило приводит к выравниванию нагрузки систем обслуживания в сети Гс. Определим обеспечивающие минимальное значение т0 вероятности 0О/ перехода требований из источника в систему С/5 / = 1,2,...,/,, когда сеть Гс находится в стационарном режиме. Очевидно, что правило (3.2) будет оптимальным, если в стационарном режиме для сети Гс выполняется равенство константа, N - число требований, находившихся в сети Гс в момент поступления очередного требования из источника. Учитывая, и обозначая получим Заметим, что с учетом вновь поступившего (N +1) -го требования V+iM=pAr+i» =1,2,...,/,.
Отсюда следует, что pN+l=(N + \)/Q, N 0. Тогда nnN=N , +1=( + 1) , /=1,2,...,/-, N 0, откуда видно, что — _ JLX %i = ni\N+l ni\N 7л = 1 2,...,L, Q и не зависит от N. Покажем, что правило (3.2) в стационарном режиме действительно выравнивает нагрузку в сети Гс. Предположим, что в момент поступления очередного требования из источника в сети Гс находится N О требований. Так как математическое ожидание числа требований Ї7 - м 1 niW=N , / = 1,2,...,2,, N 0, то в соответствии с правилом (3.2) нагрузка системы С, в стационарном режиме сети Гс "i\N + %i (N + V N + l и, nfl а т. е. нагрузка одинакова для всех систем и не зависит от номера СМО. В сети обслуживания с параллельными системами обслуживания /=0о,-» = 1,2,...,L. Используя формулу Литтла, получим X0fQ = N, где N - м.о. числа требований в сети Гс. Таким образом, правило (3.2) распределяет входящий поток требований с интенсивностью L обеспечивая минимальное значение т0. Воспользуемся теоремой 3.1 для исследования свойств открытых сетей массового обслуживания с более общей топологией и правилом управления потоками (3.1). Обозначим В = {і:іє X, h0i = 1} - множество индексов граничных входных систем обслуживания С,. / є В и Bt = {j: j є X, htJ = 1} - множест во индексов граничных выходных систем обслуживания, с которыми связана система С,. Теорема 3.2. В сети обслуживания Гс, состоящей только из граничных входных и граничных выходных систем массового обслуживания, с произвольной без контуров топологией и правилом управления потоками (3.1) т0 является убывающей функцией числа смежных по отношению к системе С(, і є В, систем обслуживания. Доказательство.
Предположим, что в некоторой системе С,, / є В, завершилось обслуживание требования и для некоторой граничной выходной системы С выполняется равенство (n-j + 1)/цу = тіп ш + 1)/цот}, (3.3) J J теВ где т Тогда, если j є 5,, то требование из системы С, перейдет в систему С , так как (лу + 1)/цу = ішп{Слт+1)Діи} J J meBj и, как следует из теоремы 3.1, средняя длительность пребывания данного требования в системе обслуживания С, будет наименьшей по сравнению со средними длительностями пребывания его в системах сети с индексами из множества В. Рассмотрим далее случай, когда j Bt. Требование из системы обслуживания С, перейдет в некоторую систему Ck, к є Bj если выполняется meBj Выбор системы Ск для перехода требования из системы Ct обеспечивает наименьшую среднюю длительность пребывания требования по сравнению со средними длительностями пребывания его в системах обслуживания с индексами из множества В(. При этом выполняется неравенство (Л +1)/Ц (Л;+1)/Цу, вследствие существующих ограничений в топологии сети обслуживания. А " с Добавим дугу (С СЛ в орграф, отображающий топологию сети Г , и пусть в момент завершения обслуживания требования в системе С; выпол няется соотношение (3.3). Тогда средняя длительность пребывания вновь поступившего требования в систему обслуживания С будет меньше сред них длительностей пребывания его в системах сети с индексами из множе ства В. Следовательно, увеличение числа дуг в сети обслуживания Гс при водит к уменьшению математического ожидания длительности пребывания требований в данной сети. Рассмотрим определенную в разделе 2.2 замкнутую экспоненциальную сеть массового обслуживания Г, в которой реализовано динамическое управление маршрутизацией требований в процессе эволюции сети. Критерием качества функционирования сети Г определим вероятность Р(п) пребывания сети обслуживания в заданном состоянии п. Будем считать, что маршрутизация требований в сети обслуживания осуществляется маршрутными матрицами Q(n) = (Q.(n)), где neS(N,L) - состояние сети Г. Таким образом, для реализации метода управления маршрутизацией требуется определить
Исследование эффективности метода динамического управления потоками
Исследование зависимости характеристик открытых сетей массового обслуживания с динамическим управлением потоками от числа связей между системами обслуживания проведем на примере однородной открытой сети массового обслуживания Гс с L = 5; Х0 = 0,3; ц = (1,0; 1,2; 1,0; 1,1; 1,1), матрицей смежности маршрутной матрицей, в которой постоянными являются маршрутные вероятности Ooi=0,4; 0 2=0,6; 90 = 1; O40-I и G0 = 1. Элементы 9,у такие, что hjj=\, i,jeH, маршрутной матрицы 0 изменяются в соответствии с правилом управления потоками, рассмотренным в разделе 3.1. Обозначим через Су матрицу, у которой все элементы равны нулю, за исключением равного единице элемента, расположенного на пересечении і-й строки и 7-го столбца, Будем последовательно добавлять дуги (Q ), (С},С5) и (С2,С2) в граф, отображающий топологию сети Гс. Значения характеристик сети Гс с различным числом связей в сети представлены в табл. 4.9, где, т0 - м.о. длительности пребывания требований в сети, Из содержания табл. 4.9 следует, что при увеличении числа связей между системами обслуживания в сети Гс уменьшается м.о. длительности пребывания требований в данной сети. Значения характеристик систем сети Гс с различным числом связей между системами обслуживания в сети представлены в табл. 4.10. Из содержания табл. 4.10 видно, что когда в сети 8 связей, интенсивности потоков требований в системах Q и С3 равны, так как 9 3 = 1.
Требования из системы С2 с вероятностью 24 = 4 Аг =0,873 направляются в систему С4, так как при небольшой интенсивности потока А. о для данной сети обслуживания велика вероятность того, что в системах С4 и С5 нет требований. Следовательно, при равных интенсивностях обслу живания в этих системах обслуженное в системе С2 требование в соответствии с правилом управления потоками переходит в систему С4. Этим объясняется высокая интенсивность потока в систему С4 по сравнению с системой С5. Добавление в сеть Гс связи между системой С1 и С4 (в сети содержится 9 связей) приводит к тому, что поток из системы Q, как правило, направляется в систему С4, так как ju4 jn3. Этим объясняется существенное уменьшение потока в систему С3 и увеличение потока в систему С4. Добавление в сеть Гс связи между системой С1 и С5 (в сети содержится 10 связей) приводит к уменьшению Х3 (по сравнению с Х3 когда сеть содержит 9 связей) и увеличению Х,5 так как V-5 из Добавление в сеть Гс связи между системой С2 и С3 (в сети содержится 11 связей) приводит к небольшому увеличению Х3 (по сравнению с Х3, когда сеть содержит 10 связей) и уменьшению Х4 и Х5. Это объясняется возникновением ситуации, когда и В этом случае требование поступает в систему С3. Вероятность возникновения этой ситуации мала, так как интенсивность Х0 мала и JLI4 ц3, д.5 №з Следует также отметить, что характеристики систем Сх и С2 не изменяются при увеличении числа связей в сети Гс, так как интенсивности потоков требований из источника С0 в системы сети являются неуправляемыми параметрами данной сети обслуживания. При исследовании влияния метода динамического управления потоками, рассмотренного в разделе 3.1, на характеристики открытой сети массового обслуживания используем однородную открытую сеть массового обслуживания Г0 с L = 5, \i = (1; 1,1; 3,0; 1,3; 1,1), матрицей смежности Н и маршрутной матрицей 0: Пусть Гс - однородная открытая сеть массового обслуживания с параметрами, совпадающими с параметрами сети Г0, за исключением маршрутной матрицы, в которой постоянными являются элементы OQ! = 0,3; 002 = 0,7; 9 0 = 1 и 9зо = 1
Остальные элементы маршрутной матрицы изменяются в соответствии с правилом управления потоками, определенным в разделе 3.1. Характеристики сетей Г0 и Гс при значениях Х0 = 0,05; 0,2; 0,4; 0,6; 0,7; 0,8 представлены соответственно в табл. 4.11 и 4.12, где X; - интенсивность потока требований в систему С,, / = 1,2,...,L. Из содержания табл. 4.11 и 4.12 видно, что сеть Гс имеет меньшие значения N и т0, чем сеть без управления Г0, при всех рассмотренных значениях А0. Следует отметить, что эффективность использования метода динамического управления потоками в сети обслуживания возрастает при увеличении А0. В частности, математическое ожидание N числа требований в сети обслуживания Гс с А0 = 0,8 существенно меньше, чем в сети Г0. Из результатов, представленных в табл. 4.12, можно сделать вывод, что при увеличении А0 интенсивность потоков 4 и А2 увеличивается пропорционально А0. При небольших А0 практически весь поток требований из систем Q и С2 направляется в систему С3, однако, при дальнейшем увеличении А0 наблюдается перераспределение потока из систем Q и С2 соответственно в системы С4 и С5. Это видно также из содержания маршрутных матриц 0е, которые получаются с использованием выражения
