Марковские системы массового обслуживания

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

Definition

Марковская система массового обслуживания — это система обслуживания, в которой клиенты прибывают в соответствии с пуассоновским процессом и требуют независимого экспоненциального времени обслуживания, так что число клиентов в системе развивается как цепь Маркова с непрерывным временем типа «рождение-гибель» с явными стационарными распределениями и распределениями времени ожидания.

Scope

Эта тема охватывает нотацию Кендалла для систем массового обслуживания, одноканальную систему M/M/1 и её геометрическое стационарное распределение, многоканальные системы M/M/c и системы с потерями, формулы Эрланга B и C, стабильность и интенсивность трафика, а также вывод средней длины очереди, времени ожидания и величин занятого периода из базового процесса рождения-гибели.

Core questions

• Как система M/M/1 возникает как процесс рождения-гибели и каково её стационарное распределение?
• Какое условие на интенсивность трафика обеспечивает стабильность очереди?
• Как получаются средняя длина очереди и время ожидания, и как применяется закон Литтла?
• Как несколько серверов и конечная ёмкость изменяют формулы Эрланга?

Key theories

Стационарное распределение и стабильность M/M/1

Число клиентов в системе M/M/1 имеет геометрическое стационарное распределение с параметром, равным интенсивности трафика (отношению скорости поступления к скорости обслуживания), и очередь стабильна именно тогда, когда это отношение меньше единицы.

Формулы потерь и задержек Эрланга

Для многоканальных систем формула Эрланга B даёт вероятность блокировки в системе с потерями, а формула Эрланга C даёт вероятность ожидания в системе с задержкой; обе формулы выводятся из уравнений баланса рождения-гибели и являются центральными для планирования пропускной способности.

Clinical relevance

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

History

Эрланг вывел формулы потерь и задержек для телефонного трафика между 1909 и 1917 годами, Кендалл ввёл систематическую нотацию поступления/обслуживания/сервера и анализ вложенных цепей в 1953 году, а трактат Кляйнрока 1970-х годов применил теорию к компьютерным и коммуникационным сетям.

Key figures

• Agner Krarup Erlang
• David Kendall
• Leonard Kleinrock

Seminal works

• kleinrock1975

Frequently asked questions

Что означает M/M/1?

В нотации Кендалла первая M обозначает марковский (пуассоновский) поток поступлений, вторая M обозначает экспоненциальное время обслуживания, а 1 обозначает один сервер.

Когда марковская система массового обслуживания стабильна?

Когда интенсивность трафика (скорость поступления, делённая на общую скорость обслуживания) меньше единицы; в противном случае очередь растёт неограниченно, и стационарное распределение не существует.