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

В.В. Афонин, В.В. Никулин





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

Учебное пособие























Москва Вологда «Инфра-Инженерия» 2023

УДК 519.87
ББК 32.973
     А94


Рецензенты:
д-р техн. наук, профессор, заведующий кафедрой телекоммуникаций Ульяновского государственного технического университета (УлГТУ) Дементьев В. Е.;
канд. техн. наук, доцент, заведующий кафедрой телекоммуникационных систем Волгоградского государственного университета Семенов Е. С.





    Афонин, В. В.
А94 Анализ и моделирование типовых систем массового обслуживания : учебное пособие / В. В. Афонин, В. В. Никулин. - Москва ; Вологда : Инфра-Инженерия, 2023. - 232 с. : ил., табл.
        ISBN978-5-9729-1187-5

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

УДК519.87
                                                          ББК 32.973










ISBN 978-5-9729-1187-5

     © Афонин В. В., Никулин В. В., 2023
     © Издательство «Инфра-Инженерия», 2023
                            © Оформление. Издательство «Инфра-Инженерия», 2023

СОДЕРЖАНИЕ

ПРЕДИСЛОВИЕ.....................................................6
ВВЕДЕНИЕ........................................................7
1. ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ...................9
  1.1. Классификация систем массового обслуживания..............9
  1.2. Приоритетные системы и дисциплины обслуживания..........12
  1.3. Задачи анализа и синтеза систем массового обслуживания..15
  1.4. Практическая часть......................................15
2. АНАЛИЗ ПОТОКОВ ПУАССОНА И ЭРЛАНГА...........................18
  2.1. Анализ входных потоков требований.......................18
     2.1.1. Свойство стационарности потока событий..................19
     2.1.2. Свойство ординарности потока событий...............19
     2.1.3. Свойство отсутствия последействия..................20
     2.1.4. Параметр и интенсивность потока требований.........20
     2.1.5. Параметр и интенсивность нестационарного потока....22
  2.2. Пуассоновский поток требований..........................22
     2.2.1. Числовые характеристики Пуассоновского потока......30
     2.2.2. Свойство вероятностей распределения Пуассона.......32
     2.2.3. Распределение длительностей интервалов между требованиями в пуассоновском потоке....................................33
     2.2.4. Числовые характеристики экспоненциального распределения.34
     2.2.5. Случайное разрежение пуассоновского потока.........36
     2.2.6. Объединение пуассоновских потоков..................38
     2.2.7. Моделирование Пуассоновского потока................40
  2.3. Потоки Эрланга..........................................42
     2.3.1. Закон распределения интервалов времени между требованиями потока Эрланга k-го порядка...............................43
     2.3.2. Числовые характеристики потока Эрланга k-го порядка.....46
     2.3.3. Замена реальных потоков требований потоками Эрланга.....47
     2.3.4. Практическая часть. Моделирование потоков Пуассона и Эрланга........................................47
3. ТИПОВЫЕ МАРКОВСКИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ.
АНАЛИЗ ОДНОКАНАЛЬНЫХ СИСТЕМ....................................56
  3.1. Процессы размножения и гибели...........................56
     3.1.1. Дифференциальные уравнения процесса размножения и гибели ... 58
     3.1.2. Мнемоническое правило составления уравнений Колмогорова.62
     3.1.3. Процесс чистого размножения........................63
     3.1.4. Процесс чистой гибели..............................64
     3.1.5. Стационарный режим процесса размножения и гибели...65
  3.2. Одноканальные системы массового обслуживания............68
     3.2.1. Система массового обслуживания М/М/1...............68
     3.2.2. Формула Литтла. Аналоги формулы Литтла.............70

3

     3.2.3. Операционные характеристики системы М/М/1..........73
     3.2.4. Система М/М/1 с отказами...........................77
     3.2.5. Система М/М/1/К с конечным накопителем.............78
     3.2.6. Операционные характеристики системы М/М/1/К........81
     3.2.7. Система М/М/1//М с конечным числом источников нагрузки.84
     3.2.8. Система М/М/1 с ограниченным временем ожидания.....87
     3.2.9. Операционные характеристики системы М/М/1 с ограниченным временем ожидания.........................................90
  3.3. Практическая часть......................................92
4. ТИПОВЫЕ МАРКОВСКИЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ.
АНАЛИЗ МНОГОКАНАЛЬНЫХ СИСТЕМ...................................98
  4.1. Система М/М/m с m обслуживающими приборами..............99
     4.1.1. Вероятности состояний системы М/М/m...............100
     4.1.2. Операционные характеристики системы М/М/m.........102
  4.2. Система М/М/m с отказами. В-формула Эрланга............105
     4.2.1. Вероятности состояний системы М/М/m с отказами.........106
     4.2.2. Операционные характеристики системы М/М/m с отказами...108
  4.3. Система М/М/m/К с конечным накопителем......................110
     4.3.1. Вероятности состояний системы М/М/m/К..................110
     4.3.2. Операционные характеристики системы М/М/m/К............112
  4.4. Система М/М/m с ограниченным временем ожидания.........116
     4.4.1. Вероятности состояний системы М/М/m с нетерпеливыми требованиями.............................................116
     4.4.2. Операционные характеристики системы М/М/m с нетерпеливыми требованиями.............................119
  4.5. Система М/М/m/К/М с конечным числом источников нагрузки, с m обслуживающими приборами и конечным накопителем.........120
     4.5.1. Вероятности состояний системы М/М/m/К/М...........121
     4.5.2. Операционные характеристики системы М/М/m/К/М.....124
  4.6. Практическая часть.....................................126
5. ТИПОВЫЕ ПОЛУМАРКОВСКИЕ СИСТЕМЫ МАССОВОГО
ОБСЛУЖИВАНИЯ..................................................131
  5.1. Система массового обслуживания типа М/G/1..............131
  5.2. Операционные характеристики полумарковской системы М/GH.....135
  5.3. Система массового обслуживания GI/М/m..................136
  5.4. Оценка распределения длины очереди в системе GI/М/m....141
  5.5. Оценка распределения времени ожидания в системе GI/М/m......145
  5.6. Практическая часть.....................................150
6. ТИПОВЫЕ НЕМАРКОВСКИЕ СИСТЕМЫ МАССОВОГО
ОБСЛУЖИВАНИЯ..................................................161
  6.1. Система массового обслуживания типа G/G/1..............162
  6.2. Решение интегрального уравнения Линдли.................168
  6.3. Практическая часть.....................................174

4

7. ОПТИМИЗАЦИЯ ТИПОВЫХ МАРКОВСКИХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ.............................................192
  7.1. Оптимизация Марковской СМО с конечным накопителем.193
  7.2. Оптимизация СМО типа М/М/m с ограниченным временем ожидания в очереди.....................................195
  7.3. Оптимизация Марковской СМО типа М/М/m с отказами..196
  7.4. Оптимизация Марковских многоканальных СМО при больших загрузках..................................198
  7.5. Практическая часть................................201

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.................................224

5

ПРЕДИСЛОВИЕ

   Системы массового обслуживания встречаются во многих сферах современного информационного пространства. Это автоматические телефонные станции (АТС), сотовая связь, задачи телетрафика, серверы и сайты всемирной паутины, банковские, экономические и производственные объекты различного прикладного характера. В частности, в такой учебной дисциплине, как «Теория телетрафика» принято включать разделы по системам массового обслуживания. Следует отметить, что в зарубежной литературе теория систем массового обслуживания называется теорией очередей - Queue theory. Соответственно, системы массового обслуживания - это Queuing systems. В дальнейшем сокращенно системы массового обслуживания будем обозначать как СМО или QS.
   В учебное пособие включены различные темы с различной полнотой их описания. Большую часть занимает материал по Марковским системам массового обслуживания, для которых более подробно освещены выводы большинства операционных характеристик, дифференциальных уравнений, представляющих собой модели соответствующей QS в динамическом режиме, а также модели в стационарном режиме. Затрагиваются вопросы оптимизации некоторых Марковских систем с их программной реализацией, что позволяет определить, в первую очередь, необходимое число каналов или приборов обслуживания. Для полумар-ковских СМО приводятся основные интегральные и дискретные преобразования, позволяющие получить базовые операционные характеристики систем. Рассмотрены также вопросы, освещающие немарковские системы массового обслуживания, задачи их исследования, и некоторые подходы их решения, включая имитационное моделирование.
   Материал учебного пособия сопровождается функциональными схемами и необходимыми диаграммами и графиками, поясняющими анализ соответствующей системы массового обслуживания.

6

ВВЕДЕНИЕ
   Основоположником теории и систем массового обслуживания считается датский ученый А. К. Эрланг (1878-1929), который, работая в копенгагенской телефонной компании, опубликовал в 1909 году работу «Теория вероятностей и телефонные переговоры», в которой решил ряд задач по теории СМО с отказами. В дальнейшем существенное развитие данного направления было заложено в работах советского ученого А. Я. Хинчина (1884-1959), который предложил термин «теория массового обслуживания».
   Каждый тип системы массового обслуживания принято обозначать в соответствии с символикой Кендалла [14, 16,21,23, 24, 27, 34, 42, 44-47], которая состоит из четырех позиций, разделяемых вертикальными или наклонными линиями: А/В/m /К, где
   А - распределение моментов поступлений требований на обслуживание или закон распределения поступающих в систему требований;
   В - распределение времени обслуживания требований;
   m - число параллельно функционирующих узлов (каналов, приборов) обслуживания;
   К - максимальное число допускаемых в систему требований, т. е. число требований в очереди плюс число требований, принятых на обслуживание.
   Кроме указанных обозначений могут иметь место и такие, которые связаны с емкостью источника нагрузки, генерирующего требования на обслуживание, и с дисциплиной очереди.
   Поля А и В в СМО могут принимать идентичные значения из следующего набора обозначений:
   М - экспоненциальное (показательное) распределение. Для входящего потока промежутки времени между последовательными поступлениями требований распределены экспоненциально, а поступление самих требований в систему подчиняется простейшему закону Пуассона с постоянной интенсивностью X = const; М(t) - пуассоновский входной поток при интенсивности, зависящей от времени t, т.е. X = X(t);
   D - детерминированный интервал времени между моментами последовательных поступлений в систему требований на обслуживание или детерминированная продолжительность обслуживания;
   Ег - распределение Эрланга порядка г интервалов времени между моментами последовательных поступлений требований в обслуживающую систему или продолжительностей обслуживания;
   HM - гиперэкспоненциальное распределение;
   НЕ - гиперэрланговское распределение;
   РН- распределение фазового типа;
   GI - распределение произвольного вида моментов поступления в систему требований на обслуживание (или интервалов времени между последовательными поступлениями требований);
   G - распределение произвольного вида моментов выбытия из системы обслуженных требований (или продолжительностей обслуживания).

7

   Если два первых символа являются М (Марков), то говорят, что это Марковская система обслуживания. Если только один из двух первых символов будет М, то это обозначается полумарковская система обслуживания. Когда первые два символа не содержат М, то это обозначение немарковской системой массового обслуживания.
   Для Марковских систем массового обслуживания получено большое число законченных результатов, они, как правило, анализируются с помощью аналитического моделирования. Соответственно, для полумарковских систем результаты в замкнутой форме, например, в виде аналитических формул, получены для некоторых частных случаев, поэтому их анализ часто осуществляется с помощью инструментов имитационного моделирования, например, в GPSS World, AnyLogic, MATLAB.
   Немарковские системы массового обслуживания анализируются в основном с помощью имитационного моделирования.

8

1. ОСНОВНЫЕ ПОНЯТИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1. Классификация систем массового обслуживания
   Дадим определение СМО из [29]: массового обслуживания система - понятие, которое включает в себя случайный «входящий» поток требований (вызовов, звонков, заявок, клиентов), нуждающихся в «обслуживании», и механизм (алгоритм), осуществляющий это «обслуживание». Требования поступают в некоторые устройства, приборы, узлы или каналы обслуживания, где они пребывают в общем случае случайное время. Процесс, характерный для типовой СМО, показан на рис. 1.1.



СМО

Входной

Очередь

поток требований

Приборы обслуживания

Выходной

поток требований

Рис. 1.1. Схема процессамассового обслуживания


   На рис. 1.1 пунктирная стрелка означает, что очереди может и не быть при поступлении требований в систему массового обслуживания (СМО).
   Моделирование процессов массового обслуживания осуществляется на базе Q-схем [Советов], где Q - queue (очередь). В символике Q-схем i-й прибор обслуживания Пi изображают в виде схем, показанных на рис. 1.2.

Рис. 1.2. Примеры приборов обслуживания требований

   На рис. 1.2 Wi - поток заявок, Ui - поток обслуживаний, Н i- накопитель заявок (очередь), Кi - собственно канал/прибор обслуживания, yi - поток обслуженных заявок (требований).
   В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q-схемы, образуемые композицией многих элементарных приборов обслуживания.

9

   На рис. 1.1 блок с надписью «Приборы обслуживания» иногда так и называют блоком обслуживания. Блок обслуживания может состоять из одного или нескольких каналов (узлов). Канал обслуживания - это устройство или средство (включая человека-оператора), способное в данный момент времени обслуживать лишь одно требование. Основными характеристиками канала обслуживания являются - пропускная способность и среднее время обслуживания одного требования.
   Если блок обслуживания состоит из одного канала, он называется одноканальным (однолинейным), при нескольких каналах обслуживания блок называют многоканальным (многолинейным) [3, 4, 23, 43]. Различают однофазные и многофазные блоки обслуживания. Если требование после обслуживания только одним прибором покидает систему обслуживания, имеет место однофазное обслуживание. При многофазном обслуживании требование последовательно обслуживается несколькими приборами, причем, приборы могут быть одной или разной последовательности, при обслуживании перед каждым прибором может оказаться своя очередь. Пример СМО с несколькими каналами обслуживания приведен на рис. 1.3.


Рис. 1.3. Схема системы с накопителемНи m каналами обслуживания

   Пример многофазной системы с возможной очередью перед каждой фазой (устройством/каналом) обслуживания показан на рис. 1.4.


Рис. 1.4. Схемамногофазной системы обслуживания

10

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


Рис. 1.5. Схемамногофазно-многолинейной СМО

   Значения,/.L. ....Лна рис. 1.5 означают количество параллельно включенных приборов в каждой из фаз многофазно-многолинейной системы массового обслуживания. В практических случаях структура систем массового обслуживания может быть очень разнообразной. а не только в виде схем. представленных на рис. 1.3-1.5. В частности. на схемах может быть такой распределительный элемент. как клапан или ключ (Кл). Обозначение ключей (Кл) на Q-схемах приведены на рис. 1.6 варианты а) и б).

а)                                                    б)

Рис. 1.6. СхемноеобозначениеключаКл

   По времени пребывания требований в системе до начала обслуживания выделяют:
   • системы с неограниченным временем ожидания.
   • системы с отказами.
   • смешанного вида (прождав определенное время. получают отказ).

11

   •    системы с нетерпеливыми требованиями, когда требования в очереди после некоторого ожидания обслуживания самостоятельно покидают систему.
   Различают также замкнутые и разомкнутые системы массового обслуживания с ожиданием.
   В замкнутой системе массового обслуживания входящий поток требований ограничен. В символических обозначениях используется дополнительное поле, например, 44.IG/m/KIM, где K - допустимое число требований в системе, последнее M - число требований источника нагрузки, из которых формируется входящий поток требований в СМО.
   Разомкнутые системы массового обслуживания - это системы с неограниченным источником нагрузки входного потока требований.
   В общем случае системы массового обслуживания могут иметь различное число приборов (каналов, узлов) обслуживания:
   •    с одним прибором;
   •    с несколькими (конечным числом) одинаковыми по производительности приборами;
   •    с бесконечным числом одинаковых по производительности приборов;
   •    с несколькими приборами разной производительности.
1.2. Приоритетные системы и дисциплины обслуживания
   В обозначениях систем массового обслуживания может входить дополнительное поле для определения приоритета обслуживания. Например, в продолжении символики Кендалла для приоритетных систем в пятом/шестом поле фиксируется символ f/, i = 0, 1, 2; j = 0,1 Если i = 0, то осуществляется обслуживание без приоритета, при i =1 в системе имеется относительный приоритет; i = 2 означает наличие абсолютного приоритета; значениеj = 0 указывает, что требование, заставшее все места занятыми, теряется^' = 1 - вновь прибывшее требование вытесняет требование с низшим приоритетом. Приоритетное обслуживание применяется в тех случаях, когда в систему поступают разнородные требования.
   По поводу однородных и неоднородных требований надо отметить следующее. Если требования, поступающие в систему массового обслуживания, различаются только моментами времени поступления в СМО, то такие требования называются однородными. Если требования имеют признаки, по которым формируются приоритетные свойства, то такие требования будут называться неоднородными . Приоритетным требованиям задается некоторый параметр, который определяет его приоритет. Этот параметр может задаваться либо в числовом виде (статический приоритет), либо в виде функции, которая зависит от времени пребывания в системе (динамический приоритет). Статические приоритеты не изменяются во время функционирования СМО. Статические приоритеты назначаются заранее и не зависят от состояний Q-схемы. Динамические приоритеты возникают при моделировании в зависимости от возникающих ситуаций. Назначение динамических приоритетов - это элемент управления функционированием системы массового обслуживания.

12

   Для неоднородных требований различают следующие дисциплины обслуживания [3, 42].
   Относительный приоритет. При завершении обслуживания очередного требования из очереди на обслуживание выбирается требование с наивысшим приоритетом. Относительный приоритет предусматривает, что поступление требования с более высоким приоритетом не прерывает обслуживания менее приоритетного требования.
   Абсолютный приоритет. При поступлении в систему требования более высокого приоритета, чем требование, обслуживающееся на приборе, происходит прерывание обслуживания, начинает обслуживаться поступившее требование.
   Если прерванное на обслуживании требование теряется, то это соответствует разрушающему приоритету.
   Если требование возвращается в очередь с последующим дообслуживанием, то это соответствует абсолютному приоритету с запоминанием.
   Если же обслуживание начинается заново, то это соответствует абсолютному

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


Рис. 1.7. Схема СМО с абсолютным приоритетом

   В модели на рис. 1.7 блок с диспетчером (Диспетчер) управляет поступлением разнородных требований на обслуживание в прибор обслуживания «К». Разнородные требования помещаются в соответствующие очереди/накопители (Н1,Н2,...). При этом входные потоки требований (Вход 1, Вход 2, ...) также разделены, и некоторые направляются в выделенные для них очереди/накопители.
   Чередующийся приоритет. С ним происходит закрепление за требованиями того типа, который находится на обслуживание наивысшего приоритета. После

13