Содержание
Введение… 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)
Приоритетыбывают двух типов – абсолютный и относительный.
Еслитребование в процессе обслуживания может быть удалено из канала и возвращено вочередь (либо вовсе покидает СМО) при поступлении требования с более высокимприоритетом, то система работает с абсолютным приоритетом. Если обслуживаниелюбого требования, находящегося в канале не может быть прервано, то СМОработает с относительным приоритетом. Существуют также приоритеты,осуществляемые с помощью конкретного правила или набора правил. Примером можетслужить приоритет, изменяющийся с течением времени.
СМО описываются некоторыми параметрами, которые характеризуютэффективность работы системы.
/> – число каналов в СМО;
/> – интенсивность поступления в СМО заявок;
/> – интенсивность обслуживания заявок;
/> – коэффициент загрузки СМО;
/> – число мест в очереди;
/> – вероятность отказа в обслуживаниипоступившей в СМО заявки;
/> – вероятность обслуживания поступившей в СМОзаявки (относительная пропускная способность СМО);
При этом:
/> (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 с.