Теория массового обслуживания

Теория массового обслуживания (Queueing theory; ТМО, теория очередей) — раздел теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящих из нее, длительности ожидания и длины очередей. В теории массового обслуживания используются методы теории вероятностей и математической статистики.

Сокращение ожидания обычно требует вложений — дополнительных станков, операторов, линий связи. Модели массового обслуживания позволяют заранее оценить, как такие вложения повлияют на время ожидания, и поэтому применяются при проектировании производственных, транспортных и складских систем, систем связи и обработки информации: при выборе их компоновки, мощностей и правил управления¹. Теория стала областью прикладной теории вероятностей, ее результаты используются в исследовании операций, информатике, телекоммуникациях, организации дорожного движения, теории надежности².

Потоки событий

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

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

Теория потока однородных событий легла в основу ТМО.

Важнейший частный случай — пуассоновский (простейший) поток (Poisson process) с интенсивностью λ. Интервалы между событиями в нем независимы и распределены экспоненциально со средним 1/λ, а число событий за время t имеет распределение Пуассона со средним λt. Вероятность события в малом интервале Δt примерно равна λΔt независимо от прошлого, т. е. события происходят «совершенно случайно» во времени. Объединение двух независимых пуассоновских потоков снова дает пуассоновский поток. Такой поток часто хорошо описывает реальные потоки заявок, поэтому им моделируют поступление клиентов в системы обслуживания и спрос в системах управления запасами³.

Экспоненциальное распределение обладает отсутствием последействия (memoryless property): оставшееся время до события не зависит от того, сколько его уже ждали. Это свойство сильно упрощает анализ моделей с пуассоновским входящим потоком и экспоненциальным обслуживанием³.

Система массового обслуживания

Система массового обслуживания (СМО) описывается следующими характеристиками⁴²:

Входящий поток требований — обычно задается распределением интервалов между поступлениями, которые считаются независимыми и одинаково распределенными. Требования могут поступать по одному или группами.
Поведение клиентов — готовы ли они ждать сколько угодно или покидают очередь, не дождавшись обслуживания (как звонящие в колл-центр).
Время обслуживания — обычно независимые одинаково распределенные случайные величины, не зависящие от входящего потока: детерминированные, экспоненциальные или произвольные.
Дисциплина обслуживания — порядок выбора следующего требования: в порядке поступления (FIFO, first in — first out), в обратном порядке (LIFO), в случайном порядке, по приоритетам (с прерыванием обслуживания или без), разделение процессора (processor sharing), при котором мощность делится между всеми требованиями поровну.
Число каналов обслуживания (приборов) — один или несколько.
Вместимость системы — ограничено ли число требований, которые могут в ней находиться; если места нет, новое требование теряется.

Обозначения Кендалла

Для краткого описания СМО используются обозначения, предложенные Д. Кендаллом (D. G. Kendall): A/B/c, где A — распределение интервалов между поступлениями, B — распределение времени обслуживания, c — число каналов. Буква M обозначает экспоненциальное распределение (от Markovian, или memoryless), D — детерминированное время, G — произвольное распределение⁴⁵.

Расширенная запись A/B/c/K/n/D добавляет вместимость системы K (включая требования на обслуживании), численность источника требований n и дисциплину обслуживания D. Если вместимость и источник бесконечны, а дисциплина — FIFO, последние поля опускаются⁵. Примеры:

M/M/1 — пуассоновский входящий поток, экспоненциальное время обслуживания, один канал;
M/G/c — пуассоновский поток, произвольное время обслуживания, c каналов;
M/D/1 — пуассоновский поток, постоянное время обслуживания, один канал;
M/M/1/N — то же, что M/M/1, но в системе может находиться не более N требований⁴.

Показатели эффективности

Цель анализа СМО — найти вероятностные характеристики (распределение, среднее, дисперсию) числа требований в системе и в очереди, времени ожидания и времени пребывания требования в системе, загрузки, периодов занятости и простоя каналов². Время пребывания равно времени ожидания плюс время обслуживания. Распределения удается найти в основном для простых, марковских моделей; для остальных обычно находят средние значения или преобразования распределений².

Коэффициент загрузки (occupation rate, server utilization) одноканальной системы ρ = λE(B), где λ — интенсивность входящего потока, E(B) — среднее время обслуживания. Это доля времени, когда канал занят. Чтобы очередь не росла неограниченно, нужно ρ < 1; при ρ = 1 средняя длина очереди тоже неограниченно растет, если в системе есть хоть какая-то случайность. Для системы с c каналами условие — λE(B) < c, а загрузка одного канала равна λE(B)/c⁴.

Формула Литтла

Формула Литтла (Little’s law) связывает средние показатели любой устойчивой системы:

E(L) = λ · E(S),

где E(L) — среднее число требований в системе, E(S) — среднее время пребывания требования в системе, λ — средняя интенсивность поступления требований. Строгое доказательство опубликовал Дж. Литтл в 1961 году⁴⁶.

Интуитивно формулу можно объяснить так. Пусть каждое требование платит единицу за каждую единицу времени пребывания в системе. Если плата взимается непрерывно, система в среднем получает E(L) в единицу времени. Если всю плату взимать при уходе, то в установившемся режиме в единицу времени уходит в среднем λ требований, каждое платит в среднем E(S), и доход равен λE(S). Доход в обоих случаях один и тот же⁴.

Формулу можно применять к любой части системы. Для очереди без канала она дает связь средней длины очереди и среднего времени ожидания: E(L_q) = λ · E(W). Для одного канала она дает ρ = λE(B): среднее число требований на обслуживании равно загрузке⁴.

Система M/M/1

В простейшей модели M/M/1 требования поступают пуассоновским потоком с интенсивностью λ и обслуживаются одним каналом за экспоненциальное время со средним 1/μ; ρ = λ/μ < 1. Для нее известны средние показатели⁷:

среднее число требований в системе E(L) = ρ / (1 − ρ);
среднее время пребывания E(S) = (1/μ) / (1 − ρ);
средняя длина очереди E(L_q) = ρ² / (1 − ρ).

Все эти величины неограниченно растут при приближении ρ к единице. Такое поведение вызвано случайностью входящего потока и обслуживания и характерно почти для всех систем массового обслуживания⁷.

Пример для иллюстрации: если в мастерскую поступает в среднем 8 заказов в час, а мастер выполняет в среднем 10 заказов в час, то ρ = 0,8, в мастерской в среднем находится 0,8 / 0,2 = 4 заказа, а заказ проводит в ней в среднем 0,1 / 0,2 = 0,5 часа. Если поток вырастет до 9 заказов в час (ρ = 0,9), среднее время пребывания удвоится — до 1 часа, хотя загрузка выросла всего на 10 процентных пунктов.

Система с отказами Эрланга

В системе M/M/c/c (система с отказами, Erlang loss system) c каналов и нет мест для ожидания: требование, заставшее все каналы занятыми, теряется. Это старейшая модель теории; с ее изучения началась теория трафика, или теория перегрузок⁸. Вероятность потери требования дается формулой Эрланга (Erlang’s loss formula):

B(c, ρ) = (ρᶜ / c!) / Σₙ₌₀ᶜ (ρⁿ / n!), где ρ = λE(B).

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

Применение

Типичные задачи, которые решаются методами ТМО¹:

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

История

Первые задачи теории возникли в телефонии. Датский математик А. К. Эрланг в 1908 году начал работать в Копенгагенской телефонной компании и в 1909 году опубликовал работу «Теория вероятностей и телефонные разговоры», где показал, что вызовы, поступающие случайно, подчиняются распределению Пуассона. В 1917 году он опубликовал формулы для вероятности потери вызова и времени ожидания, которые вскоре стали использовать телефонные компании многих стран¹⁰. В 1946 году единицу телефонной нагрузки назвали в его честь эрлангом¹⁰. Работы Эрланга побудили инженеров и математиков применять вероятностные методы к задачам об очередях².

В 1953 году Д. Кендалл опубликовал в Annals of Mathematical Statistics работу о случайных процессах в теории очередей¹¹, а в 1961 году Дж. Литтл в журнале Operations Research — доказательство формулы L = λW⁶.

Литература

Erlang A. K. The theory of probabilities and telephone conversations // Nyt Tidsskrift for Matematik B. — 1909. — Vol. 20. — P. 33–39.
Kendall D. G. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain // The Annals of Mathematical Statistics. — 1953. — Vol. 24, № 3. — P. 338–354. — DOI: 10.1214/aoms/1177728975.
Little J. D. C. A Proof for the Queuing Formula: L = λW // Operations Research. — 1961. — Vol. 9, № 3. — P. 383–387. — DOI: 10.1287/opre.9.3.383.
Adan I., Resing J. Queueing Systems. — Eindhoven: Eindhoven University of Technology, 2015.
Sztrik J. Basic Queueing Theory. — Debrecen: University of Debrecen, Faculty of Informatics, 2012, 2021.

Ссылки

Agner Krarup Erlang — биография в архиве MacTutor History of Mathematics, Университет Сент-Эндрюс

См. также

Adan I., Resing J. Queueing Systems. 2015. Глава 1 «Introduction». ↩ ↩²
Sztrik J. Basic Queueing Theory. 2012, 2021. Глава 1 «Fundamental Concepts of Queueing Theory». ↩ ↩² ↩³ ↩⁴ ↩⁵
Adan I., Resing J. Queueing Systems. 2015. Разделы 2.4.3 «Exponential distribution» и 2.6 «Poisson process». ↩ ↩²
Adan I., Resing J. Queueing Systems. 2015. Глава 3 «Queueing models and some fundamental relations». ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷
Sztrik J. Basic Queueing Theory. 2012, 2021. Раздел 1.2 «Kendall’s Notation». ↩ ↩²
Little J. D. C. A Proof for the Queuing Formula: L = λW // Operations Research. 1961. Vol. 9, № 3, p. 383–387. ↩ ↩²
Adan I., Resing J. Queueing Systems. 2015. Глава 4 «M/M/1 queue», раздел 4.3. ↩ ↩²
Sztrik J. Basic Queueing Theory. 2012, 2021. Раздел 2.6 «The M/M/n/n Queue, Erlang-Loss System». ↩
Adan I., Resing J. Queueing Systems. 2015. Глава 11, раздел о модели M/M/c/c и формуле Эрланга. ↩ ↩²
O’Connor J. J., Robertson E. F. Agner Krarup Erlang. MacTutor History of Mathematics Archive, University of St Andrews. ↩ ↩²
Kendall D. G. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain // The Annals of Mathematical Statistics. 1953. Vol. 24, № 3, p. 338–354. ↩