Исследование систем массового обслуживания с коррелированными потоками в специальных предельных условиях

Математические модели систем массового обслуживания широко применяются при исследовании процессов в. системах управления и организаций промышленными и сельскохозяйственными предприятиями, в сфере обслуживания (от предприятий общественного питания и бытового обслуживания до регулирования уровня воды в водохранилищах [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) и рассмотрен случайный процесс который является двумерной цепью.

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

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а&bdquo-,< т 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(„'} (г) является таким решением уравнения дй“ !)(-), дЯ&trade- (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{tn{t), z{i)^, который является марковским процессом. Для этого марковского процесса определена векторная характеристическая функция H (u, z, t) и для нее составлено матрично-дифференциальное уравнение Колмогорова, из которого при задании начального условия получена задача Коши.

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

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

H (u, t0) = R, t0.

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

Рк=Кь,.

О «3.

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

— 00 О.

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

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

Р~р т)2.

2а у=0 сг.

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

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

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

Ес1и.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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