Задачи теории массового обслуживания. Задача Эрланга

Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания;

эта задача возникла из практических нужд телефонии и была решена в начале нашего века датским математиком Эрлантом. Задача ставится так: имеется п каналов (линий связи), на которые поступает поток заявок с интенсивностью λ. Поток обслуживании имеет интенсивность μ (величина, обратная среднему времени обслуживания t _об). Найти финальные вероятности состояний СМО, а также характеристики ее эффективности:

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

Q — относительную пропускную способность, т. е. среднюю долю пришедших заявок, обслуживаемых системой;

Р _отк — вероятность отказа, т. е. того, что заявка покинет СМО не обслуженной;

k — среднее число занятых каналов.

Решение. Состояния системы S (СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):

S₀ — в СМО нет ни одной заявки,

S₁ — в СМО находится одна заявка (один канал занят, остальные свободны),

S_k — в СМО находится k заявок (k каналов заняты, остальные свободны),

S_n — в СМО находится п заявок (все n каналов заняты).

Граф состояний СМО соответствует схеме гибели в размножения (рис. 20.1). Разметим этот граф — проставим у стрелок интенсивности потоков событий. Из S ₀ в S₁ систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S₀ в S₁). Тот же поток заявок переводит

систему из любого левого состояния в соседнее правое (см. верхние стрелки на рис. 20.1).

Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии S ₁ (работает один канал). Он производит μ обслуживании в единицу времени. Проставляем у стрелки S ₁ → S ₀ интенсивность μ. Теперь представим себе, что система находится в состоянии S₂ (работают два канала). Чтобы ей перейти в S₁, нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами — kμ. Проставляем эти интенсивности у нижних стрелок на рис. 20.1.

А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:

Члены разложения будут представлять собой коэффициенты при р₀ в выражениях для p₁

Заметим, что в формулы (20.1), (20.2) интенсивности λ и μ входят не по отдельности, а только в виде отношения λ/μ. Обозначим

λ/μ = ρ (20.3)

и будем называть величину р «приведенной интенсивностью потока заявок». Ее смысл—среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:

(20.4)

(20.5)

Формулы (20.4), (20.5) для финальных вероятностей состояний называются формулами Эрланга — в честь основателя теории массового обслуживания. Большинство других формул этой теории (сегодня их больше, чем грибов в лесу) не носит никаких специальных имен.

Таким образом, финальные вероятности найдены. По ним мы вычислим характеристики эффективности СМО. Сначала найдем Р _отк. — вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все п каналов были заняты, значит,

Р_отк = р_n = . (20.6)

Отсюда находим относительную пропускную способность — вероятность того, что заявка будет обслужена:

Q = 1 – P_отк. = 1 - (20.7)

Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ, на Q:

A = λQ = λ . (20.8)

Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0, 1,..., п и вероятностями этих значений р₀ р₁,..., р_n:

k = 0 · р₀ + 1 · p₁ + 2 · р₂ +... + п · р_n.

Подставляя сюда выражения (20.5) для р _k, (k = 0, 1,..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это — не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый i.шал в единицу времени обслуживает в среднем |л заявок. Значит, среднее число занятых каналов равно

k = A/μ, (20.9)

или, учитывая (20.8),

k = (20.10)

Рекомендуем читателю самостоятельно решить пример. Имеется станция связи с тремя каналами (n = 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t _об = 2 (мин.), все потоки событий (как и во всем этом параграфе) — простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P _отк, k. На всякий случай сообщаем ответы: p ₀ = 1/13, p ₁ = 3/13, p ₂ = 9/26, р₃ = 9/26 ≈ 0,346,

А ≈ 0,981, Q ≈ 0,654, P _отк ≈ 0,346, k ≈ 1,96.

Из ответов видно, между прочим, что наша СМО в значительной мере перегружена: из трех каналов занято в среднем около двух, а из поступающих заявок около 35% остаются не обслуженными. Предлагаем читателю, если он любопытен и неленив, выяснить: сколько потребуется каналов для того, чтобы удовлетворить не менее 80% поступающих заявок? И какая доля каналов при этом будет простаивать?

Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит — увеличение доходов или расходов? Это зависит от условий операции, от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же «неленивому и любопытному читателю» придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.