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

ОСНОВЫ ТЕОРИИ  

МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

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

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

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

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

Рыков В.В.
Основы теории массового обслуживания (Основной курс: марковские модели, методы марковизации) : учебное пособие / В.В. Рыков, Д.В. Козырев. — Москва : ИНФРА­М, 2024. — 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

Р94

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

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

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

Подписано в печать 15.06.2017.  
Формат 60×90/16. Бумага офсетная. Гарнитура Computer Modern. Печать цифровая.  

ТК 358700­792498­061115

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

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

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

Предисловие

Настоящее издание возникло на основе курса “Теория массового обслуживания”, читавшегося в течение ряда лет студентам
Российского университета дружбы народов указанных выше специальностей, студентам специальности “Прикладная математика”
Российского государственного университета нефти и газа им. И.М.
Губкина и студентам специальности “Прикладная математика и
информатика” Московского государственного университета имени
М.В.Ломоносова, на базе которого в 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.
Многофазная система с неограниченными очередями
M|M|n1 → . . . |M|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. Дублирование с восстановлением < GI2|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.Приоритетная система Mr|GIr|1 . . . . . . . . . . . . . 186

14.1. Описание системы . . . . . . . . . . . . . . . . . . . . . . . . . . 186
14.2. Структура процесса числа требований для приоритетной системы Mr|GIr|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