ФЭНДОМ


Ботва

Незаконченная ботва



Это незаконченная статья. Автор отправился ботать или спать.

Или... зависит от автора.

Наверняка он будет благодарен, если вы найдёте в себе силы продолжить статью.


Математические модели простейших систем массового обслуживанияПравить

Одноканальная СМО с отказами  http://gendocs.ru/v26445/?cc=11    с середины страницыПравить

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

Найти: абсолютную и относительную пропускную способность СМО и вероятность того, что заявка, пришедшая в момент времени t, получит отказ.

Система при любом t > 0 может находиться в двух состояниях: S0 – канал свободен; S1 – канал занят. Переход из S0 в S1 связан с появлением заявки и немедленным началом ее обслуживания. Переход из S1 в S0 осуществляется, как только очередное обслуживание завершится.

11

Граф состояний одноканальной СМО с отказами

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

12

где λ – интенсивность потока заявок (величина, обратная среднему промежутку времени между поступающими заявками - {C}{C});

μ – интенсивность потока обслуживаний (величина, обратная среднему времени обслуживания {C}{C})

Относительная пропускная способность (средняя доля заявок, обслуживаемых системой):

{C}{C}

Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной):

{C}{C}

Очевидны следующие соотношения: {C}{C} и {C}{C}.

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

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

Дано: в системе имеется n – каналов, на которые поступает поток заявок с интенсивностью {C}{C}. Поток обслуживаний имеет интенсивность {C}{C}. Заявка, заставшая систему занятой, сразу же покидает ее.

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

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

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

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

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

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

{C}{C}

Рис.5 Граф состояний для n – канальной СМО с отказами

Почему граф состояний размечен именно так? Из состояния S0 в состояние S1 систему переводит поток заявок с интенсивностью {C}{C}(как только приходит заявка, система переходит из S0 в S1). Если система находилась в состоянии S1 и пришла еще одна заявка, то она переходит в состояние S2 и т.д.

Почему такие интенсивности у нижних стрелок (дуг графа)? Пусть система находится в состоянии S1 (работает один канал). Он производит {C}{C}обслуживаний в единицу времени. Поэтому дуга перехода из состояния S1 в состояние S0 нагружена интенсивностью {C}{C}. Пусть теперь система находится в состоянии ^' S2(работают два канала). Чтобы ей перейти в S1, нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равна {C}{C}и т.д.

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

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

{C}{C}

где n – количество каналов СМО;

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

{C}{C}

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

Для того, чтобы написать формулу для определения {C}{C}, рассмотрим рис.6

Граф, представленный на этом рисунке, называют еще графом состояний для схемы «гибели и размножения». Напишем сначала для {C}{C}общую формулу (без доказательства): {C}{C}

Кстати, остальные финальные вероятности состояний СМО запишутся следующим образом.

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

{C}{C}

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

{C}{C}

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

{C}{C}

Теперь для n – канальной СМО с отказами

{C}{C}

При этом {C}{C}{C}{C}{C}{C}

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

{C}{C}

Напомним, что это средняя доля заявок, обслуживаемых системой. При этом {C}{C};{C}{C}.

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

{C}{C}

Напомним, что это вероятность того, что заявка покинет СМО необслуженной. Очевидно, что {C}{C}.

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

{C}{C}

При этом {C}{C}.

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

{C}{C},

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

{C}{C}.

Граф состояний системы представлен на рис.7 {C}{C} Рис.7Граф состояний для рассматриваемого примера Возможные состояния системы:

S0 – в СМО (на участке) нет ни одной заявки;

S1 – в СМО (на участке) одна заявка;

S2 – в СМО (на участке) две заявки;

S3 – в СМО (на участке) три заявки (заняты все три станка).

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

{C}{C}

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

{C}{C}

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

{C}{C}

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

{C}{C}

{C}{C}

{C}{C}

{C}{C}

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

Возможные постановки задач оптимизации n – канальных СМО с отказами

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

Пример. Пусть {C}{C}. Целевая функция (затраты на СМО) запишется: {C}{C}, где {C}{C}. Найти: {C}{C}. Решение:

{C}{C}

{C}{C}

{C}{C}

Или

{C}{C}.

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

{C}{C}.

Последнее равенство начинает выполняться при {C}{C}, т.к.

{C}{C};{C}{C};

{C}{C};

{C}{C}.

2.Определить оптимальное число каналов, обеспечивающее максимум прибыли от эксплуатации СМО в единицу времени.

         Содержание каждого канала в единицу времени обходится в какую–то сумму. Чем больше каналов, тем больше затраты на эксплуатацию СМО. Вместе с тем, чем больше каналов (при {C}{C}и {C}{C}), тем больше доля обслуживаемых заявок. А каждая обслуженная заявка дает определенный (пусть постоянный) доход в единицу времени. При увеличении числа каналов растут доходы D, но растут и расходы на эксплуатацию СМО – R. Чтобы решить эту задачу, необходимо найти оптимальное число каналов {C}{C}, обеспечивающее максимум целевой функции {C}{C}, т.е. нужно максимизировать прибыль в единицу времени.

http://gendocs.ru/v26445/?cc=11