Queueing theory
-
История и происхождение
- Теория очередей возникла из исследований Агнером Крарупом Эрлангом в 1909 году.
- Эрланг моделировал систему входящих звонков на Копенгагенской телефонной станции.
- Идеи Эрланга легли в основу телетрафика и нашли применение в различных областях, включая телекоммуникации, транспорт, вычислительную технику, управление проектами и промышленную инженерию.
-
Основные понятия и определения
- Теория очередей изучает очереди и время ожидания.
- Модели очередей строятся для предсказания длины очереди и времени ожидания.
- Теория очередей считается частью исследования операций, так как результаты используются для принятия бизнес-решений.
-
Основные модели очередей
- Односерверная система ожидания: один сервер обслуживает клиентов, которые могут ждать в очереди.
- Многосерверная система ожидания: несколько серверов обслуживают клиентов, которые могут ждать в очереди.
-
Моделирование и анализ
- Модели очередей описываются с помощью процессов рождения и смерти.
- Балансовые уравнения описывают вероятности состояний системы.
- Kendall’s notation используется для описания моделей очередей.
-
Примеры и приложения
- Пример анализа M/M/1 очереди: один сервер обслуживает клиентов с экспоненциальным распределением времени ожидания и обслуживания.
- Теория очередей применяется в различных областях, включая медицину, транспорт, телекоммуникации и управление проектами.
-
Вклад в теорию очередей
- Докторская диссертация в Массачусетском технологическом институте в 1962 году
- Публикация книги в 1964 году
- Теоретические работы в начале 1970-х годов
-
Методы и подходы
- Матричный геометрический метод и матричный аналитический методы
- Системы с coupled orbits в применении к беспроводным сетям и обработке сигналов
-
Современные приложения
- Разработка продуктов с пространственно-временным существованием
- Проблемы с метриками производительности для M/G/k очереди остаются открытыми
-
Дисциплины обслуживания
- Различные политики планирования на узлах очередей
- Стохастические процессы отказов серверов и периоды настройки
- Поведение клиентов: отказ от очереди, переключение между очередями, уход из очереди
-
Сети очередей
- Сети очередей с маршрутизацией клиентов
- Простейшие сети: тандемные очереди
- Джексон сети: стационарное распределение и анализ средних значений
- BCMP сети: стационарное распределение и алгоритм Бузена
-
Алгоритмы маршрутизации
- Max-weight scheduling: оптимальный алгоритм для одноузловых сетей
- Backpressure routing: оптимальный алгоритм для многоузловых сетей
-
Лимиты и приближения
- Лимиты среднего поля: приближение эмпирической меры при большом количестве очередей
- Тяжелая нагрузка/диффузионные приближения: аппроксимация длины очереди
- Жидкостные пределы: непрерывные модели для доказательства стабильности
-
Приложения
- Использование в компьютерных сетях и информационных технологиях
- Оптимизация систем для повышения производительности и эффективности
- Применение в повседневной жизни: оптимизация очередей в супермаркетах и общественном транспорте
-
Основные понятия
- Процесс прибытия: моделирование с помощью стохастических процессов
- Процесс обслуживания: ключевые метрики производительности
- Эффективность систем: средняя длина очереди, среднее время ожидания, пропускная способность