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

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

Синякова Ирина Анатольевна

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ИССЛЕДОВАНИЯ СИСТЕМ ПАРАЛЛЕЛЬНОГО ОБСЛУЖИВАНИЯ СДВОЕННЫХ ЗАЯВОК СЛУЧАЙНЫХ ПОТОКОВ

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

2 3 МАП 2013

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

Томск-2013

005059834

005059834

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Национальный исследовательский Томский государственный университет» на кафедре теории вероятностей и математической статистики.

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

Моисеева Светлана Петровна

Официальные оппоненты:

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

Горцев Александр Михайлович, доктор технических наук, профессор, федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Национальный исследовательский Томский государственный университет», факультет прикладной математики и кибернетики, декан

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Российский университет дружбы народов», г. Москва

Защита состоится 20 июня 2013 г. в 10.30 на заседании диссертационного совета Д 212.267.08, созданного на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Национальный исследовательский Томский государственный университет», по адресу: 634050, г. Томск, пр. Ленина, 36 (корп. 2, ауд. 102).

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

Автореферат разослан 14 мая 2013 г.

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

Скворцов

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Системы массового обслуживания (СМО) с неограниченным числом обслуживающих приборов, являются универсальными математическими моделями и могут служить как для описания социально-экономических процессов, так и для функционирования реальных распределенных вычислительных систем. Исследованием таких СМО занимаются А.Н. Дудин, В.И. Клименок, A.A. Назаров, ВЛ. Ив-ницкий, П.П. Бочаров, A.B. Печинкин, В.В. Рыков, Е.В. Морозов, D. Baum, L. Breuer и многие другие. Можно отметить работы Федоткина МЛ., Зорина A.B., М.Г. Носовой, И.Р. Гарайшиной, A.C. Морозовой, ИЛ. Захорольной, посвященные математическому моделированию транспортных потоков, демографических процессов и процессов изменения численности клиентов пенсионных фондов, торговых и страховых компаний.

Одной из модификаций СМО с неограниченным числом приборов являются системы параллельного обслуживания, которые применяются для описания процессов в мультисервисных сетях связи и телекоммуникационных системах. Системы массового обслуживания с параллельно функционирующими блоками можно встретить в статьях Г.П. Башарина, К.Е. Самуйлова, A. Movaghar, С. Knessl, J. A. Morrison, D. G. Down, N. Bam-bos, G. Michailidis и многих других. В этих работах рассматриваются системы параллельного обслуживания различной конфигурации: однолинейные СМО с конечным и бесконечным буфером, приоритетным обслуживанием, нетерпеливыми заявками и общим ординарным входящим потоком; СМО с двумя и более блоками обслуживания с конечным числом приборов и общей конечной очередью. Характерно то, что все системы имеют пуассоновский входящий поток и экспоненциальное время обслуживания.

Однако пуассоновский поток не всегда адекватно описывает реальные потоки в мультисервисных сетях связи и телекоммуникационных системах. Как считают А.Г. Лоясковский и В.М. Колчар, применение пуассоновского потока для расчета характеристик качества обслуживания в реальных системах дает большую погрешность. В их работах показано, что функция распределения длин интервалов между моментами наступления событий лучше аппроксимируется распределениями, обладающими «длинным хвостом», а для описания трафика же характерна неравномерность интенсивности поступления заявок.

Обоснованность адекватности применения непуассоновских потоков (марковски модулированного пуассоновского потока и рекуррентного потока) для описания информационных потоков в мультисервисных сетях связи и телекоммуникационных системах следует из работ таких ученых, как W.E. Leland, M.S. Taqqu, W. Willinger, V. Pax-son, S. Floyd, SH. Kang, YH. Kim, A. Klemm, C. Lindemann, M. Lohmann.

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

В настоящей работе предлагается исследование систем параллельного обслуживания сдвоенных заявок случайных входящих потоков (общего марковски модулированного пуассоновского потока (MAP®) и рекуррентного потока (GI^)), как обобщение результатов исследования аналогичных систем с пуассоновскими входящими потоками и экспоненциальным временем обслуживания, впервые описанных в работах украинских ученых ЕЛ. Лебедева, A.A. Чечельницкого и О.В. Кучеренко.

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

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

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

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

3. Впервые метод начальных моментов применен для вычисления стационарных характеристик двумерных процессов, описывающих состояния систем параллельного обслуживания сдвоенных заявок МАР(2' и С1(2) входящих потоков с экспоненциальным временем обслуживания. Данный метод позволяет последовательно находить в допредельном случае вектор средних значений, матрицу ковариаций, а также другие моменты.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. IX Всероссийская научно-практическая конференция с международным участием «Информационные технологии и математическое моделирование». Анжеро-Судженск, 2010 г.

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

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

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

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

9. Международная конференция «Теория вероятностей и ее приложения», посвященная 100-летию со дня рождения Б.В. Гнеденко. Москва, 2012 г.

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

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

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

Исследования выполнены при поддержке:

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

• 2012 г. Гранта РФФИ № «12-01-16038-моб_з_рос» на поездку в г. Москва для участия на Международной конференции «Теория вероятностей и её приложения», посвященной 100-летию со дня рождения Б.В. Гнеденко (Москва, 26-30 июня 2012 г.).

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

Публикацнп. По результатам выполненных исследований автором опубликовано 20 печатных работ, в том числе 4 в изданиях, рекомендованных списком ВАК, 1 в международной базе цитирования IEEE, 7 в материалах зарубежных конференций.

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

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

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

-7В первой главе проводится исследование математических моделей параллельного обслуживания сдвоенных заявок пуассоновского с параметром X входящего потока с экспоненциальным распределением времени обслуживания в блоках (с параметрами ц,,ц2) и неограниченным числом обслуживающих приборов. Состояние системы определяется вектором {/,(/),/.,(/)}, где ik — число заявок, находящихся на обслуживании в к -ом блоке.

Для распределения вероятностей P(i,j,k)=P{i1{t)= i,i2(t)=j} состояний двумерной цепи Маркова, характеризующей число заявок в каждом блоке в момент времени t записывается система дифференциальных уравнений Колмогорова, решите которой

00 со

находится с помощью производящей функции вида F(xl,x2,t)=^i'£xt'x2P(i,j,t). До-

1=0 у=0

казана следующая теорема.

Теорема 1.1. Производящая функция F(xj,x2,t) двумерного процесса /2(i)} -

числа приборов, занятых в момент времени t в блоках системы Л/'2'|а/2|яо имеет вид:

F(*„x2,f) = ехр{-^-(х,-\\х2 iHl +

hi ^2 j

С помощью (1) получено стационарное двумерное распределение вероятностей P(i,j), которое будем называть двумерным пуассоновским распределением зависимых случайных величин

, , ■»»&>> a'"" b1- _d

P{',J)= L "ГА--'

ti nHi~nf(j-n)

1ДС и — 7 Ч ■> и — / > U ~ ( \ •

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

Во второй главе выполнено исследование систем, с неограниченным числом приборов в каждом блоке и параллельным обслуживанием сдвоенных заявок общего марковски модулированного пуассоновского потока (МАР(2)\М2 |зо) и рекуррентного потока (С/<2)|л/2|оо). Время обслуживания для каждого блока имеет экспоненциальную функцию распределения с параметрами Ц],Ц2» зависящими от номера блока.

Входящий МАР(2)-поток, задается управляющей цепью Маркова k{t) с матрицей инфинитезимальных характеристик Q, набором условных интенсивностей У.к и вероятностями d^ наступления событий в момент изменения состояния управляющей цепи k(t).

Для исследования системы МАРт\.Мг\ю вводится дополнительная компонента k(t), характеризующая состояние управляющей цепи Маркова и рассматривается трёх-

мерный марковский случайный процесс {&(/),;,(/), г'2(/)}. Для стационарного распределения вероятностей составляется система уравнений Колмогорова, из которой записывается векгорно-матричное уравнение, являющиеся основным для дальнейших исследований

Н(0,0) = к = [Н&К(2)и.]. (2)

Здесь Н(и1,м2)=[я(1,м„к2),...,я(£,и1,и2)] - вектор частичных характеристических

ао со

функций Я(£, г/,, ы2) = ]Г е1"^г1"*1 Р(к, , г2), О - матрица инфинитезимальных характеристик Л - диагональная матрица с элементами "Кк по главной диагонали, А -матрица из элементов , В = Л + А.

Для исследования системы параллельного обслуживания сдвоенных заявок рекуррентного входящего потока, который задается функцией распределения Л(х) - длин интервалов между моментами наступления событий, рассматривается марковский трёхмерный случайный процесс (г),/2 (/■)}, где дополнительная компонента определяется как длина интервала от момента I до момента наступления очередного события в рекуррентном входящем потоке.

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

ая(г,ц„и2) |

_7>1(е->. = (3)

ди1 сиг

Здесь Я(2,«1;И2)= ¿¿^^(г,/,,/,).

¡,=01^0

Предлагаемый метод начальных моментов, заключается в последовательном дифференцировании уравнений (2-3) по щ,и2, и рекуррентном решении полученных систем линейных уравнений для характеристик системы ЫАРт\м^о и дифференциальных уравнений для 6/<2,|м^со, решаемых с помощью преобразования Лапласа-Стилтьеса. Основные вероятностные характеристики приведены в табл. 2.1, {к = 1,2).

Табл. 2.1

смо 1 МОМЕНТ 2 МОМЕНТ КОРРЕЛЯЦИОННЫМ МОМЕНТ

МАРт\мг\х> (») ИВЕ щ' =- 2ц* тп =—-—ГИВЕ + 1*1 + 14 + (т[,)+тр))вЕ]

ат\м2\<о т\' — — №) 1 Г 1 V*\}~Л (и*) 1 Г^(,)(о) ^ V + М, + д2|_ & дг

Здесьт^Ш^-дГ, « = = ^

(и.)'

Дальнейшее исследование проводится методом асимптотического анализа в условии эквивалентного роста времени обслуживания заявок в каждом блоке, то есть ц,,ц2 -» 0, с помощью которого найдены не только асимптотические моменты, но также и асимптотическое двумерное распределение вероятностей числа занятых приборов в блоках системы. Рассмотрим применение этого метода на анализе системы ШРт\М2\х,.

Для нахождения асимптотики первого порядка вводятся обозначения ц, = б , \i2=cq, где q = const и в уравнении (2) выполняются замены = ег,, и2 = ъх2, Н(й,,ы2)= F,(x„x2,e).

Теорема 23. Решение уравнения

F,(x,,x2,e) в предельном условии е-» 0 имеет вид F,(*„;c2) = +—^j, где

величина к, определяется равенством к, = RBE.

Для нахождения асимптотики второго порядка в уравнении (2) выполняется заме-

на Н(и,,к2)= Н2(м,,и2)ехр'|у

№

К[ После обозначения ц, = е2, ц, = (zq)2 и за-

мены и, = ех, , иг = щхг, Н2 (и,, и2) = Р2 (х[, х2, е) , доказана следующая теорема. Теорема 2.4. Решение уравнения

т

8хх

= F2(x„x2,s)|Q + (e^x'+',:i)-l^ + k1(e-m-l)[ + k1(e--"a:!-l)[} F2(x,,x2,c) в предельном условии е 0 имеет вид

F2(x„x2)=RexpM

/ 2 г\ м, щ

,2 (2к,-к,) к2+J и.и2-—--—>, где величина к, определяется

равенством к2=к1+Т2ЪЕ, здесь вектор Г2 удовлетворяет условию Г2Е = 0 и является решением неоднородной системы линейных алгебраических уравнений

В результате обратных замен для двумерного процесса {г,(/),;2(/)} можно записать асимптотическую характеристическую функцию, имеющую вид двумерной гауссов-ской характеристической функции

h2(u„u2)=exp'

. к, (ju,f кЛ ( . к, (jUjf к

Hi 2 (, V-2 2 ц2

¿1+/MiM2fezb)

Н1+Н2

которую будем назьшать асимптотикой второго порядка.

Реализация асимптотического метода для системы С/^|а/2|оо аналогична Параметры гауссовского распределения определяются выражениями:

к 2 = здесь функция /2 (г) удовлетворяет условию /2(со)=0 ияв-

ляется решением уравнения ^^ + (А(2)~ = 0.

Особый интерес вызывают исследования систем параллельного обслуживания с произвольной функцией распределения времени обслуживания заявок на приборах в блоках - Вк(х), (к = 1,2). В третьей главе выполнено исследование таких систем с

МАР(2) и а(2) входящими потоками (МАР{г)\в1г\«>\ 0/(2)|с7/2|оо).

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

Для реализации метода двумерного динамического просеивания определяются вероятности \-Вк{-{), (¿ = 1,2) которые имеют смысл вероятностей того, что сдвоенная заявка входящего потока, поступившая в систему в момент времени / < Т, в момент времени Т будет находиться в системе, занимая для своего обслуживания по одному из приборов каждого блока системы и формировать события двумерного просеянного потока. Заявки, завершившие обслуживание и покинувшие систему до момента времени Т не попадают в просеянный поток.

В момент времени Т число пк(Т) событий, наступивших в просеянном потоке равно числу занятых приборов в рассматриваемой системе массового обслуживания, то есть /,(Г)=И1(Г),/2(Г)=«2(Г).

В первой части третьей главы проводится исследование системы МАРЩр1-^о. Для этого получено основное векторно-матричное уравнение

Н(к„«2,0= К. (4)

Решить данное уравнение аналитическими методами не представляется возможным, поэтому для его решения предлагается метод асимптотического анализа в условии

оо

эквивалентного роста времени обслуживания при Ьк->оо, где Ьк = |(1~54(х))с& -

среднее значение времени обслуживания заявки на приборе в каждом блоке (к = 1,2).

Для нахождения асимптотики первого порядка вводятся обозначения Ь^ = 1/е, Ь2 = 1/<7Б и в уравнении (4) выполняются замены: /е = т,

5(1)(/)=5(,)(4 5(2)(0=5<2)(4 «1 = «Р«2 = «2, Н(«,,«2,г)=

Теорема 3.1. Решение уравнения

ОХ

+ (е/"> -1)?(2)(т)+(ел -г^е'"' -1)?(1)(т)?(2)(т)]в} в предельном условии

£ —> 0 имеет вид

Р1(*1,х2,т)=Кехр-|/г1к1 |5,'1'(г)оЬ+_/х2к1 где величина к, определяется

I ]

равенством к.! = ИВЕ.

Для нахождения асимптотики второго порядка в уравнении (4) выполняются замены Н(«,,и2,г)=Н2(и1,г/2,/)ехр|ум1к, + уи2к,

6, = 1/£2, Ь2 =1/^, ,е2 Д ¡0е2 =т0,50)(г), = "1 = Щ,и2 = ех2, Н2(и„и2,г)= Р2(х,,х2,т,е). Теорема 3.2. Решение уравнения

+ - - ))?(,)(т)?<2>(т)]В- [уех1к1.?М(т)+7«2к,5(2»(т))} ^(х.^т.е) в щ>еделъ-ном условии г —> 0 имеет вид

Рг(-г1>х2,т) = 1^ехр

(а.)1

V 'о

(¿О2

+ 2к2 +/\х2(к, +

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

В результате при рассмотрении момента времени Г < Г = 0 для двумерного процесса {',(/),'2(')} можно записать асимптотическую характеристическую функцию, имеющую вид двумерной гауссовской характеристической функции

17 (' У

1ь{щ,и2)= ехр^ уи.кД + ]

1ч '

+ + 2к2р2]|+/а1м2[к1 +2к2]р1:

которую будем назьтать асимптотикой второго порядка. Здесь

о «о о

=|(1 - Вх{-т - В2(~ № =р12.

-00 О

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

о/(2)|о/2|*>.

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

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

мость изучаемых процессов достигается при одинаковых параметрах времени обслуживания. Например, для МАР(2) - потока с параметрами:

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

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

0,5 0,3 -0,8 0 0 3 од 0,2 0

для различных значений ц, и ц2 значения коэффициента корреляции г(/„/2) составили, (табл. 4.1).

Табл. 4.1

1 0,5 0,1 0,01

1 0,577 0,554 0,347 0,121

0,5 0,554 0,598 0,457 0,171

од 0,347 0,457 0,625 0362

1 0,01 0,121 0,171 0,362 0,634

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

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

Д = шах

ОедКаО

X 2 ^ 0> ~ X X А' где Л ('>-/) _ функция распределения, полученная с

(=0 ¡л мо у=ю i

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

"-0,3 0,1 0,2' '1 0 0" "0 0 0"

0 = 0,5 -1 0,5 ,л = 0 1 0 ,0 = 0 0 0

0,25 0,25 -0,5 0 0 1 0 0 0

Для различных значений е (ц, = е, ц2 = 2е) значения Д составили (табл. 4.2).

Табл. 4.2

є ЮАОО 8/100 6/100 4/100 2Я00 1/100

д 0,092 0,073 0,063 0,055 0,044 0,036

Из таблицы 4.2 видно, что с уменьшением значений величины є расстояние Д уменьшается, и уже при є = 2/100 расстояние Колмогорова не превосходит 0,05.

Для систем с входящими МАР(2) и 01(2) потоками область применимости асимптотических алгоритмов находится путем сравнения характеристик, полученных с помощью метода асимптотического анализа в условии эквивалентного роста времени обслуживания и характеристик, полученных с помощью метода начальных моментов.

Например, для системы с входящим МАР(2) потоком заданным матрицами:

-0,3 0,1 0,2" "1 0 0" "0 0,5 0 "

0 = 0,5 -1 0,5 ,л = 0 2 0 , 0 = 1 0 0,8

0,25 0,25 -0,5 0 0 3 0 0,4 0

для различных значений є (ц, = є, ц2 = 2є) получаем следующие характеристики (табл. 4.3).

Табл. 4.3

Щ тг

I 8 Допр. Асимп. Допр. Асимп. Допр. Асимп.

од 33,307 35,494 15,832 17,747 0,651 0,676

1 0,01 352,430 354,936 175,002 177,468 0,673 0,676

Из результатов, приведенных в таблице 4.3 можно сделать вывод о том, что при уменьшении параметра е асимптотические результаты приближаются к допредельным. Для большей наглядности приведем значение относительной погрешности при различных значениях е (табл. 4.4).

Табл. 4.4

Е т2

од 0,065 0,120 0,038

0,01 0,007 0,014 0,004

Из таблицы 4.4 видно, что относительная погрешность при е = 0,01 составляет менее 1%, что говорит о высокой точности применяемого метода асимптотического анализа в условии эквивалентного роста времени обслуживания в блоках системы.

Также в диссертации описан алгоритм и приведен анализ результатов имитационного моделирования систем параллельного обслуживания сдвоенных заявок случайных потоков. Показано что отклонение результатов, полученных с помощью имитационного моделирования от аналитических результатов при увеличении числа поступивших сдвоенных заявок до N = 10® составляют не более 2-3%, что говорит о высокой точности разработанных программ.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Ивановская (Синякова) И.А. Исследование модели параллельного обслуживания сдвоенных заявок в нестационарном режиме / С.П. Моисеева, И.А. Ивановская (Синякова) // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 3 (12). - С. 21 - 28. - 0,33 / 0,23 п.л.

2. Ивановская (Синякова) И.А. Исследование математической модели параллельного обслуживания заявок смешанного типа / С.П. Моисеева, И.А. Ивановская (Синякова) // Известия Томского политехнического университета. Управление, вычислительная техника и информатика - 2010. - Т. 317, № 5. - С. 32 - 34. - 0,16 / 0,11 п.л.

3. Синякова И.А. Исследование системы МАР^вУ00 методом просеянного потока / С.П. Моисеева, ИЛ. Синякова // Вестник Кемеровского государственного университета. - 2012. - Вып. 1 (49). - С. 47 - 53. -0,27/0,19 п.л.

4. Синякова И.А. Метод моментов для исследования математической модели параллельного обслуживания сдвоенных заявок потока марковского восстановления / С.П. Моисеева, И.А. Синякова // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2012. - т. 321, № 5. — С. 24 - 29. -0,24/0,17 п.л.

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

5. Ивановская (Синякова) И.А. Исследование системы ММР^ОЫ«» методом просеянного потока / С.П. Моисеева, И.А. Ивановская (Синякова) // Информационные тех-

нологии и математическое моделирование (ИТММ-2009) : материалы VIII Всероссийской научно-практической конференции с международным участием :в2ч. 13-14 ноября 2009 г. - Томск: Изд-во Том. ун-та, 2009. - Ч. 1. - С. 32 - 36. - 0,10 / 0,07 пл.

6. Sinyakova I. Investigation of output flows in the system with parallel service of multiple requests / S. Moiseeva, I. Sinyakova // Problems of Cybernetics and Informatics (PCI'2012) : IV International Conference. Baku, Azerbaijan. September 12 - 14, 2012. -Baku: Elm, 2010.-P. 180-181.-0,15/0,11 п.л.

7. Ивановская (Синякова) И.А. Математическая модель параллельного обслуживания заявок в распределенных вычислительных системах / С.П. Моисеева, ИА. Ивановская (Синякова) // Теория вероятностей, математическая статистика и их приложения : сборник научных статей. - Минск : РИВШ, 2010. - Вып.З. - С. 122 - 126. -0,19/0,13 пл.

8. Ivanovskaya (Sinyakova) I. Investigation of the queuing system MMP(2)|M2|°o by method of the moments / S. Moiseeva, I. Ivanovskaya (Sinyakova) // Problems of Cybernetics and Informatics : the third international conference. Baku, Azerbaijan. September 6 - 8,2010. - Baku: Elm, 2010. - Vol. 2. - P. 196 - 199. -0,13/0,10 п.л.

9. Ивановская (Синякова) И.А. Немарковская модель параллельного обслуживания сдвоенных заявок / С.П. Моисеева, ИА. Ивановская (Синякова) // Научное творчество молодежи : материалы XIV Всероссийской научно-практической конференции : в 2 ч. 15 - 16 апреля 2010 г. - Томск : Изд-во Том. ун-та, 2010. - Ч. 1. - С. 35 - 38. -0,15/0,10 пл.

10. Ивановская (Синякова) И А. Исследование системы массового обслуживания ММР®|М2|со методом моментов / М.Д. Жалкеева, ИА. Ивановская (Синякова) // Научное творчество молодежи : материалы XIV Всероссийской научно-практической конференции : в 2 ч. 15 -16 апреля 2010 г. -Томск: Изд-во Том. ун-та, 2010. -Ч. 1. - С. 81 -83.-0,08 / 0,06 пл.

П.Ивановская (Синякова) И А. Исследование системы МАРКСЫ® методом просеянного потока / С.П. Моисеева, И А. Ивановская (Синякова) // Новые информационные технологии в исследовании сложных структур : тезисы докладов Восьмой Российской конференции с международным участием, 5-8 октября 2010 г. - Томск : Изд-во НТЛ, 2010. - С. 33. - 0,06 / 0,04 пл.

12. Ивановская (Синякова) И А. Исследование системы массового обслуживания GI<2>|GI2|t» методом просеянного потока / С.П. Моисеева, И. А. Ивановская (Синякова) // Информационные технологии и математическое моделирование (ИТММ-2010) : материалы IX Всероссийской научно-практической конференции с международным участием : в 2 ч. 19 - 20 ноября 2010 г. - Томск: Изд-во Том. ун-та, 2010. - Ч. 1. - С. 77 - 82. -0,17/0,12 пл.

13. Sinyakova I. Investigation of queuing system GI(2)jM2|°o / S. Moiseeva, I. Sinyakova // Queues: flows, systems, networks : proceedings of the International Conference «Modern Probabilistic Methods for Analysis and Optimization of Information and Telecommunication Networks». Minsk, January 31 - Februaiy 3, 2011. - Минск : РИВШ, 2011. - P. 219 - 225. -0,18/0,12 пл.

14. Синякова И.А. Исследование системы обслуживания сдвоенных заявок с входящим потоком марковского восстановления методом моментов / С.П. Моисеева, И А. Синякова // Научное творчество молодежи : материалы XV Всероссийской научно-практической конференции : в 2 ч. 28 - 29 апреля 2011 г. — Томск : Изд-во Том. ун-та, 2011. - Ч. 1. - С. 34 - 37. - 0,14 / 0,10 пл.

15. Синякова И А. Исследование модели параллельного обслуживания сдвоенных заявок с рекуррентным входящим потоком/ С.П. Моисеева, И А. Синякова // Информационные технологии и математическое моделирование (ИТММ-2011) : материалы X

Всероссийской научно-практической конференции с международным участием : в 2 ч.

25 - 26 ноября 2011 г. - Томск : Изд-во Том. ун-та, 2011. - Ч. 1. - С. 175 - 179. -0,15/0,10 п.л.

16. Sinyakova I. Modeling of Insurance Company as Infinite-Servers Queueing System / S. Moiseeva, A. Moiseev, I. Sinyakova // International conference on application of information and communication technology and statistics in economy and education. Sofia, Bulgaria. 2012. - Sofia: UNWE, 2012. - P. 78 - 84. - 0,20 / 0,14 п.л.

17. Синякова И.А. Исследование системы массового обслуживания сдвоенных заявок с входящим МАР(2) -потоком [Электронный ресурс] / ИА. Синякова // Научное творчество молодежи : материалы XVI Всероссийской научно-практической конференции : в 2 ч. 17 - 18 мая 2012 г. - Электрон, дан. - Анжеро-Судженск, 2012. - Ч. 1. -1 электрон, опт. диск.

18. Синякова И А. Сравнение асимптотических и точных результатов исследования СМО МАР(2)|М2| со / С.П. Моисеева, ИА. Синякова // Информационные технологии и математическое моделирование (ИТММ-2012): материалы XI Всероссийской научно-практической конференции с международным участием : в 2 ч. 23 - 24 ноября 2012 г. -Кемерово : Практика, 2012. - Ч. 2. - С. 127 - 130. - 0,14 / 0,10 пл.

19. Синякова И.А. Математические модели параллельного обслуживания сдвоенных заявок / ИА. Синякова // Теория вероятностей и ее приложения : тезисы докладов международной конференции, посвященной 100-летию со дня рождения Б.В. Гнеденко.

26 - 30 июня 2012 г. - М.: ЛЕНАНД, 2012. - С. 206 - 207. - 0,05 пл.

20. Синякова И А. Математическая модель страховой компании в виде системы массового обслуживания М|М|со / С.П. Моисеева, ИА. Синякова // Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей : международная научная конференция. Минск, 28-31 января 2013 г. - Минск : Изд-во центр БГУ, 2013. - С. 154-159.-0,15/0,10 п.л.

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

Национальный исследовательский Томский государственный университет

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И МЕТОДЫ ИССЛЕДОВАНИЯ СИСТЕМ ПАРАЛЛЕЛЬНОГО ОБСЛУЖИВАНИЯ СДВОЕННЫХ ЗАЯВОК СЛУЧАЙНЫХ ПОТОКОВ

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

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

Научный руководитель: кандидат технических наук, доцент Моисеева С.П.

Томск-2013

Содержание

Введение................................................................................................................................................................................5

Глава 1. Исследование систем параллельного обслуживания сдвоенных заявок с пуассоновским входящим потоком..................................................................................31

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

1.1.1 Постановка задачи..............................................................................................................................................................31

1.1.2 Нахождение производящей функции....................................................................................32

1.1.3 Двумерное распределение вероятностей состояний системы М(2)М2оо..............................................................................................................................................................................35

1.1.4 Моменты............................................................................................................................................................................36

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

1.2.1 Постановка задачи..............................................................................................................................................................38

1.2.2 Нахождение производящей функции......................................................................................39

1.2.3 Нестационарное двумерное распределение вероятностей состояний выходящего потока..........................................................................................................................42

1.2.3 Моменты............................................................................................................................................................................42

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

Резюме..................................................................................................................................................................................49

Глава 2. Исследование систем параллельного обслуживания сдвоенных заявок непуассоновских входящих потоков............................................................................................51

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

с входящим МАР(2)-потоком................................................................................................................................................................52

2.1.1 Уравнение Колмогорова..............................................................................................................................................52

2.1.2 Характеристическая функция......................................................................................................53

2.1.3 Метод начальных моментов............................................................................................................54

2.1.4 Метод асимптотического анализа........................................................................................59

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

с входящим а^ потоком......................................................................................................................................................................66

2.2.1 Уравнение Колмогорова..............................................................................................................................................66

2.2.2 Характеристическая функция....................................................................................................67

2.2.3 Метод начальных моментов..........................................................................................................68

2.2.4 Метод асимптотического анализа........................................................................................75

Резюме........................................................................................................................................................................81

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

3.1 Модифицированный метод двумерного динамического просеивания .... 84

3.2 Исследование системы МАР{2)

GL

оо

3.2.1 Модифицированный метод двумерного динамического просеива-

ния для исследования системы МАР(2)

GL

00

3.2.2 Асимптотический анализ системы MAP

(2)

GL

оо

3.3 . Исследование системы GI

(2)

GL

00

86

86 88 95

3.3.1 Модифицированный метод двумерного динамического просеива-

00

GL

оо

95 97

ния для исследования системы

3.3.2 Асимптотический анализ системы

Резюме....................................................................................... 106

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

4.1 Программа нахождения двумерного распределения вероятностей

состоянии системы

М®

М Jco,

109

4.2 Численная реализация метода начальных моментов........................... 110

4.2.1 Программа метода начальных моментов для системы 111

мар{2)

■м,

00

4.2.2 Программа метода начальных моментов для системы

Gl

(2)

Л/,

оо

вероятностей числа занятых приборов системы MAP

(2)

М,

оо

системы

МАР{1)

М,

00

4.2.3 Влияние параметров времени обслуживания на изменение значений коэффициента корреляции.......................................................... 114

4.3 Программа нахождения асимптотического распределения вероятностей

числа занятых приборов............................................................................... 115

4.3.1 Сравнение асимптотического и допредельного распределения

4.3.2 Сравнение асимптотических и допредельных характеристик

117

118

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

сдвоенных заявок с произвольным временем обслуживания..........................................120

4.4.1 Алгоритм имитационного моделирования....................................................................120

4.4.2 Анализ результатов, полученных с помощью имитационного моделирования................................................................................................................................................................125

Резюме................................................................................................................................................................................129

Заключение........................................................................................................................................................................130

Список использованной литературы........................................................................................................133

Введение

Большой скачок в развитии теории массового обслуживания (ТМО) произошел в середине XX века. В это время решались наиболее интересные математические задачи ТМО, связанные с анализом систем массового обслуживания (СМО), на вход которых поступают пуассоновские потоки заявок [11,7, 65, 68, 85 и др.]. А также были разработаны некоторые общие приемы решения широких классов задач и осмыслены специфические особенности самой теории. В свою очередь, ТМО оказала существенное воздействие на развитие других разделов теории вероятностей, в частности на теорию случайных процессов.

С конца XX века интенсивно развивается теория многолинейных систем и сетей, а также RQ-систем (Retrial Queue Systems), становление и развитие которой в значительной мере стимулировалось практическими задачами проектирования вычислительных систем и сетей. В этой области следует отметить работы А.Н. Дудина, В.И. Климснок [19, 20, 21], В.А. Ивницкого [35, 36], Г.П. Башарина [5, 6], П.П. Бочарова и A.B. Печинкина [10, 12, 63, 64], Ю.В. Малинковского [38], М.А. Маталыцкого [43, 44], Г.И. Фалина, J.G. Tempelton, J.R. Artalejo [94, 107, 108, 109], Т. Yang [140] и многих других.

Математическим методам исследования и моделирования информационных систем, основанным на теории массового обслуживания и теории телетрафика, посвящено большое количество статей, опубликованных за последние десять лет [1, 4, 9, 59, и др.].

Например, в работах Г.Г1. Башарина, К.Е. Самуйлова, Ю.В. Гайдамака [8, 14, 13, 66] рассматриваются однолинейные модели массового обслуживания, в том числе и с параллельно функционирующими блоками для расчета качества обслуживания в сетях сотовой подвижной связи (ССПС) с приоритетной передачей вызовов, для оценки производительности транзитного пункта сигнализации, описания процесса «фотонизации» транспортных сетей и функционирования SIP-сервера в нормальном и перегруженном режимах.

В статье A.B. Печинкима, И.А. Соколова и В.В. Чаплыгина [62] рассматривается важная для приложений задача анализа многолинейной системы массового обслуживания с ненадежными приборами. Предложены методы расчета стационарного распределения числа заявок в системе при различных вариантах функционирования системы.

Статья А.И. Зейфмана, ЯЛ. Сатина, A.B. Коротышевой и H.A. Тереши-ной [25] посвящена изучению предельных характеристик системы обслуживания с катастрофами в предположении, что интенсивности катастроф зависят от числа требований в системе. Получены достаточные условия слабой эргодичности процесса, описывающего число требований в системе, и соответствующие оценки.

В работах Е.В. Морозова [50, 51] развивается метод регенерации для исследования условия существования стационарности в СМО различной конфигурации.

В работах О.М. Тихоненко [80, 81] рассматриваются актуальные задачи проектирования информационных систем, учитывающих зависимость между объемом требования и временем его обслуживания.

Основным отличием систем с неограниченным числом обслуживающих приборов является отсутствие очередей и отказа в обслуживании заявок. Поэтому они являются удобными математическими моделями для описания социально-экономических процессов. Можно отметить работы М.А. Федоткина [84, 83], A.B. Зорина [26], М.Г. Носовой [60], И.Р. Гарайшиной [15], A.C. Морозовой [52], И.А. Захорольной [24], посвященные математическому моделированию транспортных потоков, демографических процессов и процессов изменения численности клиентов пенсионных фондов, торговых и страховых компаний.

Исследования СМО с неограниченным числом приборов можно встретить в статьях П.П. Бочарова, A.B. Печшисина [12], В.В. Рыкова [37], A.A. Назарова [16, 58], D. Baum и L. Breuer [98, 99], Е.А. Van Doom и А.А Jagers [138],

M. Parulekar и A.M. Makowski [130], С. Fricker и M.R. Jaibi [110], N.G. DuffieldM [106], A.K. Jayawardene и О. Kella [115], В. D'Auria [95] и многих других.

Важно отметить, что большая роль в развитии методов исследования систем с неограниченным числом обслуживающих приборов принадлежит профессору Томского государственного университета доктору технических наук A.A. Назарову. Предложенный им метод асимптотического анализа, суть которого изложена в монографиях [16, 53, 58], является оригинальной разработкой автора и может быть применен для исследования СМО различной конфигурации [54, 55, 69, 79]. Метод заключается в расширении фазового пространства состояний системы таким образом, что соответствующий многомерный случайный процесс их изменения во времени оказывается марковским (метод мар-ковизации). Составляются уравнения Колмогорова для распределения вероятностей, частичных производящих функций или характеристических функций значений полученных многомерных марковских случайных процессов. В этих уравнениях выполняется предельный переход в некоторых предельных условиях, который позволяет получить предельные (асимптотические) уравнения. Решениями этих уравнений являются соответствующие предельные (асимптотические) характеристики рассматриваемых систем обслуживания.

Обсуждаемый метод асимптотического анализа содержит несколько классов, в зависимости от применяемых предельных условий, среди которых можно выделить: предельное условия растущего времени обслуживания, условие высокой интенсивности входящего потока, условие большой задержки заявке в RQ-системах, предельное условие большой загрузки однолинейных систем, условие предельно-редких изменений состояний специальных потоков (ММРР, MAP, SM). Применение метода позволяет находить приемлемое для практических приложений решение.

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

ях A. Movaghar [129, 117], С. Knessl и J. A. Morrison [119], М. Armony и N Bambos [90], G. Michailidis [97], D. G. Down [104] и многих других [100, 113, 133]. В этих работах рассматриваются системы параллельного обслуживания различной конфигурации: однолинейные СМО с конечным и бесконечным буфером, приоритетным обслуживанием, нетерпеливыми заявками и общим ординарным входящим потоком; СМО с двумя и более блоками обслуживания с конечным числом приборов и общей конечной очередью. Характерно то, что все системы имеют пуассоновский входящий поток и экспоненциальное время обслуживания.

Однако пуассоновский поток не всегда адекватно описывает реальные потоки в мультисервисных сетях связи и телекоммуникационных системах. Как считают А.Г. Ложковский и В.М. Колчар [40, 41], применение пуассоновского потока для расчета характеристик качества обслуживания в реальных системах дает большую погрешность. В их работах показано, что функция распределения длин интервалов между моментами наступления событий лучше аппроксимируется распределениями, обладающими «длинным хвостом», а для описания трафика же характерна неравномерность интенсивности поступления заявок.

Обоснованность адекватности применения непуассоновских потоков (марковски модулированного пуассоновского потока и рекуррентного потока) для описания информационных потоков в мультисервисных сетях связи и телекоммуникационных системах следует из работ таких ученых, как, W.E. Leland, M.S. Taqqu, W. Willinger [125], V. Paxson, S. Floyd [131], SH. Kang, YH. Kim [116], A. Klemm, С. Lindemann, M. Lohmann [118].

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

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

(общего марковски модулированного пуассоновского потока (МАР(2)) и рекуррентного потока (GI(2))) с неограниченным числом приборов, экспоненциальным и произвольным временем обслуживания, как обобщение результатов исследования аналогичных систем с пуассоновскими входящими потоками и экспоненциальным временем обслуживания, впервые описанных в работах украинских ученых Е.А. Лебедева, A.A. Чечельницкого и О.В. Кучеренко [86, 122, 123].

Межпрсдметность рассматриваемых моделей. Системы массового обслуживания с неограниченным числом приборов являются универсальными и могут служить для описания работы Пенсионного фонда, определения маркетинговой политики торговых компаний с целыо оптимизации дохода, для демографического прогнозирования на среднесрочную и долгосрочную перспективу и других социально-экономических процессов [52, 15, 60, 24]. Кроме того, СМО с неограниченным числом приборов используются для определения объема памяти стохастической вычислительной системы и учета зависимости между объемом требования и временем его обслуживания, а также в ряде других приложений.

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

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

В соответствии с целыо поставлены следующие задачи:

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

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

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

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

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

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

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