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

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

005007227

Лапатин Иван Леонидович

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

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

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

12 йкб тг

Томск -2012

005007227

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

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

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

Официальные оппоненты: доктор физико-математических наук, профессор

Воробейчмков Сергей Эрикович

кандидат физико-математических наук, доцент Гарайшина Ирина Рашитовна

Ведущая организация: Московский физико-технический институт

(государственный университет), г. Москва

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

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

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

Автореферат разослан 20 декабря 2011 г.

Ученый секретарь

диссертационного совета,Д 212.267.08 доктор технических наук, профессор

А.В. Скворцов

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

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

Большой вклад в развитие теории массового обслуживания внесли Ю.К. Беляев, A.A. Боровков, Б.В. Гнеденко, Дж.Р. Джексон, Ф. Келпи, Дж. Кендалл, Дж.Ф.С. Кингмэн, JI. Клейнрок, Г.П. Климов, И.Н. Коваленко, С. Пальм, Ф. Поллачек, Т.Саати, АЛ. Хинчин и др.

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

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

Основные результаты по исследованию выходящих потоков относятся к моделям с пуассоновским входящим потоком. П. Берк, Е. Рейч, П. Финч независимо друг от друга установили, что выходящий поток для системы с пуассоновским входящим потоком и экспоненциальным временем обслуживания будет пуассоновским. А в 1963 году Н. Мирасол показал, что выходящий поток систем с неограниченным числом приборов и произвольным распределением времени обслуживания, на вход которых поступает простейший поток, также является простейшим. Исследованию выходящих потоков других моделей с простейшим входящим потоком посвящены работы, например, Д. Дели, Н.М. Акулиничева, Л.К. Горского, A.M. Александрова и др.

В качестве существенного обобщения простейших потоков для более адекватного описания реальных потоков были предложены классы МАР-потоков (Markovian Arrival Process) и SM-потоков (Semi-Markovian process). В книге Б.В.Гнеденко, И.Н. Коваленко, классы MAP- и SM-потоков названы специальными потоками однородных событий. В монографии А.Н. Дудина и В.И. Кли-менок специальные потоки названы коррелированными.

Исследованием выходящего потока однолинейной системы с входящим МАР-потоком занимались Н. Бин, Д. Грин, П. Тейлор, но общих подходов по исследованию выходящих потоков систем массового обслуживания с непуас-соновским входящим потоком найдено не было. Именно поэтому разработка методов исследования выходящих потоков для более адекватных математических моделей систем обслуживания с коррелированными входящими потоками является актуальной задачей.

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

Для достижения вышеуказанной цели поставлены и решены следующие задачи:

1. Определение условий, при выполнении которых МАР-потоки являются пуассоновскими.

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

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

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

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

1. Найдены два новых достаточных условия на параметры МАР-потоков, при выполнении которых число наступивших событий за некоторое время имеет распределение Пуассона. Данные результаты обобщают и расширяют известное условие равенства интенсивностей в каждом состоянии управляющей цепи. Полученные условия имеют простой вид и позволяют определять: является ли рассматриваемый МАР-поток пуассоновским, что значительно может упростить исследуемую модель.

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

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

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

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

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

1. Два новых достаточных условия на параметры МАР-потоков, при выполнении которых число наступивших событий за некоторое время имеет распределение Пуассона.

2. Новые асимптотические условия сходимости последовательностей MAP (ММР)-потоков к потокам Пуассона.

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

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

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

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

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

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

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

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

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

2. VII, VIII, IX, X Всероссийские научно-практические конференции с международным участием «Информационные технологии и математическое моделирование». г. Анжеро-Судженск, 2008,2009,2010,2011 г.

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

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

5. Всероссийская конференция с элементами научной школы для молодежи. г. Ульяновск, 2009.

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

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

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

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

- НИОКР в качестве победителя программы У.М.Н.И.К. (2009-2010 годы) по теме «Разработка методов исследования выходящих потоков для систем массового обслуживания с неограниченным числом приборов.» государственный контракт № 6360 р/8858 от 8 декабря 2008 г, государственный контракт № 7661р/10273 от 31.03.2010.

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

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

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

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

В первой главе приведены определения потоков однородных событий, модели которых рассматриваются в диссертационной работы. Это пуассонов-ские потоки, класс марковских потоков (ММР, MAP) и полумарковские (SM) потоки.

МАР-поток задается матрицей инфинитезимальных характеристик Q управляющей цепи Маркова k(t); условными интенсивностями (£>0), которые будем записывать в виде диагональной матицы А соответствующей размерности; и матрицей D вероятностей наступления событий при переходе управляющей цепи Маркова из одного состояния в другое. Число событий, наступивших в МАР-потоке за некоторое время t, обозначим n(t).

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

Теорема 1.1. Если для характеристик МАР-потока выполняется равенство векторов

BE = кЕ, (1)

то рассматриваемый МАР-поток является простейшим с параметром к.

Здесь В - матрица с элементами X* на главной диагонали и d^'iv* вне главной диагонали, а Е - единичный вектор-столбец соответствующей размерности; к - интенсивность МАР-потока, определяемая формулой k=RBE, a R — стационарное распределение вероятностей управляющей цепи Маркова k(t).

Лемма 1.1. Для того, чтобы случайные величины k(t) и n(t) в рассматриваемом МАР-потоке были стохастически независимы необходимо и достаточно выполнения равенства векторов

RB = kR. (2)

Теорема 1.2. Если в МАР-потоке величины k(t) и n(t) стохастически независимы, то есть выполняется равенство (2), то рассматриваемый МАР-поток является простейшим.

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

Для характеристик МАР-потока было получено дифференциально-матричное уравнение с начальным условием

[ Н(и,0) = R

где Н(и,/)={Я(1,й,/), #(1,и,/),...}, H (к, и,() = Ze'mP{k,n,t), j = 4-ï - мнимая

и=0

единица, a P{k,rt,t) = P{k{i) = А,и(0 = и} - распределение вероятностей двумерной цепи Маркова {k{t),n{t)}.

Будем рассматривать последовательность ММР-потоков в условии предельно частых изменений его состояний. Зафиксируем некоторую матрицу ин-финитезимальных характеристик Q(1), которая определяет управляющую цепь Маркова k{t), и матрицу А. Затем, полагая, что S некоторая положительная величина, в задаче (3) сделаем следующие замены

Q = 5-Q(1>,H(M,Î) = F(«,Î,5).

Тогда для вектор-функций F(u,t,S) можно записать

[ F(«,0,5) = R

Теорема 1.3. Сумма компонентов предельного, при S -» оо, значения вектор-строки F (к,/) решения F задачи (4) имеет вид

F(K,OE = exp^-l)K/J, (5)

где Е - единичный вектор-столбец, величина к имеет смысл интенсивности ММР-потока.

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

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

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

Основным объектом исследования является выходящий поток, рассматриваемых систем. Для нахождения его характеристик предлагается рассматривать случайный процесс m(t), определяющий количество заявок, закончивших обслуживание в системе за некоторый промежуток времени. Предполагается, что исследуемые системы функционируют в стационарном режиме. Число заявок в системе обозначается i(t).

В разделе 2.1 получено дифференциально-матричное уравнение, определяющее характеристики системы MAP | M | оо, в том числе характеристики выходящего потока

8t дх (6)

= Н(дг,М,/)}з + (еА-1)в}

где Щх,и,(у={Н{\,х,и,1), Н{\,х,и,!),...), Н(к,х,и,1) = ^е'*^™ Р(кМт,1),

I т

j = - мнимая единица, а Р{к,1,т,1) = Р{к(1) = ¿,1(0 = /,т(/) = т) - распределение вероятностей трехмерной цепи Маркова {к(1),1(1),т(1)}.

В разделе 23 рассматривается система в условии растущего времени обслуживания, то есть когда среднее значение времени обслуживания каждой заявки стремиться к бесконечности. В системе с экспоненциальным временем обслуживания это условие принимает вид 1/ц—*оо. Или, что то же самое, ¿1—*0.

Рассмотрим систему МАР|М|оо в условии растущего времени обслуживания. Для этого в уравнении (6) сделаем следующие замены

ц = е, х=еу ,Н(х,и,/)=Р(у,и,/,£), (7)

тогда для вектор-функции Р(у,г/,/,е) получим дифференциально-матричное уравнение

д?{х,и,1, е) + ./ у» _ .л д¥(х,и^,в) =

& Л дх (8)

Теорема 2.1. Сумма компонентов предельного, при е -> 0, значения вектор-строки ¥(х,и,{) решения Т(х,и,уравнения (8) имеет вид

Р(>>,М)Е = ехр(/>к + {е]и - 1>к/), (9)

где Е - единичный вектор-столбец, величина к определяется равенством

к = Ш$Е, ' (10)

а вектор-строка К. - стационарное распределение вероятностей управляющей цепи Маркова.

В разделе 2.4 аналогичная теорема доказывается для системы с полумарковским входящим потоком, то есть для системы БМ | М | °о.

В разделе 2.5 исследуется система ММР | М | °о в условии предельно частых изменений состояний входящего потока. Зафиксируем некоторую матрицу инфинитезимальных характеристик <3<!), которая определяет управляющую цепь Маркова Ж(/), и матрицу Л. Затем, полагая, что 5 некоторая положительная величина, в уравнении (6) сделаем следующие замены

0 = 5-0(1), Н(х,и,() = Р(х,«,/,5).

Тогда для вектор-функций можно записать

бР(д:,»,/,5) ■ (ере-р _»Щх,!!,^) =

аг дх (П)

Теорема 2.4. Сумма компонентов предельного, при 5 —> <*>, значения вектор-строки Р(х,и,1) решения ¥(х,и, 1,5!) уравнения (11) имеет вид

(е^ -1)— + - 1)кГ I, (12)

» I

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

= ех;

В разделе 2.6 аналогичная теорема доказывается для системы МАР|М|оо.

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

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

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

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

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

Подробнее остановимся на этом методе.

Пусть Г]>0, 7>0 - некоторые заданные величины, а Ъ = ^(\~В(х))с1х -

о

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

Здесь S(t) - вероятность того, что заявка, поступившая в систему в момент времени /e[0,67'i+7'], завершит свое обслуживание в момент времени, принадлежащий интервалу [ЬТ^ЬТ^ +Т\

Л/{е>тМ} = Н(0,и,г)Е»

(14)

00

BibTi+^-BipTi-t+T), О <t<bT{

BlbT, -t+T), bT,<t<bT,+T <15)

Будем полагать, что если событие входящего потока наступает в момент t, то с динамической (зависящей от момента времени /) вероятностью S(l) эта заявка просеивается, то есть отправляется в просеянный поток, а с вероятностью 1 -S(t) не рассматривается.

Очевидно, что в просеянном потоке рассматриваются те заявки, которые формируют на интервале \bT^bTx + Г] события выходящего потока.

Обозначим w(f) - число событий просеянного потока, наступивших до момента времени /, то есть на интервале [о,/].

Если в начальный момент времени to=0 система свободна, то число событий просеянного потока к моменту ЬТХ+Т равно числу заявок, закончивших обслуживание на интервале \ЬТХ,ЬТ{ +7], то есть выполняется равенство

п(ЬТ1+Т) = т(Т,ЬТ1), (16)

где т(Т,ЬТ\) - число событий выходящего потока рассматриваемой системы, наступивших на интервале \bTx,bTA + Т\.

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

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

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

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

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

1. Пуассоновский MAP.

2. Имитация МАР_М.

3. Имитация MAP_GI.

4. Имитация SM_M.

5. Имитация SMGI.

6. Гауссовская аппроксимация.

направлены на исследование потоков в допредельной ситуации.

Результаты, полученные в первой главе с помощью асимптотического анализа для МАР-потока, сравнивались с допредельными, полученными с помощью численного анализа МАР-потока, реализованного в модуле «Пуассоновский MAP». В качестве критерия близости распределений рассматривалось расстояние Колмогорова А, определяемое формулой

Д = тах

F{H,t)-F{n,t)

(17)

где F(w,/)= £.Р(/,/) - допредельная функция распределения числа событий на-/=о

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

К;а'4в - Р - МГВ^В - О - уа1)-'Е^а,

п

ЛХ0= - функция распределения Пуассона, которая соответствует

1=0

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

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

Для нахождения допредельных характеристик выходящих потоков систем массово обслуживания с неограниченным числом приборов была построена имитационная модель, реализованная для различных моделей в модулях 2. — 6. («Имитация МАР М», «Имитация МАР_С1», «Имитация 8М_М», «Имитация 8М_01», «Гауссовская аппроксимация»).

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

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

Л = шах

F(n)-F(n)

(18)

где F{ri) - эмпирическое распределение, полученное с помощью имитационного моделирования, F(ri) - асимптотическое распределение, которое находится на основании результатов, полученных в первых трех главах.

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

рядок (101) и более. При разнице порядка 102 ошибка аппроксимации менее 2%.

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

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

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

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

1. Лапатин ИЛ. Асимптотический анализ выходящего потока системы МАР|С1|=о / И.Л. Лапатин, А.А. Назаров // Известия политехнического университета. Управление, вычислительная техника и информатика. -

2009. - Т. 315, № 5. - С. 191 -194.

2. Лапатин ИЛ. Асимптотически пуассоновские МАР-потоки / ИЛ. Лапатин, А.А. Назаров // Вестник Томского государственного университета. Сер. Управление, вычислительная техника и информатика. -

2010. - № 4 (13). - С. 72 - 78.

3. Лапатин ИЛ. Характеристики марковсих систем массового обслуживания при асимптотически пуассоновских входящих потоках / ИЛ. Лапатин, А.А. Назаров // Вестник Томского государственного университета. Сер. Управление, вычислительная техника и информатика. - 2011. -№3(16).-С. 24-30.

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

4. Лапатин ИЛ. Исследование выходящего потока системы в! | в! | оэ методом просеянного потока / И.Л. Лапатин, А.А. Назаров // Вестник Томского государственного университета. Сер. Управление, вычислительная техника и информатика. - 2009. - № 4 (9). - С. 59 - 64.

5. Лапатин И.Л. Исследование выходящего потока системы БМ | М | оо в условиях растущего времени обслуживания / И.Л. Лапатин // Научное творчество молодежи : материалы XII Всероссийской научно-практической конференции : в 2 ч. - Томск : Изд-во Том. ун-та, 2008. - Ч. 1. - С. 29 - 31.

6. Лапатин И.Л. Исследование выходящего потока системы в! | йГ | го в условиях растущего времени обслуживания / И.Л. Лапатин, А.А. Назаров // Информационные технологии и математическое моделирование (ИТММ-2008): материалы VII Всероссийской научно-практической конференции с международным участием (14-15 ноября 2008 г.) : в 2 ч. - Томск : Изд-во Том. ун-та, 2008.-4.2.-С. 30-34.

7. Лапатин И.Л. Исследование выходящего потока системы БМ | 1 да в условиях растущего времени обслуживания / И.Л. Лапатин, А.А. Назаров //

Массовое обслуживание: потоки, системы, сети : материалы международной научной конференции «Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей» (26-29 января 2009 г.). - Минск, 2009. - С. 175 -179.

8. Лапатин ИЛ. Исследование выходящего потока системы MAP|GI|œ в условии растущего времени обслуживания / И.Л. Лапатин, A.A. Назаров // Труды VIII Международной ФАМ конференции : в 2 т. / Сибирский федеральный ун-т. - Красноярск, 2009. - Т. 1. - С. 153 -158.

9. Лапатин И.Л. Исследование выходящего потока системы ММР | M | со / И.Л. Лапатин, A.A. Назаров // Научное творчество молодежи : материалы XIII Всероссийской научно-практической конференции : в 2 ч. - Томск : Изд-во Том. ун-та, 2009. - Ч. 1. - С. 59 - 60.

10. Лапатин И.Л. Исследование выходящего потока системы MAP | M | да в условии растущего времени обслуживания / И.Л. Лапатин, A.A. Назаров // Теория вероятностей, математическая статистика и их приложения : сборник научных статей. - Минск : РИВШ, 2009. - Вып. 2. - С. 76 - 80.

11. Лапатин И.Л. Исследование выходящего потока системы MAP | M | со различными асимптотическими методами / ИЛ. Лапатин, A.A. Назаров // Информационные технологии и математическое моделирование (ИТММ-2009) : материалы VIII Всероссийской научно-практической конференции с международным участием (13-14 ноября 2009 г.) : в 2 ч. - Томск : Изд-во Том. ун-та, 2009,-4.1.-С. 52-56.

12. Лапатин И.Л. Асимптотический анализ выходящего потока системы ММР IMI оо / О.Л. Лапатин // Материалы Всероссийской конференции с элементами научной школы для молодежи (1-5 декабря 2009 г.) : в 5 т. / Ульянов, гос. тех. ун-т. - Ульяновск, 2009. - Т. 4. - С. 430 - 435.

13. Лапатин И.Л. Пуассоновские МАР-потоки / И.Л. Лапатин, A.A. Назаров // Теория вероятностей, математическая статистика и их приложения : материалы Международной конференции (22-25 февраля 2010 г.). - Минск : РИВШ, 2010.-С. 191-195.

14. Лапатин ИЛ. Выходящий поток системы MAP|GI¡a> в смешанном асимптотическом условии / ИЛ. Лапатин // Труды IX Международной ФАМЭТ конференции / Сибирский федеральный ун-т. - Красноярск, 2010. - С. 185 -187.

15. Лапатин ИЛ. Условие предельно частых изменений состояний управляющей цепи ММР-потока / ИЛ. Лапатин // Научное творчество молодежи : материалы XIV Всероссийской научно-практической конференции : в 2 ч. -Томск : Изд-во Том. ун-та, 2010. - Ч. 1. - С. 53 - 56.

16. Лапатин ИЛ. Исследование выходящего потока системы MAP¡GI|oo в условии растущего времени наблюдения / ИЛ. Лапатин // Информационные технологии и математическое моделирование (ИТММ-2010) : материалы IX Всероссийской научно-практической конференции с международным участием (19-20 ноября 2010 г.). - Томск : Изд-во Том. ун-та, 2010. - Ч. 1. - С. 20 - 24.

17. Лапатин ИЛ. Система MR|R|œ в условии растущего времени обслуживания / ИЛ. Лапатин, C.B. Лопухова // Массовое обслуживание: потоки, системы, сети : материалы международной научной конференции «Современные

математические методы анализа и оптимизации информационно-телекоммуникационных сетей». - Минск: РИВШ, 2011. - С. 127 - 130.

18. Лапатин И.Л. О точности аппроксимации выходящих потоков систем массового обслуживания пуассоновским потоком / И.Л. Лапатин И Информационные технологии и математическое моделирование (ИТММ-2011) : материалы X Всероссийской научно-практической конференции с международным участием: в 2 ч. - Томск: Изд-во Том. ун-та, 2011. - Ч. 1. - С. 20 - 24.

Тираж 120 экз. Отпечатано в ООО «Позитив-НБ» 634050 г. Томск, пр. Ленина 34а

61 12-1/521

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

ЛАПАТИН ИВАН ЛЕОНИДОВИЧ

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

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

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

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

Томск-2012

Оглавление

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

Глава 1. Пуассоновские свойства коррелированных потоков............................................31

1.1. Случайные потоки однородных событий........................................................................31

1.2. Уравнения Колмогорова для характеристик МАР-потока............................35

1.3. Пуассоновские МАР-потоки....................................................................................................37

1.4. Примеры пуассоновских МАР-потоков........................................................................41

1.5 Асимптотически пуассоновские ММР-потоки........................................................43

1.6. Асимптотически пуассоновские МАР-потоки............................................45

Резюме......................................................................................................................................................................47

Глава 2 Асимптотическое исследование выходящих потоков марковских

систем с неограниченным числом приборов..................................................................................49

2.1. Уравнения Колмогорова для характеристик системы МАР|М|оо............50

2.2. Уравнения Колмогорова для характеристик системы 8М|М|со................52

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

времени обслуживания..................................................................................................................................55

2.4. Выходящий поток системы 8М|М|со в условии растущего

времени обслуживания..............................................................................................................................58

2.5. Выходящий поток системы ММР|М|оо в условии

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

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

2.7. Выходящий поток системы МАР|М|оо в условии растущего

времени обслуживания и времени наблюдения за потоком..................................66

Резюме....................................................................................................................................................................................71

Глава 3 Асимптотическое исследование выходящих потоков

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

3.1. Метод просеянного потока для исследования выходящих потоков... 74

3.2. Уравнения Колмогорова для характеристик системы MAP|GI|oo....... 76

3.3. Уравнения Колмогорова для характеристик системы SM|GI|co........ 78

3.4. Выходящий поток системы MAP|GI|co в условии растущего

времени обслуживания............................................................... 80

3.5. Выходящий поток системы SM|GI|co в условии растущего

времени обслуживания............................................................... 82

3.6. Выходящий поток системы MMP[GI|oo в условии

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

3.7. Выходящий поток системы MAP|GI|co в условии

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

3.8. Выходящий поток системы MAP|GI|oo в условии растущего

времени обслуживания времени наблюдения за потоком.................... 92

Резюме.................................................................................. 98

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

неограниченным числом приборов..................................................... 101

4.1. Численный анализ МАР-потока.................................................... 101

4.2. Имитационное моделирование систем массового обслуживания

с неограниченным числом приборов.............................................. 105

4.3. Алгоритм численного нахождения распределения

вероятностей числа событий выходящих потоков.............................. 107

4.4. Оценка точности результатов, полученных с помощью имитационного моделирования.................................................... 108

4.5. Оценка точности аппроксимации выходящих потоков

систем массового обслуживания с неограниченным числом приборов пуассоновским потоком.............................................................. 110

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

с неограниченным числом приборов............................................................................................115

4.7. Краткое описание комплекса проблемно-ориентированных программ численного анализа рассматриваемых моделей......................................117

4.8. Оценка области применимости асимптотических результатов..................119

Резюме......................................................................................................................................................................121

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

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

Введение

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

Возникла необходимость построения разнообразных моделей сложных систем, таких как научно-производственные объединения и крупные предприятия, транспортные системы, медицинские центры, информационно-телекоммуникационные и социально-экономические системы. При построении моделей процессов, происходящих в сложных системах, при описании их структуры, для оценки эффективности и оптимизации этих систем используются различные математические схемы. Однако исключительная роль при этом отводится различным типам систем массового обслуживания [14, 16, 22, 28, 31, 33,35,41,44, 70, 75,86, 88,91].

Становление теории массового обслуживания связывают с непрерывным расширением телефонных сетей в крупных городах Европы и Америки в начале XX века и необходимостью решения задач о задержке вызовов в этих системах.

Такие задачи были описаны еще в 1907 г. Ф.В. Иоханнсенном, а первые шаги по их решению предприняты в 1909 г. датским математиком А.К. Эрлан-гом, чьи работы стали ядром классической теории массового обслуживания.

В 1917 году А.К. Эрланг развил теорию телефонной связи и получил формулы для вероятностей различного числа обслуживаемых абонентов, распределение времени ожидания при равновесном состоянии системы и вероятности отказов для системы с потерями. Он опубликовал свои труды в 1917 году вначале на датском, а затем на английском, немецком и французском языках. Труды Эрланга послужили толчком для других работ в этом направлении. В данной области работали Фрай (1928), Молина (1927) и О'Делл (1920). Строгое научное описание случайных процессов в теории массового обслуживания и их исследование впервые было осуществлено А.Я. Хинчиным. Он исследовал од-

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

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

Большой вклад в развитие теории массового обслуживания внесли Ю.К. Беляев, A.A. Боровков, Б.В. Гнеденко, Дж.Р. Джексон, Ф. Келли, Дж. Кендалл, Дж.Ф.С. Кингмэн, Л. Клейнрок, Г.П. Климов, И.Н. Коваленко, С.Пальм, Ф. Поллачек, Т.Саати, А.Я. Хинчин и др. Краткий исторический очерк развития теории массового обслуживания содержится, например, в работах [22, 86].

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

Популярность этого потока долгое время объяснялась тем, что он вполне удовлетворительно описывал многие реальные потоки, а также простотой его исследования. В то же время было замечено, что простейший поток появляется и в качестве предельного для некоторых последовательностей потоков. В связи с этим, в середине XX века появился ряд работ, посвященных анализу сходимости суммы большого числа независимых потоков малой интенсивности к простейшему потоку. Среди них следует отметить работы Пальма [123], Реньи

[125], Г. А. Ососкова [78], Б.И. Григелиониса [25] и А .Я. Хинчина. Вопрос о скорости сходимости таких предельных сумм к потокам Пуассона рассматривался в работах [26, 81].

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

Таким образом, как для теоретических, так и для практических целей представляет интерес исследование условий возникновения пуассоновских потоков.

Исследованию рекуррентного потока также посвящено немало работ. Так, например, в книге Д. Кокса, В. Смита [40] подробно исследуется рекуррентный поток событий.

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

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

Потоки Кокса стали основой класса специальных или коррелированных потоков, наиболее популярным из которых является МАР-поток (Markovian Arrival Process). Впервые понятие МАР-потока было введено Ньютсом в 1979 году [121], а затем во время нового всплеска исследований уточнено Лукантони [116, 117]. Описание этого потока однородных событий можно найти в работах Б.В. Гнеденко, И.Н. Коваленко [22], А.Н. Дудина, В.И. Клименок [28], С.П.

Моисеевой, A.A. Назарова [73]. Так, например, в работах [11, 12, 13, 36, 71, 79, 95-97,109] рассматриваются системы, в которых на входе - МАР-поток. Непосредственно исследованию самого МАР-потока посвящены, например, работы [66, 67, 76, 93, 121].

В терминах различных математических школ МАР-потоки также называются дважды стохастическими потоками [23, 24, 111], которые были введены в 1964 году Кингменом [115]. В таких потоках, во-первых, интервалы времени между наступлениями событий являются случайными, во-вторых, с течением времени интенсивность потока меняется случайным образом.

Наиболее общим ординарным потоком однородных событий является полумарковский или SM-поток (Semi-Markovian process) [44]. Идея введения такого потока была выдвинута Леви (1954) и Смитом (1955). В книге Д. Кокса, В. Смита [41] наряду с исследованием простого процесса восстановления (рекуррентного потока) представлен альтернирующий процесс восстановления, модель которого может быть обобщена на случай полумарковского потока или его частного случая - потока марковского восстановления (Markovian renewal process). Системы массового обслуживания с таким входящим потоком интенсивно изучаются в настоящее время [80, 105]. Анализ распределения числа событий, наступивших в SM-потоке за некоторое время можно найти в работах [65, 77].

В книге [22] Б.В.Гнеденко, И.Н. Коваленко, изданной в 2007, классы MAP- и SM-потоков названы специальными потоками однородных событий. В монографии А.Н. Дудина и В.И. Клименок [28] специальные потоки названы коррелированными.

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

Описание первых подходов к анализу сетей массового обслуживания было дано в работах Дж. Джексона [107], Гордона и Ньюела. Однако эти работы

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

Дальнейшее расширение области применения теории сетей массового обслуживания связано с совершенствованием аппаратного и программного обеспечения вычислительных систем, а также с появлением сетей ЭВМ [29], представляющих собой совокупность территориально удаленных вычислительных систем, объединенных сетью передачи данных. Значительный вклад в развитие теории сетей массового обслуживания внесли Г.П. Башарин, A.A. Боровков, Э. Геленбе, Дж. Джексон, В.А. Ивницкий, Ф.П. Келли, Д. Кениг, JI. Клейнрок, Ю.В. Малинковский, М.А. Маталыцкий, П.К. Поллетт, Р. Серфозо, Г.И. Фалин и многие другие.

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

Первые попытки исследования выходящих потоков в рамках классической теории были сделаны во второй половине XX в. такими учеными, как П. Берк [100], Е. Рейч [106], П. Финч [124]. Независимо друг от друга они установили, что выходящий поток для системы с пуассоновским входящим потоком и экспоненциальным временем обслуживания также будет пуассоновским. А в 1963 году Н. Мирасол [119] показал, что выходящий поток систем с неограниченным числом приборов и произвольным распределением времени обслуживания, на вход которых поступает простейший поток, также является простейшим. Дальнейшее изучение выходящих потоков развивалось достаточно медленно, так как не было найдено общих методов и подходов по их исследованию. В [1] были получены асимптотические распределения вероятностей числа обслуженных заявок в смешанной системе М | G | 1 | m и системе М | М | m | т, обслуживающее устройство которой подвержено отказам. С помощью полу-

марковских процессов в [104] получены условия рекуррентности выходящих потоков однолинейных систем массового обслуживания. Обзор работ 50-х - 70-х годов по исследованию выходящих потоков содержится в работе [103]. Изучение свойств выходящих потоков продолжается и в настоящее время. В [110] было найдено распределение числа заявок, обслуженных за период занятости в стационарной системе Оеот | Оеот | 1 с дискретным временем. Анализу выходящих потоков в системах с циклическим обслуживанием посвящены работы исследователей из школы Нижегородского государственного университета (М.А. Федоткин, Е.В. Пройдакова) [82-84]. В работах американского ученого Д. Грина [99, 112] исследуется выходящий поток однолинейной системы с коррелированным входящим потоком. Анализ выходящих потоков 11С)-систем можно найти в [42, 54]Исследованию характеристик выходящих потоков различных систем массового обслуживания посвящены работы [2, 3, 7, 8, 30. 38, 42, 69, 87, 102, 108, 114, 122, 123, 127].

Настоящая диссертационная работа посвящена исследованию выходящих потоков систем массового обслуживания с неограниченным числом приборов (исследование самих систем можно найти в [20, 27, 98, 118]) и моделями коррелированных входящих потоков, что значительно расширяет и обобщает результаты, полученные для систем с пуассоновскими моделями входящих потоков. Также рассматриваются различные условия, при выполнении которых МАР-поток является пуассоновским. Заметим, что большая часть исследований ведется при помощи метода асимптотического анализа, различные модификации которого рассматриваются в [4, 5, 17, 42, 64, 72, 73].

Межпредметность рассматриваемых моделей. Исследуемые модели коррелированных потоков (класс МАР-потоков) являются обобщением простейших потоков, которые используются в качестве реальных потоков в различных предметных областях: потоки поступающих вызовов, потоки кл