Исследование систем массового обслуживания с коррелированными потоками в специальных предельных условиях тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Горбатенко, Анна Евгеньевна

• Горбатенко, Анна Евгеньевна
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Горбатенко, Анна Евгеньевна

Введение.

Глава 1 Исследование коррелированных потоков в специальных предельных условиях.

1.1 Математические модели коррелированных потоков.

1.2 Уравнения Колмогорова для коррелированных потоков.

1.3 Специальные предельные условия для коррелированных потоков.

1.4 Исследование МАР-потока в условии предельно редких изменений состояний.

1.5 МАР-потоки в условии растущих условных интенсивностей.

1.6 Исследование квазиразложимого МАР-потока.

1.7 Исследование БМ-потока в условии предельно редких изменений состояний.

1.8 Исследование квазиразложимого 8М-потока.

Резюме.

Глава 2 Исследование марковских СМО с неограниченным числом приборов и коррелированными входящими потоками в специальных предельных условиях.

2.1 Уравнения Колмогорова для марковских СМО с неограниченным числом приборов и коррелированными входящими потоками.

2.2 Исследование систем МАР|М|оо в условии предельно редких изменений состояний входящего потока.

2.3 Системы МАР|М|оо в условии растущих условных интенсивностей входящего потока и конечной загрузки системы.

2.4 Исследование систем МАР|М|со с квазиразложимым входящим потоком.

2.5 Исследование систем 8М|М|оо в условии предельно редких изменений состояний входящего потока.

2.6 Исследование систем 8М|М|оо с квазиразложимым входящим потоком. 78 Резюме.

Глава 3 Исследование немарковских СМО с неограниченным числом приборов и коррелированными входящими потоками в специальных предельных условиях.

3.1 Метод просеянного потока.

3.2 Уравнения Колмогорова для немарковских СМО с неограниченным числом приборов и коррелированными входящими потоками.

3.3 Исследование систем МАР|С1|оо в условии предельно редких изменений состояний.

3.4 Системы МАР|С1|оо в условии растущих условных интенсивностей входящего потока и конечной загрузки системы.

3.5 Исследование систем МАР|ОЦсо с квазиразложимым входящим потоком.

3.6 Метод матричной экспоненты для исследования систем МАРр|оо.

3.7 Исследование систем 8М|СТ|оо в условии предельно редких изменений состояний входящего потока.

3.8 Исследование систем 8М|С1|оо с квазиразложимым входящим потоком.

3.9 Метод интегральных преобразований для исследования систем 8М|Б|оо 108 Резюме. НО

Глава 4 Численный анализ коррелированных потоков, систем массового обслуживания с такими потоками в специальных предельных условиях.

4.1 Имитационные модели СМО с неограниченным числом приборов и коррелированными входящими потоками.

4.2 Применение алгоритмов численного анализа к исследованию коррелированных потоков и СМО с детерминированным обслуживанием

4.3 Сравнение результатов имитационного моделирования и асимптотического анализа СМО с коррелированными входящими потоками.

Резюме.

Введение диссертации (часть автореферата) на тему «Исследование систем массового обслуживания с коррелированными потоками в специальных предельных условиях»

Математические модели систем массового обслуживания широко применяются при исследовании процессов в. системах управления и организаций промышленными и сельскохозяйственными предприятиями, в сфере обслуживания (от предприятий общественного питания и бытового обслуживания до регулирования уровня воды в водохранилищах [69-70]); очистки воды [69]; в системах проектирования и анализа функционирования автоматизированных систем управления (АСУ) [69], в распределенных болыпемасштабных вычислительных системах, кластерных и Grid-системах, в системах противовоздушной обороны и средствах радиолокации, в различных экономических системах, системах телекоммуникации и т.п.

Первые работы по теории массового обслуживания связаны с именем датского ученого А.К. Эрланга (1878 - 1929) — сотрудника телефонной компании (до 1922). Его труды, опубликованные в 1908-1922 годах, в области проектирования и анализа функционирования телефонных станций вызвали большой интерес к математическим задачам по организации работы телефонных сетей.

Краткий исторический очерк развития теории массового обслуживания содержится, например, в работе [102].

В 1924 г Д. Юл (G. Jule). опубликовал работу, в которой определил понятие процесса чистого размножения, а в 30-х годах В. Феллер (W. Feller) ввел понятие процесса размножения и гибели. Одновременно были опубликованы фундаментальные работы по теории массового обслуживания А.Н. Колмогоровым, А .Я. Хинчиным [80] и Ф. Поллачеком (F. Pollaczek).

Основные работы в СССР по теории массового обслуживания с 60-х годов принадлежат школам Б.В. Гнеденко [26-28], A.A. Боровкова [7, 8].

Развитие микроэлектроники в 80-е года привело к существенным изменениям в области вычислительной техники и средств связи. Системы массового обслуживания оказались наиболее лучшим математическим аппаратом для исследования и оптимизации процессов в телекоммуникационных сетях. Применение классических моделей систем массового обслуживания к исследованию процессов в телекоммуникационных сетях давало достаточно грубые результаты. В связи с этим появилась необходимость создания адекватных математичеI ских моделей систем массового обслуживания применимых к реальным телекоммуникационным системам, и, прежде всего адекватных моделей телекоммуникационных потоков.

Одним из новых направлений исследований стало изучение процессов обслуживания в системах, входящие потоки которых отличны от классических потоков (пуассоновский и рекуррентный потоки [25-28, 52, 53]). В книге [28] Б.В.Гнеденко, И.Н. Коваленко, изданной в 2007, потоки этого класса названы специальными потоками однородных событий. В монографии А.Н. Дудина и В.И. Клименок [46] специальные потоки названы коррелированными.

В 1955 году Д. Кокс [89] предложил рассматривать потоки, интенсивность которых зависит от состояний некоторого процесса, управляющего такими потоками. Эти потоки были названы процессами Кокса. Позже были даны общие определения таких потоков [28].

Потоки Кокса являются основой класса специальных или коррелированных потоков, наиболее популярным из которых является МАР-поток (Mark-ovian Arrival Process). Впервые понятие МАР-потока было введено Ньютсом в 1979 году [99], а затем во время нового всплеска исследований уточнено Jly-кантони [97, 98]. Описание этого потока однородных событий можно найти в работах Б.В. Гнеденко, И.Н. Коваленко [28], А.Н. Дудина [46], A.A. Назарова [64]. Данный поток широко применим при исследовании СМО. Так, например, в работах [9, 10, 12, 24, 25, 73, 81, 97-99] рассматриваются системы, в которых на входе - МАР-поток. Непосредственно исследованию самого МАР-потока посвящена работа [99].

В терминах различных математических школ МАР-потоки также называются дважды стохастическими потоками, которые были введены в 1964 году Кингменом [95]. В таких потоках, во-первых, интервалы времени между наступлениями событий являются случайными, во-вторых, с течением времени интенсивность потока меняется случайным образом. Частными случаями дважды стохастических потоков [29, 30, 46] являются альтернирующие [54], синхронные [18, 19] и полусинхронные потоки [32], рассматриваемые A.M. Торцевым и его учениками с целью оценки параметров этих потоков.

Наиболее общим ординарным потоком однородных событий является полумарковский или SM-поток (Semi-Markovian process) [58]. Идея введения такого потока была выдвинута Леви (1954) и Смитом (1955). В книге Д. Кокса, В. Смита [54] наряду с исследованием простого процесса восстановления (рекуррентного потока) представлен альтернирующий процесс восстановления, модель которого может быть обобщена на случай полумарковского потока или его частного случая — потока марковского восстановления (Markovian renewal process). Системы массового обслуживания с таким входящим потоком интенсивно изучаются в настоящее время [72,73, 93, 95, 97, 98, 101].

Исследователи, занимающиеся потоками, также занимались изучением СМО с неограниченным числом приборов, на вход которых поступают специальные потоки, применяя главным образом методы численного анализа. В работах Д. Баума [8], JL Броера [9], были рассмотрены СМО BMAP|GI|oo, COX|GI|oo^ получено асимптотическое распределение числа занятых приборов в условии растущего времени обслуживания.

Для изучения потоков однородных событий и систем массового обслуживания применяют методы аппроксимации, имитационного моделирования, численного анализа, а также диффузионной или гауссовской аппроксимации. Эти методы не учитывают существенной особенности коррелированных потоков, заключающейся в дискретности процессов, управляющих этими потоками.

Цель и задачи исследования. Как показывают многочисленные примеры, достаточно популярная диффузионная или гауссовская аппроксимация в определенных условиях дает значительную погрешность при анализе коррелированных потоков и систем массового обслуживания с такими входящими потоками.

В частности для МАР-потока, заданного матрицами

1 0 0 -0.8 0.2 0.6 " 0 0.7 0.5

Л = 0 4 0 0.2 -0.5 0.3 0.6 0 0.8

0 0 8 0.2 0.3 -0.5 0.2 0.3 0 при заданных значениях 8 = 0.01 и ¿ = 5 распределение вероятностей

Р(м)=Р{и(*) = л}, где ;;(/) - число событий, наступивших в МАР-потоке за время имеет вид, как на следующем рисунке.

Данное распределение существенно отличающееся от гауссовского, поэтому возникает необходимость разработки нового метода исследования коррелированных потоков. В этой ситуации метод асимптотического анализа в специальных предельных условиях позволит найти распределение вероятностей числа событий, наступивших в потоке за определенное время, распределение вероятностей числа занятых приборов в системе массового обслуживания с неограниченным числом приборов и произвольной функцией распределения времени обслуживания, а также другие характеристики в других СМО.

Основной целью данной работы является разработка метода исследования коррелированных потоков и систем массового обслуживания с такими потоками.

В рамках указанной цели были поставлены следующие задачи: 1. Определение специальных предельных условий и классификация этих условий.

2. Модификация метода асимптотического анализа в специальных предельных условиях для исследования моделей коррелированных потоков, систем массового обслуживания с неограниченным числом приборов и такими входящими потоками.

3. Исследование допредельных моделей'систем массового обслуживания с неограниченным числом приборов с коррелированными входящими потоками и детерминированным временем обслуживания.

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

1. Определены предельные условия, которые названы специальными, учитывающие специфику коррелированных потоков, управляемых случайными процессами с дискретным множеством состояний, выполнена их классификация.

2. Введено понятие квазиразложимых цепей Маркова, допускающее предельно редкие переходы между классами, которое позволяет существенно сократить размерность решаемых задач, в том числе при исследовании коррелированных потоков и систем массового обслуживания с такими потоками больших размерностей.

3. Разработана модификация метода асимптотического анализа моделей коррелированных потоков однородных событий и систем массового обслуживания с такими потоками, позволяющая в предельных условиях находить аналитические выражения для вероятностно-временных характеристик коррелированных потоков и систем массового обслуживания с такими потоками.

4. Применив интегральный подход к исследованию систем массового обслуживания с неограниченным числом приборов с входящим МАР-потоком и детерминированным обслуживанием с использованием методов просеянного потока, матричной экспоненты и формулы Сильвестра [25, 59] найдено допредельное распределение вероятностей числа занятых приборов в системе.

Методы исследования. Основная часть исследований носит теоретический характер и основана на рассмотрении различных математических моделей коррелированных потоков однородных событий и систем массового обслуживания с такими входящими потоками. В ходе исследования рассмотренных моделей потоков и систем массового обслуживания с такими потоками применялся аппарат теории вероятностей, теории случайных процессов, теории массового обслуживания, теории дифференциальных уравнений. Для определения области применимости асимптотических результатов применялись численные расчеты на основе полученных в допредельной ситуации формул, а также была реализована имитационная модель систем массового обслуживания с неограниченным числом приборов.

Результаты, представленные в работе, имеют как теоретическое, так и практическое значение.

Теоретическая ценность работы заключается в разработке модификации • метода асимптотического анализа для исследования коррелированных потоков и систем массового обслуживания с неограниченным числом приборов и коррелированными входящими потоками, в обосновании многомодальности распределения вероятностей состояний таких моделей. Предложенная модификация метода асимптотического анализа допускает его дальнейшее развитие для построения и исследования неординарных потоков (ВМАР-потоков) и систем массового обслуживания с такими потоками.

Практическая ценность работы заключается в применении метода асимптотического анализа в специальных предельных условиях и разработке комплекса программ, позволяющие находить вероятностно-временные характеристики исследуемых моделей, для исследования более адекватных математических моделей потоков и систем в различных предметных областях, в частности для исследования телекоммуникационных потоков, компьютерных сетей связи, кредитно-депозитных организаций и страховых компаний.

Публикации. По материалам диссертации опубликовано 16 работ, из них 3 статьи в журналах списка ВАК:

1. Горбатенко А.Е. Асимптотический анализ системы ММР|М1|ИПВ в условии предельно редких изменений состояний входящего потока / А.Е. Горбатенко, A.A. Назаров // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2009. - Т315. - №5. - С. 187-190.

2. Горбатенко А.Е. Асимптотики произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. — № 2 (11). — С. 35-43.

3. Горбатенко А.Е. Исследование полумарковского потока в условии предельно редких изменений его состояний / А.Е. Горбатенко, A.A. Назаров // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева. - 2010. - № 2 (28). — С. 8-11.

4. Горбатенко А.Е. Исследование системы ММР | М | оо в условиях предельно редких изменений состояния входящего потока // Материалы XI Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 20-21 апреля 2007г. - Томск: Изд-во Том. ун-та, 2007. - Ч. 1. - С. 14-17. I

5. Горбатенко А.Е. Исследование системы MAP|GI|qo в условиях предельно редких изменений состояния входящего потока / А.Е. Горбатенко, А.А.Назаров // Труды VII Всероссийской конференции по финансово-актуарной математике и смежным вопросам. Красноярск, 29 февраля - 4 марта 2008 г. - Красноярск: Сибирский федеральный ун-т, 2008. -4.2. — С. 58-62.

6. Горбатенко А.Е. Исследование МАР-потока в условии растущей интенсивности / А.Е. Горбатенко, A.A. Назаров // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. — 2008. - № 3 (4). - С. 66-70.

7. Горбатенко А.Е. Метод асимптотического анализа ММР-потока в условии растущей интенсивности // Материалы XII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 18-19 апреля 2008 г. - Томск: Изд-во Том. ун-та, 2008. -Ч. 1.-С. 14-17.

8. Горбатенко А.Е. Исследование системы MAP|GI|oo в условии растущей интенсивности входящего потока / А.Е. Горбатенко, A.A. Назаров // Теория вероятностей и, случайные процессы, математическая статистика и приложения. Сборник научных статей международной научной конференции. Минск, 15-19 сентября 2008 г. - Минск: Издательский центр БГУ, 2008. - С. 52-56.

9. Горбатенко А.Е. Метод асимптотического анализа МАР-потока в условии предельно редких изменений состояний потока / А.Е. Горбатенко, A.A. Назаров // Современные информационные компьютерные технологии: сб. науч. ст. в 2 ч. (mcIT - 2008). - Гродно: ГрГУ, 2008. - Ч. 2. - С. 30-32.

10. Горбатенко А.Е. Нахождение асимптотик произвольного порядка для системы MAP|GI|oo в условии растущей интенсивности входящего потока // Информационные технологии и математическое моделирование (ИТММ-2008): Материалы VII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 14-15 ноября 2008 г. - Томск: Изд-во Том. ун-та, 2008. - Ч. 2. - С. 10-15.

11. Горбатенко А.Е. Метод асимптотического анализа ММР-потока, управляемого квазиразложимой цепью Маркова, в условии растущего времени // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции "Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск, 26-29 января 2009 г. - Минск: РИВШ, 2009. - С. 85-89.

12. Горбатенко А.Е. Асимптотический анализ МАР-потока, управляемого квазиразложимой цепью Маркова // Труды VIII Международной конференции по финансово-актуарной математике и смежным вопросам. Красноярск,

24-26 апреля 2009 г. - Красноярск: Сибирский федеральный ун-т, 2009. - Ч. 2.

- С. 26-28.

13.Горбатенко А.Е. Исследование системы ММР|м|оо в условии квазиразложимости цепи Маркова // Материалы XIII Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г.Анжеро-Судженске, 14—15 мая 2009г. - Томск: Изд-во Том. ун-та, 2009. -Ч. 1.

- С. 26-28.

14. Горбатенко А.Е. Асимптотический анализ системы MAP | M | оо в условии квазиразложимости цепи Маркова // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г.Анжеро-Судженске, 12-13 ноября 2009г. - Томск: Изд-во Том. ун-та, 2009.-Ч. 1.-С. 16-20.

15. Горбатенко А.Е. Исследование квазиразложимого полумарковского потока // Теория вероятностей математическая статистика и их приложения: сборник научных статей (материалы Международной конференции, посвященной 75-летию профессора, доктора физико-математических наук Геннадия Алексеевича Медведева). Минск, 22-25 февраля 2010г. - Минск: РИВШ, 2010.

- С. 53-59.

16. Горбатенко А.Е. Исследование системы SM|M|oo в условии предельно редких изменений состояний потока и условии растущего времени обслуживания / А.Е. Горбатенко, C.B. Лопухова // Материалы XIV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро-Судженске, 15-16 апреля 2010 г. - Томск: Изд-во Том. унта, 2010.-Ч. 1.- С. 16-19.

17. Gorbatenko A. SM|Mqo in special limit conditions / A. Gorbatenko, S. Lopuchova // The third international conference «Problems of cybernetics and in-formatics»(PCP2010), Baku, Azerbaijan. 6-8 September, 2010. - Baku: Elm, 2010. -V. 2. — P.213-217.

Апробация работы. Основные положения работы и отдельные ее результаты докладывались и обсуждались:

1. XI Всероссийская научно-практическая конференция «Научное творчество молодежи», г. Анжеро-Судженск, 2007 г.

2. VII Всероссийская конференция по финансово-актуарной математике и смежным вопросам, г. Красноярск, 2008 г.

3. XII Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2008 г.

4. Международная научная конференция «Теория вероятностей и, случайные процессы, математическая статистика и приложения», г. Минск, 2008 г.

5. Международная научная конференция «Математические методы повышения эффективности функционирования телекоммуникационных сетей». Минск, 2007 г.

6. VII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2008 г.

7. Международная научная конференция "Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск, 2009 г.

8. VIII Международная конференция по финансово-актуарной математике и смежным вопросам. Красноярск, 2009 г.

9. ХШ Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2009 г.

10.VIII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2009 г.

11 .Международная конференция, посвященной 75-летию профессора, доктора физико-математических наук Геннадия Алексеевича Медведева. Минск, 2010 г.

12.XIV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2010 г.

13.The third international Conference «Problems of Cybernetics and Informatics» (РСГ2010). Baku, 2010.

14. International conference «Modern Stochastics: Theory and Applications II», Kiev, 2010.

Структура работы. Работа состоит из введения, четырех глав, заключения и списка использованной литературы.

В первой главе определяются специальные предельные условия для рассматриваемых коррелированных потоков (MAP, SM) и проводится исследования рассматриваемых потоков с помощью метода асимптотического анализа в специальных предельных условиях.

Основной целью исследования потоков является нахождение распределения вероятностей числа n(t) событий, наступивших в потоке за время L

Случайный процесс n(t) для рассматриваемых коррелированных потоков не является марковским, поэтому с помощью метода дополнительной переменной в разделе 1.1 выполнена их марковизация, а в разделе 1.2 получены системы дифференциальных уравнений Колмогорова для характеристических функций, определяющих функционирование этих потоков.

Для МАР-потока была введена дополнительная переменная k(t) и рассмотрен случайный процесс который является двумерной цепью

Маркова. Для этого марковского процесса определены характеристические функции и для них составлена система дифференциальных уравнений Колмогорова, из которой при задании начальных условий получена задача Коши

00

H(k,u,t) = Y,eJimP(k,n,t) п=0 и,0) = Д9 для векторной характеристической функции

Здесь <2 - матрица инфинитезимальных характеристик, управляющей цепи Маркова к{(), а матрица В = А+0*(), А - диагональная матрица условных ин-тенсивностей МАР-потока, £> - матрица вероятностей наступления событий МАР-потока в момент изменения состояния управляющей цепи Маркова, Я — вектор стационарного распределения вероятностей цепи Маркова Щ).

Для 8М-потока были введены дополнительные переменные .?(/), и рассмотрен случайный процесс который является трехмерным марковским процессом. Для этого марковского процесса определены характеристические функции со л=0 и для них составлена система дифференциальных уравнений Колмогорова, из которой при задании начальных условий получена задача Коши дН{и,г,{) дН(и,0,() дt дг дг

Н(и,г,0) = для векторной характеристической функции

Н(и,г,/) = {#(1, (2,г/,г,.

Здесь / - единичная матрица, а Я{г) - вектор стационарного распределения двумерного марковского процесса {.?(/),А(г) - полумарковская матрица.

Решение полученных задач найдено с помощью метода асимптотического анализа в специальных условиях.

1. В условии предельно редких изменений состояний потока Условие предельно редких изменений состояний МАР-потока:

8^, 5—>0, определяющее достаточно малые значения инфинитезимальных характеристик. Здесь матрица инфинитезимальных характеристик управляющей

МАР-потоком цепи Маркова к(/).

Условие предельно редких изменений состояний полумарковского потока формализуется следующим равенством для матрицы Р(Ь) вероятностей переходов его вложенной цепи Маркова

Р(5) = / + 8-С>.

2. В условии растущих условных интенсивностей потока Условие растущих условных интенсивностей МАР-потока: определяющее достаточно большие значения условных интенсивностей потока и существенные различия их значений.

3. В условии квазиразложимости.

Цепь Маркова к(1) с непрерывным временем I будем называть квазиразложимой, если выполняется следующее условие:

2(1) = <2+§2(0), 8->О, где 5 — некоторый малый положительный параметр (8 —> 0).

Цепь Маркова к{1) является квазиразложимой, если множество ее состояний можно разбить на Мквазизамкнутых классов к,(/), Ы\,М (переход из одного класса в другой осуществляется редко).

МАР-поток будем называть квазиразложимым, если его управляющая цепь Маркова является квазиразложимой с непрерывным временем.

Цепь Маркова с дискретным временем будем называть квазиразложимой, если для матрицы вероятностей переходов выполнено следующее условие:

Р(8) = Р + 8-2, где 8 — некоторый малый положительный параметр (8 —0). Здесь Р — блочно-диагональная матрица, блоки которой являются стохастическими (марковскими) матрицами, а свойства матрицы совпадают со свойствами матрицы инфинитезимальных характеристик.

БМ-поток будем называть квазиразложимым, если его вложенная цепь Маркова является квазиразложимой с дискретным временем.

С помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивно-стей в разделах 1.4 и 1.5 найдено первое приближение асимптотического распределения вероятностей числа событий, наступивших в МАР-потока за время / в виде которое является, взвешенной суммой пуассоновских распределений с весами Я(к), поэтому рассматриваемое распределение может быть многомодальным. Также найдены асимптотики более высокого порядка, существенно повышающие точность аппроксимации допредельного распределения.

В разделе 1.6 был исследован МАР-поток методом асимптотического анализа в условии квазиразложимости, позволивший существенно понизить размерность решаемых задач, исследование которых выполнено методом асимптотического анализа в условии растущего времени наблюдения [60]. Найдено асимптотическое распределение вероятностей Рх{п,1) числа «(/) событий, наступивших в квазиразложимом МАР-потоке за время / в виде

1 2а„,< т 1 где параметры ат и а~ определяются равенствами а=г{т)В{т)Е, т т' здесь дО») + £)(">) * 0 тт ■ а вектор-строка /2(т) является решением матричного уравнения (системы линейных алгебраических уравнений) которое удовлетворяет условию

Лт)Ет = 0.

Константы ст определяются системой т=1

Л/

Найденное асимптотическое распределение вероятностей является взвешенной суммой дискретного аналога гауссовских распределений.

В разделе 1.7 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и преобразований Лапласа найдено асимптотическое распределение вероятностей числа и (г) событий, наступивших в 8М-потока за время которое имеет вид (М=1 - "Ш1 - «"*)£ V. (1 - о; {у)уу,

Z7t -О0 У 3 СО л Т 00

К -а, У « 4=1 где 1 »-> о а вектор г — это вектор стационарного распределения вероятностей вложенной цепи Маркова.

В разделе 1.8 был исследован БМ -поток методом асимптотического анализа в условии квазиразложимости, позволивший существенно понизить размерность решаемых задач, исследование которых выполнено методом асимптотического анализа в условии растущего времени наблюдения [60]. Найдено асимптотическое распределение вероятностей Рх{п^) числа и(7) событий, наступивших в квазиразложимом 8М-потоке за время t в виде м т=1 ехр

2а2/ т

Еехр у=0

2а2? т где 1 я« г{т)АЕ. су! = а + 2

5/^(0) т т дг

Е, т » здесь вектор функция /2("'} (г) является таким решением уравнения дй"!)(;), дЯ™ (0) дг + дг - / )" ^ « = о, которое удовлетворяет условию Константы ст определяются системой т=1 М

2>.= т=1

Найденное асимптотическое распределение вероятностей Р^и,/) является взвешенной суммой гауссовских распределений.

Во второй главе выполнено исследование марковских систем массового обслуживания с неограниченным числом обслуживающих приборов и с корре

- 19лированными входящими потоками (MAP, SM) в специальных предельных условиях (условие предельно редких изменений состояний потока, условие растущей интенсивности потока, условие квазираложимости управляющего потоком процесса).

Основной целью исследования таких систем массового обслуживания является нахождение распределения вероятностей числа i(t) занятых приборов в системе. Система функционирует в стационарном режиме.

Случайный процесс i{t) для рассматриваемых СМО с коррелированными входящими потоками не является марковским. Поэтому с помощью метода дополнительной переменной в разделе 2.1 была выполнена их марковизация и получены системы дифференциальных уравнений Колмогорова для характеристических функций, определяющих функционирование этих систем.

Для систем с входящим МАР-потоком была введена дополнительная переменная k(t) и рассмотрен случайный процесс [k(t)J(t)}, который является двумерной цепью Маркова. Для этого марковского процесса определена векторная характеристическая функция Н (г/) и для нее составлено дифференциально-матричное уравнение Колмогорова, из которого при задании дополнительного условия получена следующая задача я(о)=я.

Для систем с входящим SM-потоком были введены дополнительные переменные s(t), z(t) и рассмотрен трехмерный процесс , который является марковским процессом. Для этого марковского процесса определена векторная характеристическая функция H(u,z) и для нее составлено дифференциально-матричное уравнение Колмогорова, из которого при задании дополнительного условия получена следующая задача z v 'du dz L } z

H(0,z) = R(z).

Решение полученной задачи найдено с помощью метода асимптотического анализа в специальных условиях, определенных в разделе 1.3.

В разделах 2.2 и 2.3 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивностей найдено первое приближение асимптотического стационарного распределения вероятностей числа i(t) занятых приборов в системе МАР|М|оо, которое является взвешенной суммой пуассоновских распределений с весами R(k). Поэтому рассматриваемое распределение может быть многомодальным. где Ч

Рк= — •

Также найдены асимптотики более высокого порядка, существенно повышающие точность аппроксимации допредельного распределения.

В разделе 2.4 проведено исследование системы МАР|М|оо с квазиразложимым МАР-потоком. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условиях растущего времени обслуживания [66].

Асимптотическое стационарное распределение вероятностей /}(;) является взвешенной суммой дискретных аналоговых гауссовских распределений, то есть имеет вид м т=1 ехр

2сг

2>р v=0

2al где здесь вектор-строка /2(т) является решением матричного уравнения (системы линейных алгебраических уравнений)

В разделе 2.5 исследованы системы 8М|М|со в асимптотическом условии предельно редких изменений состояний полумарковского потока. С помощью метода асимптотического анализа в условиях растущего времени обслуживания, которое было предложено в работе [66], найдено распределение вероятностей числа занятых приборов в системе

КО=1л

Хехр т=О

2 а?

2П где а. = ■ а2 — а 5 о ' здесь функция является таким решением уравнения дг & дг которое удовлетворяет условию

В разделе 2.6 проведено исследование системы 8М|М|оо с квазиразложимым 8М-потоком. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условии растущего времени обслуживания[66]. Найдено распределение вероятностей числа занятых приборов в системе м m=1 ехр

2а!

2>р v=0

2а?

21Л 2 а + 2 у > Е , и m т' а вектор функция /2(т) (z) является таким решением уравнения которое удовлетворяет условию

В третьей главе выполнено исследование систем массового обслуживания с неограниченным числом обслуживающих приборов, произвольной функцией распределения времени обслуживания заявок и с коррелированными входящими потоками (MAP, SM) в специальных предельных условиях (условие предельно редких изменений состояний потока, условие растущей интенсивности потока, условие квазираложимости управляющего потоком процесса).

Основной целью исследования систем массового обслуживания является нахождение распределения вероятностей числа /(/) занятых приборов в системе. Случайный процесс i(t) для рассматриваемых СМО с коррелированными входящими потоками не является марковским. Применение метода дополнительной переменной не дает марковизацию процесса i(t), поэтому в данной главе был рассмотрен метод просеянного потока [66], основная идея которого заключается в том, что с вероятностью S(f) поступившая заявка формирует событие просеянного потока, а с вероятностью 1 - S(t) не рассматривается. Зависимость S от / определяется распределением времени обслуживания.

В некоторый конечный момент времени i\ число n(t) событий, наступивших в просеянном потоке равно числу занятых приборов в рассматриваемой системе массового обслуживания, то есть п(Н) = /(/1). Исследование таких систем массового обслуживания сводится к исследованию просеянного потока.

Для просеянного потока системы МАР|С1|оо введена дополнительная переменная к{{) и рассмотрен двумерный процесс который является нестационарной цепью Маркова. Для этого марковского процесса определена векторная характеристическая функция Н (и,/) и для нее составлено матричнодифференциальное уравнение Колмогорова, из которого при задании начального условия получена задача Коши

Для просеянного потока системы SM|GI|oo были введены дополнительные переменные s(t), z(t) и рассмотрен трехмерный процесс {s{t\n{t),z{i)^, который является марковским процессом. Для этого марковского процесса определена векторная характеристическая функция H(u,z,t) и для нее составлено матрично-дифференциальное уравнение Колмогорова, из которого при задании начального условия получена задача Коши

Решение полученных задач найдено с помощью метода асимптотического анализа в специальных условиях, определенных в разделе 1.3.

В разделах 3.3 и 3.4 с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и условиях растущих условных интенсивностей найдено первое приближение асимптотического распределения вероятностей числа г(/) занятых приборов в системе МАР|01|оо, которое является взвешенной суммой пуассоновских распределений с весами Я(к). Поэтому рассматриваемое распределение может быть многомодальным:

H(u,t0) = R, t0<t<tx. dt с

H(u,z,t0) = R(z). где

Рк=К -ь,

О «3

6= |(1-Я (*))*&.

-00 О

Также найдены асимптотики более высокого порядка, существенно повышающие точность аппроксимации допредельного распределения.

В разделе 3.5 проведено исследование системы МАР|01|оо с квазиразложимым МАР-потоком. В предельных условиях удается существенно понизить размерность решаемых задач, исследование которых выполняется методом асимптотического анализа в условиях растущего времени обслуживания [66]. Найдено распределение вероятностей числа занятых приборов в системе и т=\ ехр<

Р~р т)2

2а у=0 сг

Р т = атЪ, ст2и=рт+2ктР, ¡32(х)с1х, к т =

00

В разделе 3.6 исследована система массового обслуживания МАРр|оо с неограниченным числом приборов, на вход которой поступает МАР-поток заявок, а продолжительность обслуживания заявок является детерминированной величиной, равной Ь.

Исследование системы МАР|Б|оо выполнено методом матричной экспоненты. Найдено распределение вероятностей числа занятых приборов в системе МАРр|оо 2п} ыь Ц ю,(г/) —ш (г/)

Ес1и.

В разделах 3.7 и 3.8 исследованы системы 8М|С1|оо с помощью метода асимптотического анализа в условиях предельно редких изменений состояний потока и в условии квазиразложимости с помощью метода асимптотического анализа в условиях растущего времени обслуживания [66].

В условии предельно редких изменений состояний полумарковского потока найдено распределение вероятностей числа занятых приборов в системе

В предельном условии квазиразложимости удается существенно понизить размерность решаемых задач. Найдено распределение вероятностей числа занятых приборов в системе

В разделе 3.9 исследована система массового обслуживания 8М|Б|оо с неограниченным числом приборов, на вход которой поступает полумарковский поток заявок, а продолжительность обслуживания заявок является детерминированной величиной, равной Ъ.

Исследование системы 8М|Э|со проводилось с помощью преобразования Фурье-Стильтьеса. Найдено распределение вероятностей числа занятых приборов в системе $М|Б|оо. о

00

00 о величина а определяется равенством а - -, гАЕ матрица А имеет вид

00 о а вектор г - это вектор стационарного распределения вероятностей вложенной цепи Маркова.

В главе 4 применяются алгоритмы численного анализа коррелированных потоков, систем массового обслуживания с такими потоками в специальных предельных условиях.

Для определения точности аппроксимации находится расстояние Колмогорова Ак.

Для коррелированных потоков Ак определяется следующим образом

Ак = тах|^(л,/)-^(т7,/) , где - допредельная функция распределения числа событий наступивших в потоке за время /, полученная с помощью метода матричной экспоненты для МАР-потока и с помощью интегрального преобразования для 8М-потока, (/?,/) - аппроксимация допредельной функции распределения числа событий наступивших в потоке за время полученная с помощью метода асимптотического анализа в специальных предельных условиях .

Для СМО с неограниченным числом приборов и коррелированными входящими потоками реализована имитационная модель.

Для оценки точности результатов, полученных с помощью имитационного моделирования рассматривается система МАР|С1|оо, на вход которой поступает МАР-поток с параметрами Хк = X и - 0. Также рассматривается систе-I ма 8М|01|оо, на вход которой поступает полумарковский поток, для которого условные функции распределения имеют вид О^ (х) = 1 - . Время обслуживания заявок является рекуррентным с функцией распределения В(х). В этих системах входящие потоки являются простейшими и распределение числа занятых приборов является пуассоновским (формула Эрланга) с параметром Где Ъ - среднее значение времени обслуживания заявки. Погрешность имитационной модели составляет менее 1%.

Для СМО с неограниченным числом приборов и коррелированными входящими потоками величина Ак определяется следующим образом где ^Р(г) - функция распределения числа занятых приборов в системе, полученная с помощью имитационного моделирования, ^ (/') — аппроксимация допредельной функции распределения числа занятых приборов в системе, полученная с помощью метода асимптотического анализа в специальных предельных условиях.

При уменьшении параметра 5 уменьшается отклонение результатов асимптотического анализа в специальных предельных условиях от результатов допредельного исследования коррелированных потоков и от результатов имитационного моделирования для СМО с неограниченным числом приборов и коррелированными входящими потоками.

При 5 < 0,01 величины Ак составили менее 0,01. Это позволяет сделать вывод о том, что применение метода асимптотического анализа для коррелированных потоков дает достаточно точную аппроксимацию допредельного распределения.