Исследование математических моделей выходящих потоков систем массового обслуживания с неограниченным числом приборов тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Лапатин, Иван Леонидович

• Лапатин, Иван Леонидович
• кандидат физико-математических наук
• 2012

Оглавление диссертации кандидат физико-математических наук Лапатин, Иван Леонидович

Оглавление

Введение

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Резюме

Заключение

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

Введение диссертации (часть автореферата) на тему «Исследование математических моделей выходящих потоков систем массового обслуживания с неограниченным числом приборов»

Введение

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

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

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

учитывая различные его особенности. Это относится, например, к телекоммуникационным и транспортным потокам.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Связь работы с крупными научными программами и проектами.

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

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

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

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

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

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

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

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

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

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

7. Лапатин И.Л., Назаров А.А. Исследование выходящего потока системы 8М | 1 оо в условиях растущего времени обслуживания // Массовое обслуживание: потоки, системы, сети. Материалы международной научной кон-ференции"Современные математические методы анализа и оптимизации ин-

формационно - телекоммуникационных сетей"Минск, 26-29 января 2009г, С.175-179.

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

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

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

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

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

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

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

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

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

17. Лапатин И.Л., Лопухова С.В. Система MR.IR.loo в условии растущего времени обслуживания // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции" Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск: РИВШ, 2011. С.127-130.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Марковские входящие потоки рассматриваются в качестве существенного обобщения простейших потоков. Так, например, подбирая параметры MAP-

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

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

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

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

BE = кЕ, (1.13)

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

Здесь В - матрица с элементами Хк на главной диагонали и dvk-qvk вне главной диагонали, а Е - единичный вектор-столбец соответствующей размерности; к - интенсивность МАР-потока, определяемая формулой k=RBE, a R -стационарное распределение вероятностей управляющей цепи Маркова k{t).

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

RB = klR . (1.16)

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

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

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

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

Н(и,0) = R

(1.19)

где W(u,ty={H(\,uj), H(\,u,t),...}, H(k,u,t) = ^е]ипр(к,п,1), j = - мнимая

п=О

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

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

Тогда для вектор-функций F(u,t,S) можно записать 'dF(u,t,S). = ¥{UtttS)[s.Q(» +[eju

F(u,0,S) = R

dt

(1.22)

Теорема 1.3. Сумма компонентов предельного, при S —> оо, значения вектор-строки F(u,t) решения Г(u,t,S) задачи (1.22) имеет вид

F(m,0E = exp{(é> - l)tó}, (1.23)

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

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

дом состоянии стремятся к нулю) является асимптотически простейшим. При этом равномерный рост интенсивностей перехода управляющей цепи Маркова k{t) из одного состояния в другое не влияет на стационарное распределение состояний этой цепи и на интенсивность потока.

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

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

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

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

P(k,i,m,t) = P{k(t) = k,i(t) - i,m{t) = m} - распределение вероятностей трехмерной цепи Маркова.

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

(2.3)

где H{k,x,u,t) = j = 4-Т - мнимая единица, а

/ m

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

ц = 8, х-гу ,Н(х,и^) = ¥(у,и^,г), (2.8)

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

д¥(у,и^, е) ]и Чгу д¥(у,и,г, в)

--1- ](е е —1)-■ =

3? дх . (2.9)

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

¥{у,и,т = ехр[]ук + {е1и -\)к1\, (2.10)

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

к = ИВЕ, (2.11)

а вектор-строка И определяется системой

= о,

(2.12)

Б1Е = 1.

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

В разделе 2.5 исследуется система ММР | М | оо в условии предельно частых изменений состояний входящего потока. Зафиксируем некоторую матрицу инфинитезимальных характеристик 0(1), которая определяет управляющую цепь Маркова к{(), и матрицу Л. Затем, полагая, что £ некоторая положительная величина, в уравнении (2.3) сделаем следующие замены

0 = £ <2(1), Н(х,м,0 = ¥{х,и,1,8).

Тогда для вектор-функций ¥(х,и^,8) можно записать

д¥(х,и^,8) | . ^ р _ ЭБХад^) =

д1 дх . (2.27)

= ¥(х,и,1,

Теорема 2.4. Сумма компонентов предельного, при 5* —»• оо, значения вектор-строки ¥{х,и,()решения ¥{х,и,5) уравнения (2.27) имеет вид

¥(х,и,0Е = ехр|(б> -1)- + (е]и - 1)к/|, (2.31)

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

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

е = гt - т, вм? = и , еу = х, Н(х,и,/) = ^(2.38) для ¥\(у;иуи,е) получим дифференциально-матричное уравнение

+ _ цд^р^т.е) =

5т ду . (2.39)

= ^(у,VI/,т,+ (е^ - 1)В]

Теорема 2.6. Сумма компонентов предельного, при е—>0, значения вектор-строки Е^х^т)решения ¥\{х,м?,т,е)уравнения (2.39) приу=0 имеет вид

Е! (О, м?, х)Е = ехр^итст}, (2.40)

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

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

Щх,и^) = И2(х,и,1У'ш, тогда система относительно Н2(х,м,0

ЭН2(*,ц,0 + ,е]ие-]х _ ц дН2(х,ц,0 =

Ы Эх (2.44)

= Н2(х,м,о{о + (е]х - 1)В - ]ик1\

здесь I - единичная матрица соответствующей размерности. В уравнении (2.44) сделаем следующие замены

2 2

в = р,, в / = т, ем? = м , гу = = ¥2(у,, (2.45)

тогда для Г2(у,-и>,т,е) получим дифференциально-матричное уравнение

д¥2(у,м?,т,г) _

8" ___ + -1)-

дх ду

(2.46)

= ¥2(у,м;,т,8){д + - 1)В - уем^} Теорема 2.7. Сумма компонентов предельного, при е-+0, значения вектор-строки ¥2(х,м?,т)решения Р2(х,г,е)уравнения (2.46) приу=0 имеет вид

Е2(0,м;,т)Е = ехр-

кт + 2^ВЕт + 2Г2ВЕ(е""т -1

(2.47)

где Е — единичный вектор-столбец, величина к определяется равенством (2.11) и имеет смысл интенсивности входящего МАР-потока, вектор 12 решением системы

[£2О + К(В-к11) = 0

£2Е = 0

(2.48)

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

М{£>от(/)} = Н(0 ,м,0 Е « /нпст + ^¿(к + 2Г2ВЕ)т + -\)> = .

■ ехр<

(2.53)

= ехр

¡иШ +

О)

2 Г

(к + 2^ВЕ> + 2^ВЕ-

-1

I

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

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

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

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

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

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

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

со

Пусть 7i>0, 7>0 — некоторые заданные величины, а b= J(1 -B{x))dx -

о

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

= Г В{ЪТХ + T)-B(bTl-t + T), 0 <t< ътх

\B{bTx-t + T), bTx<t<bTx+T (ЗЛ)

Здесь S(t) - вероятность того, что заявка, поступившая в систему в момент времени t &[0,ЬТ{ +Г], завершит свое обслуживание в момент времени,

принадлежащий интервалу [ЬТг,ЬТ{ +Т].

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

заявка просеивается, то есть отправляется в просеянный поток, а с вероятностью 1-5(0 не рассматривается.

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

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

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

п{ЪТх +Т) = т{Т,ЪТ\), (3.2)

где т{Т,ЪТ{) - число событий выходящего потока рассматриваемой системы, наступивших на интервале [ЬТ{,ЬТ{ + Г].

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

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

Так как предлагаемый просеянный поток является марковизируемым, то, записав систему дифференциальных уравнений Колмогорова для многомерного распределения вероятностей и решая которое, получим одномерное маргинальное распределение вероятностей для числа событий наступивших в просеянном потоке за время А затем, применив равенство (3.2), найдем распределение вероятностей числа событий выходящего потока, наступивших в интервале \ЬТХ,ЬТХ +Т\ как в переходном режиме функционирования системы массового обслуживания при конечных Т\, так и в стационарном режиме, полагая 7^—ню.

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

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

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

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

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

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

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

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

пределений рассматривалось расстояние Колмогорова А, определяемое формулой

А = шах

п

(4.2)

п А

где - - допредельная функция распределения числа событий на-

1=0

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

п

^(и,/) = - функция распределения Пуассона, которая соответствует

1=0

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

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

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

А = шах

п

Е{п) - Р(п)

(4.4)

где Р{п) - эмпирическое распределение, полученное с помощью имитационного моделирования, Г{п) - асимптотическое распределение, которое находится

на основании результатов, полученных в первых трех главах.

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

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

интервала между моментами наступления событий во входящем потоке на по-

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Лапатин, Иван Леонидович

Основные результаты третьей главы были получены при решении дифференциально-матричных уравнений (3.5) и (3.7) методом асимптотического анализа.

В разделе 3.4 уравнение (3.5) решено в условии растущего времени обслуживания, то есть когда средняя длина времени обслуживания поступающих заявок Ъ стремится к бесконечности. Сформулирована и доказана теорема 3.1, которая говорит о том, что распределение числа событий выходящего потока системы MAP|GI|oo в условии растущего времени обслуживания является пуас-соновским. Причем интенсивность выходящего потока совпадает с интенсивностью входящего МАР-потока.

Уравнение (3.7) в условии растущего времени обслуживания решается в разделе 3.5. В теореме 3.2 доказано, что выходящий поток системы SM|GI|oo в условии растущего времени обслуживания является асимптотически пуассо-новским.

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

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

В пункте 3.6 выходящий поток системы MMP|GI|co рассматривался в условии предельно частых изменений входящего потока. Это условие подробно описано в первой главе. В результате было показано, что в условии предельно частых изменений состояний входящего потока число заявок, закончивших обслуживания в системе ММР|М|оо имеет распределение Пуассона с параметром к t.

Обобщение результатов раздела 3.6 на случай общего МАР-потока приведено в теореме 3.4 в пункте 3.7.

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

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

Глава 4

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

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

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

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

Некоторые результаты, представленные в четвертой главе, были опубликованы в работах [50, 53, 61].

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

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

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

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

Р(п, 0 = — {¿Г7'а?к((В - О - у'а1)4 в)" (В - О - уа1)4 Е

В качестве критерия «близости» распределений предлагается находить расстояние Колмогорова [43] А. Величина А определяется следующим образом

А = шах п Л

4.2) где = - допредельная функция распределения числа событий на

1=0 ступивших в потоке за время /, в которой Р(1/) полученэ с помощью формулы п

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

Оценка погрешности вычислений

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

1 0 0" -1,5 0,5 1 " "0 0 0"

Л = 0 1 0 ,0 = 0,3 -0,8 0,5 0 0 0

0 0 1 0,2 0,8 -1 0 0 0

Очевидно, что интенсивность такого потока равна 1. Расстояния Колмогорова, определенные формулой (4.2), для различных значений времени / приведены в таблице 4.1.

Заключение

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

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

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

Во второй главе исследовались выходящие потоки марковских систем массового обслуживания с неограниченным числом приборов методом асимптотического анализа. Было показано, что независимо от модели входящего потока (ММР, MAP, SM) в условии растущего времени обслуживания выходящий поток марковской системы с неограниченным числом приборов является асимптотически пуассоновским, причем интенсивности входящего и выходящего совпадают. Также было доказано, что в условии предельно частых изменений состояний входящего потока число заявок, закончивших обслуживания в системе ММР|М|оо имеет распределение Пуассона с параметром кt, а число занятых приборов в момент времени t также имеет распределение Пуассона с параметром к/|1. Данный результат обобщен на случай общего МАР-потока. В заключительной части главы приведено исследование выходящего потока системы МАР|М|оо в условии растущего времени наблюдения за потоком и получена гауссовскую аппроксимацию числа событий, наступивших в выходящем потоке за некоторое время t.

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

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

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

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

Выходящий поток системы массового обслуживания с неограниченным числом приборов можно аппроксимировать простейшим, если среднее значение времени обслуживания Ъ больше значения средней длины интервала между моментами наступления событий во входящем потоке на порядок (101) и более. При разнице порядка 10 ошибка аппроксимации менее 2%.

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

Список литературы диссертационного исследования кандидат физико-математических наук Лапатин, Иван Леонидович, 2012 год

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

1. Акулиничев Н.М., Горский JI.K. Об асимптотических распределениях выходящих потоков некоторых систем массового обслуживания // Кибернетика. 1973. №1. С. 71-78.

2. Александров A.M. О выходящих потоках некоторых систем массового обслуживания // Труды Ленинградского политехнического института. 1966. -Т.275.-С. 18-21

3. Александров A.M. О выходящих потоках одного класса систем массового обслуживания // Известия АН СССР. Техническая кибернетика. - 1968. -№4. -С. 3-11.

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

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

6. Баруча-Рид А.Т. Элементы теории марковских процессов и их приложения. - М.: Наука, 1969. - 511 с.

7. Бертсекас Д., Галагер Р. Сети передачи данных. - М.: Мир, 1989. -

544с.

8. Бокучаева И.Т., Донадзе Н.К., Гелдиашвили Н.И. О выходящем потоке системы с потерями // Сообщения АН Груз. ССР. - 1969. - №53. - С. 37-40.

9. Боровков A.A. Асимптотические методы в теории массового обслуживания. - М.: Наука, 1980. - 381 с.

10. Бородин А.Н. Элементарный курс теории вероятностей и математической статистики. 3-е изд. - СПб.: изд. «Лань», 2002. - 256 с.

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

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

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

14. Бочаров П.П., Печинкин A.B. Теория массового обслуживания. -М.: Изд-во РУДН, 1995. - 529 с.

15. Булинский A.B., Ширяев А.Н. Теория случайных процессов. - М.: ФИЗМАТЛИТ; Лаборатория Базовых знаний, 2003.-400 с.

16. Буримов А.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания: учебное пособие по спецкурсу. - Гродно, 1984.

17. Вавилов В.А. Исследование математических моделей сетей множественного доступа, функционирующих в случайной среде: Дис. ... канд. физ.-мат. наук. - Томск, 2006. - 158 с.

18. Вентцель Е.С. Теория вероятностей: учебник для вузов. 5-е изд. -М.: Высш. шк., 1998. - 576 с.

19. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. - М.: Наука, 1991.

20. Галажинская О. Бесконечно линейная бесконечно фазная СМО с произвольным распределением времени обслуживания на каждой фазе и прерыванием обслуживания // Математические методы повышения эффективности функционирования телекоммуникационных сетей: Материалы международной научной конференции. - Гродно, 2007. С. 58-61.

21. Гихман И.И., Скороход A.B. Теория случайных процессов. Т.1. -М.: Наука, 1971.-567 с.

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

23. Горцев A.M., Шмырин И.С. Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в измерениях моментов времени // Автоматика и телемеханика. - 1999. - № 1. - С. 52-66.

24. Горцев А., Нежельская Л. Полу синхронный дважды стохастический поток событий при продлевающемся мертвом времени // Математические методы повышения эффективности функционирования телекоммуникационных сетей: Материалы международной научной конференции. - Гродно, 2007. С. 68-78.

25. Григелионис Б.И. О точности приближения композиции процессов восстановления пуассоновским процессом // Литов. Мат. сб. 1962. Т.2 №.2. С. 135- 143.

26. Григелионис Б.И. Уточнение многомерной предельной теоремы о сходимости к закону Пуассона // Литов. Мат. сб. 1962. Т.2 №.2. С. 143 - 148.

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

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

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

30. Ивницкий В.А. О восстановлении характеристик системы с ограниченной очередью по наблюдениям над выходящим потоком // Труды I Всесоюзного симпозиума по статистическим наблюдениям в технической кибернетике. - М.: Наука, - 1968. - №3.

31. Ивченко Г.И., Каштанов, В.А., Коваленко И.Н. Теория массового обслуживания: учебное пособие для вузов. -М.: Высшая школа, 1982. - 256 с.

32. Карлин С. Основы теории случайных процессов. - М.: Мир, 1971. -

536 с.

33. Кёниг Д., Рыков В., Штойян Д. Теория массового обслуживания (основной курс: марковские модели, методы марковизации): учебное пособие

по математике для студентов специальности 0647 - прикладная математика.-М., 1979 г.

34. Кёниг Д., Штойян Д. Методы теории массового обслуживания. -М.: Радио и связь, 1981.

35. Клейнрок J1. Теория массового обслуживания. - М.: Машиностроение, 1979.-432 с.

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

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

38. Коваленко И.Н. О восстановлении характеристик системы по наблюдениям над выходящим потоком // Доклады АН СССР. - 1965. - т.164. №5. -С. 979-981.

39. Коваленко И.Н., Кузнецов Н.Ю., Шуренков В.М. Случайные процессы. - Киев: Наук, думка, 1983. - 366 с.

40. Кокс Д., Смит В. Теория восстановления. - М.: Сов. радио, 1967 -

298 с.

41. Кокс Д., Смит В. Теория очередей. - М.: изд. «МИР», 1966 -216 с.

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

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

44. Королюк B.C. Стохастические модели систем. - Киев: Наук, думка, 1989.-208 с.

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

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

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

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

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

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

51. Лапатин И.Л., Лопухова C.B. Система MR|M|oo в условии растущего времени обслуживания // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции"Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей". Минск: РИВШ, 2011. С.127- 130.

52. Лапатин И.Л., Назаров А.А. Асимптотический анализ выходящего потока системы MAP|GI|oo // Известия политехнического университета. Управление, вычислительная техника и информатика. 2009. Т. 315. №5. С. 191 - 194.

53.Лапатин И.Л., Назаров А.А. Асимптотически пуассоновские МАР-потоки // Вестник Томского государственного университета. Серия Управление, вычислительная техника и информатика. 2010. № 4(13). С. 72-78.

54. Лапатин И.Л., Лопухова C.B. Асимптотическое исследование потока обращений к прибору в марковской RQ-системе // Материалы XV Всероссийской научно-практической конференции «Научное творчество молодежи». Томск: Изд-во Том. ун-та, 2011. Ч. 1. С. 17-19.

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

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

57. Лапатин И.Л., Назаров А.А. Исследование выходящего потока системы SM | GI | оо в условиях растущего времени обслуживания // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции" Современные математические методы анализа и оптимизации информационно - телекоммуникационных сетей"Минск, 26-29 января 2009г, С.175-179.

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

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

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

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

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

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

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

65. Лопухова C.B. Исследование полумарковского потока асимптотическим методом третьего порядка // Информационные технологии и математическое моделирование: Материалы VI Международной научно-практической конференции. - Томск, 2007. - Ч. 2. - С. 30-34.

66. Лопухова C.B., Назаров A.A. Исследование МАР-потока методом асимптотического анализа N-ro порядка // Вестник ТГУ. Серия Информатика. Кибернетика. Математика. - 2006. - № 293. - С. 110-115.

67. Лопухова C.B., Назаров A.A. Численный алгоритм нахождения распределения вероятностей для МСМР-потока // Вестник ТГУ. Серия Информатика. Кибернетика. Математика. - 2006. - Приложение №16 - С. 113-119.

68. Лукач Е. Характеристические функции. - М.: Наука, Главная редакция физ. мат. лит., 1979. - 424 с.

69. Малинковский Ю.В. Выходные потоки в модифицированных сетях Джексона // Автоматика и телемеханика. - 1992. - №9. - С. 134-138.

70. Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. -М.: изд. МГУ, 1984.-240 с.

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

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

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

74. Назаров A.A., Терпугов А.Ф. Теория вероятностей и случайных процессов: учебное пособие. - Томск: изд. НТЛ, 2006. - 204 с.

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

76. Назаров A.A., Лопухова C.B. Исследование МАР-потока методом асимптотического анализа второго порядка // Проблемы кибернетики и информатики: Материалы международной конференции. - Баку, 2006. - Т. 1. -С. 201-204.

77. Назаров A.A., Лопухова C.B., Гарайшина И.Р. Исследование полумарковского потока событий // Вычислительные технологии, 2008. - Т 13. -Спецвыпуск 5. - С. 56-62.

78. Ососков Г.А. Одна предельная теорема для потоков однородных событий // Теория вероятностей и ее применение. 1956. Т.1. №.2. С. 274 - 282.

79. Печинкин A.B. Стационарные вероятности состояний в системе MAP/G/1/n с дисциплиной преимущественного разделения прибора // Вест. Росс, ун-та дружбы народов. Сер. Прикл. Матем. и информ. - 1998. - № 1. - С. 104-109.

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

81. Погожев И.Б. Оценка отклонения потока отказов в аппаратуре многофазового использования от пуассоновского потока // Кибернетику - на службу коммунизму. Т.2. М.¡Энергия, 1964. С. 228 - 245.

82. Пройдакова Е.В., Федоткин М.А. Определение условий существования стационарного распределения выходных потоков в системе с циклическим управлением // Вест. Нижегород. гос. ун-та им. Н.И. Лобачевского. Математика. 2006. Вып. 1 (4). С. 92-102.

83. Пройдакова Е.В., Федоткин М.А. Определение достаточного условия существования стационарного распределения выходных потоков в системе с циклическим управлением // Вест. Нижегород. гос. ун-та им. Н.И. Лобачевского. Математическое моделирование и оптимальное управление. 2006. Вып. 3 (32). С. 57-68.

84. Пройдакова Е.В., Федоткин М.А. Определение условий существования стационарного распределения выходных потоков в системе с циклическим управлением // Автоматика и телемеханика. 2008. №6. С. 96-106.

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

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

87. Симонова С.И. О выходящем потоке однолинейных систем обслуживания // Украинский математический журнал. - 1969. - Т.21. - №3. - С. 501— 510.

88. Скитович В.П. Элементы теории массового обслуживания. - Ленинград: изд. ЛГУ, 1976. - 95 с.

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

90. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. - М.: Наука, 1966. Т. 1. - 608 с.

91. Хинчин А .Я. Работы по математической теории массового обслуживания. - М.: Физматгиз, 1963. - 236 с.

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

93. Шмырин И. Оценивание состояний МАР-потока событий по критерию максимума апостериорной вероятности состояний // Современные математические методы анализа и оптимизации телекоммуникационных сетей: Материалы международной научной конференции. - Гомель, 2003. - С. 231-237.

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

95. Aguilera G., Bocharov P.P., Pechinkin A.V. Stationary state probabilities of a two-phase queueing system with a Markov Arrival Process and blocking // Proc. of the Fourth Internat. Workshop on Queueing Networks with Finite Capacity. - Ilk-ley, 2000.-P. 07/1-07/12.

96. Attahiru Sule Alfa, Chakravarthy S. A discrete queue with the Mark-ovian Arrival Process and phase type primary and secondary services // Stochastic Models. - 1994. - V. 10, №2. - P 437-451.

97. Aguilera G., Bocharov P.P., Pechinkin A.V. Stationary state probabilities of a two-phase queueing system with a Markov Arrival Process and internal losses // Proc. of the Fourth Internat. Workshop on Queueing Networks with Finite Capacity. - Ilkley, 2000. - P. 06/1-06/10.

98. Baum D. The Infinite Server Queue with Markov Additive Arrivals in Space // Proc. of the Int. Conf. «Probabilistic Analysis of Rare Events: Theory and Problems of Safety, Insurance and Ruin». Riga: RAU, 1999. P. 136-142.

99. Bean N.G., D.A. Green, P.G. Taylor The output process of an MMPP|M|1 queue // J. of Applied Probability. 1998. No. 35(4). P. 998-1002.

100. Burke P.J. The Output of Queueing Systems // Operations Research. 1956. V. 4. P. 699-704.

101. Cox D.R. The analysis of non-Markovian stochastic processes / Proc. Cambr. Phil. Soc. - 1955. - V. 51.-№3.-P. 433-441.

102. Dalay D.J. Notes on Queueing Output Procecces // Lect. Notes in Econ. And Math. Systems / Math. Models in Queueing Theory, ed. A.B. Clarke. - 1974. -V.8-P. 351 -358.

103. Dalay D.J. Queueing Output Procecces // Adv. Appl. Probab. - 1976. -V.8-P. 395-415.

104. Disney R.L., Farell R.L., de Morais P.R. Characterization of M|G|1 Queues with Renewal Departure Processes // Manag. Sci. 1973. V. 19. No. 11. P. 1222-1228.

105. Dudin A.N., Klimenok V.I., Kim C.S., Lee M.H. The SM/PH/N queueing system with broadcasting service // Proceedings of the 13th International conference on analytical and stochastic modeling techniques and applications. - Bonn, Germany, 2006.-P. 8-13.

106. Finch P.D. The Output Process of the Queueing System M|G|1 // J. Roy. Statist. Soc. 1959. V. 21. No. 2. P. 375-380.

107. Jackson J.R. Networks of Waiting Lines // Oper. Research. 1957. V. 5. No. 4 P. 518-521.

108. Jenkins J.H., On the correlation structure of the departure process of the M|E|1 queue // J. Roy.Statist. Soc. Ser. B. - 1966. - №28. - P. 336-344.

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

110. Goswami V. Distribution of the number of customs served during a busy period in a discrete time Geom|Geom|l // Indian J. Pure Appl. Math. 2002. V. 33. No. 9. P. 1405-1508.

111. Grandell J. Double stochastic Poisson processes. // Lect. Notes. Math., 1976.-V.529.

112. Green D. Departure Processes from MAP/PH/1 Queues. PhD thesis, Department of Applied Mathematics, University of Adelaide, 1999

113. Kendall D.G. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain// Ann. Math. Statist. 1953. V. 24 P. 338-354.

114. King R.A. The covariance structure of the departure process from M|G| 1 queues with finite waiting lines // J. Roy. Statist. Soc. Ser. - 1971. - №33. - P. 401406.

115. Kingman J. F.C. On doubly stochastic Poisson process / Proc. Cambr. Phil. Soc. - 1964. - V. 60. - №4. - P. 923-930.

116. Lucantoni D. New results for the single server queue with a batch Mark-ovian arrival process // Stochastic Models. 1991. - V. 7. - P. 1-46.

117. Lucantoni D.M., Meier-Hellsten K.S., Neuts M.F. A single-server queue with server vacations and a class of non-renewal arrival processes // Adv. Appl. Prob. - 1990. - №22. - P. 676-705.

118. Massey W.A., Whitt W. Networks of infinite-server queues with nonsta-tionary Poisson input // Queuing Syst. 1993. No. 13. P. 183-250.

119. Mirasol N.M. The output of an M | G | oo queueing system is Poisson // Operations Research. 1963. No. 11. P. 282-284.

120. Moor F.R. Computational Model of a Closed Queueing Network with Exponential Servers // IBM J. Res. and Dep. 1972. V. 16. No. 6. P. 567-573.

121. Neuts M.F. A versatile Markovian arrival process // Journal of Appl. Prob. 1979. - V. 16. - P. 764-779.

122. Pack C.D., The output of an M/D/l queue // Oper. Res. - 1975. - №23. -P. 750-760.

123. Palm. C. Intensitatsschwankungen in Fernsprechverkehr //Ericson Technics. 1943. V.44.№1. S. 1-189.

124. Reich E. Waiting Times When Queues are in Tandem // Ann. Math. Statist. 1957. V. 28. No. 3. P. 768.

125. Renyi A. Poisson-folyamat egy jemllemzëse // Тр. Мат. Ин-та АН Венгрии. 1956. Е.1. №4. С. 519 - 527.

126. Н. Saito, The departure process of an N|G|1 queue // Performance Evaluation. - 1990. - №11. - P. 241-251.

127. Yeh P., Chang J. Characterizing the departure process of a single server queue from the embedded Markov renewal process at departures // Queueing Systems. - 2000. - №35. - P.381-395