Тема. Теория систем массового обслуживания.
Каждая СМО состоит из
какого–то количества обслуживающих единиц, которые называются каналами
обслуживания (это станки, транспортные тележки, роботы, линии связи,
кассиры, продавцы и т.д.). Всякая СМО предназначена для обслуживания какого–то потока
заявок (требований), поступающих в какие-то случайные моменты времени.
Классификация
СМО по способу обработки входного потока заявок.
Классификация
по способу функционирования:
1.
открытыми, т.е. поток заявок не зависит от
внутреннего состояния СМО;
2.
закрытыми, т.е. входной поток зависит от
состояния СМО (один ремонтный рабочий обслуживает все каналы по мере их выхода
из строя).
Классификация систем массового обслуживания
Первое деление (по
наличию очередей):
1.
СМО с отказами;
2.
СМО с очередью.
В СМО с отказами заявка,
поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в
дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая
в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает
возможности быть обслуженной.
СМО с очередями
подразделяются на разные виды в зависимости от того, как организована
очередь – ограничена или не ограничена. Ограничения могут касаться как
длины очереди, так и времени ожидания, «дисциплины обслуживания».
·
СМО с нетерпеливыми заявками (длина очереди и время обслуживания
ограничено);
·
СМО с обслуживанием с приоритетом, т.е. некоторые заявки
обслуживаются вне очереди и т.д.
Кроме этого СМО делятся
на открытые СМО и замкнутые СМО.
В открытой СМО характеристики
потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов
занято). В замкнутой СМО – зависят. Например, если один рабочий
обслуживает группу станков, время от времени требующих наладки, то
интенсивность потока «требований» со стороны станков зависит от того, сколько
их уже исправно и ждет наладки.
Одноканальная система массового обслуживания с отказами
Размеченный граф состояний одноканальной СМО представлен на
рисунке 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.
Рисунок 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= при k<n,
Pk= при .
Через эти вероятности выражается среднее число занятых каналов
=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 мин. Время работы и время
наладки распределено по экспоненциальному закону.
Найдите среднюю долю
свободного времени для каждого рабочего и среднее время работы станка.
Найдите те же
характеристики для системы, в которой:
а) за каждым рабочим
закреплены два станка;
б) два рабочих всегда
обслуживают станок вместе, причем с двойной интенсивностью;
в) единственный
неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а
при появлении еще хотя бы одного неисправного станка они начинают работать
порознь, причем каждый обслуживает один станок (вначале опишите систему в
терминах процессов гибели и рождения).
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.