Содержание к диссертации
Введение
Глава 1 Исследование RQ-систем MGI 1 с вытеснением заявок 14
1.1 Исследование RQ-систем M GI 1 с вытеснением заявок и экспоненци альным распределением времени между повторами обращения заявок из ИПВ 15
1.1.1 Математическая модель .15
1.1.2 Пропускная способность RQ-систем M GI 1 с вытеснением зая-вок 18
1.1.3 Численное исследование некоторых свойств RQ-систем M GI 1 с вытеснением заявок 20
1.1.4 Асимптотический анализ .25
1.2 Исследование RQ-систем M GI 1 с вытеснением заявок и гиперэкспо ненциальным распределением времени между повторами обращения заявок из ИПВ 38
1.2.1 Математическая модель. .38
1.2.2 Асимптотический анализ .41
1.3 Выводы по Главе 1 57
Глава 2 Диффузионная аппроксимация RQ-систем MGI 1 с вытеснением заявок 59
2.1 Асимптотический анализ .60
2.2 Локальная диффузионная аппроксимация в RQ-системах 62
2.3 Глобальная диффузионная аппроксимация в RQ-системах 69
2.4 Выводы по Главе 2 72
Глава 3 Исследование RQ-систем M(2) B(x)(2) 1 с r-настойчивым вытеснением альтернативных заявок 74
3.1 Математическая модель 74
3.2 Асимптотический анализ .79
3.3 Выводы по Главе 3 105
Глава 4 Комплекс проблемно-ориентированных программ и алгоритмов для исследования RQ-систем с вытеснением заявок и численный анализ резуль-татов 106
4.1 Численный алгоритм для исследования RQ-систем M GI 1 с вытеснением заявок .106
4.1.1 Численный анализ RQ-систем M GI 1 с вытеснением заявок в условии конечной ненулевой пропускной способности .107
4.1.2 Численный анализ RQ-систем с вытеснением заявок в условии неограниченной пропускной способности 111
4.1.3 Численный анализ нестационарных RQ-систем с вытеснением заявок и ограничением на объем ИПВ 115
4.1.4 Численная реализация асимптотической аппроксимации 120
4.1.5 Численная реализация диффузионной аппроксимации для двумодаль-ных распределений 1 4.2 Имитационная модель RQ-систем M GI 1 с вытеснением заявок и гиперэкспоненциальной задержкой 125
4.3 Имитационная модель RQ-систем M(2) B(x)(2) 1 с r-настойчивым вытеснением альтернативных заявок 129
4.4 Выводы по Главе 4 132
Заключение 134
Список использованной литературы
- Численное исследование некоторых свойств RQ-систем M GI 1 с вытеснением заявок
- Глобальная диффузионная аппроксимация в RQ-системах
- Асимптотический анализ
- Численный анализ RQ-систем с вытеснением заявок в условии неограниченной пропускной способности
Численное исследование некоторых свойств RQ-систем M GI 1 с вытеснением заявок
Полученные равенства (1.1.13), (1.1.14), (1.1.18), (1.1.19) позволяют реализовать достаточно эффективный численный алгоритм нахождения двумерного стационарного распределения вероятностей (см. п. 4.1).
Были рассмотрены примеры численной реализации распределения вероятностей P{i) = PQ{i) +Рх{ї) для различных функций распределения В(х) и различных значений параметров X и а. В частности рассмотрена взвешенная сумма гамма и экспоненциального распределений {x)-q{ +-) +( -q){ +-) , в котором заданы положительные параметры а, Р, у и 0 g 1. Отметим, что плотность распределения В (х) имеет вид B (x) = q —xa-1e-Vx+(\-q)ye-lx. (1.1.21) Г(а) Такое распределение для различных значений его параметров позволяет получить все три варианта значений пропускной способности 5 из (1.1.10). На рисунке 2 приведен график распределения P(i), полученного реализацией численного алгоритма, при значениях параметров времени обслуживания q = 0,5, а = 2, 0 = 5, у = 5, S = B (0) = (l-q)y, 5 = 2,5. Интенсивность X здесь полагается равной А, = 1,5. Из вида графика распределения Р{ї) представляется целесообразным его сравнение с гауссовским распределением (Рисунок 3). Рисунок 2 - График распределения Рисунок 3 - Графики распределения P(i) P(i) при а = 0,005 , X = 1,5, N = 500. и гауссовского распределения при а = 0,005, А, = 1,5, N = 500. Рассмотрим пример со следующими значениями параметров q = 1, а = 1,5, р = 1, а = 0,01, S = 0. (1.1.22) На рисунке 4 изображен график распределения вероятностей P(i) при значениях параметров, указанных в (1.1.22).
График распределения P(i) при X = 0,4, N = 400. Если значение интенсивности X положить = 0,35, то при 7V = 400 график распределения P(i) (Рисунок 5) близок к нормальному. На рисунке 5 изображен график распределения вероятностей P(i), найденных реализацией численного алгоритма при значениях параметров q = l, a = l,5, p = l, a = 0,01. Из вида графика на рисунке 5 целесообразна его аппроксимация гауссов-ским распределением (Рисунок 6). Рисунок 5 - График распределения Рисунок 6 - Графики распределения P(i) и P(i) при X = 0,35, N = 400. гауссовского распределения при X = 0,35, 7V = 400. Если в качестве примера рассмотреть взвешенную сумму вырожденного и экспоненциального распределений -1 1 + ± B\x) = qe-cuc+(\-q) V У) то получим ситуации, когда стационарного режима в системе не существует, а график распределения Р{Г) (Рисунок 7) является двумодальным. На рисунке 7 изображен график распределения вероятностей P(i) при значениях параметров g = 0,93, а = 1, у = 10, а = 0,01. 25 Рисунок 7 - График распределения P(i) при X = 0,3118, N = 1000. Более подробно примеры распределений P(i) в каждом из этих вариантов рассмотрены в Главе 4.
В следующих параграфах предлагается исследовать RQ-систему с вытесне-ним заявок модифицированным методом асимптотического анализа, который значительно улучшает аппроксимацию. Методом асимптотического анализа в ТМО называется решение уравнений, которые определяют некоторые характеристики системы, при выполнении каких-то предельных условий, в частности, в данной работе используется предельное условие большой задержки при а- 0. Модификация состоит в построение асимптотик первого, второго и третьего порядков. Асимптотика первого порядка позволяет найти среднее число заявок в источнике повторных вызовов и является аналогом закону больших чисел. Вторая асимптотика позволяет построить гауссовскую аппроксимацию распределения вероятностей числа заявок в ИПВ и является аналогом центральной предельной теоремы. И наконец, третья асимптотика позволяет найти семиинварианты, с помощью которых можно построить некоторую аппроксимацию, которая, как будет показано, является точнее гауссовской аппроксимации.
Асимптотическое условие большой задержки заявок в источнике повторных вызовов имеет вид: а —» 0. Асимптотика первого порядка Теорема 2. Пусть i{t) - число требований в источнике повторных вызовов RQ-системы с вытеснением заявок. Тогда для последовательности характеристических функций выполняется следующее равенство lim М ехр \jw 5i(t)\ = ехр Ь-WK, }, ач 0 где Kj является решением уравнения оо = ( + к1)е"(Х+Кі)хй(.х). (1.1.23) о Доказательство теоремы 2 и теоремы 3 не приводятся, в связи с тем, что аналогичные выкладки и математические приемы используются при доказательстве теоремы 4, которое является более сложным и представлено в данной работе. Для более детального исследования рассматриваемой RQ-системы, найдем асимптотику второго порядка.
Глобальная диффузионная аппроксимация в RQ-системах
В данном параграфе исследуются RQ-системы с вытеснением заявок, простейшим входящим потоком, произвольной функцией распределения времени обслуживания заявок и гиперэкспоненциальным распределением времени между повторами обращения заявок из источника повторных вызовов.
Рассмотрим (Рисунок 10) RQ-систему с простейшим входящим потоком, произвольным временем обслуживания, гиперэкспоненциальной задержкой в ИПВ и вытеснением альтернативных заявок.
На вход RQ-системы поступает простейший поток заявок с интенсивностью X. Если в момент прихода заявка обнаруживает прибор свободным, то она занимает прибор для обслуживания в течение случайного времени с функцией распределения В{х). Если в момент прихода заявка обнаруживает прибор занятым, то она вытесняет обслуживаемую заявку и сама встает на прибор для обслуживания. Вытесненная заявка уходит в источник повторных вызовов (ИПВ). Вре 39 мя пребывания в ИПВ имеет гиперэкспоненциальное распределение с параметрами C1, с2, q. С вероятностью q заявка осуществляет экспоненциальную задержку с параметром о1 (1 фаза) и с вероятностью 1-q заявка осуществляет экспоненциальную задержку с параметром с2 (2 фаза). После случайной задержки заявка вновь встает на прибор. Дисциплина обращения заявок из ИПВ аналогична дисциплине обращения первичных заявок. Обозначим i1(t) - число заявок в ИПВ на 1 фазе, i2(t) - число заявок в ИПВ на 2 фазе, k(t) - определяет состояние прибора следующем образом: Г0, если прибор свободен, 1, если прибор занят. Ставится задача нахождения двумерного стационарного распределения вероятностей числа / = \ + i2 заявок в ИПВ и распределения вероятностей состояний прибора. Так как процесс (А:(ґ),/1(ґ),/2(ґ)}не является марковским, то для его маркови зации рассмотрим процесс с переменным числом компонент, определяемый следующим образом.
Если k(t) = 0, то рассматриваем процесс [k(t)J1(t)j2(t)} . Если k(t) = n, и = 1,2, то рассматриваем процесс [k(t)j1(t)j2(t),z(t)}, где z() – остаточное время от момента t до момента окончания обслуживания.
Обозначим p{k(t) = 0J1(t) = i1,i2(t) = i2} = P0(i1,i2J), /1 0, /2 0 вероятность того, что прибор в момент времени t находится в состоянии 0, в ИПВ на первой фазе находится \ заявок, в ИПВ на второй фазе находится /2 заявок; P{k(t) = п,1( ) = i1,i2(t) = i2,z(t) z} = Pn(hJ2,z,t), n = 1,2 вероятность того, что прибор в момент времени t находится в состоянии п, в ИПВ1 находится \ заявок, в ИПВ2 находится /2 заявок, остаточное время обслуживания меньше z. Для этого распределения вероятностей запишем систему уравнений Колмогорова: (l + i1a1 + i2a2)P0(i1,i2), dz дР1(і1,і2,0) dP1(i1,i2,z) = -(I + /1CT1 + /2ст2)Ж 1Л, ) + B(z)p0(l1, 2) + dz dz +(/1 -Ь1 0(/1 +1,/2) + (/2 +1)CT25(z)P0(/1,/2 +1) + (Z) ( 1 -1,/2)+ (1.2.1) +A,(1 - q)B(z)P1(i1,i2 -1) + (/1 + 1)CT15(z)(1- q)P1(i1 + 1,i2 -1) + +i1G1qB(z)P1(i1,i2) + /2ст2(1 - q)B(z)P1(i1J2) + (i2 + 1)G2B(z)qP1(i1 - 1,i2 +1). От системы (1.2.1) перейдем к системе уравнений для частичных характеристических функций. Для этого выполним замены: GO GO GO GO Я0 (щ, и2) = е-7 "1 1 е-7 "2 2 Р0 (/1, /2), H1(u1,u2,z)=YuYu eJU1k еШ2 Р0 (h , 2 ,Z), /1=0/2=0 /1=0/2=0 где у = v 1 - мнимая единица. Обозначим Н1(и1,и2,со) = Н1(и1,и2), дН1(и1,и2,0) dH1(u1,u2,z) z=0 dz dz Запишем систему уравнений для частичных характеристических функций: ag1(»1,»2,0) = -ш0(И1,«2)+ус ж0("1,"2)+м»«И2) , dzw 2 1 5м1 дм2 дН1(щ,щ,г) дЩ(щ,щ,0) . дЩ(щ,щ,г) . дЩ(щ,щ,г) dz dz 1 du1 2 du2 +ХВ(г)Н0(щ,и2)- je JU1G1B(z)dH0(U1,U2) - je-JU2G2B(z)dH0(U1,U2) + du1 +XqB(z)eJUiH1(u1,u2) + ЦІ - q)B{z)e ju Hl{ubu2) - jqGlB(z)dHl Ul,U -7(1 -q)G2B(z)dHl("V2) -7(1 -q)alB(z)eл"2""} dH u _ (1.2.2) ди2 дщ -je - qa2B(z)dHliV2 )-lHM 2 du2 1V : 2 Аналитически данную систему решить затруднительно. Будем решать ее методом асимптотического анализа в условии большой задержки (а—»0), полагая, что а: = зух, а2 = ау2.
Обозначим хт, т = \,2 - асимптотическое среднее значение числа заявок на /72-ой фазе в источнике повторных вызовов, а Rk, к = 0,1 - распределение вероятностей состояний прибора. Ниже будет показано, что Rk, = 0,1 определяется значениями хт,т = 1,2, поэтому будем применять обозначение Rk(xbx2), к = 0,1. Сформулируем следующее утверждение. Теорема 5. Пусть ix{t) и i2(t) число требований в источнике повторных вызовов на первой и второй фазах RQ-системы с вытеснением заявок и гипер-экспоненциальным распределением времени между повторами обращения заявок из ИПВ. Тогда для последовательности характеристических функций выполняется равенство
Асимптотический анализ
RQ-системы с двумя входящими потоками являются более общими моделями систем с вытеснением, рассмотренных в Главе 1. Системы с повторами и двумя типами заявок могут быть рассмотрены в качестве математической модели транспортной системы – автономно управляемого перекрестка (Autonomous Intersection Management). В качестве входящих потоков являются пересекающиеся потоки движение, а обслуживающим прибором является вышка, предающая сигнал о возможности проехать перекресток.
В данной главе рассмотрена RQ-система с двумя входящими простейшими потоками, произвольным временем обслуживания и r-настойчивым вытеснением альтернативных заявок. Исследование системы проводится методом асимптотического анализа в предельном условии большой задержки заявок в ИПВ.
Ставится задача нахождения распределения вероятностей числа заявок в каждом источнике повторных вызовов и состояний прибора.
Рассмотрим (рисунок 13) RQ-систему с двумя входящими простейшими потоками, произвольным временем обслуживания и вытеснением альтернативных заявок. B2 Рисунок 13 - RQ-система М(2) В{х){2)\ 1 с вытеснением альтернативных заявок На вход RQ-системы поступают два простейших потока заявок с параметрами Хх и Х2 , соответственно. Если прибор свободен, то пришедшая заявка занимает прибор для обслуживания в течение случайного времени с функциями распределения В}(х)и В2(х), соответственно.
Если в момент прихода заявка первого типа обнаруживает прибор занятым заявкой первого типа, то она уходит в ИПВ1 (источник повторных вызовов для заявок первого типа), где осуществляет случайную задержку, распределенную по экспоненциальному закону с параметром о}. После случайной задержки заявка
вновь обращается к прибору с повторной попыткой его захвата. Если же в момент прихода заявка первого типа обнаруживает прибор занятым заявкой второго типа, то пришедшая заявка с вероятностью г} вытесняет заявку второго типа, которая
уходит в ИПВ2, а сама встает на обслуживание, иначе с вероятностью 1 - г} уходит в ИПВ1, где осуществляет случайную задержку.
Если в момент прихода заявка второго типа обнаруживает прибор занятым заявкой первого типа, то пришедшая заявка с вероятностью г2 вытесняет заявку первого типа, которая уходит в ИПВ1, а сама встает на обслуживание, иначе с вероятностью 1 - г2 уходит в ИПВ2 (источник повторных вызовов для заявок второго типа), где осуществляет случайную задержку, распределенную по экспоненциальному закону с параметром с2. После случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата.
Таким образом, происходит r-настойчивое вытеснение (r-persistent exclusion) альтернативных заявок. При обращении заявок из ИПВ1 и ИПВ2 г-настойчивое вытеснение происходит аналогичным образом.
Обозначим ix{t) - число заявок в ИПВ1, i2(t) - число заявок в ИПВ2, k{t) определяет состояние прибора следующим образом: ГО, если прибор свободен, k(t) = \, есди прибор занят заявкой первого типа, 2, если прибор занят заявкой второго типа. Ставится задача нахождения среднего числа заявок в ИПВ1, ИПВ2 и распределения вероятностей состояний прибора. Так как процесс { (ї),/ ),/ )} не является марковским, то рассмотрим процесс с переменным числом компонент. Если k(t) = 0, то рассматриваем процесс {k(t)Jl(t)j2(t)} . Если k(t) = n, и = 1,2, то рассматриваем процесс {k(t)jl(t)j2(t),z(t)}, где z(0 - остаточное время от момента t до момента окончания обслуживания.
Обозначим p{k(t) = 0Jl(t) = ilJ2(t) = i2} = P0(ilJ2J), іх 0, /2 0 вероятность того, что прибор в момент времени t находится в состоянии 0, в ИПВ1 находится \ заявок, в ИПВ2 находится /2 заявок; P{k(t) = nJl(t) = ilJ2(t) = i2,z(t) z} = Pn(ilJ2,z,t\ и = 1,2, /! 0, /2 0 вероятность того, что прибор в момент времени t находится в состоянии п, в ИПВ1 находится \ заявок, в ИПВ2 находится /2 заявок, остаточное время обслуживания меньше
Численный анализ RQ-систем с вытеснением заявок в условии неограниченной пропускной способности
Для анализа области применимости, полученных асимптотических результатов применено имитационное моделирование RQ-системы с вытеснением заявок и гиперэкспоненциальным распределением времени между повторами обращения заявок из ИПВ. Для этого было разработано компьютерное приложение для имитационного моделирования указанной системы. Приложение реализовано на базе программного комплекса ODIS [21, 23, 24]. Главное окно программы изображено на рисунке 25. В этом окне задаются основные параметры моделирова 127 ния: интенсивность входящего потока, параметры гиперэкспоненциального распределения, распределение времени обслуживания и его параметры.
Рисунок 25 – Главное окно программы имитационного моделирования RQ-систем с вытеснением заявок и гиперэкспоненциальным распределением времени задержки
В результате процесса моделирования приложение выводит окно с результатами (рисунок 26), в котором выводятся средние значения числа заявок на каждой фазе, их дисперсии и ковариация, а также одномерные распределения вероятностей числа заявок на каждой фазе (в виде графиков). В этом же окне имеется возможность сравнить результаты имитационного моделирования с полученным с помощью асимптотических методов гауссовским распределением (рисунок 27).
С помощью описанной программы получены результаты имитационного моделирования RQ-систем с вытеснением заявок и гиперэкспоненциальным распределением времени между повторами обращения заявок из ИПВ при различных значениях параметра а. Результаты сравнения полученных эмпирических распределений с соответствующими гауссовскими аппроксимациями приведены в таблице 4.10.
Таблица 4.10 - Расстояния Колмогорова между асимптотическим распределением и распределением, полученным на основе имитационного моделирования, для RQ-системы с вытеснением заявок и гиперэкспоненциальной задержкой
Из таблицы видно, что, начиная со значения а = 0,005, расстояние Колмогорова между асимптотическим распределением и распределением, полученным на основе имитационного моделирования, для обеих фаз не превышает величины 0,05. Таким образом, полученная в п.1.2 гауссовская аппроксимация распределения вероятностей числа заявок на фазах применима при значениях а 0,005.
Анализ области применимости асимптотических результатов, полученных в Главе 3 для RQ-системы с r-настойчивым вытеснением альтернативных заявок, проводился на основе сравнения гауссовской аппроксимации, полученной в Главе 3, и распределения вероятностей состояния прибора R0, Ru R2 с результатами имитационного моделирования. Для этого на основе программного комплекса ODIS было разработано приложение для имитационного моделирования указанных систем, главное окно которого представлено на рисунке 28. В этом окне за 130 даются основные параметры моделирования: интенсивности входящих потоков, параметры экспоненциальных распределений времени задержки заявок в ИПВ, вероятности вытеснения альтернативных заявок, распределения времени обслуживания заявок каждого типа.
Рисунок 28 – Главное окно программы имитационного моделирования RQ-систем с r-настойчивым вытеснением альтернативных заявок Полученные в результате процесса моделирования характеристики распределения выводятся в окне результатов, аналогичном, описанному в п. 4.2, но отличающимся возможностью вывода распределения вероятностей состояния прибора (рисунок 29).
Рисунок 29 - Результаты моделирования: распределение вероятностей состояния прибора Анализ приведен для примеров с различными функциями распределений В}(х), В2(х)и различными значениями параметров Хх, Х2 и аі = аУьа2 = аЇ2- В частности рассмотрены взвешенные суммы гамма и экспоненциальных распределений
Значения вероятностей положим равными qx = 0,5, q2 = 0,7, rx = 1, r2 = 0,5. В таблице 4.11 приведены расстояния Колмогорова между асимптотическими и эмпирическими распределениями. Таблица 4.11 - Расстояние Колмогорова между асимптотическими распределениями и распределениями, полученными на основе имитационного моделирования, для RQ-системы с r-настойчивым вытеснением альтернативных заявок Как видно из таблицы 4.11, предложенная в Главе 3 аппроксимация распределения вероятностей числа заявок в источниках повторных вызовов гауссовским распределением является приемлемой при значениях ст 0,05, так как расстояния Колмогорова не превышают 0,05, в то же время, расстояние Колмогорова, вычисленное для распределения вероятностей состояний прибора, не превышает 0,02 уже для а = 0,5.
Численный алгоритм для нахождения распределения вероятностей Р{Г) числа заявок в источнике повторных вызовов для RQ-систем с вытеснением заявок и экспоненциальным распределением времени между повторами обращения заявок из ИПВ. Программы имитационного моделирования для RQ-систем с вытеснением заявок и гиперэкспоненциальным распределением времени между повтора 133 ми обращения заявок из ИПВ, для RQ-систем с r-настойчивым вытеснением альтернативных заявок.
Показано, что распределение P(i) , полученное с помощью численного алгоритма, в случае конечной ненулевой пропускной способности, при достаточно больших значениях величины задержки заявок в ИПВ, можно аппроксимировать нормальным распределением (аппроксимация второго порядка) и так же, как правило, еще лучше выполняется аппроксимация третьего порядка. Проведена аппроксимация распределения P(i) гауссовским распределением с моментами, найденными с помощью асимптотических семиинвариантов. А также проведена аппроксимация третьего порядка. Установлено, что аппроксимация третьего порядка, как правило, является точнее аппроксимации гауссовским распределением, с моментами, найденными по распределению P(i) .
Показано, что распределение P(i) , в случае неограниченной пропускной способности, также можно аппроксимировать гауссовским распределением и выполнить аппроксимацию третьего порядка, и их точность возрастает на порядок, по сравнению со случаем, когда пропускная способность имеет конечное ненулевое значение. Также исследована система в случаи, когда пропускная способность нулевая, то есть не существует стационарного режима, и показано, что существует область стабильного функционирования нестационарной RQ-системы с вытеснением заявок, которая установлена в данной главе.
Было получено дискретное распределение, которое называем диффузионной аппроксимацией исходного распределения вероятностей. С помощью данного распределения показана возможность аппроксимации двумодальных распределений.
Была установлена область применимости асимптотических результатов для RQ-систем с r-настойчивым вытеснением альтернативных заявок и RQ-систем с вытеснением заявок и экспоненциальным распределением времени между повторами обращения заявок из ИПВ. Для этого на основе программного комплекса ODIS было разработано приложение для имитационного моделирования. Результаты, представленные в Главе 4, опубликованы в работах [45, 47, 48, 50, 51, 69].