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

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

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

ОСНОВНОй кУРС:  

МАРкОВСкИЕ МОдЕЛИ,  

МЕТОдЫ МАРкОВИзАЦИИ

В.В. РыкоВ
Д.В. козыРеВ

Рекомендовано в качестве учебного пособия 

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

01.03.02 «Прикладная математика и информатика», 

02.03.02 «Фундаментальная информатика и информационные технологии», 

02.03.01 «Математика и компьютерные науки» 

(квалификация (степень) «бакалавр»)

Москва 

ИНФРА-М 

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

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

Рыков В.В.

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

Издание выходит в авторской редакции и авторском наборе. 

Подготовка оригинал­макета — Д.В. Козырев

Подписано в печать 31.05.2022.  

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

Усл. печ. л. 13,94. ППТ10. Заказ № 00000

ТК 358700­1893206­061115

Отпечатано в типографии ООО «Научно­издательский центр ИНФРА­М» 

127214, Москва, ул. Полярная, д. 31В, стр. 1 

Тел.: (495) 280­15­96, 280­33­86. Факс: (495) 280­36­29

© Рыков В.В., Козырев Д.В., 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

Предисловие

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

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

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

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

1.1. Предмет
теории
массового
обслуживания.
Примеры

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

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

11

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

n1

nk

m
1

n

...

...

1

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

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

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

...

...

K

Абоненты

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

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

12

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

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

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

...

ЭВМ

Запросы

Информация

Задачи АСУ

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

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

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

13

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

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

t
0

ремонт

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

работа

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

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

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

I
II

.
..

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

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

14