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

• Шкленник Мария Александровна
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Шкленник Мария Александровна

Введение

1 Метод производящей функции для исследования потоков в двухфазных системах М|М|да с мгновенной обратной связью

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

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

1.2.1 Исследование суммарного потока заявок в двухфазной СМО М\М\ю с мгновенной обратной связью

1.2.2 Исследование потока повторных обращений заявок в двухфазной СМО М\М\да с обратной связью

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

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

1.3 Исследование потока повторных обращений в двухфазной системе М\М\ю при нестационарном режиме работы

2 Метод предельной декомпозиции для исследования потоков в двухфазной системе М\01\^ с мгновенной обратной связью

2.1 Исследование потоков в двухфазной системе М\01\^ при стационарном режиме работы

2.1.1 Совместная производящая функция потоков в двухфазной СМО М\01\^ с мгновенной обратной связью

2.1.2 Исследование суммарного потока заявок в двухфазной СМО М\01\^ с мгновенной обратной связью

2.2 Исследование потока повторных обращений в двухфазной системе М\01\^ при нестационарном режиме работы

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

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

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

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

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

3.3 Исследование потока повторных обращений в двухфазной СМО М\01\^ с мгновенной обратной связью при нестационарном режиме

3.4 Асимптотический анализ потока повторных обращений в системе ММ|ю

3.5 Исследование потока повторных обращений в двухфазных СМО ММРР\01\ю и МАР\01\юс мгновенной обратной связью при нестационарном режиме

3.5.1 Асимптотический анализ первого порядка

3.5.2 Асимптотический анализ второго порядка

3.5.3 Исследование потока повторных обращений в двухфазной СМО МАР\01\ю с мгновенной обратной связью при нестационарном режиме

3.6 Исследование потока повторных обращений в двухфазной СМО 01\01\ю с мгновенной обратной связью при нестационарном режиме методом марковского суммирования

3.6.1 Асимптотический анализ первого порядка

3.6.2 Асимптотический анализ второго порядка

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

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

4.1.1 Построение распределения вероятностей числа событий в потоках в двухфазной системе М\М\^> с мгновенной обратной связью

4.1.2 Построение нестационарного распределения вероятностей числа событий в потоке повторных обращений в двухфазной системе М\01\ю с мгновенной обратной связью

4.1.3 Реализация алгоритма расчета параметров асимптотического распределения вероятностей числа заявок в потоке повторных обращений для СМО с непуассоновскими входящими потоками

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

4.3 Численный анализ точности аппроксимации для потока повторных обращений в двухфазной системе ММРР\01\ю с мгновенной обратной связью

4.4 Численный анализ точности аппроксимации для потока повторных обращений в системе 01\01\ю с мгновенной обратной связью

Заключение

Список литературы

157

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

Введение

Актуальность темы исследования и степень ее разработанности. Интерес к теории массового обслуживания как к математическому аппарату, позволяющему исследовать случайные процессы в различных системах, существенно вырос в последние десятилетия. Это связано с развитием систем коммуникаций, возникновением сложных и многоуровневых информационно-вычислительных систем, созданием автоматизированных систем управления практически во всех областях промышленности и жизнедеятельности. В качестве математических моделей используются, как правило, многолинейные системы массового обслуживания (СМО) [55, 56], в том числе системы с неограниченным числом приборов [1, 9, 99], а также системы с повторными вызовами или RQ-системы (Retrial Queueing System) [81, 94].

Системы массового обслуживания с неограниченным числом обслуживающих устройств уже с конца двадцатого века широко применяются при решении прикладных задач как математические модели распределенных вычислительных и информационных систем [45, 80, 86, 93], а также при моделировании в демографических и социально-экономических исследованиях [2, 3, 51], страховых организаций и торговых компаний [15, 18, 43]. В частности, СМО с неограниченным числом приборов успешно аппроксимируют многолинейные системы при условии, что вероятность отказа в обслуживании заявки пренебрежимо мала. Это показали в своих работах А. Пухальский, А. Мандельбаум, Д. Рид. [100, 101, 107, 108].

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

системы с отсроченной обратной связью [14, 26, 28]. Одним из первых исследованию систем с обратной связью свои работы посвятил Л. Такач [113, 115]. Впоследствии несколько десятилетий исследователи не проявляли интерес к таким системам, и лишь в последние пару десятков лет с развитием теории массового обслуживания в целом системы с обратной связью снова привлекли к себе внимание.

Для марковских систем с большим числом обслуживающих приборов большинство задач было решено еще в первой половине XX века. Показано, что число занятых приборов в системе М\М\ю имеет распределение по закону Пуассона [24, 25]. Исследование потоков заявок в системах с неограниченным числом приборов, простейшим входящим потоком и мгновенной обратной связью выполнено в работах [38, 41]. Полученные уравнения решаются аналитически методом производящей или характеристической функции.

Системы с произвольной функцией распределения времени обслуживания исследовались Б. А. Севастьяновым [58 - 60], который решил задачу Эрланга для системы М\0\Ы и показал, что при И^ю распределение заявок в системе сходится к пуассоновскому. Л. Такач [114] показал, что при стационарном режиме работы количество заявок в системе М\0\ю имеет распределение Пуассона, параметр которого зависит от средней скорости поступления заявок и среднего времени обслуживания вызовов. Потоки заявок в системах с обратной связью с произвольным временем обслуживания и входящим пуассоновским потоком исследованы работах [1, 45]. Для исследования таких систем предлагается метод предельной декомпозиции, согласно которому исследование системы массового обслуживания с неограниченным числом приборов сводится к исследованию совокупности однолинейных систем. К сожалению, область применения этого метода ограничивается только системами с простейшим входящим потоком заявок.

Основой исследования немарковских СМО являются классические методы марковизации процессов обслуживания [9, 23]. Первым еще в 1932 г. появился метод вложенных цепей Маркова (А.Я. Хинчин [61, 62], Д. Кендалл [97]). Однако он позволяет находить характеристики системы лишь в специальные моменты

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

Аналитический вид решения конкретных задач во многих случаях получить довольно непросто, а в некоторых случаях невозможно. В таких случаях применяют асимптотические методы [31, 40, 48], которые дают результат, приемлемый для применения на практике при определенных ограничениях. А. А. Боровковым [6] было предложено исследование систем массового обслуживания, когда в случайных процессах, описывающих состояние системы, выполняется предельный переход при определенных асимптотических условиях. Также широкое применение при исследовании систем массового обслуживания различных конфигураций нашел метод асимптотического анализа, предложенный А. А. Назаровым [48]. Применение данного метода к СМО различных конфигураций изложено в работах С. В. Лопуховой [31], С.П. Моисеевой [40], А. Н. Моисеева [35], Л. А. Жидковой [16, 19], Е. Ю. Лисовской [29].

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

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

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

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

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

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

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

- провести исследование потоков заявок в двухфазных марковских системах вида ММ™ с обратной связью при стационарном и нестационарном режиме работы системы;

- разработать модификацию метода предельной декомпозиции для исследования потоков в двухфазных системах М\01\^ с обратной связью при стационарном и нестационарном режиме работы системы; используя разработанную модификацию, исследовать потоки заявок в соответствующей системе;

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

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

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

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

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

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

3) получены выражения для производящих функций распределения вероятностей числа событий в потоках заявок в двухфазной системе вида М\01\ю с мгновенной обратной связью при стационарном и нестационарном режиме работы;

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

5) получены выражения для асимптотической характеристической функции распределения вероятностей числа событий в потоке повторных обращений в системах ММРР\01\ю, МЛР\01\ю, 01\01\ю при нестационарном режиме работы в условии высокой интенсивности входящего потока.

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

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

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

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

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

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

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

2. Модификация метода предельной декомпозиции для исследования потоков в двухфазной системе вида М\01\^ при стационарном и нестационарном режимах работы.

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

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

5. Теоремы о виде асимптотической характеристической функции распределения вероятностей числа событий в потоке повторных обращений в системах ММРР\01\ю, МЛР\01\ю, G/\G/\да при нестационарном режиме работы в условии высокой интенсивности входящего потока.

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

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

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

Публикации. По материалам диссертации опубликовано 20 работ, в том числе 5 статей в журналах, включенных в Перечень рецензируемых научных изданий, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени кандидата наук, на соискание ученой степени доктора наук (из них 1 статья в зарубежном научном журнале, входящем в Scopus, 1 статья в российском научном журнале, переводная версия которого входит в Web of Science, 3 статьи в российских научных журналах, входящих в Web of Science), 2 статьи в сборниках материалов конференций, представленных в изданиях, входящих в Scopus, 13 публикаций в сборниках материалов международных и всероссийской с международным участием конференций и чтений.

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

1. Двенадцатая Международная азиатская школа-семинар «Проблемы оптимизации сложных систем», г. Новосибирск, 2016 г.

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

3. V Всероссийская молодежная научная конференция с международным участием «Математическое и программное обеспечение информационных, технических и экономических систем», г. Томск, 2017 г.

4. XX Международная научная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь фССК)», г. Москва, 2017 г.

5. XVI Международная конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование», г. Казань,

2017 г.

6. XXI Международная научная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь фССК)», г. Москва, 2018 г.

7. XVII Международная конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование», г. Томск,

2018 г.

8. XVIII Международная конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование», г. Саратов,

2019 г.

9. XIX Международная конференция имени А. Ф. Терпугова «Информационные технологии и математическое моделирование», г. Томск,

2020 г.

10. 24-я Международная научная конференция «Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связь фССК)», г. Москва, 2021 г.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы. Общий объем диссертации составляет 171 страница; иллюстративный материал представлен 17 рисунками и 4 таблицами; список литературы содержит 119 наименований.

В Главе 1 исследуются потоки заявок в двухфазной системе М\М\ю с мгновенной обратной связью. Для исследования потоков в системе предлагается метод производящей функции.

В Главе 2 исследуются потоки заявок в двухфазной системе М\01\^ с мгновенной обратной связью. Для исследования потоков предлагается модификация метода предельной декомпозиции.

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

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

1 Метод производящей функции для исследования потоков в двухфазных системах М\М\го с мгновенной обратной связью

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

Несмотря на то, что огромное количество задач для марковских систем с большим или неограниченным числом приборов решено, интерес к таким системам не пропадает. С развитием теории телекоммуникационных сетей растет потребность в построении новых математических моделей систем массового обслуживания, учитывающих все больше параметров. В частности, СМО с обратной связью позволяют адекватно описывать процессы дополнительного обслуживания в коммуникационных системах, а также могут применяться при описании процессов в социальной и экономической сфере [39, 43, 47]. Исследование потоков заявок в марковских СМО с обратной связью проводилось в работах А. С. Морозовой, С. П. Моисеевой, А. А. Назарова [37, 38, 41, 42].

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

Гетерогенная СМО с обратной связью

Входящий поток заявок

г.

£1«

В2(х)

В2(х)

1 - Г1

Двухфазная СМО с обратной связью 1 - Г1

1 - Г0

1 - Г0

Рисунок 1.1 - СМО с мгновенной обратной связью и различным обслуживанием

первичных и повторных заявок

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

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

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

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

Рисунок 1.2 - Двухфазная СМО М|М|да с обратной связью

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

• I(?) - число обращений к системе заявок из внешнего источника за время ?;

• п1(?) - число повторных обращений после обслуживания на первой фазе системы за время ?;

• п2(?) - число повторных обращений после обслуживания на второй фазе системы за время ?;

• п(?) = п1(?) + п2(?) - суммарное число повторных обращений к системе за время ?;

• s(t) = /(?) + п(?) - суммарное число обращений к системе за время ?.

Рассмотрим следующие потоки требований в системе: поток повторных обращений к первой фазе системы (считающий процесс п1(?)), поток повторных обращений ко второй фазе (считающий процесс п2(?)), суммарный поток повторных обращений (считающий процесс п(?)), суммарный поток обращений в системе (считающий процесс £(?)).

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

1.2 Исследование потоков в двухфазной системе массового обслуживания М\М\х> с мгновенной обратной связью при стационарном режиме работы

1.2.1 Исследование суммарного потока заявок в двухфазной СМО М|М|го с

мгновенной обратной связью

Найдем производящую функцию суммарного числа заявок, обратившихся к системе за время ?, то есть производящую функцию процесса {^ (?)}.

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

Обозначим число приборов системы, занятых обслуживанием поступивших из внешнего источника заявок, в момент времени ? через /1(?); число приборов системы, занятых обслуживанием повторных заявок, в момент времени ? через ¿2(?); распределение вероятностей числа заявок в рассматриваемой системе через

Р(\, /2, *) = Р (*) = \, /2 (*) = /2}. Будем считать, что в начальный момент система

Г1, если ^ = /2 = 0, пуста, то есть Р(1Х, /2,0) = <

[0, иначе.

Докажем следующую лемму.

Лемма 1.1 Производящая функция ^хь х2) двумерного процесса {^(0, ¿2(0} числа заявок в системе М\М\ж с мгновенной обратной связью в стационарном режиме имеет вид

g(Xl,х2) = ехр] — (х1 -1)+ ^Г (X -1) I. (1.1)

[ Ц Ц 2 (1 - Г2 ) ]

Доказательство. Прямая система дифференциальных уравнений Колмогорова [57] для Р(г1, /2, *) имеет вид

Список литературы диссертационного исследования кандидат наук Шкленник Мария Александровна, 2022 год

используя

разложения

1

еуще = 1 + уще +1 (уще)2 + о(е2)

2

ф(щ, е, г) = а0 (г) + а (г) ■ уще + о(е), получим

^ дф 2(щ г) [г + g ■ уще^(г )]е + Ф2 (щ, г )[г + g ■ ущеу(г)] ущеЩ )е = дг

и

I Г 1

Ф2 (щ г) [г + g ■ ущеу(г)] < Ое+ гх уще + - (у ще)2 + о(б2 )

V 2

В(Т - г) +

+г

1 \

1 + уще + -(уще)2 + о(е2) (ао(г) + а:(г) ■ уще + о(е))

2 у

Ле ^ + о(е 2).

Так как гО = 0, ге = 1, гЛе = X, то разделив на е2 и выполнив предельный переход при е ^ 0, для функции Ф2(^,?) получим дифференциальное уравнение

дФ 2(щ, г) = ф

дг :

(щ, г)

(М 2

[гХу(г) + 2гхг^к (а0 (г) + а (г)) + 2г& (Л - XI) е у2 (г)

решение которого с учетом начального условия имеет вид

Ф2( ж, г) = ехр-

(

г1Х}[|(х) + 2г2 ( а0 (х) + а1(х) )] Сх

+

Обозначим

+2г^ (Л -Я1) е 112 (х)Сх о

к = 2g (Л - XI) е.

Тогда выражение (3.803.803.80) можно переписать в виде

Ф 2(ж, г) = ехр-

(М2

г1А|Ц\|/(х) + 2г2 ( а0 (х) + а (х) )] Сх + г к {\|/2 (х)йХ

Подставив это выражение в (3.78), получим вид асимптотического решения задачи Коши (3.76), (3.77)

^ (ж, г) = Нш^ (ж, г, е) = г ехр { (

е ^о I 2

Г X {[|( х) + 2т2 ( а0 ( х) + а (х) )] Сх

+

+г1к} |2 ( х)Сх о

Итак, вектор-строка частичных характеристических функций числа событий, наступивших в г-потоке

+ О*- r1N 2 1

Ь(ы, г) = г ехр { г 11(х)Сх +

о

/ г

X| |(х) + 2г2 (а0(х) + а1(х))! Сх + к ||2(х)Сх

Умножим обе части этого равенства на е. Тогда, возвращаясь к исследуемому процессу числа повторных обращений в системе {п(г)}, подставим г = Т и получим выражение для характеристической функции Н(и) числа повторных обращений к системе в асимптотическом условии высокой интенсивности входящего потока.

г

+

(м

2

Н(и,Т) «ехр ^ уиЩХг11 у(х)йх +

о

гхХЫ 1| у( х) + 2г2 (а0 (х) + а (х))] йх + гЩкI у2 (х)йх

Подставив сюда выражения (3.69), (3.70) и (3.72), определяющие вид функций, а0(х), а1(х) и у(х) получаем выражение для характеристической функции в виде

Н (и,Т)« ехр

]иЩгх Х

+да 7 *

Iв(у*»+^ I Ь11(а)ь*(*;)л

0 уа (1 - гЬ* (а))

Т -

1 - е

уа

йа

+

+^ щ

+да

ХIВ(у)йу + Х^ I

Ь*(а)Ь (а) (3 - гЬ* (а))

уа (1 - г2Ь2(а))

Т -

1 - е

- уаТ

уа

йа +

Т

+да 7*/ \ 7 * / \ ^ ^ _ - уау Л

+ кI В:(у) + ^ 1

01 2п1(1 - а))

уа

йа

йу

что совпадает с выражением (3.64). Теорема доказана.

Таким образом, при достаточно больших значениях N распределение числа событий в потоке повторных обращений за интервал времени [0, Т] аппроксимируется нормальным распределением с математическим ожиданием

М {п(Т)} = ИгхХ

+да

N у)йу+^

0 2л-да уа(1 - ^(а))

Т

1 - е

~]аТ

уа

й а

(3.81)

и дисперсией

Б{п(Т)} = Щ

Т

+да ,

х1 в (у)йу1 Ь'(аЬ'(а) (3 - ^)

0 2^-да уа(1 - ^(а))

\ 1 - е-уаТ V уа

й а +

<

Т

2

+Kr s,(y)+r. T 5(a)b2(a)

J0v 1(У) - ^(a))

Л1 - e" Jay Л Ja

d a

dy

(3.82)

3.5.3 Исследование потока повторных обращений в двухфазной СМО MAP\GI\да с мгновенной обратной связью при нестационарном режиме

Аналогично теореме 3.3, сформулируем следующую теорему для системы, на вход которой поступает МАР-поток заявок, определяющийся следующим образом: пусть имеется цепь Маркова k(t) с конечным числом состояний, k(t) = 1, 2, ... , K, определяемая матрицей инфинитезимальных характеристик Q = \\qVk\\, k, v е {1, 2, ... ,K}; пусть заданы неотрицательные величины Х1, X2, ..., XK, определяющие условные интенсивности наступления событий в МАР-потоке для каждого состояния цепи k(t), а также совокупность условных вероятностей dkv того, что в потоке наступает событие в момент, когда цепь k(t) меняет свое состояние с k на v (предполагается, что k Ф v и dkk = 0). Цепь k(t) называется управляющей цепью Маркова для рассматриваемого МАР-потока. Обозначим диагональную матрицу условных интенсивностей Л = diag(X1,.,XK) и матрицу вероятностей наступления событий в момент смены состояния управляющей цепи Маркова D = \\dvk||, причем все dkk = 0. Тогда входящий МАР-поток полностью определяется матрицами Q, Л и D.

Теорема 3.4 Пусть r = [r(1), r(2),...,r(^)j - вектор-строка стационарного распределения вероятностей состояний цепи Маркова k(t), определяемый

ire = 1

решением системы уравнений \ , вектор-строка g удовлетворяет

[rQ = 0

матричному уравнению g • Q = r [r - r (Л + DQ)], а X = г(Л + DQ)e. Тогда асимптотическая характеристическая функция распределения числа событий в потоке повторных обращений за интервал времени [0; T] H(u,T) = M jeJun(T)| при условии высокой интенсивности входящего потока, имеет вид

йа +

л2

(3.83)

где

к =

2g (Л + DQ - XI) е.

Доказательство этой теоремы аналогично доказательству теоремы 3.3 и приведено в работе [76].

Таким образом, распределение числа событий в потоке повторных обращений за интервал времени [0, Т] в системе МАР^Цю при достаточно больших значениях N также аппроксимируется нормальным распределением с математическим ожиданием и дисперсией, которые могут быть вычислены по формулам (3.81), (3.82) с соответствующими значениями X и к из теоремы 3.4.

Алгоритм расчета параметров распределения (3.81) и (3.82), реализованный в пакете программ MathCaD, представлен в главе 4.

3.6 Исследование потока повторных обращений в двухфазной СМО С7|б7|го с мгновенной обратной связью при нестационарном режиме методом

марковского суммирования

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

X = --1-. (3.84)

| [1 - А( г )]сЪ

Дисциплина обслуживания описана в разделе 3.4.

Обозначим г(1) - остаточное время от момента г до момента наступления следующего события в исходном рекуррентном потоке, п(0 - число событий г-потока, сформированных всеми заявками входящего потока, поступившими в систему на интервале [0, Обозначим вероятность того, что к моменту времени г в г-потоке произошло п событий и при этом г(1) < г:

Р(п, г, г) = Р{п(г) = п, г(г) < г} . Также введем следующие обозначения:

• - число событий в г-потоке, сформированных за интервал времени [I, Т] одной заявкой, пришедшей в момент времени

• g(i, = Р{£(0 = ¿} - вероятность того, что заявка, поступившая в систему в момент времени I, к моменту времени Т сформирует в г-потоке i событий.

Тогда по формуле полной вероятности можно записать следующее равенство:

п

Р(п, г, г + А) = Р(п, г + Аг, г) - Р(п, А, г) + А( г) X Р(п - /, А, г) g (/, г) + о( А).

г=0

При А( ^ 0 получим дифференциальное уравнение Колмогорова для распределения вероятностей Р(п, г,

ЗР(п, г, г) _ ЗР(п, г, г) ЗР(п, 0, г^ сР(п - ¿,0, г)

Зг & & ¿=о &

с начальным условием

ГЯ(г), п = 0, Р(п, г,0) = <! ^

[0, п > 0,

где ^(г) - распределение вероятностей значений случайного процесса г(1) в стационарном режиме.

Определим характеристические функции вида

0

Н(и,z,г) = I ejmP(n, z, t)

п=0

в{и, г) =1 е-^'я (', г)

г=0

и запишем дифференциальное уравнение для характеристической функции исследуемого процесса п(г)

Ы дг дг У Х ' Х ' }

Характеристическая функция 0(ы, г) процесса найдена в работе и имеет вид (3.15). Тогда получаем уравнение вида

дН (и, г, г) дН (и, г, г)

дг

дг

+

дН (и,0, г)

дг

А(г) -1 + А(2)гх(е]и -1) (Т - г) + т2е]иф(и,г))

(3.85)

с начальным условием

Н (и, г,0) = г)

(3.86)

Решение задачи (3.85), (3.86) будем искать методом асимптотического анализа при условии высокой интенсивности входящего потока. Для этого запишем функцию распределения длин интервалов времени между событиями входящего потока в виде Л(Ы£), где N > 0 - параметр высокой интенсивности потока.

Тогда, выполнив соответствующие преобразования, уравнение (3.85) можем переписать в виде

1 дН (и, г, г) дН (и, г, г)

N дг

дг

дН (и,0, г) дг

А(г) -1 + А(2)гх(е]и -1) (Т - г) + т2е]иф(иг))

(3.87)

Теорема 3.5 Пусть параметр X входящего рекуррентного потока определяется выражением (3.84), а случайная величина с функцией распределения А(х) имеет конечные математическое ожидание а и дисперсию о2. Тогда асимптотическая характеристическая функция распределения числа событий в

потоке повторных обращений за интервал времени [0; Т Н(и,Т) = М{е]ип(Т)} при

условии высокой интенсивности входящего потока, имеет вид

Н (и,Т)« ехр

]иЫгх X

7 *

IУК + ^ I . *(а»(?)

0 2п -1 ]а (1 - г2Ь2 (а))

Т -

1 - е

-]аТ

]а

Ла

+

+М

Т

XI В1(у)йу + X ^ I

¡*(а)Ь2(а) (3 - г2ь2 (а))

]а (1 - г2Ь2 (а))

Т

1 - е~]аТ

]а

Ла +

Т

+ к Г В1(у) + ? ¡1*(а)Ь^(а)

- е~]ауЛ

а

2

Ла

Лу

(3.88)

где

к = г1Х3 (а2 - а2

(3.89)

Доказательство теоремы будем проводить, используя метод асимптотического анализа [48].

3.6.1 Асимптотический анализ первого порядка

Используя метод асимптотического анализа, выполним замены [48] 1

— = е, и = еw, Н(и, г) = г, е), тогда уравнение (3.87) можно переписать в виде

& дг дг [

<

+ А(г)гх(ем-1)(В1(Т - г) + г2емф(м,г,е))]. (3.90)

Пусть существуют пределы Нш F1 (■м, г, г, е) = F1 (м, г, г),

е

^ д/^(м,г,г,е) _ д¥х(м,г,г)Щ^гЛе) = д2,1)

е^о дг дг ' е^о дг дг

1. В уравнении (3.90) выполним предельный переход е ^ 0, получим

о=авсмгО + аЩмМ г А( г) -11

дг дг

Следовательно, асимптотическое решение уравнения будет иметь вид

В(м, г, г) = Я(г)Ф1, г), (3.91)

где Ф1(^, г) - некоторая скалярная функция.

2. Выполним в (3.90) предельный переход г ^ да, получим

е ^г,е) = ^ (М'°'г'Е) «е* -1)(В(Т - г) + г2еМф(м,г,е)). дг дг ^ '

Подставим сюда выражение (3.91) и воспользуемся разложением в ряд экспоненты и функции ф(^, г, е), тогда

д

е-(ВДФ^мг)) = г [В1(Т - г) + г («о(г) + а (г) • jwе + ф))(1 + ]м>е + ф))] х

я

х( >е + о(е) )-( ОДФ^, *)),

где а0(г) и а1(г) определяются выражениями (3.69) и (3.70).

Разделим обе части равенства на е и произведем предельный переход е ^ 0. С учетом того, что Я'(О) = Л [103], получаем дифференциальное уравнение относительно функции Ф1(^, ¿):

^^г) = ъУмФ:(м,г)(В(Т - г) + т2ао(г)). дг

Учитывая обозначение (3.72), решим это уравнение при начальном условии Ф1(^, 0) = 1. Получим

(w, t) = exp <j jwrlX j x)dx f-.

(3.92)

Подставив в (3.92) выражения (3.69), (3.72) и выполнив несложные преобразования, выражение для функции Ф1(^,г) можно представить в виде

Ф^, t) = exp

j'wAiX

+ад

* , ч , *

г ЙЛЛД;, '2 г bi (a)b2(а)

J Bi(y)dy + — J —1-2*7~\

t-t ja (1 - (а))

( e~ jaT - g- ja(T-t) >\

t +-

ja

da

Следовательно, асимптотическое решение F (w, z, t) = lim F (w, z, t, e) задачи (3.90) имеет вид

F (w, z, t) = R(z)exp < jw'X

T

j Bi(y)dy +

t-t

+ад b* (a)b-* (a)

-ад ja (l - '2b* (a))

( e~ jaT - e~ja(T-t) Л

t +-

ja

da

(3.93)

3.6.2 Асимптотический анализ второго порядка

В уравнении (3.87) выполним замену [48]

H (u, z, t) = H2(u, z, t )exp

t

juNrY X j x)dx

(3.94)

получим уравнение относительно функции H2(u, z, t):

1 öH2(u, z, t) . . . . . . öH2(u, z, t) 2 + juXr1H2 (u, z, t )y(t) = —2 7 +

N öt

öz

öH2 (u,0, t)

öz

^(z) -1 + Дz)r (eju -1)(B1(T -1) + r2ej>(u,t))

Выполним здесь замены [48]

1 2

— = е , и = ем, Н(и,г,г) = г,г,е);

получим уравнение

2 г, г, е) . л л ддм, г, г,е)

е2 2 ' + ./ем^ ( м, г, г, е)¥(г) = 2 ' " ' +

дг дг

+д^2(м,0, г, е)

дг

А(г) -1 + А(г)(е7ем -1)(В1(Т - г) + г2е7е>(м,г,е))]. (3.95)

Пусть существуют пределы Иш В (м, г, г, е) = В (м, г, г),

2 2

Ит дЩж^ = дВ(м г р г t,е) = дв(м г г)

дг дг ' е^о дг дг

1. Положим в (3.95) е ^ 0, получим

+ дВ2(мДг) г А( г) -11= о.

дг дг

Следовательно, асимптотическое решение уравнения г, г) будет иметь вид

В 2, г, г) = Я( г) Ф 2(м, г),

где Ф2(^, г) - некоторая функция, не зависящая от г.

2. Решение уравнения (3.95) запишем в виде разложения

г, г, е) = Ф 2(м, г) [ Я( г) + 7ем )/(г) ] + о (е), (3.96)

где Д(£) - некоторая функция. Подставим это выражение в (3.95). Используя разложения е= 1 + jwе + о(е) и ф( м, е, г) = а0 (г) + ах (г) • 7Ме + о(е), где коэффициенты а0(г) и а1(г) определяются выражениями (3.69) и (3.70) соответственно, получим

]емАгх )Ф2 (м, г ) Я( г) = Ф2 (м, г ){Я'( г ) + jеwf'( ) + Я'(°) [ А( г) -1] + +Я (О) Ум А( г )у(г) + уем/' (°)у(г) [ А( г) -1]} + о ( е ). В [103] показано, что

Я' (г) = Я' (О) [1 - А( г)],

тогда, приведя подобные и сократив обе части на jеw, получим ЦЯ(г) = /'(г) + /'(0) [ А(г) -1] + ЦА(г) + о(е).

Отсюда при е ^ 0 получаем дифференциальное уравнение относительно неизвестной функции /(г)

/'(г) = /'(0) [1 - А(г)] + ХГ1 [А(г) - Я(г)]. Проинтегрируем обе части этого уравнения по г от 0 до да, получим:

f (ад) - f (0) = f' (0) • 1 - X'i

Решение этого уравнения дает

j[l - R(z)]dz -j[l - A(z)]dz

V о

f' (0) - Xf (ад) =

к 2

(3.97)

где к определяется выражением (3.89) [103].

3. В уравнении (3.95) выполним предельный переход при z ^ да. В силу способа построения функции F2(w, z, t, s) она является монотонно неубывающей и ограниченной сверху функцией по z. Следовательно,

lim S^CwzM = 0.

Учитывая это \2

z^ад

и

dz

применяя

разложение

экспоненты

e = 1 + jew -

(j e w)2 2

о (e2) и функции 9(w, s,t) = a(t) + a(t) • jws + o(s), получаем

2 öF (w, ад, t, s) . , , ч „ , N öF (w,0, t, s)

s2—2 ' ' J + jswXr^t)F2(w, ад, t, s) = - 2 ' ' ' y

д t

öz

jswr^t) +

+

( j sw)2 2

1 (y(t) + 2r2Ü0(t) + 2^1(0 ) + о (s2 )

Подставим сюда разложение (3.96), при z ^ да получим

5Ф2(W, t)

+ (jew)2 Xrw2(t)f (^(w, t) =

dt

= Ф 2 (w, t) ^ ri [x(l(t) + 2Г2 [ a0(t) + ax(t)]) + 2| 2(t )f' (0) ] + о (e 2 2

2

Приведем подобные и сократим на e2, тогда

d^ (w, t) ( jw)

dt

2

r^(w, t) [(f) + 2r2 [ao(t) + ai(t)]) + 2|2(0 (f (0) - Xf («) )] ■

+O(e).

Учитывая (3.97) и переходя к пределу при е ^ 0, получим дифференциальное уравнение относительно неизвестной функции Ф2 (м, г)

dФ2(w, t) _ ( jw)2

dt

2

Ф22, t )r [x(|(i) + 2r2 [ao(t) + aiO)]) + |2(0к

Решение этого уравнения с учетом начального условия Ф2(^, 0) = 1 имеет вид

Ф22, t) = exp

Тогда получаем

F (w, z, t) = R( z)exp

(jw)7

t t Xj |(x) + 2r2 (a0 (x) + a (x))] dx + k|i|/2(x)dx

(jw)7

t t Xj |(x) + 2r2 (a0 (x) + a (x))] dx + к||2(x)dx

Подставив сюда выражения (3.69), (3.70), (3.72) для функций a0(x), a1(x) и y(x) и выполнив несложные преобразования, получаем асимптотическое решение F2( w, z, t) = lim F2(w, z, t, в) уравнения (3.95)

e ^0

F (w, z, t) = R( z)exp

(jw)2 2

X j Bi(y)dy

+

t-t

3r2 7 b*(a)b2*(a)

+X 3Г2 j —bp 2я j ;a(i

ja(i - r2b2(a))

f e-ja(T-t) _ jaT ^ t--

V

ja

da +

У

Xr22 +ад b*(a)

+-

/ , *

J

ж ' ia

-ад

b2(a)

1 - ^(a)

e- ja(T-t) - e~j'aT л

ja

da +

+ Kf B1(y) + ^ ?b1*(a)b2(a)

tL ^^^ 2"i(1-rb*(a))

r\ - e- jay Л ja

d a

dy

(3.98)

Вернемся к характеристической функции Я(и, г, г) исследуемого процесса. Выполним обратные замены и получим аппроксимацию

H(u, z, t) ~ R(z)exp

juN^X

j B1(y)dy

+