автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Асимптотическое и численное исследование моделей RQ-систем и систем с неограниченным числом приборов с коррелированными входящими потоками

На правах рукописи

ООЬО!^"

Семенова Инна Анатольевна

асимптотическое и численное исследование моделей шз-систем и систем с неограниченным чиоом приборов с коррелированными входящими

потоками

05.13.18 - Математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

1 2 ДПР 2012

Томск - 2012

005019909

Работа выполнена в ФГБОУ ВПО «Национальный исследовательский Томский государственный университет» на кафедре теории вероятностей и математической статистики

Научный руководитель: доктор технических наук, профессор

Назаров Анатолий Андреевич

Официальные оппоненты: Змеев Олег Алексеевич - доктор физико-

математических наук, профессор, зав. кафедрой программной инженерии ФГБОУ ВПО «Национальный исследовательский Томский государственный университет»

Ивницкий Виктор Аронович - доктор технических наук, доктор физико-математических наук, профессор, профессор кафедры «Автономные системы управления» ФГБОУ ВПО «Московский государственный университет путей сообщения»

Ведущая организация: ФГБОУ ВПО «Национальный исследовательский Томский политехнический университет»

Защита состоится 17 мая 2012 г. в 10.30 на заседании диссертационного совета Д 212.267.08 при Томском государственном университете по адресу: 634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 102.

Отзывы на автореферат (в двух экземплярах), заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан 4 апреля 2012 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор

Скворцов Алексей Владимирович

общая характеристика работы

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

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

Для построения адекватных моделей массового обслуживания для сетевых систем, необходим учет фактора повторных заявок. Поэтому прибегают к системам с повторными вызовами - RQ-системам (Retrial Queue Systems). Наличие повторных попыток получить обслуживание является неотъемлемой чертой этих систем, игнорирование данного эффекта может привести к значительным погрешностям при принятии инженерных решений.

Первые математические результаты, касающиеся систем с повторными вызовами, были опубликованы в 40-х гг. прошлого века. В монографиях известных специалистов в области теории систем с повторными вызовами Г.И. Фалина, Дж. Темплтона, подчеркнуто, что стандартные модели очередей не в силах описать RQ-системы, так как в них отсутствует эффект повторения, и поэтому они не могут быть применены к решению многих фактически важных проблем. В одной из работ Г.И. Фалина, Дж. Темплтона проведено исследование RQ-системы М|М|1, где найдена гауссовская аппроксимация или асимптотика второго порядка. В тоже время асимптотика второго порядка в ряде случаев не позволяет достичь необходимой точности аппроксимации, поэтому возникает проблема разработки более точной теории, учитывающей асимптотики более высокого порядка порядка.

Исследованию RQ-систем посвящено большое количество работ. Только в монографии Д.Р. Арталехо приведено более семисот ссылок на издания различного уровня.

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

являются следующие виды коррелированных входящих потоков: МАР-поток (Markovian Arrival Process) и SM-поток (Semi-Markovian).

Подробное описание МАР-потока можно найти в работах Б.В. Гнеден-ко, И.Н. Коваленко, А.Н. Дудина, A.A. Назарова, Gomez-Corral A., Attahiru Suie Alfa, Chakravarthy S. и др.

Наиболее общей моделью ординарных потоков с непрерывной компонентой является полумарковский поток - SM-поток. СМО с таким входящим потоком интенсивно изучаются в настоящее время такими авторами как Назаров A.A., Дудин А.Н., Клименок В.И., Печинкин A.B., Чаплыгин В.В., Моисеева С.П., Cinlar Е., Sengupta В., El-Gohary А. и др.

Исследователи, занимающиеся потоками, также занимались изучением СМО с неограниченным числом приборов, на вход которых поступают коррелированные потоки, применяя главным образом методы численного анализа, которые не всегда позволяют получить точные характеристики. Анализ числа занятых приборов в системах BMAP|GI|oo, COX|GI|œ, можно найти, например, в работах немецких ученых Д. Баума и JI. Броера. A.A. Боровков в одной из своих работ выполнил исследование систем с бесконечным числом каналов обслуживания, где доказываются предельные теоремы для случайных процессов. В работе A.B. Лебедева изучается бесконечнолинейная СМО с групповым числом заявок, одновременно поступающих в систему, и доказывается теорема о максимальном числе заявок в группе. В настоящее время не существует универсального метода исследования немарковских систем с неограниченным числом приборов и непуассоновским входящим потоком, что не позволяет получить точные характеристики, аналитические выражения для вероятностей состояний исследуемых систем.

Целью работы является развитие метода асимптотических семиинвариантов для анализа RQ-систем (без конфликтов) и систем с неограниченным числом приборов с коррелированными входящими потоками в условии большой задержки в ИПВ и растущего времени обслуживания, а также развитие метода просеянного потока для исследования немарковских СМО с неограниченным числом приборов, рекуррентным обслуживанием и коррелированными входящими потоками.

В рамках указанной цели были поставлены и решены следующие задачи:

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

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

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

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

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

5. Разработка комплекса проблемно-ориентированных программ расчета вероятностных характеристик Яр-систем и систем с неограниченным числом приборов.

Научная новизна:

1. Выполнена модификация метода асимптотического анализа для исследования марковских Я(3-систем в виде мегода асимптотических семиинвариантов в предельном условии большой задержки заявок в ИПВ. Предложенный метод определяет вид предельной характеристической функции в форме экспоненты с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка. Данный метод позволяет последовательно находить аппроксимации допредельного распределения вероятностей состояний системы более чем второго порядка, и отличается возможностью получения семиинвариантов произвольного порядка.

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

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

4. Впервые для марковской системы с неограниченным числом приборов и входящим МАР-потоком разработан алгоритм последовательного нахождения допредельных моментов произвольного (более чем второго) порядка.

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

семиинвариантами этих потоков и определенными параметрами времени обслуживания, при этом количество семиинвариантов потока и параметров обслуживания совпадает с порядком асимптотики и аппроксимации.

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

Положения и результаты, выносимые на защиту:

1. Метод асимптотических семиинвариантов для исследования ИО-систем в предельном условии растущей задержки заявки в ИПВ.

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

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

4. Алгоритм последовательного нахождения допредельных моментов произвольного порядка для системы с неограниченным числом приборов и входящим МАР-потоком.

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

6. Численные методы и комплекс проблемно-ориентированных программ нахождения вероятностно-временных характеристик рассматриваемых систем.

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

Теоретическая значимость работы заключается в разработке методов исследования ЯС^-систем, применимых для широкого класса таких моделей, определяемых разнообразием класса входящих потоков, а также в разработке методов исследования систем с неограниченным числом обслуживающих

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

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

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

Личное участие автора в получении результатов, изложенных в диссертации. Постановка изложенных в диссертации задач была сделана научным руководителем аспиранта, д.т.н., проф. A.A. Назаровым. Доказательство и обоснование полученных в диссертации результатов, математические выкладки, численные расчеты выполнены лично автором. В совместных публикациях научному руководителю A.A. Назарову принадлежат постановки задач и указания основных направлений исследований, а основные результаты, выкладки и численные расчеты выполнены диссертантом.

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

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

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

3. VIII Российская конференция с международным участием «Новые информационные технологии в исследовании сложных структур». Томск, 2010.

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

5. Российская научная конференция с участием зарубежных исследователей «Моделирование систем информатики». Новосибирск, 2011 г.

Работа выполнена при поддержке АВЦП «Развитие научного потенциала высшей школы (2009-2011 гг.)» Федерат,ного агентства по образованию по проекту № 11803 «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи».

Публикации. По результатам выполненных исследований автором опубликовано 16 печатных работ, в том числе 6 статей, из которых 4 в изданиях, рекомендованных списком ВАК.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы из 108 наименований. Общий объем работы составляет 168 страницы, в том числе основной текст - 153 страницы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В параграфе 1.1 строится математическая модель марковских RQ-систем с входящим МАР-потоком (MAPjMjl), описывается процесс функционирования исследуемых RQ-систем.

Случайный процесс {n(t\k(t),/(*)} изменения во времени состояний RQ-системы МАР|М|1 определяет: состояние прибора n(t), n(t)= 0, если прибор свободен, и n(í)=l, если прибор занят; k(t) - состояние эргодической цепи Маркова управляющей МАР-потоком (к = 1, ¿v); /'(/) - число заявок в ИПВ.

В параграфе 1.2 для распределения вероятностей f'{n(t) = п, k(t) = к, i(t) = /} = Р(п, к,г) состояний {и, к,¿J рассматриваемой RQ-системы МАР|М|1 записывается система уравнений Колмогорова в стационарном режиме. Так как МАР-поток является общим потоком для широкого класса потоков однородных событий, в данном параграфе для RQ-систем с простейшим входящим потоком, ММРР-поток и синхронным МАР-потоком (SMAP-поток) также получены системы уравнений Колмогорова.

В параграфе 1.3 для марковского процесса {«(?), k(¡), ;(/)} RQ-системы МАР|М|1 определены характеристические функции

Н(п,к,и)=^е'"'P(n,k,i), для которых записана система векторно-матрич-

/=0

ных уравнений

q/^A0«)=H(")B(>), (О

где векторная характеристическая функция Ц(м) имеет вид

Н(и) = {//(0,1,г/), //(1,1,иI /1(0,2,и), H(1,2,и),..., Н(0, N,и\и( 1, Л',«)}, а матрицы л (ju) и в (ju) блочного вида являются матрицами коэффициентов системь( уравнений Колмогорова относительно характеристических функций н(п,к,и).

Выполнено допредельное исследование RQ-системы с простейшим входящим потоком и найден явный вид характеристической функции h(u)

h(u) = Ме'^ = [l - р(> -l)| -i-X- , р = Х/й,

где X - интенсивность входящего потока, (i - параметр времени обслуживания заявки на приборе, распределенного по экспоненциальному закону, а -параметр времени задержки заявок в ИПВ, распределенного по экспоненциальному закону.

Дальнейшее исследование RQ-систем с входящим простейшим потоком, ММРР-потоком и SMAP-потоком показало, что уравнения для характеристических функций всех рассматриваемых RQ-систем имеют одинаковый матричный вид (1), обличающийся лишь видом матриц Mju) и в (ju). Поэтому, предложенный унифицированный подход, позволил свести исследование рассматриваемых RQ-систем с простейшим и коррелированными входящими потоками к решению матричных уравнений одинаковой структуры. Этот результат дает возможность единообразно исследовать различные классы моделей.

В параграфе 1.4 выполнено исследование марковских моделей RQ-систем методом асимптотических семиинвариантов, при о -> 0, где I/o -среднее время задержки заявки в ИПВ.

Для нахождения асимптотики первого порядка вводится обозначение а = s и в уравнении (1) выполняются замены: и = ш, H(m) = F,(iv,e).

Теорема 1.1 Предельное, при с -> 0, значение F,(n•). решения F,(w,e)

уравнения j ' ^ а(/еи') = f, (if, е)в(/'еч>), удовлетворяющего условию ô\v

F,(О,е)Е = 1, имеет вид F,(\v) = R • e;>ïl, где вектор R является решением системы

R(B0 + k,A0)=0, (2)

удовлетворяющим условию нормировки

RE = 1. (3)

а величина к] есть решение нелинейного уравнения R(B, + к,А,)Е = 0, в котором вектор R= R(k,) зависит от к, и является решением системы (2)-

(3).

Для нахождения асимптотики произвольного порядка, выполняются замены о = е"+1, и = ш, H„tl(«)= F„+1(w,e).

Теорема 1.2 Предельное, при е—>0, значение решения Р„ч(м>,е)

уравнения

v=¡

удовлетворяющего условию Рл )1(0,е)Е = 1, имеет вид

где вектор Я определен в теореме 1.1, а величина к„+1 определяется равенством

]ешв1 + к,а!)е + ка!е},

в котором векторы g, gn определяются неоднородными системами линейных алгебраических уравнений

В(В0 + к1Л0)+НА0=0,

8„(в0 + к,А0)+§с;г¥(в11.¥ + в, + §сХ1А„.Л=о

v—! v / v. *•=<> )

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

региения этих систем из множества всех га решений, а векторы задаются разложениями ^ = + кУ+|8> V = 1,« -1.

, (\ [^очгч] й

Определение. Функцию /г„+1(и)=ех— г будем называть

и V! о]

асимптотикой (п + 1)-го порядка, а величину кп+]/о - асимптотическим семиинвариантом (п + 1)-го порядка.

В параграфе 1.5 предложено численное обращение допредельной характеристической функции И(и) числа заявок в ИПВ, а также асимптотик (у = 1,2,3,...), аппроксимирующих И(и) для числа заявок в ИПВ, которое определяет допредельное распределение Р(/) и все его аппроксимации /*„(')■ А также сформулирован численный алгоритм, реализованный в главе 4, для вычисления распределения вероятностей состояний ЯО-системы МАР(М|1 и ее частных случаев. Найдены расстояния Колмогорова Л2 и Д3 между допредельными распределениями и его второй и третьей аппроксимациями для различных значений параметра а. Значения этих расстояний приведены в таблице 1.1.

Таблица 1.1

а 0,1 0,05 0,01 0,005

Л, 0,1676 0,1298 0,0672 0,0425

А, 0,1449 0,1287 0,0505 0,0304 1

Полагая приемлемой погрешность аппроксимации равную значению 0,05 расстояния Колмогорова, можно определить область применимости а <0,005 для асимптотики второго порядка и с <0,01 для асимптотики третьего порядка. На рисунке 1.1 показана одна из графических реализаций полученных результатов.

Рис. 1.1. Допредельное и асимптотическое распределения вероятностей числа заявок в ИПВ при с = 0,01

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

В параграфе 2.3 система с неограниченным числом приборов и входящим МАР-потоком исследуется при помощи метода асимптотических семиинвариантов в предельном условии растущего времени обслуживания, ц 0, где 1/ц - среднее время обслуживания.

Для исследуемой системы случайный процесс {¿(г),/'(/)} является двумерной цепью Маркова с непрерывным временем, где /(/) - число приборов, занятых в системе в момент времени I, а к({) - эргодическая цепь Маркова управляющая МАР-потоком. Для этого процесса определены характеристи-

оо

ческие функции Н{к,и)=^е'и'Р(к,1), и составлена система векторного

матричных уравнений Колмогорова

н(о)=и,

где Н(и)= {и(\,и),Н(2,и),---,Н(К,и)}, Л - стационарное распределение вероятностей значений цепи Маркова к(/), определяемое системой

здесь Е - единичный вектор столбец, О - матрица инфинитезимальных характеристик цепи Маркова к(/), матрица В определяется элементами -интенсивности наступления событий в потоке, расположенных по главной диагонали и произведением с1к^г ■ вне главной диагонали, где (¡к]к1 - вероятности наступления событий в потоке, причем с1кк = 0.

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

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

В параграфе 2.6 марковская система с неограниченным числом приборов и входящим полумарковским потоком (БМ-потоком), заданным полумарковской матрицей а(дг), исследуется при помощи метода асимптотических семиинвариантов в предельном условии растущего времени обслуживания, ¿1 -> 0, где 1/(1 - среднее время обслуживания.

Рассматривается трёхмерный случайный процесс ),:(<), «'(<)}, который является марковским с непрерывным временем, где г(/) - длина интервала от момента времени г до момента наступления очередного события в БМ-потоке, а дискретный процесс определяется следующим образом ¿(г) = £(« +1), если < г < /„+|, где моменты восстановления 1„ определяются

1*0 = 0, ЯЕ = 1,

равенством t„ = то есть процесс s[t) на интервале i(1 < t < прини-

/=1

мает и сохраняет значение £(« + ]). Составлена система векторно-матричных уравнений Колмогорова

онЫ ai(M^ ((е_,„ _ = 0

& & V W ; К ' ди

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

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

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

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

Для реализации метода просеянного потока определяется вероятность 5(0, которая имеет смысл вероятности того, что заявка входящего потока, поступившая в систему в момент времени t </,, в момент времени f, будет находиться в системе, занимая для своего обслуживания один из приборов системы и формировать событие просеянного потока. Зависимость S от ( определяется функцией распределения вероятностей времени обслуживания S(t) = 1 - ß(r, - 0. Не попавшие в просеянный поток заявки, завершат обслуживание и покинут систему до момента

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

В параграфе 3.3 для просеянного потока системы с входящим МАР-потоком и рекуррентным обслуживанием (MAP|GI|=o) введена дополнительная переменная k{t) и рассмотрен двумерный процесс [k{t),n(t)\. Составлена система векторно-матричных дифференциальных уравнений Колмогорова

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

вания, Ь -> =о, где Ь — |(] - В{х)) с1х - среднее значение времени обслужива-

о

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

Асимптотика первого порядка аналогично закону больших чисел определяет асимптотическое среднее значение числа занятых приборов и определяется равенством к, = ЯВЕ.

Для нахождения асимптотики второго порядка в уравнении

= н2(и.ОЮ + - 1)В -уик,1]}

д/

выполняются замены г2 = 1/Ь, 12£ = т,е2/0 = т0,= 5,(т), и = гпг, Н2(г/,^) = Р2 (н',т,с), и доказываются следующие утверждения:

Теорема 3.1 Предельное, при е —► 0, значение \;2 (»', т) решения Р2 (iv, т, е) уравнения

: ЭР2(н',Т,Е) 8т

= Р2(и*, т,+ 5]- 1)В - ушк^]}, имеет вид

Р2(™,т) = Яехр-

т т

к, _[<>,(=)£/-+ 2к2

где величина к2 опре-

деляется равенством к2=Г2ВЕ, а вектор Г2 удовлетворяет условию ^Е = 0 и является решением неоднородной системы линейных алгебраических уравнений Г2<3 + ЩВ- к,1) = 0.

Для нахождения асимптотики третьего порядка выполняются замены б3=1/Ь, /3е = т,е3/0=т0,5(/)=51(т), и = ей', Н3(и,*)=Рз(н-,т,е). Теорема 3.2 Предельное, при е 0, значение Р3 (IV, т) решения

Йт

(IV, т, е) уравнения

= Р30.',т,Е)|0 + 51(Т)

имеет вид

(е

,/еи' _

1)В-к

уе1У +

и^г

-(УЕИ')2512(т) к21

Р3(и',т) = Яехр-

О)3

к, |5,(г)^ + бк-2 ^(.-Кг + бкз |5,3(г)^ ,

. т0 То т0

где величина к3 определяется равенством к3 = С3ВЕ, а вектор Г3 удовлетворяет условию Г3Е = 0 и является решением неоднородной системы линейных алгебраических уравнений Г3(3 + (В - к,1) - к2Я = 0.

Определение. Функцию

А3(и) = ехр|у«к1р1 + 2к2Р2]+^^[к1Р, +6к2р2 + 6к3р3]|

будем называть асимптотикой третьего порядка, а величину [к,р, +6к2р2 +6к3р3] - асимптотическим семиинвариантом третьего поряд-

со

ка, здесь Pv = J(l - В(х)У dx - среднее значение минимума из v времен обо

служивания заявок, v = 1,2,3.

В параграфе 3.5 для просеянного потока системы с полумарковским входящим потоком и рекуррентным обслуживанием (SM|GI|œ) были введены дополнительные переменные s{t), :(t) и рассмотрен трехмерный процесс n(t),;(/)}, который является марковским процессом. Для этого процесса определены характеристические функции

H(s,:,u,t) = P(s,~,n,t), и составлена система векторно-матричных дифференциальных уравнений Колмогорова

= аяьи,,) + ш(о,м) (л(;) _ I+^ _ ^ A(:)j

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

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

Для системы MAP]GI|oo (SM|GI|oo) асимптотическое (е условии растущего времена обслуживания) распределение вероятностей ее состояний определяется лишь только асимптотическими семиинвариантами входящего ¡viAP-потока (SM-потока) и параметрами Pv времени обслуживания.

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

K2 = s,p,+(s2-s,)p2,

К3 = 5,3, +3(S2-S,)р2 +(53 -3S2 + 25,)рз, здесь Kv - асимптотические семиинварианты системы, a Sv - асимптотические семиинварианты потока.

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

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

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

Л„ = шах

2>„(0-2>(0

(/7 = 2,3),

где />„(/) - функция распределения вероятностей, полученная с помощью асимптотического анализа, а /'(/) - эмпирическая функция распределения вероятностей, полученная с помощью имитационного моделирования.

Например, заданы значения параметров: Ь - средняя продолжительность обслуживания заявок, которая в данном примере распределена равномерно,

-0,5 0,3 0,2 " "1 0 0" ' 0 од 0,2

0 = 0,2 -0,6 0,4 , Л = 0 2 0 , 0 = 0,2 0 0,3

0,5 0,3 -0,8 0 0 з. 0,1 0,2 0

для различных значений Ь значения Д„ составили (табл. 4.1).

Таблица 4.1

50 100 150 200

Л2 0,999 0,079 0,046 0,009

Аз 0,041 0,038 0,023 0,007

Полагая приемлемой погрешность аппроксимации равную значению 0,04 расстояния Колмогорова, можно сделать вывод о том, что применение метода асимптотического анализа к исследованию систем с неограниченным числом обслуживающих приборов целесообразно при ¿>150, применяя асимптотическую аппроксимацию второго порядка, и уже при ¿>50 для

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

Рис. 4.1. Имитационное и асимптотическое распределения вероятностей числа занятых приборов при Ь = 50

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

Разработанный комплекс состоит из следующих приложений:

• Численный алгоритм вычисления распределения вероятностей состояний ЛО-системы МАР\Щ 1;

• Рекуррентный матричный алгоритм нахождения распределения вероятностей числа занятых приборов в системе МАР|Л/]оо;

• Имитационное моделирование С МО с неограниченным числом приборов и статистическая обработка его результатов;

• Численные алгоритлгы расчета асимптотических семиинвариантов.

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

публикации по теме диссертации

Статьи в журналах, рекомендованных ВАК

1. Семенова H.A. Исследование RQ-систем методом асимптотических семиинвариантов / A.A. Назаров, И.А. Семенова // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 3 (12). - С. 85-96.

2. Семенова И.А. Исследование системы MMP|Gl|oo методом просеянного потока / A.A. Назаров, И.А. Семенова // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. -2011.-№ 4 (17).-С. 74-84.

3. Семенова И.А. Сравнение асимптотических и допредельных характеристик системы МАР|М|со / A.A. Назаров, И.А. Семенова / Доклады ТУ СУ Р. Управление, вычислительная техника и информатика. - 2011. -№ 2 (42), ч. 3. - С. 202-209.

4. Семенова И.А. Исследование систем массового обслуживания с повторными вызовами методом асимптотического анализа. / A.A. Назаров, И.А. Семенова// Автометрия. - 2011. - Т. 47, № 4. - С. 104-113.

Публикации в других научных изданиях:

5. Semenova 1. Asymptotic analysis of retrial queueing systems / I. Semenova, A. Nazarov // Optoelectronics, Instrumentation and Data Processing, DOI 10.3103/S8756699011040121. - 2011. Vol. 47, № 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.

П.Семенова И.А. Исследование системы массового обслуживания с неограниченным числом обслуживающих приборов и входящим рекуррентным потоком / И.А. Семенова, 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|uo / И.А. Семенова, A.A. Назаров // Информационные технологии и математическое моделирование (ИТММ-2011) : материалы X Всероссийской научно-практической конференции с международным участием. Филиал КемГУ в г. Анжеро-Судженске, 25-26 ноября 2011 г. - Томск: Изд-во Том. ун-та, 2011. - Ч. 1. - С. 164-170.

Авторские свидетельства о регистрации электронного ресурса

И.А. с. Вычисление распределения вероятностей состояний RQ-системы МАР]М|1 / И.А. Семенова, A.A. Назаров. - №17615; дата регистрации 22.11.2011.

16. А. с. Рекуррентный матричный алгоритм нахождения распределения вероятностей числа занятых приборов в системе ММР|М|го / И.А. Семенова, A.A. Назаров. -№17616; дата регистрации 22.11.2011.

Подписано в печать 02.04.2012 г. Формат А4/2. Ризография Печ. л. 0,95. Тираж 120 экз. Заказ № 68 Отпечатано в ООО «Позитив-НБ» 634050 г. Томск, пр. Ленина 34а

Введение.

Глава 1. Исследование марковских ЯС^-систем методом асимптоты- 29 ческих семиинвариантов.

1.1 Математическая модель марковских ЯС^-систем.

1.2 Уравнение Колмогорова для ЯС^-системы МАР|М| 1.

1.3 Метод характеристических функций для анализа ЯС>-системы МАР|М| 1.

1.4 Метод асимптотических семиинвариантов исследования марковских моделей ЯС)-систем.

1.5 Сравнение асимптотических и допредельных результатов марковской

Ж^-системы МАР|М| 1 и ее частных случаев.

Резюме.

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

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

2.2 Уравнение Колмогорова для системы с неограниченным числом обслуживающих приборов и входящим МАР-потоком.

2.3 Метод асимптотических семиинвариантов для исследования системы с неограниченным числом обслуживающих приборов и входящим МАР-потоком.

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

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

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

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

Резюме.

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

3.1 Математическая модель немарковских СМО с неограниченным числом обслуживающих приборов.

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

3.3 Исследование системы MAP|GI|co методом просеянного потока.

3.4 Метод асимптотических семиинвариантов исследования системы MAP|GI|oo.

3.5 Исследование системы SM|GI|oo методом просеянного потока.

3.6 Метод асимптотических семиинвариантов исследования системы SM|GI|oo.

3.7 Сравнение асимптотических семиинвариантов входящего потока и системы массового обслуживания с неограниченным числом приборов.

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

Резюме.

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

4.1 Численные алгоритмы вычисления распределения вероятностей состояний RQ-системы МАР|М|1 и ее частных случаев.

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

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

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

4.5 Комплекс проблемно-ориентированных программ расчета вероятностных характеристик RQ-систем и систем с неограниченным числом приборов.

Резюме.

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

Основоположником теории массового обслуживания считается датский ученый К.А. Эрланг (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 годы)» Федерального агентства по образованию, проект № 11803: «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи».

Публикации. По материалам диссертации опубликовано 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. Свидетельство о регистрации электронного ресурса №17615. Вычисление распределения вероятностей состояний RQ-системы МАР|М| 1 / И.А. Семенова, A.A. Назаров. Дата регистрации 22.11.2011.

16. Свидетельство о регистрации электронного ресурса №17616. Рекуррентный матричный алгоритм нахождения распределения вероятностей числа занятых приборов в системе ММР|М|оо / И.А. Семенова, 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(t) - число заявок в ИПВ.

В параграфе 1.2 для распределения вероятностей P\n{t) = п, k{t) = к, ¿(t) = /} = Р{п, к, /) состояний [п, к, /} рассматриваемой RQсистемы МАР|М|1 получена система уравнений Колмогорова в стационарном режиме

-{Хк + io)P(0,к,/) + ц/>(1,к,i) + XР(0, V,i)(l -dvk)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.

Так как МАР-поток является общим потоком для целого класса потоков однородных событий, то положив в данном потоке все вероятности dk^2 =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) — цепь Маркова управляющая МАРпотоком. Для этого процесса определены характеристические функции

00

H{k,u) = YejuiP{k,i), i=о для них составлена система векторно-матричных уравнений Колмогорова

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

Н(и) = {Н( 1, и), Н(2, иН(К, и)}, где R - стационарное распределение вероятностей значений цепи Маркова k{t), определяемое системой

RQ = 0, RE = 1,

Е - единичный вектор столбец, Q - матрица инфинитезимальных характеристик эргодической цепи Маркова k{t), Л - диагональная матрица с элементами Хк >0 по главной диагонали и набором вероятностей dk^2, причем dkk =0, матрица В с элементами Хк по главной диагонали и произведением dk^2 •qк^2 вне главной диагонали.

Результатом исследования данной системы является доказательство того, что вид предельной характеристической функции имеет вид экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка: (и) = ехр< ju — \, где к, = RBE;

I ^J 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<t< tn+l принимает и сохраняет значение +1). Реализации процесса непрерывны слева.

Для процесса определены характеристические функции

00 0 для них составлена система векторно-матричных уравнений Колмогорова решение и) которой удовлетворяет условию

Н(г,0) = 1ф), где Я^) - стационарное распределение вероятностей значений двумерного случайного процесса {$(/), 2^)}. Известно, что распределение К(г) имеет вид [31]

2 о где А(х) - полумарковская матрица, Р = А(оо) - стохастическая матрица вероятностей переходов вложенной цепи Маркова, г - стационарное распределение вероятностей значений вложенной цепи Маркова, а величина к, определяется равенством 1 к. =-,

1 гАЕ где матрица А определяется равенством

00

А = |(Р - А(х))ск. о

Результатом исследования данной системы является доказательство того, что вид предельной характеристической функции имеет вид экспоненты, с показателем в виде многочлена, коэффициентами которого являются асимптотические семиинварианты соответствующего порядка: к, (и) = ехр ум к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-систем и систем с неограниченным числом приборов. Предложены и описаны численные алгоритмы анализа ЛС^-систем и систем с неограниченным числом приборов с коррелированными входящими потоками.

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

1. Анисимов В.В Асимптотические методы анализа стохастических систем. Тбилиси: Мицниереба, 1984. - 178 с.

2. Баранцев Р.Г. Перспективные идеи в асимптотической методологии. Автообзор // Вестник молодых ученых. Серия Прикладная математика и механика. 2000. - С. 27-35.

3. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, 1989.

4. Боровков A.A. Асимптотические методы в теории массового обслуживания. М.: Наука. Главная редакция физико-математической литературы, 1980.-384 с.

5. Бочаров П.П. Система МАР/Г/l/r в условиях большого коэффициента вариации времени обслуживания // Автоматика и телемеханика. 2005. - № 11. -С. 89-98.

6. Бочаров П.П., Вискова Е.В. Однолинейная система массового обслуживания конечной емкости с марковским потоком и обслуживанием в дискретном времени // Автоматика и телемеханика. 2005. - № 2. - С. 73-91.

7. Бочаров П.П., Шлумпер JI.O. Система массового обслуживания MAP/G/1 /г с фоновыми заявками // Информационные процессы. 2005. - Т. 5, №5.-С. 367-369.

8. Вероятность и математическая статистика: энциклопедия / гл. ред. Прохоров Ю.В. -М.: Большая Российская энциклопедия, 1999. С. 239, 244.

9. Вискова Е.В. Анализ систем массового обслуживания с марковским потоком и Марковским обслуживанием в дискретном времени: Дис. . канд. физ.-мат. наук. Москва, 2005. - 122 с.

10. Ю.Вискова Е.В. Двухфазная система массового обслуживания с марковским потоком и обслуживанием в дискретном времени // Информационные процессы. 2005. - Т. 5, № 3. - С. 247-257.

11. Гарайшина И.Р., Моисеева С.П., Назаров A.A. Методы исследования коррелированных потоков и специальных систем массового обслуживания. -Томск: изд. НТЛ, 2010. 204 с.

12. Гнеденко Б. В., Хинчин А .Я. Элементарное введение в теорию массового обслуживания. 6-е изд. М.: Наука, 1964. - 146 с.

13. Гнеденко Б.В. Коваленко И.Н. Введение в теорию массового обслуживания. 4-е изд. М.: изд-во ЛКИ, 2007. - 400 с.

14. Гнеденко Б.В. Курс теории вероятностей: учебник. 6-е изд. М.: Наука, 1988.-448 с.

15. Двуреченский А.О., Ососков Г.А. О предельных свойствах обобщенной системы массового обслуживания с бесконечным числом каналов // Изв. АН СССР. Техническая кибернетика. 1985. - №4. - С. 60-64.

16. Дудин А.Н. Ненадежная многолинейная система с управляемым широковещательным обслуживанием // Автоматика и телемеханика. 2009. N 12. -С. 147-160.

17. Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками Мн.: БГУ, 2000. - 175 с.

18. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и приложение к сетям ЭВМ. Радио и связь, 1989.

19. Ивницкий В.А. Асимптотическое исследование стационарного распределения вероятностей состояний одного класса однолинейных систем обслуживания (без памяти) // Проблемы Передачи информации. 1969. Т.5. -№3. -С. 88-95.

20. Касконе А., Мандзо Р., Печинкин А., Салерно С. Система MAP/G/1/co в дискретном времени с инверсионной вероятностной дисциплиной обслуживания // Автоматика и телемеханика, 2010. — № 12. С. 57-69.

21. Клейнрок JI. Вычислительные системы с очередями. М.: Мир, 1979.

22. Клименок В.И. Многолинейная система массового обслуживания с групповым марковским входным потоком и повторными вызовами // Автоматика и телемеханика. 2001. - №8. - С. 97-108.

23. Кобелев Н.Б. Основы имитационного моделирования сложных экономических систем. М: «Дело», 2003. - С. 333.

24. Коблев Н.Б. Основы имитационного моделирования сложных экономических систем. М.: Дело. 2003.

25. Кокс Д., Льюис П. Статистический анализ последовательностей событий. М.: изд. «Мир», 1969. - 310 с.

26. Колоусов Д.В. Исследование математических моделей потоков в сетях случайного доступа: Дис. . канд. физ.-мат. наук. Томск, 2004. - 141 с.

27. Комшаев В.А., Калинина В.Н. Теория вероятностей и математическая статистика: учебник. -М.: ИНФРА, 1997. 302 с.

28. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1984. - 832 с.

29. Лебедев A.B. Асимптотика максимумов в бесконечнолинейной системе с ограниченным размером групп // Фундаментальная и прикладная математика. 1996.- Т. 2, № 4. - С. 1107-1115.

30. Лопухова C.B. Асимптотические и численные методы исследования специальных потоков однородных событий: Дис. . канд. физ.-мат. наук: 05.13.18; Томский гос. ун-т. Томск. 2008. - 167 с.

31. Мушко B.B. Система МАР/М/С с адресной стратегией повторных вызовов и идентичными приборами // Computer Modeling and New Technologies. -2005. V. 9. - № 2. - P. 33-40.

32. Назаров A.A. Асимптотический анализ марковизируемых систем. -Томск: изд-во Том. ун-та, 1991. 158 с.

33. Назаров A.A., Моисеева С.П. Метод асимптотического анализа в теории массового обслуживания. Томск: Изд-во HTJI, 2006. - 112 с.

34. Назаров A.A., Семенова И.А. Исследование RQ-систем методом асимптотических семиинвариантов // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2010. - №3 (12). -С. 85-96.

35. Назаров A.A., Семенова И.А. Исследование систем массового обслуживания с повторными вызовами методом асимптотического анализа // Автометрия.-2011.-Т. 47.-№4.-С. 104-113.

36. Назаров A.A., Семенова И.А. Исследование системы MMP|GI|co методом просеянного потока // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. - №4 (17). - С. 74 -84.

37. Назаров A.A., Семенова И.А. Сравнение асимптотических и допредельных характеристик системы МАР|М|оо // Доклады ТУСУР. Управление, вычислительная техника и информатика. 2011. -№2 (42). Ч. 3. - С. 202 - 209.

38. Назаров A.A., Судыко Е.А. Метод асимптотических семиинвариантов для исследования математической модели сети случайного доступа //Проблемы Передачи информации. 2010. -№1. С. 94-111.

39. Назаров A.A., Терпугов А.Ф. Теория массового обслуживания: Учебное пособие. Томск: Изд-во HTJI. 2004. - 228 с.

40. Павский В.А. Лекции по теории вероятностей и элементам математической статистики: учеб. пособие для студентов технолог, специальностей /В.А. Павский. Кемерово: КемТИПП, 2005. - 184 с.

41. Павский В.А. Моделирование процесса очистки природных и сточных вод: монография / В.А. Павский, Ю.Л. Сколубович, Т.А. Краснова. Новосибирск: НГАСУ, 2005. - 144 с.

42. Печинкин A.B. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. - № 9. С. 85100.

43. Печинкин A.B. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. - N 9.

44. Печинкин A.B., Зарядов И.С. Стационарные временные характеристики системы GI/M/n/oo с некоторыми вариантами дисциплины обобщённого обновления // Автоматика и телемеханика. 2009. - № 12. - С. 161-174.

45. Рыжиков Д.И. Имитационное моделирование систем массового обслуживания. Л.: ВИККИ им А.Ф, Можайского. 1991. - 111 с.

46. Саати T.J1. Элементы теории массового обслуживания и ее приложения. 2-е изд. М.: Советское радио, 1971. - 519 с.

47. Семенова И.А., Назаров A.A. Свидетельство о регистрации электронного ресурса №17615. Вычисление распределения вероятностей состояний RQ-системы МАР|М|1. Дата регистрации 22.11.2011 г.

48. Семенова И.А., Назаров A.A. Свидетельство о регистрации электронного ресурса №17616. Рекуррентный матричный алгоритм нахождения распределения вероятностей числа занятых приборов в системе ММР|М|оо. Дата регистрации 22.11.2011 г.

49. Синяков М.В., Моисеев А.Н. Свидетельство о регистрации электронного ресурса №16326. Объектно-ориентированная имитационная модель системы массового обслуживания с одним или несколькими блоками обслуживания. Дата регистрации 22.10.2010 г.

50. Справочник по прикладной статистике: в 2-х т. / под ред. Ллойда Э., Ледермана У., Тюрина Ю.Н. М.: Финансы и статистика, 1989. - Т.1. - 510 с.

51. Степанов С.Н. Численные методы расчета моделей с повторными вызовами. М.: Наука, 1983.

52. Терпугов А.Ф. Теория случайных процессов. Томск: изд. Томск. Унта, 1974.-136 с.

53. Тихоненко О.М. Модели массового обслуживания в системах обработки информации. -Мн.: Университетское, 1990. 191 с.

54. Хинчин, А.Я. Работы по математической теории массового обслуживания /А.Я. Хинчин; под ред. Б.В. Гнеденко. М.: Наука, 1963. - 528 с.

55. Хинчин, А.Я. Работы по математической теории массового обслуживания /А.Я. Хинчин; под ред. Б.В. Гнеденко. М.: Наука, 1963. - 528 с.- 161

56. Чаплыгин В.В. Многолинейная система массового обслуживания с конечным накопителем и блокировкой полумарковского потока заявок // Информационные процессы. 2008. - Т. 8. - № 1. С. 1-9.

57. Шеннон Р. Имитационное моделирование систем. Искусство и наука. -М.: Мир, 1978

58. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление: учебник для физических и физико-математических факультетов университетов. М.: Эдиториал УРСС, 2000. - 424 с.

59. Artalejo J.R. (Ed.), Algorithmic Methods in Retrial Queues, Annals of Operations Research 141, 2006. 1-301.

60. Artalejo J.R. A classified Bibliography of Research on Retrial Queues: Progress in 1990-1999. Complutense Univ. of Madrid, Spain. September 22-24 1999. - Top 7 - № 2. - P. 187-211.

61. Artalejo J.R. Accessible bibliography on retrial queues, Mathematical and Computer Modelling. 1999. Vol. 30. - P. 223-233.

62. Artalejo J.R. and Gromez-Corral A. (Eds.) Advances in Retrial Queues, European Journal of Operational Research, in press. 2008.

63. Artalejo J.R., Gomez-Coral A. Retrial queueing systems: A computational approach. Springer. Berlin. — 2008. 318 p.

64. Baltzer J.C. On the fluid limit of the M/G/oo queue queueing systems // Theory and applications. August 2007. - Vol. 56, Issue 3-4. - P. 255-265.

65. Baum D. The infinite server queue with Markov additive arrivals in space // Proceedings of the international conference "Probabilistic analysis of rare events" -Riga, Latvia, 1999.-P. 136-142.

66. Breuer L., Baum D. The Inhomogeneous BMAP/G/infinity queue // Proceedings 11th GI/ITG Conference on measuring, modelling and evaluation of com- 162puter and communication systems (MMB 2001) Aachen, Germany, 2001. - P. 209223.

67. Decreusefond L., Moyal P. A functional central limit theorem for the M/GI/oo queue Электронный ресурс. Режим доступа: http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euc lid.aoap/1227708915 (дата обращения: 05.05.2011).

68. Falin G.I. A diffusion approximation for retrial queueing systems. // Theory of Probability and Its Applications. 1991. - Vol. 36. - № 1. - P. 149 - 152.

69. Falin G.I. A Survey of Retrial Queues // Queuing Systems. 1990. -Vol. 7.-P. 127-167.

70. Falin G.I. A survey of retrial queues, Queuing Systems 1990. Vol.7. -P. 127-167.

71. Falin G.I. Asymptotic investigation of fully available switching systems with high repetition intensity of blocked calls. // Moscow University Mathematics Bulletin. 1984. - Vol. 39. - № 6. - P. 72 - 77.

72. Falin G.I. Continuous approximation for a single server system with an arbitrary service time under repeated calls. // Engineering Cybernetics. 1984. - Vol. 22. - № 2. - P. 66-71.

73. Falin G.I. Limit theorems for queueing systems with repeated calls. // A paper presented at the 4th Int. Vilnius Conf. on Probability Theory and Mathematical Statistics. Vilnius. 1985.

74. Falin G.I. M|G|1 system with repeated calls in heavy traffic. //Moscow University Mathematics Bulletin. 1980. -Vol. 35. -№ 6. - P. 48 - 51.-163

75. Falin G.I. Multichannel Queuing System with Repeated Calls Under High Intensity of Repetition // Journal of Inform. Processing and Cybernetics. 1987. -№23.-P. 37-47.

76. Falin G.I. On ergodicity of multilinear queueing systems with repeated calls. // Soviet Journal of Computer and systems sciences. 1987. - Vol. 18. - № 4. -P. 60-65.

77. Falin G.I. On Sufficient Conditions for Ergodicity of Multichannel Queuing Systems with Repeated Calls // Advanced in Applied Probability. 1984. -Vol. 16.-P. 447-448.

78. Falin G.I. Single-line Repeated Order Queuing Systems // Optimization. -1986. Vol. 17. - P. 649 - 667.

79. Falin G.I., Artalejo J.R. A Finite Source Retrial Queue // European Journal of Operation Research. 1998. - № 108. - P. 409 - 424.

80. Falin G.I., Artalejo J.R., Martin M. One the Single Server Retrial Queue with Priority Customers // Queuing Systems. 1993. - № 14. - P. 439 - 455.

81. Falin G.I., Sukharev Yu.I. On single-line queue with double connections. // All-Union Institute for Scientific and Technical Information, Moscow. 1985.

82. Falin G.I., Tempeton J.G.C. Retrial Queues. London: Chapman and Hall, 1997.-328 p.

83. Falin G.I., Templeton J.G.C. Retrial Queues. London: Chapman & Hall. 1997.- 328 p.

84. Gomez-Corral A. A tandem queue with blocking and Markovian Arrival Process // Queueing Systems. 2002. - №41. - P. 343-370.

85. Jonin G.L., Sedol J.J. Telephone systems with repeated calls // A paper presented at 6th International Teletraffic Congress, Munich. -1970.

86. Kosten L. On the influence of repeated calls in the theory of probabilities of blocking, De Ingenier. 1947. №1. - P. 1 - 25.

87. Kulkarni V.G., Liang H.M. Retrial queues revisited. Frontiers in Queuing. In: Models and Applications in Science and Engineering /J.H. Dshalalow (eds.). CRC Press, Inc., Boca Raton, 1997. P. 19-34.- 164

88. Nazarov A., Semenova I. Asymptotic analysis of retrial queueing systems // Optoelectronics, Instrumentation and Data Processing, DOI 10.3103/S8756699011040121, 2011. Vol. 47. -Num. 4. P. 406-413.

89. Nazarov A., Semenova I. The research of RQ-system with input MMP process // The third international conference «Problems of cybernetics and informatics» (РСГ2010), Baku, Azerbaijan. 6-8 September, 2010. Baku: Elm, 2010. -Vol. 2.-P. 209-213.

90. Reed J. Distribution-valued heavy-traffic limits for the G/GI/oo queue Электронный ресурс. Режим доступа: http://pages.stern.nyu.edu/~jreed/Papers/DistributionFinal.pdf, свободный (дата обращения: 10.05.2011).

91. Sengupta В. The semi-markovian queue: theory and applications / Stochastic Models. 1990. - V. 6. - № 3. - P. 383 - 413.

92. Syski R. A personal view of queueing theory // Frontiers in Queueing Vodels and Applications in Science and Engineering/ Boca Raton: CRC. 1997. -P. 13-18.

93. Templeton J.G.C. (Ed.) Retrial Queues // Queueing Systems 7, 1990. -№2.-P. 125-227.

94. Yang Т., Templeton J.G.C. A survey of retrial queues // Queuing Systems, 1987. №2.-P. 201-233.