Лекция Элементы теории систем массового обслуживания

11. Элементы теории систем массового обслуживания

Вопросы темы:

1. Основные понятия. Классификация СМО.

2. Понятие марковского случайного процесса.

3. Потоки событий.

4. Уравнения Колмогорова. Предельные вероятности состояния.

11.1 Основные понятия. Классификация СМО

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

В качестве показателей эффективности СМО используются:

· среднее число заявок, обслуживаемых в единицу времени;

• среднее число заявок в очереди;
• среднее время ожидания обслуживания;
• вероятность отказа в обслуживании без ожидания;

· вероятность превышения количества заявок в очереди заданного значения.

СМО разделяются на два основных типа:

• СМО с отказами;

· СМО с ожиданием (очередью).

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

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

Принцип обслуживания заявок, - "первая пришла - первая обслужена", "последняя пришла - первая обслужена", "обслуживание с приоритетом".

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

11.2 Понятие марковского случайного процесса

Функционирование СМО представляет собой некоторый случайный процесс.

Случайным (вероятностным, стохастическим) процессом называется процесс состояние которого изменяется согласно вероятностных закономерностей.

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

Процесс называется процессом с непрерывным временем, если моменты перехода происходят в заранее не фиксированные, случайные, моменты времени.

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

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

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

Процессы с дискретным состоянием описываются геометрической схемой, графиком состояния.

Пример: Устройство состоит из двух узлов, каждый из которых в случайные моменты времени может выйти из строя и в состоянии ремонта находится заранее неизвестное время.

Состояние - оба узла исправны, - первый ремонтируется, второй - исправен, - второй ремонтируется, первый исправен, - оба узла ремонтируются.

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

11.3 Потоки событий

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

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

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

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

Поток событий называется ординарным, если вероятность попадания на малый интервал времени двух и более событий пренебрежимо мала по сравнению с вероятностью попадания одного события (пример: поток поездов подходящих к станции, - ординарен, поток вагонов, -неординарен).

Поток событий называется простейшим, или стационарным пуассоновским, если он одновременно стационарен, ординарен, и не имеет последействия.

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

Если поток простейший, то число событий попадающих на произвольный участок времени распределено по закону Пуассона

для которого

Вероятность того, что за время  не произойдет ни одного события

Вероятность того, что за период времени t не появится ни одного из последующих событий

Вероятность противоположного события

Плотность вероятности случайной величины

Интервал времени между двумя соседними произвольными событиями имеет показательное распределение для которого

Свойство показательного распределения: если промежуток времени, распределенный по показательному закону уже длился некоторое время , то это не влияет на закон распределения оставшейся части.

Если поток простейший с интенсивностью то вероятность попадания на малый отрезок времени хотя бы одного события потока

11.4 Уравнения Колмогорова. Предельные вероятности состояния.

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

Полагаем, что все переходы из в происходит под воздействием простейших потоков событий с интенсивностями (i, j = 0,1,2,3).

Переход из в происходит под воздействием потока отказов первого узла.

Обратный переход из в происходит под воздействием потока "окончание ремонтов первого узла".

Вероятностью i-го состояния называется вероятность того, что в момент времени t система находится в состоянии . В любой момент времени

Пусть система S находится в некотором состоянии в момент времени . Определим вероятность нахождения системы в состоянии в момент времени .

1. Система в момент времени , с вероятностью находилась в и за время не вышла из него.

Вывести систему из состояния можно суммарным простейшим потоком с интенсивностью с вероятностью приближенно равной .

Вероятность невыхода системы из состояния равна .

По теореме умножения вероятностей, вероятность того, что система находилась в состоянии и не вышла из него за время равна:

2. Система в момент с вероятностями (либо ) находилась в (либо ) и за время перешла в состояние . Потоком интенсивностью (или ) перейдет в с вероятностью (или ). Вероятность нахождения в состоянии по этому способу (или ).

По теореме сложения вероятностей

или

Предельный переход задает производную:

Для других состояний системы можно получить систему дифференциальных уравнений Колмогорова для вероятностей состояний

(1)

Правило составления системы уравнений Колмогорова.

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

В системе (1) независимых уравнений на единицу меньше общего числа уравнений, поэтому для решения системы необходимо добавить условие, и задать начальное состояние системы в момент времени .

Систему (1) следует решать при условии, что система находится в состоянии и , .

Уравнения Колмогорова позволяет найти все вероятности как функции времени и определить финальные вероятности в стационарном режиме при .

.Условие существования решения

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

Предельные вероятности состояния определяют среднее относительное время пребывания системы в -ом состоянии.

Например: определяет, система, в среднем, половину времени находится в состоянии .

Учитывая, что предельные вероятности есть постоянные величины, и, соответственно производные по времени равны нулю, систему (1) можно представить в виде:

(2)

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

Вопросы самопроверки:

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

2. Какие показатели эффективности используются для оценки работы СМО?

3. На какие основные типы подразделяются СМО?

4. Каким случайным процессом можно характеризовать работу СМО?.

5. Какой случайный процесс называется марковским?

6. Что представляет собой поток случайных событий?

7. Что означает: поток регулярный, без последействия, ординарный?

8. Определение пуассоновского потока событий.

9. Формула закона распределения Пуассона.

10. Свойства показательного закона распределения.

11. Уравнения Колмогорова для предельных состояний СМО.

12. Правило составления системы уравнений Колмогорова для СМО.

13. Что определяют уравнения Колмогорова для СМО?

14. Как определяется дискретный случайный процесс с непрерывным временем?