Понятие и классификация систем массового обслуживания

Содержание

Введение . 3

1 Марковские цепи с конечным числом состояний и дискретным временем 4

2 Марковские цепи с конечным числом состояний и непрерывным временем 8

3 Процессы рождения и гибели 11

4 Основные понятия и классификация систем массового обслуживания . 14

5 Основные типы открытых систем массового обслуживания 20

5.1 Одноканальная система массового

обслуживания с отказами 20

5.2 Многоканальная система массового обслуживания с отказами . 21

5.3 Одноканальная система массового обслуживания с ограниченной длиной очереди 23

5.4 Одноканальная система массового обслуживания с неограниченной очередью 26

5.5 Многоканальная система массового обслуживания с ограниченной очередью 27

5.6 Многоканальная система массового обслуживания с неограниченной очередью 30

5.7 Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди . 32

6 Метод Монте-Карло . 36

6.1 Основная идея метода . 36

6.2 Разыгрывание непрерывной случайной величины 36

6.3 Случайная величина с экспоненциальным распределением . 38

7 Исследование системы массового обслуживания . 40

7.1 Проверка гипотезы о показательном распределении 40

7.2 Расчет основных показателей системы массового обслуживания 45

7.3 Выводы о работе исследуемой СМО . 50

8 Исследование видоизмененной СМО 51

Заключение 53

Список использованных источников 54

Введение

Темой моей дипломной работы является исследование системы массового обслуживания. В своем изначальном состоянии рассматриваемая мной СМО представляет собой один из классических случаев, а конкретно M/M/2/5 по принятому обозначению Кэндалла. После исследования системы были сделаны выводы о неэффективности ее работы. Были предложены методы оптимизации работы СМО, но с этими изменениями система перестает быть классической. Основная проблема при исследовании систем массового обслуживания заключается в том, что в реальности они могут быть исследованы с использованием классической теории массового обслуживания только в редких случаях. Потоки входящих и исходящих заявок могут оказаться не простейшими, следовательно, нахождение предельных вероятностей состояний с использованием системы дифференциальных уравнений Колмогорова невозможно, в системе могут присутствовать приоритетные классы, тогда расчет основных показателей СМО также невозможен.

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

1 Марковские цепи с конечным числом состояний и дискретным временем

Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S1, S2,…, Sn, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t1, t2, t3, называемые шагами.

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

Случайный процесс называется марковским, если вероятность перехода из любого состояния Si в любое состояние Sj не зависит от того, как и когда система S попала в состояние Si (т.е. в системе S отсутствует последствие). В таком случае говорят, что функционирование системы S описывается дискретной цепью Маркова.

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

Рисунок 1 – Пример размеченного графа состояний

Вершины графа S1, S2, S3 обозначают возможные состояния системы. Стрелка, направленная из вершины Si в вершину Sj обозначает переход ; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i-той вершине графа, обозначает, что система остается в состоянии Si с вероятностью, стоящей у стрелки.

Графу системы, содержащему n вершин, можно поставить в соответствие матрицу NxN, элементами которой являются вероятности переходов pij между вершинами графа. Например, граф на рис. 1 описывается матрицей P:

называемой матрицей вероятностей переходов. Элементы матрицы pij удовлетворяют условиям:

(1)

(2)

Элементы матрицы pij – дают вероятности переходов в системе за один шаг. Переход

Si – Sj за два шага можно рассматривать как происходящий на первом шаге из Si в некоторое промежуточное состояние Sk и на втором шаге из Sk в Si. Таким образом, для элементов матрицы вероятностей переходов из Si в Sj за два шага получим:

В общем случае перехода за m шагов для элементов матрицы вероятностей переходов справедлива формула:

(3)

Получим два эквивалентных выражения для :

Пусть система S описывается матрицей вероятностей переходов Р:

Если обозначить через Р(m) матрицу, элементами которой являются рi вероятности переходов из Si в Sj за m шагов, то справедлива формула

,

где матрица Рm получается умножением матрицы P саму на себя m раз.

Исходное состояние системы характеризуется вектором состояния системы Q(qi) (называемым также стохастическим вектором).

где qj - вероятность того, что исходным состоянием системы является Sj состояние. Аналогично (1) и (2) справедливы соотношения

 Скачать реферат