Основы теории массового обслуживания (Основной курс:марковские модели, методы марковизации)


ВЫСШЕЕ ОБРАЗОВАНИЕ



серия основана в 1 996 г.



В.В. РЫКОВ
Д.В. КОЗЫРЕВ




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




            ОСНОВНОЙ КУРС: МАРКОВСКИЕ МОДЕЛИ, МЕТОДЫ МАРКОВИЗАЦИИ



УЧЕБНОЕ ПОСОБИЕ


             Рекомендовано в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлениям подготовки 01.03.02 «Прикладная математика и информатика», 02.03.02 «Фундаментальная информатика и информационные технологии», 02.03.01 «Математика и компьютерные науки» (квалификация (степень) «бакалавр»)


znanium.com

Москва
ИНФРА-М


2021

УДК 519.872(075.8)
ББК 22.18я73
      Р94



   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

      Рыков В.В.
Р94 Основы теории массового обслуживания (Основной курс: марковские модели, методы марковизации) : учебное пособие / В.В. Рыков, Д.В. Козырев. — Москва : ИНФРА-М, 2021. — 223 с. — (Высшее образование).
          ISBN 978-5-16-010945-9 (print)
          ISBN 978-5-16-102970-1 (online)
          Предлагаемое учебное пособие предназначено для бакалавров и магистров по направлениям подготовки высшего образования 01.03.02 (01.04.02) «Прикладная математика и информатика», 02.03.02 (02.04.02) «Фундаментальная информатика и информационные технологии», 02.03.01 (02.04.01) «Математика и компьютерные науки», а также может быть использовано при подготовке специалистов по другим направлениям, где изучаются дисциплины с подобным или близким содержанием, таких как, например, 27.03.04 «Управление в технических системах», 15.03.04 «Автоматизация технологических процессов и производств», 01.03.04 «Прикладная математика», 09.03.03 «Прикладная информатика» и др. От читателя предполагается знакомство с курсами теории вероятностей и теории случайных процессов в объеме, изучаемом студентами вузов с повышенной математической подготовкой.

УДК 519.872(075.8)
ББК 22.18я73

ISBN 978-5-16-010945-9 (print)
ISBN 978-5-16-102970-1 (online)

© Рыков В.В., Козырев Д.В., 2016

ООО «Научно-издательский центр ИНФРА-М» 127214, Москва, ул. Полярная, д. 31В, стр. 1 Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29 E-mail: books@infra-m.ru http://www.infra-m.ru



Издание выходит в авторской редакции и авторском наборе. Подготовка оригинал-макета — Д.В. Козырев

Подписано в печать 01.03.2021.
Формат 60x90/16. Бумага офсетная. Гарнитура Computer Modern. Печать цифровая.
Усл. печ. л. 13,94. ППТ20. Заказ № 00000

ТК 358700-1018908-061115

Отпечатано в типографии ООО «Научно-издательский центр ИНФРА-М»
127214, Москва, ул. Полярная, д. 31В, стр. 1
Тел.: (495) 280-15-96, 280-33-86. Факс: (495) 280-36-29

        Предисловие




        Настоящее издание возникло на основе курса “Теория массового обслуживания”, читавшегося в течение ряда лет студентам Российского университета дружбы народов указанных выше специальностей, студентам специальности “Прикладная математика” Российского государственного университета нефти и газа им. И.М. Губкина и студентам специальности “Прикладная математика и информатика” Московского государственного университета имени М.В.Ломоносова, на базе которого в 1979 г. было подготовлено учебное пособие [5], изданное небольшим тиражом университетским издательством и не доступное современному широкому кругу читателей. Вместе с тем, несмотря на прошедшие с того момента годы и появившиеся новые издания (например, [1, 3, 4, 6] и др.) данное пособие по-прежнему представляет определённый интерес благодаря компактности изложения и достаточно широкому охвату материала.
        При построении курса и отборе материала приходится выбирать между широтой охвата материала и строгостью его изложения. Такой компромисс предпринят в настоящем пособии, которое предназначено для одно-семестрового курса. Поэтому, как следует из подзаголовка, пособие посвящено марковским моделям теории массового обслуживания и основным методам марковизации: методам вложенных марковских цепей, фаз Эрланга и методам введения дополнительной переменной, а также некоторым новейшим подходам, связанным с регенеративным методом. Главы 1-3 могут составлять основу односеместрового курса бакалавриата. Глава 4 содержит более деликатные методы и может быть использована в качестве материала специального курса для магистрантов и для самостоятельного более углублённого изучения предмета, в том числе и для аспирантов. Различные обобщения содержатся в замечаниях, которые, таким образом, составляют второй уровень сложности (и могут быть

3

    пропущены при первом чтении). Еще более тонкие проблемы формулируются в задачах, предназначенных для серьёзного самостоятельного изучения предмета. При подготовке курса и составлении пособия использовались как широко известные [1, 3], так и менее доступные [87] издания и журнальные статьи.
       Основной единицей курса является параграф, поэтому в пособии принята сплошная нумерация параграфов, каждый из которых разбит на пункты. В пособии используется двойная нумерация формул, рисунков, таблиц, теорем и т.п. своя внутри каждого параграфа. В конце каждого параграфа приведены вопросы для самоконтроля, упражнения, задачи и краткие библиографические комментарии. Ссылки на литературные источники разделены на основную и специальную литературу и приводятся лишь в тех случаях, когда они могут помочь более глубокому изучению предмета. Доказательство теорем, лемм и утверждений завершается символом □.

4

        Список сокращений и обозначений


         (й, F, P) — вероятностное пространство, 16
         P, M, D—символы вероятности, математического ожидания и дисперсии, 51
         АЗС — автозаправочная станция, 11
         АСУ — автоматизированная система управления, 13
         АТС — автоматическая телефонная станция, 12
         в.б.р. — время безотказной работы, 98
         ВМР — вложенный момент регенерации, 173
         ВПВ — вложенный процесс восстановления, 198
         ВПР — вложенный период регенерации, 174
         ВПРП — вложенный полурегенерирующий процесс, 173
         ВС — вычислительная система, 13
         ВСР — вложенное состояние регенерации, 174
         КЛМП — кусочно-линейные марковские процессы, 150
         к.м.р. — конечно-мерные распределения, 75
         МВВ — матрица вложенного восстановления, 175
         МИП — матрица интенсивностей переходов (инфинитезимальная матрица) процесса, 52
         ММ —марковский момент, 166
         МПВ — матрица переходных вероятностей, 51
         МР — момент регенерации, 166
         МЦ — марковская цепь, 170
         н.о.р. — независимые одинаково распределенные (с.в.), 19
         ОРТП — общий рекуррентный точечный процесс , 47
         ОТП — общий точечный процесс, 47
         ПЗ — период занятости, 178
         ПДО — процесс длин очередей, 187

5

         ПЛ п.ф.м. — преобразование Лапласа производящей функции моментов, 179
         ПЛС — преобразование Лапласа-Стилтьеса, 146
         ПМВ — процесс марковского восстановления, 170
         ПММ — полумарковская матрица, 170
         ПМП — полумарковский процесс, 170
         ПМЦ — полумарковская цепь, 170
         ПОП — простейшая операция просеивания, 46
         ПП — поллинг процесс, 195
         ПР — период регенерации, ??
         ПРГ — процесс рождения и гибели, 50
         ПРП — полурегенерирующий процесс, 169
         п.ф.м. — производящая функция моментов, 92
         РП — (однородный) регенерирующий процесс, 167
         РПРП — разложимый полурегенерирующий процесс, 174
         РеП — рекуррентный поток, 47
         РеТП — рекуррентный точечный процесс, 47
         СеМО — сеть массового обслуживания, 112
         СП — свободный период, 178
         с.в. — случайная величина, 19
         с.п. — случайный процесс, 169
         СМО — система массового обслуживания, 15
         СР — состояние регенерации, 168
         СУР — система уравнений равновесия, 65
         ТМО — теория массового обслуживания, 11
         ТП — точечный процесс, 47
         ФВ — функция восстановления, 168
         ф.р. — функция распределения, 19
         ЦО — цикл обслуживания,193
         ЦР — цикл регенерации, 169
         ЯВВ — ядро вложенного восстановления, 175
         FIFO - First In First Out — прямой порядок обслуживания, 19
         LITO - Last In First Out — обратный (инверсионный) порядок обслуживания, 19
         SITO - Service In Random Order — случайный порядок обслуживания, 19

6

        Содержание




             Предисловие                                 3

             Список сокращений   и обозначений           5

    Глава  1.   Введение                                11
       § 1. Основные понятия и определения ............ 11
        1.1. Предмет теории массового обслуживания. Примеры 11
        1.2. Понятие СМО. Элементы СМО ................ 15
        1.3. Классификация СМО. Обозначения ........... 17
        1.4. Характеристики СМО. Задачи TMO. Методы исследования ....................................... 20
        1.5. Примеры. Упражнения ...................... 24
        1.6. Дополнения ............................... 28

    Глава 2. Марковские модели                          30
       § 2.  Простейший поток ......................... 30
        2.1. Модели процесса поступления требований ... 30
        2.2. Простейший поток. Определение. Основные свойства 33
        2.3. Структура простейшего потока ............. 38
        2.4. Свойства простейшего потока .............. 42
        2.5. Дополнения ............................... 46
       § 3.  Класс марковских моделей ................. 50
        3.1. Однородные марковские процессы и их инфинитезимальная матрица ............................... 50
        3.2. Классификация состояний и решение уравнений Кол        могорова ...................................... 53

7

        3.3.  Пример. Основная теорема ................... 58
        3.4.  Предельная теорема ......................... 63
        3.5.  Эргодическая теорема и критерии положительной возвратности ..................................... 66
        3.6.  Процессы рождения и гибели ................. 69
        3.7.  Дополнения ................................. 74


      § 4. Система Эрланга M|M|n, 0 .............. 78

         4.1.  Описание системы. Вычисление инфинитезимальной матрицы ............................................ 78
         4.2. Исследование стационарного режима ............ 79
         4.3. Обобщение: бесконечное число линий ........... 82
         4.4. Дополнения ................................... 85


       § 5. Смешанная система M|M|n, m ................. 89
        5.1.  Описание системы. Вычисление инфинитезимальной матрицы ........................................ 89
        5.2. Исследование стационарного режима ......... 90
        5.3. Дополнения ................................ 95

       § 6. Задача об обслуживании станков < Mn |M |m > . . 98
        6.1.  Описание системы. Вычисление инфинитезимальной матрицы ........................................ 98
        6.2. Исследование стационарного режима ......... 99
        6.3. Резервирование с восстановлением ......... 100
        6.4. Функция надёжности системы ............... 102
        6.5. Дополнения ............................... 104

       § 7. Многофазное обслуживание и разомкнутые сети107
        7.1. Выходной поток системы M|M |n ............ 107
        7.2. Многофазная система с неограниченными очередями
        MIM\n 1 ^ ... IM\nr ............................109
        7.3. Разомкнутая сеть СМО M\M\n, Q..............112
        7.4. Дополнения ............................... 115

8

       § 8.  Замкнутые СеМО .............................. 119
        8.1. Описание системы ............................ 119
        8.2. Определение стационарных вероятностей ....... 120
        8.3. Алгоритм вычисления нормирующего множителя . . 122
        8.4. Вычисление характеристик системы ............ 123
        8.5. Дополнения .................................. 124

    Глава 3. Методы марковизации                           127
       § 9.  Метод фаз Эрланга ........................... 128
        9.1. Распределение Эрланга ....................... 128
        9.2. Метод фаз Эрланга ........................... 129
        9.3. Система с потерями Энгсета < Mn| E2| 1, 0 > . 131
        9.4. Гиперэрланговское распределение ............. 132
        9.5.  Аппроксимация посредством гипер-эрланговских распределений ....................... 133
        9.6. Замечания к применению ...................... 136
        9.7. Дополнения .................................. 138
       § 10. Метод вложенных марковских цепей ............ 139
        10.1. Введение ................................... 139
        10.2.  Описание метода. Сущность метода вложенных марковских цепей .................................... 139
        10.3. Исследование длины очереди модели M|GI|1 ... 143
        10.4. Определение стационарного распределения вероятно        стей состояний в модели Пальма < Mn |GI |1 > ..... 146
        10.5. Дополнения ................................. 148
       § 11. Метод дополнительных переменных ............. 150
        11.1. Введение ................................... 150
        11.2. Сущность методов дифференциальных и интегро-дифференциальных уравнений ....................... 150
        11.3. Дублирование с восстановлением < GI₂ |M|1 > (метод дифференциальных уравнений) ...................... 154
        11.4.  Система Эрланга M |GI |n, 0 (метод интегро-дифференциальных уравнений) ...................... 158
        11.5. Кусочно-линейные марковские процессы ....... 162
        11.6. Дополнения ................................. 164

9

    Глава 4. Регенеративный метод

166

       § 12. Регенерирующие процессы .................... 166
        12.1. Введение .................................. 166
        12.2. Регенерирующий процесс .................... 166
        12.3. Полурегенерирующие процессы ............... 168
        12.4. Разложимые полурегенерирующие процессы .... 173
       § 13. Система M|GI|1 ............................. 178
        13.1. Описание системы и структура РП ........... 178
        13.2. Процесс числа требований в системе M|GI|1 . 179
        13.3. Стационарный режим ........................ 183
        13.4. Дополнения ................................ 185
       § 14. Приоритетная система Mᵣ |GIᵣ |1 ............ 186
        14.1. Описание системы .......................... 186
        14.2. Структура процесса числа требований для приоритетной системы Mᵣ |GIᵣ |1 .......................... 187
        14.3. Исследование процесса числа требований .... 188
        14.4. Дополнения ................................ 190
       § 15. Системы поллинга ........................... 192
        15.1. Описание модели ........................... 192
        15.2. Структура процесса поллинга ............... 194
        15.3. Стохастические соотношения для поллинг процесса 195
        15.4. Поведение ПП на отдельном ПЗ .............. 198
        15.5. Поведение ПП на отдельном цикле обслуживания . . 199
        15.6. Поведение ПП на отдельном этапе обслуживания . . 200
        15.7.  Исследование ПП на отдельном этапе обслуживания с переключением ................................. 207
        15.8. Исследование ПП на отдельном цикле обслуживания 209
        15.9. Исследование ПП на отдельном ПЗ ........... 212
        15.10. Исследование стационарного режима ........ 214
        15.11. Дополнения ............................... 214

10

Глава 1. Введение

  Глава 1

    Введение




      § 1.  Основные понятия и определения

    1.1. Предмет теории массового обслуживания. Примеры
    Теория массового обслуживания (ТМО) является дисциплиной, которую принято относить к области прикладной математики, в частности к её разделу «Исследование операций», и изучает функционирование систем в условиях массового поступления требований и наличия случайных факторов. При этом в ТМО изучаются явления загруженности систем, проявляющиеся в виде образования очередей, простоя оборудования, задержек или отказов в обслуживании и т. п., вне зависимости от конкретного вида требований и обслуживающих средств, а также конкретного содержания процесса их обслуживания. Это позволяет с единой математической точки зрения рассматривать широкий класс систем. Приведем несколько примеров.

    Пример 1.1. АЗС
      Рассмотрим автозаправочную станцию (АЗС) с n бензоколонками, содержащими несколько типов бензина, предназначенного для различных типов автомашин, и ограниченным (площадкой перед станцией) числом мест для ожидания (рис. 1.1).
      К АЗС в случайные моменты времени подъезжают автомашины и при наличии свободной бензоколонки с нужной маркой бензина начинают заправляться. В противном случае автомашины становятся в очередь, если есть места, или покидают АЗС. Так как автомашины разных марок обладают бензобаками различной емкости и подъезжающие автомашины имеют различный запас бензина, длительность заправки является, вообще говоря, случайной величиной. Нерегулярность поступления автомашин и случайность длительности их обслуживания приводит к нерегулярности работы АЗС: в отдельные периоды времени бензоколонки простаивают, в другие периоды образуются очереди, вызывающие большие задержки транспортных средств. Возникают задачи изучения, количественной и ка
11

§ 1. Основные понятия и определения

1

n 1

m£_

,1,

n k

n

Рис. 1.1. Модель АЗС



чественной оценки этих явлений, а также расчета необходимого количества бензоколонок и размеров площадки для ожидания автомобилей перед АЗС при её проектировании.

Пример 1.2. АТС
   Рассмотрим упрощённую модель автоматической телефонной станции (АТС), содержащей n линий связи (рис. 1.2).

Рис. 1.2. Модель АТС

   В случайные моменты времени на АТС поступают от абонентов вызовы на связь. При наличии свободной линии с помощью коммутатора K устанавливается связь и линия занимается на случайное время — длительность разговора, в течение которого эта линия не может быть предоставлена другим абонентам. Если в момент поступления вызова все линии окажутся занятыми, абонент получает отказ (вызов теряется). Возникают задачи исследования поведения системы во времени, которое в силу случайности моментов поступления вызовов и длительностей разговоров описывается некоторым


12

Глава 1. Введение

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

Пример 1.3. ВС
   Рассмотрим вычислительную систему (ВС) или отдельную ЭВМ, работающую в режиме автоматизированного управления некоторым объектом (предприятием), скажем, в рамках автоматизированной системы управления (АСУ) (рис. 1.3).


                           Запросы

Задачи АСУ

ЭВМ

                        Информация


Рис. 1.3. Модель ВС


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

Пример 1.4. Надежность
   Пусть некоторое сложное техническое устройство, например ЭВМ, подвержено отказам, возникающим в случайные моменты времени, на выявление и устранение которых тратится также случайное время; кроме того для уменьшения риска отказов устройство допус


13

§ 1. Основные понятия и определения

кает профилактические осмотры, в течение которых устраняются «скрытые» отказы (рис. 1.4).


   ремонт

профилактика

работа 0


Рис. 1.4. Профилактика

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


Рис. 1.5. Модель супермаркета

   Таким образом, обслуживание покупателей состоит из двух фаз — каждый покупатель должен выбрать и получить товар в жела



14