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 -канальной СМО с отказами

.

При этом ; ; .

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

.

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

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

.

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

.

При этом .

Пример № 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, т. е. нужно максимизировать прибыль в единицу времени.