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

Содержание

<p/>

Введение… 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<sub/>- вероятность того, что исходным состояниемсистемы является 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)

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

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

СМО описываются некоторыми параметрами, которые характеризуютэффективность работы системы.

/> – число каналов в СМО;

/> – интенсивность поступления в СМО заявок;

/> – интенсивность обслуживания заявок;

/> – коэффициент загрузки СМО;

/> – число мест в очереди;

/> – вероятность отказа в обслуживаниипоступившей в СМО заявки;

/> – вероятность обслуживания поступившей в СМОзаявки (относительная пропускная способность СМО);

При этом:

/>                                                                             (8)

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

/>                                                                                           (9)

/> – среднее число заявок, находящихся в СМО

/> – среднее число каналов в СМО, занятыхобслуживанием заявок. В тоже время это /> – среднее число заявок,обслуживаемых в СМО за единицу времени. Величина /> определяется какматематическое ожидание случайного числа занятых обслуживанием n каналов.

/>,                                                           (10)

где /> – вероятность нахождения системы вSk состоянии.

/> – коэффициент занятости каналов

/> – среднее время ожидания заявки в очереди

/> – интенсивность ухода заявок изочереди

/> – среднее число заявок в очереди.Определяется как математическое ожидание случайной величины m – числа заявок,состоящих в очереди

/>                                                                        (11)

Здесь /> – вероятность нахождения в очередиi заявок;

/> – среднее время пребывания заявки с СМО

/> – среднее время пребывания заявки в очереди

Для открытых СМО справедливы соотношения:

/>                                                                            (12)

/>                                                                                            (13)

Этисоотношения называются формулами Литтла и применяются только для стационарныхпотоков заявок и обслуживания.

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

 
5.Основные типы открытых систем массового обслуживания 5.1Одноканальная система массового обслуживания с отказами

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

/>

Рисунок 3 – Граф состояний одноканальной СМО

Здесь /> и /> – интенсивностьпотока заявок и выполнения заявок соответственно. Состояние системы So обозначает, что каналсвободен, а S1 – что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеетвид:

/>

где po(t) и p1(t)– вероятности нахождения СМО в состояниях So и S1 соответственно.Уравнения для финальных вероятностей po и p1 получим, приравниваянулю производные в первых двух уравнениях системы. В результате получим:

/>                                                                               (14)

/>                                                                               (15)

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

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

Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна />, а интенсивность обслуживания заявки каждымканалом равна />. Размеченный граф состоянийсистемы изображён на рисунке 4.

/>

Рисунок 4 – Граф состояний многоканальной СМО с отказами

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

Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, чтомногоканальная СМО с отказами является частным случаем системы рождения игибели, если в последней принять /> и

/>                                                               (16)

При этом для нахождения финальных вероятностей можновоспользоваться формулами (4) и (5). С учётом (16) получим из них:

/>                                                                 (17)

/>                                                                       (18)

Формулы (17) и (18) называются формулами Эрланга – основателятеории массового обслуживания.

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

/>                                                                             (19)

Относительную пропускную способность СМО найдём из (8) и (19):

/>                                                             (20)

Абсолютную пропускную способность найдём из (9) и (20):

/>

Среднее число занятых обслуживанием каналов можно найти по формуле(10), однако сделаем это проще. Так как каждый занятый канал в единицу времениобслуживает в среднем /> заявок, то /> можнонайти по формуле:

/>

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

В СМО с ограниченной очередью число мест m в очереди ограничено.Следовательно, заявка, поступившая в момент времени, когда все места в очередизаняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 5.

S0

  />

Рисунок 5 – Граф состояний одноканальной СМО с ограниченнойочередью

Состояния СМО представляются следующим образом:

S0– канал обслуживания свободен,

S1 – канал обслуживания занят, но очереди нет,

S2 – канал обслуживания занят, в очереди одна заявка,

Sk+1 – канал обслуживания занят, в очереди k заявок,

Sm+1 – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться темобстоятельством, что СМО на рисунок 5 является частным случаем системы рожденияи гибели, представленной на рисунке 2, если в последней принять /> и

/>                                                                           (21)

/>                                                   (22)

/>                                                                      (23)

Выражения для финальных вероятностей состояний рассматриваемой СМОможно найти из (4) и (5) с учётом (21). В результате получим:

При р = 1 формулы (22), (23) принимают вид

При m = 0 (очереди нет) формулы (22), (23) переходят в формулы (14) и (15)для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМОнаходится в состоянии Sm+1, т.е. вероятность отказа в обслуживаниизаявки равна:

/>

/>

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

/>

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

/>

Среднее число заявок, стоящих в очереди Lоч, находится по формуле

/>

и может быть записано в виде:

/>                                                        (24) 

При /> формула (24) принимает вид:

/>

/> – среднее число заявок, находящихся в СМО,находится по формуле(10)

/>

и может быть записано в виде:

/>                                              (25)

При />, из (25) получим:

/>

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

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

Примером такой СМО может служить директор предприятия, вынужденныйрано или поздно решать вопросы, относящиеся к его компетенции, или, например,очередь в булочной с одним кассиром. Граф такой СМО изображён на рисунке 6.

/>

Рисунок 6 – Граф состояний одноканальной СМО с неограниченнойочередью

Все характеристики такой СМО можно получить из формул предыдущегораздела, полагая в них />. При этом необходимо различать двасущественно разных случая: а) />; б) />. В первом случае, как это видно из формул (22),(23), р0= 0 и pk = 0 (при всех конечных значениях k). Это означает, что при /> очередь неограниченно возрастает, т.е. этотслучай практического интереса не представляет.

Рассмотрим случай, когда />. Формулы (22)и (23) при этом запишутся в виде:

/>

/>

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

/>

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

/>

Среднее число заявок в очереди получим из формулы (24) при />:

/>

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

/>

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

/>

Среднее время пребывания заявки в СМО и в очереди определяютсяформулами (12) и (13).

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

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

Граф такой системы представлен на рисунке 7.

/>

Рисунок 7 – Граф состояний многоканальной СМО с ограниченнойочередью

/> – все каналы свободны, очереди нет;

/> – заняты l каналов (l = 1, n), очереди нет;

/> — заняты все n каналов, в очереди находится i заявок (i = 1, m).

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

/>

/>

Выражения для финальных вероятностей легко найти из формул (4) и (5).В результате получим:

/>                                         (26)

/>

Образованиеочереди происходит, когда в момент поступления в СМО очередной заявки всеканалы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m – 1) заявок. Т.к. этисобытия несовместны, то вероятность образования очереди pоч равна суммесоответствующих вероятностей />:

/>                                                             (27)

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

/>

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

/>

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

/>

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

/>                                      (28)

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

/>

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

/>

Среднее время пребывания заявки в СМО и в очереди определяетсяформулами (12) и (13).

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

Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке7 при />.

/>

Рисунок 8 – Граф состояний многоканальной СМО с неограниченнойочередью

Формулы для финальных вероятностей можно получить из формул для n-канальной СМО сограниченной очередью при />. При этом следует иметь в виду, что при /> вероятность р0= р1=…=pn = 0, т.е. очередьнеограниченно возрастает. Следовательно, этот случай практического интереса непредставляет и ниже рассматривается лишь случай />. При /> из (26) получим:

/>

Формулы для остальных вероятностей имеют тот же вид, что и для СМОс ограниченной очередью:

/>

Из (27) получим выражение для вероятности образования очередизаявок:

/>

Поскольку очередь не ограничена, то вероятность отказа вобслуживании заявки:

/>

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

/>

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

/>

Из формулы (28) при /> получим выражение для среднего числа заявок вочереди:

/>

Среднее число обслуживаемых заявок определяется формулой:

/>

Среднее время пребывания в СМО и в очереди определяется формулами (12)и (13).

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

Отличие такой СМО от СМО, рассмотренной в подразделе 5.5, состоитв том, что время ожидания обслуживания, когда заявка находится в очереди,считается случайной величиной, распределённой по показательному закону спараметром />, где /> – среднеевремя ожидания заявки в очереди, а /> – имеет смыслинтенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке9.

/>

Рисунок 9 – Граф многоканальной СМО с ограниченной очередью иограниченным временем ожидания в очереди

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

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

/>

/>             (29)

Выражения для финальных вероятностей легко найти из формул (4) и (5)с учетом (29). В результате получим:

/>

/>

/>,

где />. Вероятность образования очередиопределяется формулой:

/>

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

/>

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

/>

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

/>

Среднее число заявок, находящихся в очереди, находится по формуле (11)и равно:

/>

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

/>

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

/> 

 
6.Метод Монте-Карло 6.1Основная идея метода

Сущность методаМонте-Карло состоит в следующем: требуется найти значение а некоторойизучаемой величины. Для этого выбирают такую случайную величину Х,математическое ожидание которой равно а: М(Х)=а.

Практически же поступаюттак: производят n испытаний, в результате которых получают n возможных значений Х;вычисляют их среднее арифметическое /> и принимают /> в качестве оценки (приближённого значения) a* искомого числа a:

/>.

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

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

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

/>,                                                                                              (30)

где /> – случайная величина, равномернораспределенная на интервале />.

Т.е. выбрав очередное значение /> надорешить уравнение (30) и найти очередное значение />. Для доказательстварассмотрим функцию:

/>

Имеем общие свойства плотности вероятности:

/>                                                                                        (31)

/>                                                                                            (32)

Из (31) и (32) следует, что />, апроизводная />.

Значит, функция /> монотонно возрастает от 0до 1. И любая прямая />, где />,пересекает график функции /> в единственной точке,абсциссу которой мы и принимаем за />. Таким образом, уравнение(30) всегда имеет одно и только одно решение.

Выберем теперь произвольный интервал />,содержащийся внутри />. Точкам этого интервала отвечаютординаты кривой, удовлетворяющие неравенству />.Поэтому, если /> принадлежит интервалу />, то

/> принадлежит интервалу />, и наоборот. Значит: />.Т.к. /> равномерно распределена в />, то

/>, а это как раз и означает, чтослучайная величина />, являющаяся корнем уравнения (30)имеет плотность вероятностей />.

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

Простейшимпотоком (или потоком Пуассона) называется такой поток заявок, когда промежутоквремени /> между двумя последовательными заявками естьслучайная величина, распределенная на интервале /> сплотностью

/>

Вычислимматематическое ожидание: />

Послеинтегрирования по частям, получим:

/>.

Параметр /> есть интенсивность потока заявок.

Формулу длярозыгрыша /> получим из уравнения (30), которое в данномслучае запишется так: />.

Вычисливинтеграл, стоящий слева, получим соотношение />. Отсюда,выражая />, получим:

/>                                                                                  (33)

Т.к. величина/> распределена также как и />, следовательно, формулу (33) можно записатьв виде:

/>                                                                                        (34)

 

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

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

 

Исследуемое мной предприятие представляет собой двухканальнуюсистему массового обслуживания с ограниченной очередью. На вход поступаетпуассоновский поток заявок с интенсивностью λ. Интенсивности обслуживаниязаявок каждым из каналов μ, а максимальное число мест в очереди m.

Начальныепараметры:

/>

/>

Времяобслуживания заявок имеет эмпирическое распределение, указанное ниже и имеетсреднее значение />.

/>

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

Таблица 6.1 –Группировка заявок по времени обработки

Количество заявок 22 25 23 16 14 10 8 4 Время обработки, мин 0–5 5–10 10–15 15–20 20–25 25–30 30–35 35–40

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

Для тогочтобы, при уровне значимости /> проверить гипотезу о том,что непрерывная случайная величина распределена по показательному закону, надо:

1) Найти позаданному эмпирическому распределению выборочную среднюю />. Для этого, каждый i – й интервал заменяемего серединой /> и составляем последовательностьравноотстоящих вариант и соответствующих им частот.

2) Принять вкачестве оценки параметра λ показательного распределения величину,обратную выборочной средней:

/>

3) Найтивероятности попадания X в частичные интервалы по формуле:

/>

4) Вычислитьтеоретические частоты:

/>,

где /> — объем выборки

5) Сравнитьэмпирические и теоретические частоты с помощью критерия Пирсона, приняв числостепеней свободы />, где S – число интерваловпервоначальной выборки.

Таблица 6.2 –Группировка заявок по времени обработки с усредненным временным интервалом

Количество заявок 22 25 23 16 14 10 8 4 Время обработки, мин 2,5 7,5 12,5 17,5 22,5 27,5 32,5 37,5

Найдемвыборочную среднюю:

/>

2) Примем вкачестве оценки параметра λ экспоненциального распределения величину,равную />. Тогда:

/> (/>)

3) Найдемвероятности попадания X в каждый из интервалов по формуле:

/>

Для первогоинтервала:

/>

Для второгоинтервала:

/>

Для третьегоинтервала:

/>

Длячетвертого интервала:

/>

Для пятогоинтервала:

/>

Для шестогоинтервала:

/>

Для седьмогоинтервала:

/>

Для восьмогоинтервала:

/>

4) Вычислимтеоретические частоты:

/>

Результатывычислений заносим в таблицу. Сравниваем эмпирические /> итеоретические /> частоты с помощью критерияПирсона.

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

Таблица 6.3 –Результаты вычислений

i

/>

/>

/>

/>

/>

/>

1 22 0,285 34,77 -12,77 163,073 4,690 2 25 0,204 24,888 0,112 0,013 0,001 3 23 0,146 17,812 5,188 26,915 1,511 4 16 0,104 12,688 3,312 10,969 0,865 5 14 0,075 9,15 4,85 23,523 2,571 6 10 0,053 6,466 3,534 12,489 1,932 7 8 0,038 4,636 3,364 11,316 2,441 8 4 0,027 3,294 0,706 0,498 0,151 122

/>

Т.к. />, то нет оснований отвергнуть гипотезу ораспределении Xпо показательному закону. Другими словами, данные наблюдений согласуются с этойгипотезой.

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

Даннаясистема представляет собой частный случай системы гибели и размножения.

Граф даннойсистемы:

/>

Рисунок 10 –Граф состояний исследуемой СМО

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

/>      (1)

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

/>

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

/>

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

/>

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

/>

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

/>

/>

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

/>

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

/>

/>; />; />; />; />;

/>; />.

Или, с учетом(1):

/>

/>; />; />; />; />; />;

/>.

Коэффициентзагруженности СМО:

/>

/>

С учетомэтого предельные вероятности перепишем в виде:

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

Наивероятнейшеесостояние – оба канала СМО заняты и заняты все места в очереди.

Вероятностьобразования очереди:

/>

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

/>

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

/>

Вероятностьтого, что вновь поступившая заявка будет обслужена, равна 0,529

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

/>

СМОобслуживает в среднем 0,13225 заявок в минуту.

Среднее числозаявок, находящихся в очереди:

/>

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

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

/>

В среднем всеканалы СМО постоянно заняты.

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

/>

Для открытыхСМО справедливы формулы Литтла:

Среднее времяпребывания заявки с СМО:

/>

Среднее времяпребывания заявки в очереди:

/>

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

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

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

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

Пользователюпри работе с программой необходимо задать основные параметры СМО, такие как интенсивностипотоков, количество каналов, приоритетных классов, мест в очереди (есликоличество мест в очереди равно нулю, то СМО с отказами), а также временнойинтервал модуляции и количество испытаний. Программа преобразовываетсгенерированные случайные числа по формуле (34), таким образом, пользовательполучает последовательность временных интервалов />,распределенных показательно. Затем отбирается заявка с минимальным />, и ставится в очередь, согласно ееприоритету. За это же время /> происходит перерасчеточереди и каналов. Затем эта операция повторяется до окончания временимодуляции, задаваемого изначально. В теле программы присутствуют счетчики, наосновании показаний которых и формируются основные показатели СМО. Если дляувеличения точности было задано несколько испытаний, то в качестве конечныхрезультатов принимается оценка за серию опытов. Программа получилась достаточноуниверсальной, с ее помощью могут быть исследованы СМО с любым количествомприоритетных классов, либо вообще без приоритетов. Для проверки корректностиработы алгоритма, в него были введены исходные данные классической СМО,исследуемой в разделе 7. Программа смоделировала результат близкий к тому,который был получен с помощью методов теории массового обслуживания (см.приложение Б). Погрешность, возникшая в ходе имитационного моделирования, можетбыть объяснена тем, что проведено недостаточное количество испытаний.Результаты, полученные с помощью программы для СМО с двумя приоритетнымиклассами и увеличенным числом каналов, показывают целесообразность этихизменений (см. приложение В). Высший приоритет был присвоен более «быстрым»заявкам, что позволяетбыстро обследовать короткие задания. Сокращается средняя длина очереди всистеме, а соответственно минимизируется средство для организации очереди. Вкачестве основного недостатка данной организации можно выделить то, что«долгие» заявки находятся в очереди длительно время или вообще получают отказ.Введенные приоритеты могут быть переназначены после оценки полезности того илииного типа заявок для СМО.

Заключение

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

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

1 Вентцель, Е.С. Исследование операций / Е.С. Вентцель.- М.: «Советское радио», 1972. — 552 с.

2 Гмурман, В.Е. Теориявероятностей и математическая статистика / В.Е. Гмурман. — М.: «Высшая школа», 2003.-479 с.

3 Лаврусь, О.Е. Теориямассового обслуживания. Методические указания/ О.Е. Лаврусь, Ф.С. Миронов.-Самара: СамГАПС, 2002.- 38 с.

4 Саакян, Г.Р. Теориямассового обслуживания: лекции / Г.Р. Саакян. — Шахты: ЮРГУЭС, 2006. — 27 с.

5 Авсиевич, А.В. Теориямассового обслуживания. Потоки требований, системы массового обслуживания / А.В. Авсиевич,Е.Н. Авсиевич. — Самара: СамГАПС, 2004. — 24 с.

6 Черненко, В.Д. Высшаяматематика в примерах и задачах. В 3. т. Т. 3/ В.Д. Черненко. — Санкт – Петербург: Политехника,2003. — 476 с.

7 Клейнрок, Л. Теориямассового обслуживания / Л. Клейнрок. Пер.с англ./ Пер. И.И. Грушко; подред. В.И. Нейман. — М.: Машиностроение, 1979. — 432 с.

8 Олзоева, С.И.Моделирование и расчет распределенных информационных систем. Учебное пособие / С.И. Олзоева.-Улан-Удэ: ВСГТУ, 2004. — 66 с.

9 Соболь, И.М. МетодМонте-Карло / И.М. Соболь. — М.: «Наука», 1968. — 64 с.