- Преподавателю
- Другое
- Конспект урока Теория систем массового обслуживания
Конспект урока Теория систем массового обслуживания
Раздел | Другое |
Класс | - |
Тип | Конспекты |
Автор | Васяркиева Е.А. |
Дата | 30.10.2015 |
Формат | docx |
Изображения | Есть |
Тема. Теория систем массового обслуживания.
Каждая СМО состоит из какого-то количества обслуживающих единиц, которые называются каналами обслуживания (это станки, транспортные тележки, роботы, линии связи, кассиры, продавцы и т.д.). Всякая СМО предназначена для обслуживания какого-то потока заявок (требований), поступающих в какие-то случайные моменты времени.
Классификация СМО по способу обработки входного потока заявок.
Системы массового обслуживания
С отказами
(без очереди)
С очередью
Неограниченная очередь
Ограниченная очередь
С приоритетом
В порядке поступления
Относительный приоритет
Абсолютный приоритет
По времени обслуживания
По длине очереди
Классификация по способу функционирования:
-
открытыми, т.е. поток заявок не зависит от внутреннего состояния СМО;
-
закрытыми, т.е. входной поток зависит от состояния СМО (один ремонтный рабочий обслуживает все каналы по мере их выхода из строя).
Классификация систем массового обслуживания
Первое деление (по наличию очередей):
-
СМО с отказами;
-
СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь - ограничена или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».
-
СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
-
СМО с обслуживанием с приоритетом, т.е. некоторые заявки обслуживаются вне очереди и т.д.
Кроме этого СМО делятся на открытые СМО и замкнутые СМО.
В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО - зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.
Одноканальная система массового обслуживания с отказами
Размеченный граф состояний одноканальной СМО представлен на рисунке 1.
Рисунок 1 - Граф состояний одноканальной СМО
Здесь и - интенсивность потока заявок и выполнения заявок соответственно. Состояние системы So обозначает, что канал свободен, а S1 - что канал занят обслуживанием заявки.
Система дифференциальных уравнений Колмогорова для такой СМО имеет вид:
где po(t) и p1(t) - вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей po и p1 получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:
(1)
(2)
Вероятность p0 по своему смыслу есть вероятность обслуживания заявки pобс, т. к. канал является свободным, а вероятность р1 по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки ротк, т. к. канал занят обслуживанием предыдущей заявки.
Многоканальная система массового обслуживания с отказами
Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна , а интенсивность обслуживания заявки каждым каналом равна . Размеченный граф состояний системы изображён на рисунке 2.
Рисунок 2 - Граф состояний многоканальной СМО с отказами
Состояние S0 означает, что все каналы свободны, состояние Sk (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).
(4)
(5)
Формулы (4) и (5) называются формулами Эрланга - основателя теории массового обслуживания.
Вероятность отказа в обслуживании заявки ротк равна вероятности того, что все каналы заняты, т.е. система находится в состоянии Sn. Таким образом,
(6)
Относительную пропускную способность СМО:
(7)
Абсолютную пропускную способность:
Так как каждый занятый канал в единицу времени обслуживает в среднем заявок, то можно найти по формуле:
Одноканальная система массового обслуживания с ограниченной длиной очереди
В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 3.
S0
Рисунок 3 - Граф состояний одноканальной СМО с ограниченной очередью
Состояния СМО представляются следующим образом:
S0 - канал обслуживания свободен,
S1 - канал обслуживания занят, но очереди нет,
S2 - канал обслуживания занят, в очереди одна заявка,
Sk+1 - канал обслуживания занят, в очереди k заявок,
Sm+1 - канал обслуживания занят, все m мест в очереди заняты.
Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рисунок 3 является частным случаем системы рождения и гибели, если принять и
(8)
(9)
(10)
Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии Sm+1, т.е. вероятность отказа в обслуживании заявки равна:
Относительная пропускная способность СМО равна:
Абсолютная пропускная способность равна:
Среднее число заявок, стоящих в очереди Lоч, находится по формуле
и может быть записано в виде:
(11)
При формула (11) принимает вид:
- среднее число заявок, находящихся в СМО, находится по формуле:
и может быть записано в виде:
(12)
При , из (12) получим:
Среднее время пребывания заявки в СМО и в очереди находится по формулам соответственно.
Одноканальная система массового обслуживания с неограниченной очередью
Примером такой СМО может служить директор предприятия, вынужденный рано или поздно решать вопросы, относящиеся к его компетенции, или, например, очередь в булочной с одним кассиром. Граф такой СМО изображён на рисунке 4.
Рисунок 4 - Граф состояний одноканальной СМО с неограниченной очередью
Рассмотрим случай, когда .
Относительная пропускная способность равна:
Абсолютная пропускная способность равна:
Среднее число заявок в очереди получим при :
Среднее число обслуживаемых заявок есть:
Среднее число заявок, находящихся в СМО:
Среднее время пребывания заявки в СМО и в очереди определяются формулами.
Многоканальная система массового обслуживания с ограниченной очередью
Пусть на вход СМО, имеющей каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью . Интенсивность обслуживания заявки каждым каналом равна , а максимальное число мест в очереди равно .
Граф такой системы представлен на рисунке 5.
Рисунок 5 - Граф состояний многоканальной СМО с ограниченной очередью
- все каналы свободны, очереди нет;
- заняты l каналов (l = 1, n), очереди нет;
- заняты все n каналов, в очереди находится i заявок (i = 1, m).
Выражения для финальных вероятностей:
(13)
Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m - 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди pоч равна сумме соответствующих вероятностей :
(14)
Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е.:
Относительная пропускная способность равна:
Абсолютная пропускная способность:
Среднее число заявок может быть записано в виде:
(15)
Среднее число заявок, обслуживаемых в СМО, может быть записано в виде:
Среднее число заявок, находящихся в СМО:
Среднее время пребывания заявки в СМО и в очереди определяется формулами.
Многоканальная система массового обслуживания с неограниченной очередью
Граф такой СМО изображен на рисунке 6 при .
Рисунок 6 - Граф состояний многоканальной СМО с неограниченной очередью
Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:
Поскольку очередь не ограничена, то вероятность отказа в обслуживании заявки:
Относительная пропускная способность:
Абсолютная пропускная способность:
Среднее число заявок в очереди:
Среднее число обслуживаемых заявок определяется формулой:
Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди
Отличие такой СМО от других СМО, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром , где - среднее время ожидания заявки в очереди, а - имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 7.
Рисунок 7 - Граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди
Выражения для финальных вероятностей
,
где . Вероятность образования очереди определяется формулой:
Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е. вероятность отказа в обслуживании:
Относительная пропускная способность:
Абсолютная пропускная способность:
Среднее число заявок, находящихся в очереди находится по формуле
Среднее число заявок, обслуживаемых в СМО, находится по формуле
Среднее время пребывания заявки в СМО складывается из среднего времени ожидания в очереди и среднего времени обслуживания заявки:
Системы массового обслуживания с ожиданием
Одноканальная СМО с ожиданием
Рассмотрим простейшую СМО с ожиданием - одноканальную систему (n - 1), в которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (т.е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):
- канал свободен;
- канал занят, очереди нет;
- канал занят, одна заявка стоит в очереди;
- канал занят, k-1 заявок стоят в очереди;
- канал занят, т-заявок стоят в очереди.
ГСП показан на рис. 8. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны , а справа налево - . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево - поток «освобождений» занятого канала, имеющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).
Рис. 8. Одноканальная СМО с ожиданием
Вероятность отказа.
(21).
Относительная пропускная способность:
(22).
Абсолютная пропускная способность:
.
Средняя длина очереди.
.
С вероятностьюв очереди стоит одна заявка, с вероятностью- две заявки, вообще с вероятностьюв очереди стоят k-1 заявок, и т.д., откуда:
(23).
Поскольку , сумму в (23) можно трактовать как производную по от суммы геометрической прогрессии:
.
Подставляя данное выражение в (23) и используя из (20), окончательно получаем:
(24).
Среднее число заявок.
(25).
Среднее время ожидания заявки в очереди.
,
если подставить сюда выражения для вероятностей (20), получим:
(26).
(27).
Среднее время пребывания заявки в системе. .
Отсюда:
.
Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).
Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно (m = 3). Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность =1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.
Определить:
вероятность отказа;
относительную и абсолютную пропускную способности АЗС;
среднее число машин, ожидающих заправки;
среднее число машин, находящихся на АЗС (включая обслуживаемую);
среднее время ожидания машины в очереди;
среднее время пребывания машины на АЗС (включая обслуживание).
Иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Системы с неограниченным ожиданием.
В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода в ранее полученных выражениях (17), (18) и т.п.
При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q=1, .
Среднее число заявок в очереди получим из (24) при :
.
Среднее число заявок в системе по формуле (25) при :
.
Среднее время ожиданияполучим из формулы (26) при:
.
Наконец, среднее время пребывания заявки в СМО есть:
.
Многоканальная СМО с ожиданием
Система с ограниченной длиной очереди. Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди
Состояния системы нумеруются по числу заявок, связанных системой:
нет очереди:
- все каналы свободны;
- занят один канал, остальные свободны;
- заняты -каналов, остальные нет;
- заняты все -каналов, свободных нет;
есть очередь:
- заняты все n-каналов; одна заявка стоит в очереди;
- заняты все n-каналов, r-заявок в очереди;
- заняты все n-каналов, r-заявок в очереди.
ГСП приведен на рис. 9. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью , по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна , умноженному на число занятых каналов.
Рис. 9. Многоканальная СМО с ожиданием
Вероятность отказа.
(29)
Относительная пропускная способность дополняет вероятность отказа до единицы:
Абсолютная пропускная способность СМО:
(30)
Среднее число занятых каналов.
.
Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:
(31)
где .
Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (23), (24) - (26)), используя соотношение для нее, получаем:
Среднее число заявок в системе:
Среднее время ожидания заявки в очереди.
(32)
Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди только множителем , т. е.
.
Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО .
Системы с неограниченной длиной очереди. Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m-заявок.
Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при .
Вероятность отказа
Среднее число заявок в очереди получим при из (31):
,
а среднее время ожидания - из (32): .
Среднее число занятых каналов .
Среднее число заявок .
Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:
В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.
СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m-заявок, одновременно находящихся в очереди). В такой СМО заявка, разраставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).
Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.
Пуассоновский «поток уходов» с интенсивностью:
Если этот поток пуассоновский, то процесс, протекающий в СМО, будет марковским. Найдем для него вероятности состояний. Нумерация состояний системы связывается с числом заявок в системе - как обслуживаемых, так и стоящих в очереди:
нет очереди:
- все каналы свободны;
- занят один канал;
- заняты два канала;
- заняты все n-каналов;
есть очередь:
- заняты все n-каналов, одна заявка стоит в очереди;
- заняты все n-каналов, r-заявок стоят в очереди и т. д.
Граф состояний и переходов системы показан на рис. 10.
Рис. 10. СМО с ограниченным временем ожидания
Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .
Среднее число заявок в очереди: (35)
На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:
Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на : (36)
Среднее число заявок в очереди.
,
Среднее число занятых каналов
.
Замкнутые СМО
До сих пор мы рассматривали системы, в которых входящий поток никак не связан с выходящим. Такие системы называются разомкнутыми. В некоторых же случаях обслуженные требования после задержки опять поступают на вход. Такие СМО называются замкнутыми. Поликлиника, обслуживающая данную территорию, бригада рабочих, закрепленная за группой станков, являются примерами замкнутых систем.
В замкнутой СМО циркулирует одно и то же конечное число потенциальных требований. Пока потенциальное требование не реализовалось в качестве требования на обслуживание, считается, что оно находится в блоке задержки. В момент реализации оно поступает в саму систему. Например, рабочие обслуживают группу станков. Каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта - в самой системе. Каждый рабочий является каналом обслуживания.
Пусть n - число каналов обслуживания, s - число потенциальных заявок, n<s, - интенсивность потока заявок каждого потенциального требования, μ - интенсивность обслуживания:
ρ=.
Вероятность простоя системы определяется формулой
Р0=.
Финальные вероятности состояний системы:
Pk= при kk= при .
Через эти вероятности выражается среднее число занятых каналов
=P1+2P2+…+n(Pn+Pn+1+…+Ps) или
=P1+2P2+…+(n-1)Pn-1+n(1-P0-P1-…-Pn-1).
Через находим абсолютную пропускную способность системы:
A=,
а также среднее число заявок в системе
М=s-=s-.
Пример 1. На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом tобсл=1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?
Пример 2. На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью =4 заявки в час, среднее время обслуживания одной заявки t=1/μ=0,5 ч. Найти показатели эффективности работы системы.
Для рассматриваемой системы n=3, =4, μ=1/0,5=2, ρ=/μ=2, ρ/n=2/3<1.
Задача 3:
Два рабочих обслуживают группу из четырех станков. Остановки работающего станка происходят в среднем через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время наладки распределено по экспоненциальному закону.
Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.
Найдите те же характеристики для системы, в которой:
а) за каждым рабочим закреплены два станка;
б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;
в) единственный неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а при появлении еще хотя бы одного неисправного станка они начинают работать порознь, причем каждый обслуживает один станок (вначале опишите систему в терминах процессов гибели и рождения).
24