В настоящее время внимание к теории массового обслуживания в значительной степени стимулируется необходимостью применения ее результатов для важных практических задач, возникающих в связи с бурным развитием систем коммуникаций, возникновением информационно-вычислительных систем, появлением и усложнением разнообразных технологических систем, созданием автоматизированных систем управления, для задач экономико-математического моделирования.
Основоположником теории массового обслуживания считается датский ученый К. А. Эрланг (1878−1929). Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 году работу «Теория вероятностей и телефонные переговоры», в которой решил ряд задач по теории систем массового обслуживания с отказами.
Значительный вклад в создание и разработку общей теории массового обслуживания внес выдающийся советский математик А. Я. Хинчин (1984;1959), который предложил сам термин теория массового обслуживания [65]. В зарубежной литературе используется название теория очередей. Он исследовал од-ноканальную систему с простейшим входящим потоком и рекуррентным обслуживанием, установив, что стационарное распределение вероятностей числа заявок в системе совпадает с их стационарным распределением в моменты ухода заявок из системы.
Большой вклад в развитие теории массового обслуживания внесли А. Н. Колмогоров, Ю. К. Беляев, A.A. Боровков, Б. В. Гнеденко и И. Н. Коваленко [13−15], Дж. Кендалл, JI. Клейнрок, Г. П. Климов, С. Пальм, Ф. Поллачек, Т. Саати, А. Я. Хинчин [13, 66] и др.
Краткий исторический очерк развития теории массового обслуживания содержится, например, в работах [57, 106].
Важным разделом теории массового обслуживания является теория систем с повторными вызовами (Retrial Queue Systems или RQ-системы) [3, 19, 22, 62]. Это обусловлено их широкими практическими приложениями. Область приложений лежит в оценивании производительности и проектировании телефонных сетей, локальных вычислительных сетей с протоколами случайного множественного доступа, широковещательных радиосетей, мобильных сотовых радиосетей. Наличие повторных попыток получить обслуживание является неотъемлемой чертой этих систем, игнорирование данного эффекта может привести к значительным погрешностям при принятии инженерных решений.
Первые математические результаты, касающиеся систем с повторными вызовами, были опубликованы в 40-х гг. прошлого века [100]. Обзоры работ, посвященные данным системам, содержатся в статьях [72, 73, 84, 101, 108]. В монографиях известных специалистов в области теории систем с повторными вызовами Г. И. Фалина, Дж. Темплтона, например, в [97] подчеркнуто, что стандартные модели очередей не в силах описать ЯС)-системы, так как в них отсутствует эффект повторения, и поэтому они не могут быть применены к решению многих фактически важных проблем. В [97] проведено исследование ЯС)-системы М|М|1, где найдена гауссовская аппроксимация, в нашей терминологии асимптотика второго порядка, в настоящей диссертационной рабе предлагается исследование Ж^-систем методом асимптотических семиинвариантов произвольного порядка, которое существенно уточняет аппроксимацию. Также рост интереса к исследованию Ш^-систем отражен в международных журналах [49, 71, 74, 107]. По этой тематике в монографии [75] приведено более семисот ссылок на работы, опубликованные за последние двадцать лет. Исследования в области теории Ж^-систем можно найти в работах Г. И. Фалина [82, 83, 85−96].
Одной из трудных проблем, связанных с построением более адекватных моделей массового обслуживания для сетевых систем, является учет фактора повторных заявок. Особенно трудоемкой является задача исследования систем массового обслуживания с повторными заявками в случае, когда входящий поток заявок является коррелированным.
В данной работе будем рассматривать следующие модели входящих коррелированных потоков:
• МАР-поток (Markovian Arrival Process) и его частные случаи: пуассо-новский поток, ММРР-поток, SMAP-поток.
• SM-поток (Semi-Markovian).
Здесь МАР-поток является достаточно общей моделью ординарных потоков с дискретной компонентой, подробное описание которого можно найти в работах Б. В. Гнеденко, И. Н. Коваленко [14], А. Н. Дудина [17, 18], A.A. Назарова [35], С. В. Лопуховой [31]. Системам с входящим МАР-потокам посвящены работы [6, 7, 9, 10, 12, 23, 33, 98]. Непосредственно исследованию самого МАР-потока посвящена работа [69].
Наиболее общей моделью ординарных потоков с непрерывной компонентой является полумарковский поток — SM-поток. Идея введения такого потока была выдвинута Леви (1954) и Смитом (1955). Системы массового обслуживания (СМО) с таким входящим потоком интенсивно изучаются в настоящее время [12, 53,54, 67,81, 105].
Исследователи, занимающиеся потоками, также занимались изучением СМО с неограниченным числом приборов, на вход которых поступают коррелированные потоки, применяя главным образом методы численного анализа. Анализ числа занятых приборов в системах BMAP|GI|oo, COX|GI|oo, можно найти, например, в работах немецких ученых Д. Баума [77] и Л. Броера [78]. В работе О. М. Тихоненко [64] определяются характеристики суммарного объема требований в системе с неограниченным числом приборов M|G|oo.
A.A. Боровков в работе [4] выполнил исследование систем с бесконечным числом каналов обслуживания, где доказываются предельные теоремы для случайных процессов. Предложенный в настоящей диссертации метод асимптотических семиинвариантов реализуется в исследовании уравнений при выполнении некоторого асимптотического условия, вид которого конкретизируется для различных моделей исследования.
В работе [30] изучается бесконечнолинейная СМО с групповым числом заявок, одновременно поступающих в систему и доказывается теорема о максимальном числе заявок в группе. Так же исследованию систем массового обслуживания с неограниченным числом обслуживающих приборов посвящены работы [И, 21, 55, 76, 79, 80, 104].
В настоящее время не существует универсального метода исследования немарковских систем с неограниченным числом приборов и непуассоновским входящим потоком, что не позволяет получить точные характеристики, аналитические выражения для вероятностей состояний исследуемых систем.
Настоящая диссертационная работа посвящена исследованию ЯС>-систем и систем с неограниченным числом обслуживающих приборов с коррелированными входящими потоками. Исследование проводится при помощи модифицированного метода асимптотического анализа, методом асимптотических семиинвариантов [1, 20, 27, 31, 34, 36]. Также исследуются системы с неограниченным числом обслуживающих приборов методом просеянного потока.
Межпредметность рассматриваемых моделей. В настоящее время математические модели систем массового обслуживания широко применяются при исследовании систем телекоммуникации, транспортных системах, в экономических системах, таких как кредитно-депозитные организации и страховые компании.
На современном этапе развития теории массового обслуживания одним из востребованных направлений является исследование ЯС)-систем, которые возникли как аппарат моделирования систем телефонии [99] и зарекомендовали себя в исследовании моделей различных компьютерных сетей и логических системах.
В качестве математических моделей страховых компаний, кредитно-депозитных организаций, Пенсионного фонда и многих других экономических и социально-экономических систем предлагается рассматривать системы с неограниченным числом приборов. Например, количество возможных договоров между клиентами и кредитно-депозитной организацией практически неограниченно. Сроки, на которые заключаются договоры, имеют весьма широкий спектр продолжительностей, поэтому достаточно адекватно могут моделироваться некоторой случайной величиной с заданной функцией распределения их значений. Поток клиентов, обращающихся в кредитно-депозитную организацию, может быть как пуассоновским, так и коррелированным. Таким образом, математической моделью многих экономических систем может служить СМО с неограниченным числом приборов.
Также различные математические модели систем массового обслуживания широко применяются при исследовании процессов в системах управления и организаций промышленных предприятий, в сфере обслуживания (от предприятий общественного питания и бытового обслуживания до регулирования уровня воды в водохранилищах [51−52]) — очистки воды [51]- в системах проектирования и анализа функционирования автоматизированных систем управления [51].
Цель и задачи исследования
Целью данной работы является разработка метода асимптотических семиинвариантов для анализа ЯС^-систем и систем с неограниченным числом приборов с коррелированными входящими потоками в условии большой задержки в И11 В и растущего времени обслуживания, а также развитие метода просеянного потока для исследования немарковских СМО с неограниченным числом приборов, рекуррентным обслуживанием и коррелированными входящими потоками.
В рамках указанной цели были поставлены следующие задачи:
1. Модификация метода асимптотического анализа для исследования Яр-системы МАР|М| 1 и ее частных случаев, в условии большой задержки заявки в источнике повторных вызовов, в виде метода асимптотических семиинвариантов с использованием характеристических функций и матричной формы записи.
2. Развитие метода просеянного потока для исследования немарковских систем с неограниченным числом обслуживающих приборов и коррелированными входящими потоками.
3. Модификация метода асимптотического анализа для исследования систем с неограниченным числом обслуживающих приборов и коррелированными входящими потоками, в виде метода асимптотических семиинвариантов в условии растущего времени обслуживания заявки на приборе.
4. Разработка численных алгоритмов вычисления допредельного распределения вероятностей состояний ЯС>-систем и систем с неограниченным числом приборов.
5. Разработка комплекса проблемно-ориентированных программ расчета вероятностных характеристик ЯС)-систем и систем с неограниченным числом приборов.
Научная новизна и результаты, выносимые на защиту, состоят в следующем:
1. Выполнена модификация метода асимптотического анализа для исследования марковских ЛС^-систем в виде метода асимптотических семиинвариантов в предельном условии большой задержки заявок в ИПВ. Предложенный метод определяет вид предельной характеристической функции в форме экспоненты с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка. Данный метод позволяет последовательно находить аппроксимации допредельного распределения вероятностей состояний системы более чем второго порядка, и отличается возможностью получения семиинвариантов произвольного порядка.
2. Выполнено развитие метода просеянного потока для исследования систем с неограниченным числом приборов, коррелированными входящими потоками широкого класса и рекуррентным обслуживанием. Данный метод позволяет проблему исследования немарковской СМО с неограниченным числом приборов свести к задаче анализа просеянного нестационарного потока, что позволило выполнить ее исследование асимптотическим методом и найти явные выражения для характеристической функции распределения вероятностей.
3. Выполнена модификация метода асимптотического анализа для исследования систем с неограниченным числом приборов в виде метода асимптотических семиинвариантов в предельном условии растущего времени обслуживания заявки на приборе. Предложенный метод определяет вид предельной характеристической функции в форме экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты.
— 10соответствующего порядка. Данный метод позволяет последовательно находить аппроксимации допредельного распределения вероятностей состояний системы более второго порядка, и отличается возможностью получения семиинвариантов всё более высокого порядка.
4. Для марковской системы с неограниченным числом приборов и входящим МАР-потоком разработан алгоритм последовательного нахождения допредельных моментов произвольного (более чем второго) порядка.
5. С помощью полученных методов доказано, что асимптотические семиинварианты числа занятых приборов в системе с неограниченным числом приборов и коррелированными входящими потоками определяются лишь семиинвариантами этих потоков и определенными параметрами времени обслуживания, при этом количество семиинвариантов потока и параметров обслуживания совпадает с порядком асимптотики и аппроксимации.
6. Разработаны численные алгоритмы исследования ЯС)-систем и систем с неограниченным числом приборов, позволяющие находить различные вероятностно-временные характеристики рассматриваемых систем с коррелированными входящими потоками в допредельной ситуации, отличающиеся высокой точностью получаемых результатов.
Методы исследования. Основная часть проведенных исследований носит теоретических характер и основана на применении аппарата теории вероятностей, теории массового обслуживания, теории матриц, теории дифференциальных уравнений, метода асимптотического анализа. Для исследования 11(2-систем использовались методы асимптотических семиинвариантов, методы аппроксимации, численного анализа. Для исследования систем с неограниченным числом приборов в работе применялись методы просеянного потока, методы асимптотических семиинвариантов, численные алгоритмы, имитационное моделирование, результаты которого обрабатывались методами математической статистики.
Результаты, полученные в работе, имеют как теоретическое, так и практическое значения.
Теоретическая ценность работы заключается в разработке методов исследования RQ-систем, применимых для широкого класса таких моделей, определяемых разнообразием класса входящих потоков, а также в разработке методов исследования систем с неограниченным числом обслуживающих приборов, которые позволили доказать то, что асимптотическое распределение вероятностей определяется лишь только асимптотическими семиинвариантами входящего потока и определенными параметрами времени обслуживания, что существенно упрощает исследование данных систем.
Практическая ценность работы. Результаты, полученные в работе, могут быть применены для анализа важных практических задач. Область приложений рассматриваемых RQ-систем лежит в оценивании производительности и проектировании компьютерных сетей, при создании космических (спутниковых) сетей связи, в которых спутник-ретранслятор исполняет роль центрального узла связи. Системы с неограниченным числом приборов являются математическими моделями страховых компаний, кредитно-депозитных организаций, Пенсионного фонда и многих других экономических и социально-экономических систем, где одной из важных характеристик является количество заключенных договоров. По результатам разработанного комплекса проблемно-ориентированных программ получены два сертификата о регистрации электронных ресурсов, отвечающих требованиям новизны и приоритетности.
Связь работы с крупным научным проектом. Результаты, представленные в данной работе, были получены в рамках выполнения научного проекта АВЦП «Развитие научного потенциала высшей школы (2009 — 2011 годы)» Федерального агентства по образованию, проект № 11 803: «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи».
Публикации. По материалам диссертации опубликовано 16 работ, из них 4 статьи в журналах списка ВАК:
1. Семенова И. А. Исследование RQ-систем методом асимптотических семиинвариантов / A.A. Назаров, И. А. Семенова // Вестник Томского госу.
— 12дарственного университета. Управление, вычислительная техника и информатика. — 2010. — № 3 (12). — С. 85 — 96.
2. Семенова И. А. Исследование системы MMP|GI|oo методом просеянного потока / A.A. Назаров, И. А. Семенова // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. -2011.-№ 4 (17).-С. 14−84.
3. Семенова И. А. Сравнение асимптотических и допредельных характеристик системы МАР|М|оо / A.A. Назаров, И. А. Семенова / Доклады ТУСУР. Управление, вычислительная техника и информатика. — 2011. — № 2 (42). Ч. 3. — С. 202 — 209.
4. Семенова И. А. Исследование систем массового обслуживания с повторными вызовами методом асимптотического анализа. / A.A. Назаров, И. А. Семенова // Автометрия. — 2011. — Т. 47. — № 4. — С. 104 — 113.
5. Semenova I. Asymptotic analysis of retrial queueing systems / I. Semenova, A. Nazarov // Optoelectronics, Instrumentation and Data Processing, DOI 10.3103/S8756699011040121, 2011. Vol. 47. — Num. 4. — P. 406−413.
6. Семенова И. А. Численный метод исследования системы ММР|М|1 с источником повторных вызовов / И. А. Семенова, A.A. Назаров // Информационные технологии и математическое моделирование (ИТММ-2009): Материалы VIII Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 13−14 ноября 2009 г. — Томск: Изд-во Том. ун-та, 2009. — Ч. 1. — С. 68 — 70.
7. Семенова И. А. Сравнение асимптотических результатов анализа системы М|М|1|ИПВ / И. А. Семенова, A.A. Назаров // Теория вероятностей, математическая статистика и их приложения: Материалы Международной конференции в Минске 22−25 февраля 2010 г. Минск: РИВШ, — 2010. — С. 272 — 277.
8. Семенова И. А. Исследование RQ-системы методом асимптотического анализа / И. А. Семенова, A.A. Назаров // Материалы XIV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал Кем.
ГУ в г. Анжеро-Судженске, 14−15 апреля 2010 г. — Томск: Изд-во Том. ун-та, 2010.-Ч. 1.-С. 65−69.
9. Semenova I. The research of RQ-system with input MMP process / I. Semenova, A. Nazarov // The third international conference «Problems of cybernetics and informatics» (PCI'2010), Baku, Azerbaijan. 6−8 September, 2010. — Baku: Elm, 2010.-Vol. 2.-P. 209−213.
10. Семенова И. А. Исследование системы массового обслуживания с входящим ММР-потоком и неограниченным числом обслуживающих приборов / И. А. Семенова, A.A. Назаров // Информационные технологии и математическое моделирование (ИТММ-2010): Материалы IX Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 19−20 ноября 2010 г. — Томск: Изд-во Том. ун-та, 2010. — Ч. 1.-С. 57−62.
11. Семенова И. А. Исследование системы массового обслуживания с неограниченным числом обслуживающих приборов и входящим рекуррентным потоком / И. А. Семенова, A.A. Назаров // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции «Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей». Минск, 31 января — 03 февраля 2011 г. — Минск: РИВШ, 2011.-С. 179- 185.
12. Семенова И. А. Исследование системы массового обслуживания с входящим МАР-потоком и неограниченным числом обслуживающих приборов / И. А. Семенова, A.A. Назаров // Труды X Международной конференции по финансово-актуарной математике и эвентоконвергенции технологий. Красноярск, 23 — 24 апреля 2011 г. — Красноярск: Сибирский федеральный ун-т, 2011. — С. 278−281.
13. Семенова И. А. Исследование немарковской системы массового обслуживания с входящим ММР-потоком и неограниченным числом обслуживающих приборов / Материалы XV Всероссийской научно-практической конференции «Научное творчество молодежи». Филиал КемГУ в г. Анжеро.
Судженске, 28 — 29 апреля 2011 г. — Томск: Изд-во Том. ун-та, 2011. — Ч. 1. — С. 28−31.
14. Семенова И. А. Метод асимптотических семиинвариантов для исследования системы SM|M|oo / И. А. Семенова, A.A. Назаров // Информационные технологии и математическое моделирование (ИТММ-2011): Материалы X Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 25 — 26 ноября 2011 г. — Томск: Изд-во Том. ун-та, 2011.-Ч. 1.-С. 164−170.
Авторские свидетельства о регистрации электронного ресурса.
15. Свидетельство о регистрации электронного ресурса № 17 615. Вычисление распределения вероятностей состояний RQ-системы МАР|М| 1 / И. А. Семенова, A.A. Назаров. Дата регистрации 22.11.2011.
16. Свидетельство о регистрации электронного ресурса № 17 616. Рекуррентный матричный алгоритм нахождения распределения вероятностей числа занятых приборов в системе ММР|М|оо / И. А. Семенова, A.A. Назаров. Дата регистрации 22.11.2011.
Апробация работы. Основные положения работы и отдельные ее результаты докладывались и обсуждались:
1. VIII Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2009 г.
2. XIV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2010 г.
3. VIII Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур». Томск, 2010.
4. IX Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2010 г.
5. Международная научная конференция «Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей». Минск, 2011 г.
6. XV Всероссийская научно-практическая конференция «Научное творчество молодежи». Анжеро-Судженск, 2011 г.
7. Российская научная конференция с участием зарубежных исследователей «Моделирование систем информатики». Новосибирск, 2011 г.
8. X Международная научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2011 г.
Структура работы. Работа состоит из введения, четырех глав, заключения и списка использованной литературы.
В первой главе проводится исследование марковских RQ-систем методом асимптотических семиинвариантов в предельном условии большой задержки заявки в источнике повторных вызовов (ИПВ).
В параграфе 1.1 строится математическая модель марковских RQ-систем с входящим МАР-потоком (МАР|М|1), описывается процесс функционирования исследуемых RQ-систем.
МАР-поток задается: матрицей инфинитезимальных характеристик Q, с элементами qvk, эргодической цепи Маркова k (t), диагональной матрицей, А с элементами Хк > 0 по главной диагонали и матрицей D с нулевыми элементами на главной диагонали и элементами dk{k2 вне главной диагонали.
Случайный процесс {"(/),&(/),/(/)} изменения во времени состояний RQ-системы МАР|М|1 определяет: состояние прибора n{t), n{t)= 0, если прибор свободен, и «(/) = 1, если прибор занятk{i) — цепь Маркова управляющая МАР-потокомi (t) — число заявок в ИПВ.
В параграфе 1.2 для распределения вероятностей Pn{t) = п, k{t) = к, ?(t) = /} = Р{п, к, /) состояний [п, к, /} рассматриваемой RQсистемы МАР|М|1 получена система уравнений Колмогорова в стационарном режиме.
-{Хк + io) P (0,к,/) + ц/>(1,к, i) + XР (0, V, i)(ldvk)qyk = 0, V.
— - (Хк + ц) р (1, к, i)+Xk [р (0, к, i) + />(l, к, i -1)] + a (i +l)?(0, k, i +1) ¦+ Z M1' v' 00 — ?V*) + V, i) + P{1, V, i -1)] dvk } qvk = 0. V.
Частным случаем МАР-потока является пуассоновский (простейший) поток. Для RQ-системы с простейшим входящим потоком (М|М|1) распределения вероятностей P (n, i) состояний {n, i} также получена система уравнений Колмогорова.
X + ю) Р{ 0, /) + цР (1, /) = 0, -(Х + /) + ХР (0, /) + ст (/ + 1) Р (0, i +1) ¦+ ХР{1, i -1) = 0.
Так как МАР-поток является общим потоком для целого класса потоков однородных событий, то положив в данном потоке все вероятности dk2 =0, получим ММРР-поток. Для стационарного распределения вероятностей P (n, k, i) RQ-системы ММРР|М|1 получена система уравнений Колмогорова.
— (Хк + ig) p (0, к, i) + ]Г Р (0, V, i) qvk + цР (1, к, i) = 0, V.
-{Хк + ]х)р{, к, i) +? P (l, V, i) qvk + ХкР (0, к, i)+ V ст (/ + 1) р (0, к, i +1) ¦+ ХкР{, к, i-l) = 0.
Далее была рассмотрена RQ-система с входящим синхронным МАР-потоком (SMAP|M|1), в котором моменты наступления событий совпадают с моментами изменения состояний управляющей этим потоком цепи Маркова k{t). Для распределения вероятностей P{n, k, i) была получена система уравнений Колмогорова.
— ктР (0, к, i) + Р (0, к, i) qkk + |л/>(1, к, i) = 0, — к, i) +? {Р{1, V, i -1) + Р (0, V, ?)}qvk + <�т (/ + 1) Р (0, к, i +1)+ V [р (1, к, /) — Р{ 1, к, i -1) — Р (0, к, i)]qkk = 0.
В параграфе 1.3 для марковского процесса (и (г), &(/), /(/)} определены характеристические функции.
Н{п, к, и)=^шР (п, к, г),.
1=0 для которых записана система векторно-матричных уравнении.
А (/") = Н («)В (./И),.
О/ ди где векторная характеристическая функция Н (и) имеет вид.
Н (м) = {//(ОД, и), Я (1,1, и), Я (0,2, и), Я (1,2, и),., Я (0, И, и), Я (1, N. и)}, а матрицы, А (ум) и В (ум) блочного вида являются матрицами коэффициентов системы уравнений Колмогорова относительно характеристических функций Н (п, к, и).
Выполнено допредельное исследование Ж^-системы с простейшим входящим потоком и найден явный вид характеристической функции к (и).
Х+а)/а.
1-Р к (и) = Мем,) = [1 — -1)] —.
11−1 у реу где р = Л/ц.
Дальнейшее исследование ЯС)-систем с входящим простейшим потоком, ММРР-потоком и БМАР-потоком показало, что уравнения для характеристических функций всех рассматриваемых Ж^-систем имеют одинаковый матричный вид си отличающийся лишь размерностями матриц, А (ум) и В (у'м). Поэтому, предложенный унифицированный подход, позволил свести исследование рассматриваемых Яр-систем с простейшим и коррелированным входящими потоками к решению матричных уравнений одинаковой структуры. Этот результат дает возможность единообразно исследовать различные классы моделей.
В связи с тем, что уравнения для характеристических функций всех рассматриваемых RQ-систем имеют одинаковый матричный вид, поэтому предлагаемый далее метод асимптотических семиинвариантов в условии большой задержки при ст —" 0 применим для анализа всех RQ-систем, перечисленных в данной работе.
В параграфе 1.4 выполнено исследование марковских моделей RQ-систем методом асимптотических семиинвариантов. Здесь были получены формулы, позволяющие находить асимптотики любого порядка hn+l (и) допредельной характеристической функции Mejui^ которые существенно повышают точность аппроксимации допредельного распределения.
В параграфе 1.5 предложено численное обращение допредельной характеристической функции числа заявок в ИПВ, а также асимптотик hv (u), аппроксимирующих h (u) для числа заявок в ИПВ, которое определяет допредельное распределение P (i) и все его аппроксимации Pv (i). А также сформулирован численный алгоритм, реализованный в главе 4, для вычисления распределения вероятностей состояний RQ-системы МАР|М|1 и ее частных случаев. Найдены расстояния Колмогорова между допредельными распределениями и его второй и третьей аппроксимациями Л2 и А3 для различных значений параметра ст. Значения этих расстояний приведены в таблице 1.2.
Во второй главе выполнено исследование СМО с неограниченным числом обслуживающих приборов и коррелированными входящими потоками при экспоненциальном обслуживании методом асимптотических семиинвариантов при условии растущего времени обслуживания заявки на приборе.
В параграфе 2.3 марковская система с неограниченным числом приборов и входящим МАР-потоком исследуется при помощи метода асимптотических семиинвариантов в предельном условии растущего времени обслуживания.
Для исследуемой системы случайный процесс {&(/), /(/)} является двумерной цепью Маркова с непрерывным временем, где /(/) — число приборов, занятых в системе в момент времени t, a k{t) — цепь Маркова управляющая МАРпотоком. Для этого процесса определены характеристические функции.
H{k, u) = YejuiP{k, i), i=о для них составлена система векторно-матричных уравнений Колмогорова.
H (0) = R, для векторной характеристической функции.
Н (и) = {Н (1, и), Н (2, иН (К, и)}, где R — стационарное распределение вероятностей значений цепи Маркова k{t), определяемое системой.
RQ = 0, RE = 1,.
Е — единичный вектор столбец, Q — матрица инфинитезимальных характеристик эргодической цепи Маркова k{t), Л — диагональная матрица с элементами Хк >0 по главной диагонали и набором вероятностей dk2, причем dkk =0, матрица В с элементами Хк по главной диагонали и произведением dk2 •qк2 вне главной диагонали.
Результатом исследования данной системы является доказательство того, что вид предельной характеристической функции имеет вид экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка: (и) = ехр< ju —, где к, = RBE;
IJ h2 (и) — ехр
• Ki (Juf ju —- + ——— ц 2.
К] +к2 М где к2 =f2BE, а вектор удовлетворяет условиюЕ = 0 и является решением неоднородной системы линейных алгебраических уравнений.
Г2д + К (В-к, 1) = 0;
3 (и) = ехр
У" С/")2 К! +К2, 0й)3 к, +3к2 +2к3.
1 ¦ 2. М- «Г 6 5 где к3 = Г^ВЕ, а вектор Г3 удовлетворяет условию £3Е = 0 и является решением неоднородной системы линейных алгебраических уравнений ед + ^ (В — к, 1) — к2И = 0- здесь величина к,/р. является асимптотическим семиинвариантом первого пок, +к2 рядка, величина рядка, а величина И асимптотическим семиинвариантом второго пок, +3к2 + 2к3.
— асимптотическим семиинвариантом третьего порядка.
В параграфе 2.4 марковская система с неограниченным числом приборов и входящим МАР-потоком исследуется методом моментов в допредельной ситуации, записывается формула для нахождения скалярного центрального момента произвольного порядка Выполняется сравнительный анализ асимптотических и допредельных характеристик исследуемой системы.
В параграфе 2.6 марковская система с неограниченным числом приборов и входящим полумарковским потоком (8М-потоком), заданным процессом марковского восстановления {?,(«), т (и)} и полумарковской матрицей А (л:), исследуется при помощи метода асимптотических семиинвариантов в предельном условии растущего времени обслуживания.
Рассматривается трёхмерный случайный процесс {"(?), 2 г (/), /(?)}, который является марковским с непрерывным временем, где г{{) — длина интервала от момента времени / до момента наступления очередного события в БМ-потоке, а дискретный процесс определяется следующим образом.
0 = + если К < ^ *я+1″ п где моменты восстановления определяются равенством =Г т (/), то есть 1 процесс на интервале tn.
Для процесса определены характеристические функции.
00 0 для них составлена система векторно-матричных уравнений Колмогорова решение и) которой удовлетворяет условию.
Н (г, 0) = 1ф), где Я^) — стационарное распределение вероятностей значений двумерного случайного процесса {$(/), 2^)}. Известно, что распределение К (г) имеет вид [31].
2 о где А (х) — полумарковская матрица, Р = А (оо) — стохастическая матрица вероятностей переходов вложенной цепи Маркова, г — стационарное распределение вероятностей значений вложенной цепи Маркова, а величина к, определяется равенством 1 к. =-,.
1 гАЕ где матрица, А определяется равенством.
А = |(Р — А (х))ск. о.
Результатом исследования данной системы является доказательство того, что вид предельной характеристической функции имеет вид экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка: к, (и) = ехр ум к2(и) = ехр
• К1 (у'")2 ум —у И.
К, + К где к 2 = ^ Е, а вектор функция удовлетворяет условию Г2(°°)Е = 0 и является решением уравнения (А (г) -1) + —^ А (г) — К1Щг) = 0- дг дг дг.
И3(и) = ехр к, (ум)2 ум — +у '.
М- 2 к, +к2. О'")3 к1 +3к2 + 2к3 ц 1 6 где к3 = Г3ВЕ, а вектор функция ^ удовлетворяет условию Гз (оо)Е = 0 и является решением уравнения (а (2)А (2) — К, Г2 (*) — к2ВД = Ооя & ох здесь величина к,/ц является асимптотическим семиинвариантом первого пок, +к2 рядка, величина рядка, а величина И асимптотическим семиинвариантом второго пок, +3к2 + 2к3 И асимптотическим семиинвариантом третьего порядка.
В параграфе 2.7 проводится численное сравнение асимптотических и допредельных результатов исследуемых СМО с неограниченным числом приборов и коррелированными входящими потоками.
В третьей главе выполнено исследование немарковских СМО с неограниченным числом обслуживающих приборов и коррелированными входящими потоками методом просеянного потока и методом асимптотических семиинвариантов при условии растущего времени обслуживания заявки на приборе.
Для исследования таких систем возможны два подхода: метод дополнительных переменных и метод просеянного потока.
Для реализации метода дополнительных переменных случайный процесс k (t), i{t), zx{t),., z,(t)} с переменным числом компонент является марковским, где Zj (t) — остаточное время обслуживания / -ой заявки из i > /, находящихся в момент времени t в системе, и для его исследования, хотя и возможно применение теории марковских процессов, но практическое ее применение составляет значительные технические проблемы. Поэтому применен второй подход к исследованию СМО с неограниченным числом приборов и произвольным распределением времени обслуживания поступающих заявок — метод просеянного потока.
Метод просеянного потока позволяет проблему исследования немарковской системы обслуживания с неограниченным числом приборов свести к задаче анализа просеянного нестационарного потока.
Для реализации метода просеянного потока определяется вероятность S (t), которая имеет смысл вероятности того, что заявка входящего потока, поступившая в систему в момент времени t < tx, в момент времени будет находиться в системе, занимая для своего обслуживания один из приборов системы и формировать событие просеянного потока. Зависимость S от t определяется распределением вероятностей времени обслуживания. Не попавшие в просеянный поток заявки, завершат обслуживание и покинут систему до момента tx.
В некоторый конечный момент времени t число n (t) событий, наступивших в просеянном потоке равно числу занятых приборов в рассматриваемой системе массового обслуживания, то есть i (tx) = n (tx).
В параграфе 3.3 для просеянного потока системы MAP|GI|oo введена дополнительная переменная k (t) и рассмотрен двумерный процесс {k (t), n (t)}, который является нестационарной цепью Маркова. Для этого процесса определены характеристические функции.
00 п=О для них составлена система векторно-матричных дифференциальных уравнений Колмогорова.
Н (г/,/0) = Ы. для векторной характеристической функции.
Результатом исследования данной системы является доказательство того, что вид предельной характеристической функции имеет вид экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка: к{(и) = ехр^'мк^,}, где к^ = КВЕ, к2{и) = ехр' икД+^|![к1р1+2к2р2] где к2 = иВЕ, а вектор {2 удовлетворяет условию Т2Е = 0 и является решением неоднородной системы линейных алгебраических уравнений.
Г2О + Н (В-к, 1) = 0- и) = ехр
2 3.
Уик, р, +^-[к, р, + 2к2Р2 ] + [К1р, + 6к2р2 + 6кзрз ] где к3 = fзBE, а вектор fз удовлетворяет условию Г3Е = 0 и является решением неоднородной системы линейных алгебраических уравнений.
Г3<2 + (В — к^Г) — к2Б1 = 0- здесь ру = |(1 — В (х)У сЬс — среднее значение минимума из V времен обслужи-о вания заявок, = 1,2,3, величина к^, является асимптотическим семиинвариантом первого порядка, величина [к, Р, + 2к2Р2] ~~ асимптотическим семиинвариантом второго порядка, а величина [к^р, + 6к2Р2 + 6к3Р3] - асимптотическим семиинвариантом третьего порядка.
В параграфе 3.5 для просеянного потока системы 8М|01|оо были введены дополнительные переменные, г (7) и рассмотрен трехмерный процесс и (0>г (0}, который является марковским процессом. Для этого марковского процесса определены характеристические функции.
00 л=о для них составлена система векторно-матричных дифференциальных уравнений Колмогорова ш^м) = 5Н (г, и,0 + то, и,0 ^ ! + Ц. ^^Л.
Э/ дг дг 7 — для векторной характеристической функции.
Щг, и, 0 = {#(1, г, и, /), Н{ 2, г, и, /),•••, Н (К, г, и, *)}. Результатом исследования данной системы является доказательство того, что вид предельной характеристической функции имеет вид экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка:
Их (и) = ехр (/мк1Р,}, где =, гАЕ.
Ь2(и) = ехр< ик^.+^ЬЭ.+гкгРг] где к2 = Е, дг, а вектор функция ^(г) удовлетворяет условию ^(со)Е = 0 и является решением уравнения к3(и) = ехр дг дг дг.
2 3.
2к2Р2] + ^-[к1(31 +6к2р2 +6к3р3] 2 о где к3 = —^^Е, а вектор функция f3 (г) удовлетворяет условию Г3(оо)Е = 0 и дг является решением уравнения.
-^Г2 + -1 (М?) «I) + А (г) — к/2 (г) — к2К (г) = 0, дг дг дг здесь значения и смысл РУ и ку определены выше.
В параграфе 3.7 проводится сравнение асимптотических семиинвариантов входящего потока и системы массового обслуживания с неограниченным числом приборов, на основании которого доказывается утверждение для системы МАР|01|оо и МАР-потока:
1. Для системы МАР|С1|оо асимптотическое (в условии растущего времени обслуживания) распределение вероятностей ее состояний определяется лишь только асимптотическими семиинвариантами входящего МАР-потока и параметрами ру времени обслуживания.
Аналогичным образом доказывается утверждение для системы 8М|С1|оо и полумарковского потока:
2. Для системы 8М|С1|оо асимптотическое (в условии растущего времени обслуживания) распределение вероятностей определяется лишь только асимптотическими семиинвариантами входящего 5М-потока и параметрами (Зу времени обслуживания.
На основании проведенных исследований третьей главы делается вывод о том, что для асимптотического исследования систем с неограниченным числом обслуживающих приборов и коррелированными входящими потоками достаточно знать асимптотические семиинварианты этих потоков и определенные параметры времени обслуживания.
В параграфе 3.8 проводится численное сравнение асимптотических и допредельных результатов исследуемых СМО с неограниченным числом приборов и коррелированными входящими потоками.
В четвертой главе были предложены численные алгоритмы анализа систем и систем с неограниченным числом приборов с коррелированными входящими потоками, а также показана область применимости асимптотических результатов к допредельной ситуации исследуемых моделей массового обслуживания, полученных в первых трех главах.
В параграфе 4.1 описывается численный алгоритм вычисления распределения вероятностей состояний 1К2-системы МАР|М|1 и ее частных случаев: М|М|1, ММРР|М|1, 8МАР|М| 1.
В параграфе 4.2 приводится численный метод по нахождению распределения вероятностей числа занятых приборов в системе МАР|М|оо.
В параграфе 4.3 проводится анализ имитационного моделирования систем массового обслуживания с неограниченным числом приборов.
В параграфе 4.4 определяется область применимости асимптотических методов исследуемых систем с неограниченным числом приборов в допредельной ситуации.
В параграфе 4.5 приведено описание разработанного комплекса проблемно-ориентированных программ расчета вероятностных характеристик 11(2-систем и систем с неограниченным числом приборов.
Заключение
.
В представленной диссертационной работе предложена модификация метода асимптотического анализа RQ-систем в условии большой задержки в ИПВ и систем с неограниченным числом приборов с коррелированными входящими потоками в условии растущего времени обслуживания в виде метода асимптотических семиинвариантов.
Развит метод просеянного потока для исследования немарковских СМО с неограниченным числом приборов, рекуррентным обслуживанием и коррелированными входящими потоками.
Разработаны численные алгоритмы вычисления допредельного распределения вероятностей состояний RQ-систем и систем с неограниченным числом приборов.
В первой главе выполнено исследование однолинейных RQ-систем с простейшим и коррелированными входящими потоками (MAP, ММРР и SMAP-потоками) методом асимптотических семиинвариантов в предельном условии большой задержки заявки в ИПВ.
Выполнено допредельное исследование RQ-системы с простейшим входящим потоком и найден явный вид характеристической функции h (u).
Матричная форма записи уравнений позволила свести исследование RQ-систем к решению уравнений одинаковой структуры для моделей с различными входящими потоками. Этот результат дает возможность единообразно исследовать различные классы моделей RQ-систем.
Получены формулы относительно асимптотик hv{u) v = 1,2,., AT и семиинвариантов произвольного порядка, характеризующие изменение состояния системы.
Сформулирован численный алгоритм, реализованный в главе 4, для вычисления распределения вероятностей состояний RQ-системы МАР|М|1 и ее частных случаев. Выполнено численное сравнение асимптотических и допредельных результатов RQ-систем. Предложено численное обращение допре.
— 151 дельной характеристической функции h (u) числа заявок в ИПВ, а также асимптотик hv (u), аппроксимирующих h (u) для числа заявок в ИПВ, которое определяет допредельное распределение P (i) и все его аппроксимации Pv (г). Для определения точности аппроксимации найдены расстояния Колмогорова между допредельными распределениями и его второй и третьей аппроксимациями Д2 и Д3 для различных значений параметра а. При уменьшении параметра ст и увеличении порядка аппроксимации уменьшается отклонение результатов асимптотического исследования RQ-систем от результатов, полученных численным методом, что говорит о высокой точности метода асимптотических семиинвариантов.
Во второй главе выполнено исследование СМО с неограниченным числом обслуживающих приборов и коррелированными входящими потоками (MAP и SM-потоками) при экспоненциальном обслуживании. Исследование проводилось методом асимптотических семиинвариантов в условии растущего времени обслуживания заявки на приборе.
Результатом исследования систем с неограниченным числом приборов являются формулы относительно асимптотик и семиинвариантов первого, второго и третьего порядков, характеризующие изменение состояний системы.
Для системы с неограниченным числом приборов и входящим МАР-потоком была найдена формула для нахождения центрального момента произвольного порядка. На основании этого был выполнен сравнительный анализ асимптотических и допредельных моментов данной системы, по результатом которого был сделан вывод о том, что с приближением ju. —> 0 допредельные последовательности сходятся к асимптотическим результатам.
Выполнено численное сравнение асимптотических и допредельных результатов систем с неограниченным числом приборов. Сформулирован численный алгоритм, реализованный в главе 4, для вычисления распределения вероятностей состояний системы с неограниченным числом приборов. Для определения точности аппроксимации найдены расстояния Колмогорова между допреw? дельными распределениями и его второй и третьей аппроксимациями Д2 и А3 для различных значений параметра времени обслуживания р. При уменьшении параметра р и увеличении порядка аппроксимации уменьшается отклонение результатов асимптотического исследования от результатов, полученных численным методом, что говорит о высокой точности метода асимптотических семиинвариантов.
В третьей главе выполнено исследование немарковских СМО с неограниченным числом обслуживающих приборов и коррелированными входящими потоками (MAP и SM-потоками) методом просеянного потока и методом асимптотических семиинвариантов при условии растущего времени обслуживания заявки на приборе.
Метод просеянного потока исследуемых систем, позволил проблему исследования немарковской системы обслуживания с неограниченным числом приборов свести к задаче анализа нестационарного просеянного потока.
Результатом исследования систем с неограниченным числом приборов являются формулы относительно асимптотик и семиинвариантов первого, второго и третьего порядков, характеризующие изменение состояний системы.
По результатам исследований третьей главы был сделан вывод о том, что для систем с неограниченным числом приборов асимптотическое распределение вероятностей определяется лишь только асимптотическими семиинвариантами входящего потока и определенными параметрами времени обслуживания, при этом количество семиинвариантов потока и параметров обслуживания совпадают с порядком асимптотики и аппроксимации.
Выполнено численное сравнение асимптотических и допредельных результатов немарковских систем с неограниченным числом приборов на примере детерминированного времени обслуживания. Показана область применимости асимптотических результатов в допредельной ситуации.
В четвертой главе разработан комплекс программ расчета вероятностных характеристик RQ-систем и систем с неограниченным числом приборов. Предложены и описаны численные алгоритмы анализа ЛС^-систем и систем с неограниченным числом приборов с коррелированными входящими потоками.
Использован комплекс имитационного моделирования немарковских систем с неограниченным числом приборов. Показана точность функционирования имитационной модели, с помощью расстояния Колмогорова, доверительных интервалов и метода моментов. А также показана область применимости асимптотических результатов в допредельной ситуации применением имитационного моделирования.
