Теория очередей и машинное обучение

В.М. ВИШНЕВСКИЙ
Д.В. ЕФРОСИНИН
ТЕОРИЯ ОЧЕРЕДЕЙ 
И МАШИННОЕ ОБУЧЕНИЕ
МОНОГРАФИЯ
Москва
ИНФРА-М
2024

УДК 519.872+004.85(075.4)
ББК 22.18:16.63
 
В55
А в т о р ы:
Вишневский В.М., доктор технических наук, профессор, заведующий лабораторией Института проблем управления имени В.А. Трапезникова Российской 
академии наук;
Ефросинин Д.В., доктор физико-математических наук, профессор, заведующий 
кафедрой Университета Иоганна Кеплера
Р е ц е н з е н т ы:
Кузнецов Н.А., доктор технических наук, профессор, заведующий лабораторией Института радиотехники и электроники имени В.А. Котельникова Российской академии наук, академик Российской академии наук;
Семёнова О.В., доктор физико-математических наук, доцент, ведущий научный сотрудник Института проблем управления имени В.А. Трапезникова Российской академии наук
Вишневский В.М.
В55  
Теория очередей и машинное обучение : монография / В.М. Вишневский, 
Д.В. Ефросинин. — Москва : ИНФРА-М, 2024. — 370 с. : ил. — (Научная мысль).
ISBN 978-5-16-020572-4 (print)
ISBN 978-5-16-113230-2 (online)
Монография посвящена систематизированному изложению нового подхода к исследованию сложных задач теории очередей с использованием методов машинного 
обучения и его применению при проектировании телекоммуникационных сетей нового поколения. В основу положены оригинальные результаты авторов, опубликованные в ведущих российских журналах и в высокорейтинговых зарубежных изданиях, 
а также курсы лекций, прочитанных в Московском физико-техническом институте 
и Университете Иоганна Кеплера г. Линц (Австрия).
Предназначена для широкого круга специалистов в области стохастических систем 
и проектирования компьютерных и социальных сетей, а также аспирантов и студентов 
высших учебных заведений по специальностям «Теория вероятностей и математическая статистика», «Системы, сети и устройства телекоммуникаций».
УДК 519.872+004.85(075.4)
ББК 22.18:16.63
Работа выполнена при финансовой поддержке Российского научного фонда и DST-Департамента науки и технологий, Индия (грант №22-49-02023) в рамках совместного 
научно-исследовательского проекта Института проблем управления имени В.А. Трапезникова Российской академии наук и Индийского технологического института г. Дели.
ISBN 978-5-16-020572-4 (print)
ISBN 978-5-16-113230-2 (online)
© Вишневский В.М., Ефросинин Д.В., 
2024

Предисловие
Математические модели сетей и систем массового обслуживания (СМО) широко применяются для исследования и оптимизации различных технических,
экономических, производственных, медицинских, военных и других систем.
Особенно эффективны эти модели используются при проектировании современных телекоммуникационных сетей, включая анализ характеристик существующих и перспективных сетевых протоколов, оптимизацию алгоритмов
маршрутизации и топологической структуры сети и т.д.
Традиционно основное внимание при исследовании сложных СМО направлено на анализ стационарного режима функционирования, построение
многомерной марковской цепи, вывод системы дифференциальных уравнений Колмогорова и их решение с использованием аппарата преобразований
Лапласа-Стилтьеса и/или производящих функций, формулирование и решение различных оптимизационных задач как параметрическими методами,
так и с помощью динамического программирования. Однако до настоящего
времени остается значительное количество нерешенных задач в теории очередей, аналитическое и численное решение которых либо затруднено, либо
вовсе невозможно традиционными методами. Примерами таких задач являются: исследование многолинейных приоритетных СМО с корректированными входными ММАР-потоками и буфером ограниченного объема; анализ
характеристик сетей и многофазных СМО большой размерности с входящим
ВМАР-потоком и произвольными функциями распределения обслуживания
на фазах; исследование систем адаптивного динамического поллинга и сложных СМО типа fork-join; вычисление оптимальных политик управления и исследование их структурных свойств в управляемых СМО, а также ряд задач
теории надежности типа k-из-n и т.д. Отсутствие новых методов и подходов
к аналитическому и численному решению таких задач сдерживает практическое применение моделей теории очередей при оценке производительности
и проектировании сложных технических и социальных сетей.
В настоящей книге предложен новый подход для решения этой проблемы,
который заключается в объединении аналитических, численных и имитационных методов моделирования этих систем с машинным обучением. Однако
такая синергия методов часто оказывается сложной задачей из-за различий
в их функциональных возможностях и требованиях к данным. Проведенные
нами исследования показали, что данная задача решаема, а предлагаемый
iii

iv
подход является универсальным и весьма эффективным. В результате такого
объединения создаются обученные модели машинного обучения, пригодные
для качественного и, что главное, быстрого с точки зрения вычислений анализа производительности и надежности систем массового обслуживания, а
также для решения задач оптимального управления. Предлагаемый в этой
книге способ использования машинного обучения к решению задач теории
очередей не является заменой существующих классических методов, а скорее
представляет собой дополнение и расширение возможностей этой теории.
Несмотря на появление в последние годы ряда публикаций в этой области, систематизированное изложение подхода, основанного на применении
машинного обучения для исследования задач теории очередей, в современно мировой литературе отсутствует. Достаточная завершенность теоретических результатов и практические потребности разработчиков сложных систем обусловили целесообразность написания предлагаемой книги, которая
закрывает этот пробел. В основу книги положены оригинальные результаты авторов, опубликованные в ведущих российских журналах и в высокорейтинговых зарубежных изданиях, а также курсы лекций, прочитанных в
Московском физико-техническом институте и Университете Иоганна Кеплера г. Линц (Австрия).

Оглавление
1
Введение
1
1.1
Современные тенденции развития теории очередей
. . . . . . .
1
1.2
Последние достижения по использованию машинного обучения
в теории очередей . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3
Структура книги
. . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.4
Используемые обозначения и сокращения . . . . . . . . . . . . .
1
2
2
Машинное обучение для теории очередей
14
2.1
Основы машинного обучения
. . . . . . . . . . . . . . . . . . . .
14
2.1.1
Машинное обучение с учителем . . . . . . . . . . . . . . .
16
. . .
2.1.2
Признаки и целевые функции для систем обслуживания
17
2.1.3
Характеристики эффективности классификации . . . . .
20
2.1.4
Характеристики эффективности регрессии . . . . . . . .
25
2.1.5
Перекрестная проверка . . . . . . . . . . . . . . . . . . . .
27
2.1.6
Предварительная обработка данных . . . . . . . . . . . .
28
2.2
Алгоритмы машинного обучения . . . . . . . . . . . . . . . . . .
30
2.2.1
Линейная регрессия . . . . . . . . . . . . . . . . . . . . . .
32
2.2.2
Логистическая регрессия . . . . . . . . . . . . . . . . . . .
34
2.2.3
Метод ближайших соседей . . . . . . . . . . . . . . . . . .
38
2.2.4
Дерево решений . . . . . . . . . . . . . . . . . . . . . . . .
44
2.2.5
Метод случайного леса . . . . . . . . . . . . . . . . . . . .
48
2.2.6
Метод деревьев с градиентным усилением . . . . . . . . .
52
2.2.7
Метод опорных векторов . . . . . . . . . . . . . . . . . . .
56
2.2.8
Наивный Байес
. . . . . . . . . . . . . . . . . . . . . . . .
60
2.2.9
Регрессия гауссовского процесса
. . . . . . . . . . . . . .
62
2.2.10 Скрытая марковская модель . . . . . . . . . . . . . . . . .
66
2.2.11 Глубокое обучение и нейронные сети . . . . . . . . . . . .
70
2.3
Машинное обучение для задач дискретной оптимизации
. . . .
80
2.3.1
Применение МО для статической оптимизации . . . . . .
86
2.3.2
Применение МО для динамической оптимизации. Обучение с подкреплением . . . . . . . . . . . . . . . . . . . .
91
2.4
Программные пакеты для имитационного моделирования и машинного обучения . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
v

Оглавление
vi
3
Решение задач для произвольной классической СМО с использованием машинного обучения
104
3.1
Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.2
Описание СМО
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.3
Имитационное моделирование . . . . . . . . . . . . . . . . . . . . 107
3.3.1
Дискретно-событийное моделирование . . . . . . . . . . . 107
3.3.2
Моделирование по моментам ухода из системы . . . . . . 110
3.3.3
Проверка имитационной модели
. . . . . . . . . . . . . . 111
3.4
Задачи регрессии
. . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.4.1
Оценка среднего числа заявок в системе . . . . . . . . . . 114
3.4.2
Оценка распределения числа заявок в системе . . . . . . 117
3.4.3
Оценка распределения времени ожидания и пребывания
120
. . .
3.5
Задачи классификации . . . . . . . . . . . . . . . . . . . . . . . . 123
3.5.1
Классификация по значению времени ожидания . . . . . 123
3.5.2
Классификация в задаче дискретной оптимизации . . . . 126
3.5.3
Классификация СМО по временным рядам . . . . . . . . 128
3.6
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 131
4
Мультисервисные приоритетные системы с коррелированным
входным потоком и ограниченной буферной памятью
133
4.1
Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.2
Постановка задачи
. . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.3
Система с двумя приоритетными классами . . . . . . . . . . . . 138
4.3.1
Цепь Маркова для состояний системы . . . . . . . . . . . 138
4.3.2
Стационарное распределение
. . . . . . . . . . . . . . . . 144
4.3.3
Характеристики производительности . . . . . . . . . . . . 145
4.4
Оценка производительности систем с приоритетами и произвольным числом типов заявок с помощью машинного обучения
147
. . .
4.4.1
Оценка характеристик производительности с помощью
метода Монте-Карло . . . . . . . . . . . . . . . . . . . . . 148
4.4.2
Оценка производительности с помощью машинного обучения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.5
Численные результаты . . . . . . . . . . . . . . . . . . . . . . . . 155
4.5.1
Сложность аналитической модели
. . . . . . . . . . . . . 155
4.5.2
Проверка имитационной модели
. . . . . . . . . . . . . . 157
4.5.3
Формирование набора данных для алгоритмов машинного обучения . . . . . . . . . . . . . . . . . . . . . . . . . 158
4.5.4
Прогнозирование времени отклика системы . . . . . . . . 158
4.5.5
Прогнозирование потерь приоритетных заявок . . . . . . 161
4.5.6
Анализ затраченного времени . . . . . . . . . . . . . . . . 163
4.6
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 165
Приложение
167
4.A Вычисление матриц Pi(·), Ai(·, ·), и Li(·, ·).
. . . . . . . . . . . . 167

Оглавление
vii
5
Многофазные системы большой размерности с входящим MAPпотоком
170
5.1
Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.2
Постановка задачи исследования . . . . . . . . . . . . . . . . . . 171
.
.
5.3
Алгоритм точного расчета характеристик тандемной системы
. 173
5.3.1
Оценка сложности алгоритма нахождения точных характеристик производительности . . . . . . . . . . . . . . 175
5.4
Получение оценок характеристик производительности тандемной сети большой размерности
. . . . . . . . . . . . . . . . . . . 176
5.4.1
Метод имитационного моделирования . . . . . . . . . . . 177
5.4.2
Применение методов машинного обучения для получения оценок стационарных характеристик производительности
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.5
Численные результаты . . . . . . . . . . . . . . . . . . . . . . . . 181
5.5.1
Исследование межконцевых задержек . . . . . . . . . . . 182
5.5.2
Исследование вероятности успешной доставки . . . . . . 184
5.5.3
Анализ времени расчетов
. . . . . . . . . . . . . . . . . . 187
5.6
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 187
6
Системы стохастического динамического поллинга
188
6.1
Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
цик6.2
Машинное обучение для несимметричной системы поллинга с
лическим опросом и шлюзовой дисциплиной обслуживания
190
. . .
6.3
Машинное обучение для системы поллинга с входящим потоком MAP, циклическим опросом и шлюзовой дисциплиной обслуживания
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
обучение
6.4
Машинное
для системы поллинга с адаптивным циклическим опросом . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
6.5
Машинное обучение для системы поллинга с входящим MAP
потоком и адаптивным опросом . . . . . . . . . . . . . . . . . . . 194
6.6
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 195
7
Оценка максимальной длины очереди по числу маркированных заявок
197
7.1
Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
7.2
Постановка задачи для системы массового обслуживания . . . . 200
7.3
Имитационное моделирование . . . . . . . . . . . . . . . . . . . . 201
7.4
Оценка максимальной длины очереди с помощью машинного
обучения
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
7.5
Корректирующий фактор на основе ряда Фурье . . . . . . . . . 206
7.6
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 209
8
Управляемые системы массового обслуживания
210
8.1
Оценка оптимальных порогов в неоднородных системах
. . . . 211
8.1.1
Математическая модель
. . . . . . . . . . . . . . . . . . . 212

Оглавление
viii
8.1.2
Эвристическое решение . . . . . . . . . . . . . . . . . . . . 218
8.1.3
Решение с помощью нейронной сети . . . . . . . . . . . . 221
8.1.4
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . 223
. . .
8.2
Оценка оптимальных порогов в системах с разделением приборов
224
8.2.1
Управляемый марковский процесс . . . . . . . . . . . . . 226
8.2.2
Оценка и прогнозирование оптимальных пороговых значений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.2.3
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . 236
8.3
Задача оптимального расписания для систем с параллельными
очередями
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
8.3.1
Математическая модель системы с параллельными очередями
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
8.3.2
Управляемый марковский процесс . . . . . . . . . . . . . 243
8.3.3
Имитационное моделирование по событиям для общей
модели
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
8.3.4
Архитектура нейронной сети
. . . . . . . . . . . . . . . . 251
8.3.5
Оптимизация политики управления на основе нейронной сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
8.3.6
Численный анализ
. . . . . . . . . . . . . . . . . . . . . . 257
8.3.7
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . 264
8.4
Обучение с подкреплением для дискретной оптимизации в задаче распределения ресурсов
. . . . . . . . . . . . . . . . . . . . 266
8.4.1
Управляемый марковский процесс с непрерывным временем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
8.4.2
Обучение с подкреплением для динамической оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.4.3
Метод случайного поиска для параметрической оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
8.4.4
Численные результаты и сравнительный анализ . . . . . 281
8.4.5
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . 283
9
Системы с расщеплением и слиянием заявок
284
9.1
Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
9.2
Постановка задачи исследования . . . . . . . . . . . . . . . . . . 286
9.3
Исследование характеристик системы с параллельным обслуживанием заявок
. . . . . . . . . . . . . . . . . . . . . . . . . . . 287
9.3.1
Цепь Маркова, описывающая процесс функционирования системы . . . . . . . . . . . . . . . . . . . . . . . . . . 287
9.3.2
Критерий существования стационарного режима . . . . . 289
9.3.3
Стационарные характеристики производительности системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
9.3.4
Распределение времени пребывания заявки в системе . . 293
9.4
Исследование систем общего вида . . . . . . . . . . . . . . . . . . 296
9.4.1
Описание имитационной модели системы общего вида
. 298
9.4.2
Описание модели машинного обучения
. . . . . . . . . . 299

Оглавление
ix
9.5
Результаты численного исследования . . . . . . . . . . . . . . . . 301
9.5.1
Проверка реализации метода Монте-Карло . . . . . . . . 301
9.5.2
Предсказание времени пребывания заявки с помощью
алгоритмов МО . . . . . . . . . . . . . . . . . . . . . . . . 303
9.5.3
Предсказание вероятности потери заявки с помощью
методов МО
. . . . . . . . . . . . . . . . . . . . . . . . . . 305
9.6
Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 308
10 Анализ надежности системы k-из-n
310
10.1 Введение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
10.2 Постановка задачи и обозначения . . . . . . . . . . . . . . . . . . 312
10.3 Стационарные вероятности состояний системы . . . . . . . . . . 313
10.4 Результаты имитационного моделирования
. . . . . . . . . . . . 317
10.5 Модель искусственной нейронной сети . . . . . . . . . . . . . . . 321
10.5.1 Построение и настройка нейронной сети . . . . . . . . . . 323
10.5.2 Обучение сети . . . . . . . . . . . . . . . . . . . . . . . . . 326
10.6 Сравнительный анализ результатов аналитики, имитационного
моделирования и предсказания нейронной сети . . . . . . . . . . 328
10.7 Итоговые замечания
. . . . . . . . . . . . . . . . . . . . . . . . . 330
Приложение
331
10.A Псевдокод процесса моделирования системы ⟨GIk<n|GI|1⟩. . . 331
Литература
333

x