N-канальная СМО с отказами (задача Эрланга)

Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале 20 века датским математиком Эрлангом.

Пусть в системе имеется n каналов, на которые поступает поток заявок с интенсивностью l. Поток обслуживаний имеет интенсивность m. Заявка, заставшая систему занятой, сразу же покидает ее.

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

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

- S₀ – в СМО нет ни одной заявки;

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

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

- . . .

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

Граф состояний СМО представлен на рис. 4.6.

Из состояния S₀ в состояние S₁ систему переводит поток заявок с интенсивностью l (как только приходит заявка, система переходит из S₀ в S₁). Если система находилась в состоянии S₁ и пришла еще одна заявка, то она переходит в состояние S₂ и т. д.

Рис. 4.6. Граф состояний N-канальной СМО с отказами

Пусть система находится в состоянии S₁ (работает один канал). Он производит m обслуживаний в единицу времени. Поэтому дуга перехода из состояния S₁ в состояние S₀ нагружена интенсивностью m. Пусть теперь система находится в состоянии S₂ (работают два канала). Чтобы ей перейти в S₁, нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равна 2m и т. д.

Выходные характеристики (характеристики эффективности) данной СМО определяются следующим образом.

Абсолютная пропускная способность

, шт/ед. времени,

где n – количество каналов СМО; р₀ – вероятность нахождения СМО в начальном состоянии, когда все каналы свободны (финальная вероятность нахождения СМО в состоянии S₀).

Для того, чтобы написать формулу для определения р₀, рассмотрим рис. 4.7. Граф, представленный на рисунке, называют еще графом состояний для схемы «гибели и размножения».

Рис. 4.7. Граф состояний для схемы «гибели и размножения»

Вероятность того, что СМО находится в состоянии S₁, когда один канал занят

.

Вероятность того, что СМО находится в состоянии S₂, т.е. когда два канала заняты

.

Вероятность того, что СМО находится в состоянии S_n, т.е. когда все каналы заняты

.

Вероятность нахождения СМО в начальном состоянии р₀

.

Применительно к n-канальной СМО с отказами

.

При этом ; ; .

Относительная пропускная способность

.

Абсолютная пропускная способность А = lQ.

Вероятность отказа

.

Среднее число занятых каналов (среднее число заявок, обслуживаемых одновременно)

.

При этом .

Пример № 1. Имеется технологическая система (участок), состоящая из трех одинаковых станков. В систему поступают для обработки детали в среднем через 0,5 часа ( ). Среднее время изготовления одной детали = 0,6 ч. Если при поступлении заявки на изготовление детали все станки заняты, то деталь направляется на другой участок таких же станков. Необходимо найти финальные вероятности состояний системы и характеристики (показатели эффективности) данной СМО.

Интенсивность потока заявок

,

т. е. в среднем две заявки на обработку деталей в час.

.

Граф состояний системы представлен на рис. 4.8.

Рис. 4.8

Возможные состояния системы: S₀ – в СМО (на участке) нет ни одной заявки; S₁ – в СМО (на участке) одна заявка; S₂ – в СМО (на участке) две заявки; S₃ – в СМО (на участке) три заявки (заняты все три станка).

Вероятность того, что все станки свободны:

.

Вероятность того, что один станок занят

.

Вероятность того, что два станка заняты

.

Вероятность того, что все три станка заняты

.

Абсолютная пропускная способность

дет./ч.

Относительная пропускная способность

;

Вероятность отказа

.

Среднее число занятых каналов (станков)

.

Таким образом, в среднем в этой системе обрабатывается 1,82 дет./ч (примерно 91 % направляемых деталей), при этом примерно 9 % деталей направляется для обработки на другие участки. Одновременно в среднем работает в основном один станок ( ). Но из-за случайных характеристик потока заявок иногда работают одновременно все три станка (р_з = 0,09), отсюда 9 % отказов.

Пример № 2. Пусть , Р_отк £ 0,03 (т. е. £ 3 %). Найти оптимальное число каналов n_опт, обеспечивающее минимум затрат на систему, при условии достижения требуемого уровня ее безотказной работы.

Целевая функция (затраты на СМО) запишется:

y = cn ® min,

где c – постоянная величина.

Решение:

;

Р_отк £ 0,03 Þ £ 0,03 Þ .

По другому можно записать:

.

Последнее равенство начинает выполняться при n_опт = 4, т. к.

< 33; < 33;

< 33;

> 33.

Пример № 3. Для условий предыдущей задачи определить оптимальное число каналов, обеспечивающее максимум прибыли от эксплуатации СМО в единицу времени.

Содержание каждого канала в единицу времени обходится в какую-то сумму. Чем больше каналов, тем больше затраты на эксплуатацию СМО. Вместе с тем, чем больше каналов (при l и m = const), тем больше доля обслуживаемых заявок. А каждая обслуженная заявка дает определенный доход в единицу времени. При увеличении числа каналов растут доходы D и расходы на эксплуатацию R. Чтобы решить эту задачу, необходимо найти оптимальное число каналов n_опт, обеспечивающее максимум целевой функции P = D – R ® max, т. е. нужно максимизировать прибыль в единицу времени.