Xreferat.com » Рефераты по экономико-математическому моделированию » Понятие и классификация систем массового обслуживания

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

Содержание

Введение........................................................................................................... 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) справедливы соотношения

    

Обозначим через

вектор состояния системы после m шагов, где qj – вероятность того, что после m шагов система находится в Si состоянии. Тогда справедлива формула

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

 

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

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

 

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

Зная интенсивности переходов можно найти величины p1(t), p2(t),…, pn(t) – вероятности нахождения системы S в состояниях S1, S2,…, Sn соответственно. При этом выполняется условие:


Распределение вероятностей состояний системы, которое можно характеризовать вектором , называется стационарным, если оно не зависит от времени, т.е. все компоненты вектора  являются константами.

Состояния Si и Sj называются сообщающимися, если возможны переходы .

Состояние Si называется существенным, если всякое Sj, достижимое из Si, является сообщающимся с Si. Состояние Si называется несущественным, если оно не является существенным.

Если существуют предельные вероятности состояний системы:

,

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

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

Теорема 1. Если Si – несущественное состояние, то  т.е. при  система выходит из любого несущественного состояния.

Теорема 2. Чтобы система с конечным числом состояний имела единственное предельное распределение вероятностей состояний, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой.

Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p1(t), р2(t),…, pn(t) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. В левой части каждого из них стоит производная вероятности какого-то (j-го) состояния. В правой части – сумма произведений вероятностей всех состояний, из которых возможен переход в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j-го) состояния, умноженная на вероятность данного (j-го) состояния.

 

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

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

Рисунок 2 – Граф состояний для процессов гибели и размножения

Здесь величины , ,…,  – интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины ,,…, – интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.

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

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

Для состояния S0:

Следовательно:


Для состояния S1:

Следовательно:

С учетом того, что :

Аналогично получаем уравнения для остальных состояний системы. В результате получим систему уравнений:

Решение этой системы будет иметь вид:

                                               (4)


, ,…,                                          (5)

 

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

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

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

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

Поток заявок называется простейшим, если он удовлетворяет следующим условиям:

1) отсутствие последействия, т.е. заявки поступают независимо друг от друга;

2) стационарность, т.е. вероятность поступления данного числа заявок на любом временном отрезке [t1; t2] зависит лишь от величины этого отрезка и не зависит от значения t1, что позволяет говорить о среднем числе заявок за единицу времени, λ, называемом интенсивностью потока заявок;

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

Для простейшего потока вероятность pi(t) поступления в СМО ровно i заявок за время t вычисляется по формуле:

                                                                            (6)


т.е. вероятности распределены по закону Пуассона с параметром λt. По этой причине простейший поток называется также пуассоновским потоком.

Функция распределения F(t) случайного интервала времени T между двумя последовательными заявками по определению равна . Но , где  – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t, т.е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (6) при i = 0. Таким образом:

                                  

                                                                                      (7)

Плотность вероятности f(t) случайной величины T определяется формулой:

         ,

Математическое ожидание, дисперсия и среднее квадратическое отклонение случайной величины T равны соответственно:

Каналом обслуживания называется устройство в СМО, обслуживающее заявку. СМО, содержащее один канал обслуживания, называется одноканальной, а содержащее более одного канала обслуживания – многоканальной.

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

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

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

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

·                   Первым пришел – первым обслужен (FCFS – First Came – First Served)

·                   Последним пришел – первым обслужен (LCFS – Last Came – First Served)

·                   Первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE)

·                   Первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT)

·                   Первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT)

·                   Первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT)

Приоритеты бывают двух типов – абсолютный и относительный.

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: