Многоканальная СМО с отказами

Содержание

 

ВВЕДЕНИЕ

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

Лучшей иллюстрацией области применения имитационного моделирования являются системы массового обслуживания. В терминах СМО описываются многие реальные системы: вычислительные системы, узлы сетей связи, магазины, производственные участки – любые системы, где возможны очереди и отказы в обслуживании. Системы массового обслуживания отличаются высокой наглядностью отображения моделируемых объектов и вследствие этого сравнительной простотой перехода от реальных объектов к соответствующим СМО.

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

Для достижения поставленной цели выделим основные задачи:

- подробное описание многоканальной СМО с отказами;

- выбор контрольного примера и постановка задачи;

- определение алгоритма решения;

- создание имитационной модели в среде MATLAB (Simulink);

- анализ результатов и обоснование выбора оптимального количества каналов для исследуемой СМО

 

1 Математическое описание метода

1.1 Общие сведения о системах  массового обслуживания

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

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

Будем рассматривать СМО с марковским случайным процессом, когда вероятность состояния СМО в будущем зависит только от ее настоящего состояния и не зависит от прошлого (процесс без последействия или без памяти). Условие марковского случайного процесса необходимо, чтобы все потоки событий, при которых система переходит из одного состояния в другое (потоки заявок, потоки обслуживания и т.д.), были пуассоновскими. Пуассоновский поток событий обладает рядом свойств, в том числе свойствами отсутствия последействия, ординарности, стационарности.

В простейшем пуассоновском потоке событий случайная величина распределена по показательному закону:

,     (1.1)

где λ – интенсивность потока.

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

Основой СМО является определенное число обслуживающих устройств - каналов обслуживания.

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

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

Основными элементами СМО являются:

1. входной поток заявок;
2. очередь;
3. каналы обслуживания;
4. выходной поток заявок (обслуженные заявки).

Эффективность функционирования СМО определяется ее пропускной способностью — относительным числом обслуженных заявок.

По числу каналов n все СМО разделяются на одноканальные (n = 1) и многоканальные (n > 1). Многоканальные СМО могут быть как однородными (по каналам), так и разнородными (по продолжительности обслуживания заявок).

По дисциплине обслуживания различаются три класса СМО:

1. СМО с отказами (нулевое ожидание или явные потери). "Отказная" заявка вновь поступает в систему, чтобы ее обслужили (например, вызов абонента через АТС).
2. СМО с ожиданием (неограниченное ожидание или очередь). При занятости системы заявка поступает в очередь и, в конце концов, будет выполнена (торговля, сфера бытового и медицинского обслуживания).
3. СМО смешанного типа (ограниченное ожидание). Имеется ограничение на длину очереди (сервис по обслуживанию автомобилей). Ограничение на время пребывания заявки в СМО (ПВО, особые условия обслуживания в банке) также может рассматриваться.

Различают открытые (поток заявок не ограничен), упорядоченные (заявки обслуживаются в порядке их поступления) и однофазные (однородные каналы выполняют одну и ту же операцию) СМО.

Эффективность работы систем массового обслуживания характеризуют показатели, которые можно разбить на три групп:

1. Группа показателей эффективности использования СМО:

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

- относительная пропускная способность (Q) - отношение абсолютной пропускной способности к среднему числу заявок, поступивших в систему за единицу времени;

- средняя продолжительность периода занятости СМО ( );

- интенсивность нагрузки (ρ) показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость СМО;

- коэффициент использования СМО - средняя доля времени, в течение которого система занята обслуживанием заявок.

2. Показатели качества обслуживания заявок:

- среднее время ожидания заявки в очереди ( );

- среднее время пребывания (обслуживания) заявки в СМО ( );

- вероятность отказа заявки в обслуживании без ожидания ( );

- вероятность немедленного приема заявки ( );

- закон распределения времени ожидания заявки в очереди в СМО;

- среднее число заявок в очереди ( );

- среднее число заявок, находящихся в СМО ( ).

3. Показатели эффективности функционирования пары "СМО - потребитель" (вся совокупность заявок или их источник, например средний доход в единицу времени от СМО). Эта группа полезна, когда доход от СМО и затраты на ее обслуживание измеряются в одних и тех же единицах, и отражает специфику работы СМО.

 

1.2 Многоканальные СМО с отказами

Система M/M/n/0 представляет собой n- линейную СМО с r местами ожидания (r=0), в которую поступает пуассоновский поток интенсивности , а времена обслуживания заявок независимы и при этом время обслуживания каждой заявки на любом приборе распределено по экспоненциальному закону с параметром . В случае, когда , заявка, поступившая в переполненную систему (т.е. когда заняты все приборы и все места ожидания), теряется и вновь в нее не возвращаются. Система M/M/n/r также относится к экспоненциальным СМО.

Уравнения, описывающие распределение заявок в системе

Рассматривая -число заявок в системе в момент t, нетрудно показать, что процесс является однородным Марковским процессом с множеством состояний . Ниже мы покажем, что процесс представляет собой ПРГ.

Выпишем систему дифференциальных уравнений Колмогорова. Для этого рассмотрим моменты t и . Предполагая, что в момент t процесс v(t) пребывает в состоянии i, определим, куда он может попасть в момент , и найдем вероятности его переходов за время . Здесь возможны три случая.

А. i<n. В этом случае все находящиеся в системе заявки обслуживаются на приборах (если i=0- заявок в системе вообще нет). Вероятность того, что за время процесс не выйдет из состояния i равна произведению вероятности не поступления заявки за время на вероятность того, что за это время не обслужится ни одна из i заявок, т.е. равна . Вероятность перехода за время в состояние i+1 равна - вероятности поступления заявки в систему. Наконец поскольку каждый прибор закончит за время обслуживание находящейся в нем заявки с вероятностью , а таких приборов i, то вероятность перехода в состояние i-1 равна . Остальные переходы имеют вероятность .

Б. n≤i<n+r. Этот случай отличается от первого тем, что обслуживаются ровно n заявок, т.е. все приборы заняты. Значит, вероятность через время остаться в состоянии i равна , перейти в состояние i-1 за это же время -

Таким образом, мы фактически доказали, что процесс является процессом рождения и гибели с интенсивностями при при и при .

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

,        ,

,   .

Если же , то, что очевидно последнего выражения не будет, а в предпоследнем индекс i может принимать значения i=n,n+1,… .

Вычитая теперь из обеих частей равенства, деля на и переходя к пределу

 при  , получаем систему дифференциальных уравнений:     ,           ,      , (1.2)     .

Стационарное распределение очереди

В случае конечного r, например  r=0, процесс является эргодическим. Также он будет эргодическим в случае при выполнении условия, о котором будет сказано ниже. Тогда из (1) при получаем, что стационарные вероятности состояний pi  удовлетворяют систему уравнений:

,           ,   (1.3)     ,        .

Поясним теперь вывод системы уравнений (1.3), исходя из принципа глобального баланса. Так, например, согласно диаграмме переходов для фиксированного состояния i, , имеем, что суммарные потоки вероятностей входящий в состояние i и выходящий из него равны, соответственно, и .

l  l      l      l          l   l

m  2m      3m    (i-1)m             (i+1)m

 

l     l   l       l           l   l l

(i+1)m  (i+2)m (n-1)m       nm          nm  nm nm

Рисунок 1 Диаграмма переходов

Исходя теперь из принципа локального баланса, что баланс потоков вероятностей между состояниями i и i+1 отражается равенствами :         ,           ,   (1.4)  являющимися уравнениями локального баланса для данной СМО. Проверка справедливости равенств (1.4) производится непосредственным суммированием системы уравнений (1.3) по i при i=0,1,…,n+r-1.

Из соотношения (1.4), выражая рекуррентно вероятности через ,

 

 

 

получаем:   

где , а определяется из условия нормировки , т.е. . (1.6)

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

Если , то стационарный режим существует при любом .

Выпишем теперь выражения для некоторых характеристик очереди.

Стационарная вероятность немедленного обслуживания заявки (обслуживания без ожидания) совпадает со стационарной вероятностью того, что в системе находится 0,1,…,n-1 заявок, т.е.            .

Рассмотрим интересующий нас частный случай, когда r=0. тогда в системе отсутствуют места для ожидания (система с потерями M/M/n/0) и такая система носит название системы Эрланга. Система Эрланга описывает процессы, происходящие в простейших телефонных сетях, и названа так в честь А. К. Эрланга, впервые её исследовавшего. Для системы M/M/n/0 стационарные вероятности определяются формулой Эрланга           

,   .

Следовательно, стационарная вероятность потери заявки определяется формулой:  

,

которую также называют формулой Эрланга.

Наконец, когда , то мы имеем систему , для которой при любом стационарные вероятности существуют и, как следует из формул Эрланга при , имеют вид           

,   .

Вернемся теперь к соотношениям (1.4). Суммируя эти равенства по i=0,1,…,n+r-1 , получаем               ,

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