Одноканальная система с ограниченной очередью. Системы массового обслуживания с неограниченной очередью. Порядок выполнения работы
Рассмотрим многоканальную СМО, на вход которой поступает пуассоновский поток заявок с интенсивностью, а интенсивность обслуживания каждого канала составляет, максимально возможное число мест в очереди ограничено величиной m. Дискретные состояния СМО определяются количеством заявок, поступивших в систему, которые можно записать.
Все каналы свободны, ;
Занят только один канал (любой), ;
- - заняты только два канала (любых), ;
- - заняты все каналов, .
Пока СМО находится в любом из этих состояний, очереди нет. После того как заняты все каналы обслуживания, последующие заявки образуют очередь, тем самым, определяя дальнейшие состояние системы:
Заняты все каналов и одна заявка стоит в очереди,
Заняты все каналов и две заявки стоят в очереди,
Заняты все каналов и все мест в очереди,
Переход СМО в состояние с большими номерами определяется потоком поступающих заявок с интенсивностью, тогда как по условию в обслуживании этих заявок принимают участие одинаковых каналов с интенсивностью потока обслуживания равного для каждого канала. При этом полная интенсивность потока обслуживания возрастает с подключением новых каналов вплоть до такого состояния, когда все n каналов окажутся занятыми. С появлением очереди интенсивность обслуживания более увеличивается, так как она уже достигла максимального значения, равного.
Запишем выражения для предельных вероятностей состояний:
Выражение для можно преобразовать, используя формулу геометрической прогрессии для суммы членов со знаменателем:
Образование очереди возможно, когда вновь поступившая заявка застанет в системе не менее требований, т.е. когда в системе будет находиться требований.
Эти события независимы, поэтому вероятность того, что все каналы заняты, равна сумме соответствующих вероятностей
Поэтому вероятность образования очереди равна:
Вероятность отказа в обслуживании наступает тогда, когда все каналов и все мест в очереди заняты:
Относительная пропускная способность будет равна:
Абсолютная пропускная способность -
Среднее число занятых каналов -
Среднее число простаивающих каналов -
Коэффициент занятости (использования) каналов -
Коэффициент простоя каналов -
Среднее число заявок, находящихся в очередях -
В случае если, эта формула принимает другой вид -
Среднее время ожидания в очереди определяется формулами Литтла -
Многоканальная система массового обслуживания с ограниченной очередью
Пусть на вход СМО, имеющей каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью. Интенсивность обслуживания заявки каждым каналом равна, а максимальное число мест в очереди равно.
Граф такой системы представлен на рисунке 7.
Рисунок 7 - Граф состояний многоканальной СМО с ограниченной очередью
Все каналы свободны, очереди нет;
Заняты l каналов (l = 1, n), очереди нет;
Заняты все n каналов, в очереди находится i заявок (i = 1, m).
Сравнение графов на рисунке 2 и рисунке 7 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):
Выражения для финальных вероятностей легко найти из формул (4) и (5). В результате получим:
Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m - 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди p оч равна сумме соответствующих вероятностей:
Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е.:
Относительная пропускная способность равна:
Среднее число заявок, находящихся в очереди, определяется по формуле (11) и может быть записано в виде:
Среднее число заявок, обслуживаемых в СМО, может быть записано в виде:
Среднее число заявок, находящихся в СМО:
Среднее время пребывания заявки в СМО и в очереди определяется формулами (12) и (13).
Многоканальная система массового обслуживания с неограниченной очередью
Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке 7 при.
Рисунок 8 - Граф состояний многоканальной СМО с неограниченной очередью
Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при. При этом следует иметь в виду, что при вероятность р 0 = р 1 =…= p n = 0, т.е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай. При из (26) получим:
Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:
Из (27) получим выражение для вероятности образования очереди заявок:
Поскольку очередь не ограничена, то вероятность отказа в обслуживании заявки:
Абсолютная пропускная способность:
Из формулы (28) при получим выражение для среднего числа заявок в очереди:
Среднее число обслуживаемых заявок определяется формулой:
Среднее время пребывания в СМО и в очереди определяется формулами (12) и (13).
Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди
Отличие такой СМО от СМО, рассмотренной в подразделе 5.5, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром, где - среднее время ожидания заявки в очереди, а - имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 9.
Рисунок 9 - Граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди
Остальные обозначения имеют здесь тот же смысл, что и в подразделе.
Сравнение графов на рис. 3 и 9 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):
Выражения для финальных вероятностей легко найти из формул (4) и (5) с учетом (29). В результате получим:
где. Вероятность образования очереди определяется формулой:
Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е. вероятность отказа в обслуживании:
Относительная пропускная способность:
Абсолютная пропускная способность:
Среднее число заявок, находящихся в очереди, находится по формуле (11) и равно:
Среднее число заявок, обслуживаемых в СМО, находится по формуле (10) и равно:
Назначение сервиса СМО . Онлайн-калькулятор предназначен для расчета следующих показателей одноканальных СМО:- вероятность отказа канала, вероятность свободного канала, абсолютная пропускная способность;
- относительная пропускная способность, среднее время обслуживания, среднее время простоя канала.
Инструкция . Для решения подобных задач в онлайн режиме выберите модель СМО. Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Для одноканальной СМО с ограниченной длиной очереди можно указать длину очереди m , а для одноканальной СМО с неограниченной очередью - число заявок в очереди (для расчета вероятности нахождения этих заявок в очереди). см. пример решения . . Полученное решение сохраняется в файле Word .
Классификация одноканальных систем массового обслуживания
Пример №1 . Авто заправочная станция имеет одну бензоколонку. Предполагается что простейший поток автомашин поступает на станцию с интенсивностью λ=11 автомашин/ч. Время обслуживания заявки случайная величина которая подчиняется экспоненциальному закону с параметром μ=14 автомашин/ч. Определить среднее число автомашин на станции.
Пример №2
. Имеется пункт проведения профилактического осмотра машин с одной группой проведения осмотра. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,4 часа. На осмотр поступает в среднем 328 машин в сутки. Потоки заявок и обслуживаний - простейшие. Если машина, прибывшая в пункт осмотра не застает ни одного канала свободным, она покидает пункт осмотра необслуженной. Определить предельные вероятности состояний и характеристики обслуживания пункта профилактического осмотра.
Решение. Здесь α = 328/24 ≈ = 13.67, t = 0.4. Эти данные необходимо ввести в калькулятор.
Тема. Теория систем массового обслуживания.
Каждая СМО состоит из какого–то количества обслуживающих единиц, которые называются каналами обслуживания (это станки, транспортные тележки, роботы, линии связи, кассиры, продавцы и т.д.). Всякая СМО предназначена для обслуживания какого–то потока заявок (требований), поступающих в какие-то случайные моменты времени.
Классификация СМО по способу обработки входного потока заявок.
Системы массового обслуживания
С отказами
(без очереди)
С очередью
Неограниченная очередь
Ограниченная очередь
С приоритетом
В порядке поступления
Относительный приоритет
Абсолютный приоритет
По времени обслуживания
По длине очереди
Классификация по способу функционирования:
открытыми, т.е. поток заявок не зависит от внутреннего состояния СМО;
закрытыми, т.е. входной поток зависит от состояния СМО (один ремонтный рабочий обслуживает все каналы по мере их выхода из строя).
Многоканальная СМО с ожиданием
Система с ограниченной длиной очереди. Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди
Состояния системы нумеруются по числу заявок, связанных системой:
нет очереди:
- все каналы свободны;
- занят один канал, остальные свободны;
- заняты -каналов, остальные нет;
- заняты все -каналов, свободных нет;
есть очередь:
- заняты все 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)
На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:
Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на Замкнутые СМО
До сих пор мы рассматривали системы, в которых входящий поток никак не связан с выходящим. Такие системы называются разомкнутыми. В некоторых же случаях обслуженные требования после задержки опять поступают на вход. Такие СМО называются замкнутыми. Поликлиника, обслуживающая данную территорию, бригада рабочих, закрепленная за группой станков, являются примерами замкнутых систем.
В замкнутой СМО циркулирует одно и то же конечное число потенциальных требований. Пока потенциальное требование не реализовалось в качестве требования на обслуживание, считается, что оно находится в блоке задержки. В момент реализации оно поступает в саму систему. Например, рабочие обслуживают группу станков. Каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта - в самой системе. Каждый рабочий является каналом обслуживания. = =P 1 + 2 P 2 +…+(n- 1 )P n- 1 +n( 1 -P На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом t обсл =1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?
Пример 2 . /μ=2, ρ/ n =2/3<1.
Задача 3:
Два рабочих обслуживают группу из четырех станков. Остановки работающего станка происходят в среднем через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время наладки распределено по экспоненциальному закону.
Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.
Найдите те же характеристики для системы, в которой:
а) за каждым рабочим закреплены два станка;
б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;
в) единственный неисправный станок обслуживают оба рабочих сразу (с двойной интенсивностью), а при появлении еще хотя бы одного неисправного станка они начинают работать порознь, причем каждый обслуживает один станок (вначале опишите систему в терминах процессов гибели и рождения).
В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).
Рассмотрим простую одноканальную СМО с ограниченной очередью, в которой число мест в очереди т - фиксированная величина. Следовательно, заявка, поступившая в тот момент, когда все места в очереди заняты, не принимается к обслуживанию, не встает в очередь и.покидает систему.
Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения--гибели», с тем отличием, что при наличии только одного канала.
Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны
Состояния СМО можно представить следующим образом:
S0 - канал обслуживания свободен,
S, - канал обслуживания занят, но очереди нет,
S2- канал обслуживания занят, в очереди стоит одна заявка,
S3- канал обслуживания занят, в очереди стоят две заявки,
Sm+1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.
Для описания случайного процесса СМО можно воспользоваться изложенными ранее правилами и формулами. Напишем выражения, определяющие предельные вероятности состояний:
Выражение для р0 можно в данном случае записать проще, пользуясь тем, что в знаменателе стоит геометрическая прогрессия относительно р, тогда после соответствующих преобразований получаем:
с= (1- с)
Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2).
Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании.
Действительно, выражение для предельной вероятности р0в случае т = 0 имеет вид:
pо = м / (л+м)
И в случае л =м имеет величину р0= 1 / 2.
Определим основные характеристики одноканальной СМО с ожиданием: относительную и абсолютную пропускную способность, вероятность отказа, а также среднюю длину очереди и среднее время ожидания заявки в очереди.
Заявка получает отказ, если она поступает в момент времени, когда СМО уже находится в состоянии Sm+1 и, следовательно, все места в очереди да заняты и один канал обслуживает
Поэтому вероятность отказа определяется вероятностью появлением
Состояния Sm+1:
Pотк = pm+1 = сm+1 * p0
Относительная пропускная способность, или доля обслуживаемых заявок, поступающих в единицу времени, определяется выражением
Q = 1- pотк = 1- сm+1 * p0
абсолютная пропускная способность равна:
Среднее число заявок Lочстоящих в очереди на обслуживание, определяется математическим ожиданием случайной величины к - числа заявок, стоящих в очереди
случайная величина к принимает следующие только целочисленные значения:
- 1 - в очереди стоит одна заявка,
- 2 - в очереди две заявки,
т-в очереди все места заняты
Вероятности этих значений определяются соответствующими вероятностями состояний, начиная с состояния S2. Закон распределения дискретной случайной величины к изображается следующим образом:
Таблица 1. Закон распределения дискретной случайной величины
Математическое ожидание этой случайной величины равно:
Lоч = 1* p2 +2* p3 +...+ m* pm+1
В общем случае при p ?1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:
Lоч = p2 * 1- pm * (m-m*p+1) * p0
В частном случае при р = 1, когда все вероятности pkоказываются равными, можно воспользоваться выражением для суммы членов числового ряда
1+2+3+ m = m(m+1)
Тогда получим формулу
L"оч= m(m+1) * p0 = m(m+1) (p=1).
Применяя аналогичные рассуждения и преобразования, можно показать, что среднее время ожидания обслуживания заявки а очереди определяется формулами Литтла
Точ = Lоч/А (при р? 1) и Т1оч= L"оч /А(при р = 1).
Такой результат, когда оказывается, что Точ ~ 1/ л, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина Lоч является функцией от л и м и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.
Заявка, поступившая в СМО в момент времени, когда все каналы заняты, получает отказ, и, следовательно, время ее «ожидания» в СМО равно нулю. Это приводит в общем случае (при р? 1) к уменьшению Точростом л, поскольку доля таких заявок с ростом л увеличивается.
Если отказаться от ограничения на длину очереди, т.е. устремить m--> >?, то случаи р < 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду
При достаточно большом к вероятностьpk стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А --л Q -- л следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:
Lоч =p2 1-p
а среднее время ожидания по формуле Литтла
Точ = Lоч/А
В пределе р << 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t > ?). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки.
Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем с и м, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.
В качестве одной из характеристик СМО используют среднее время Тсмо пребывания заявки в СМО, включающее среднее время пребывания в очереди и среднее время обслуживания. Эта величина вычисляется по формулам Литтла: если длина очереди ограничена -- среднее число заявок, находящихся в очереди, равно:
Lсмо= m+1 ;2
Тсмо= Lсмо; при p ?1
A тогда среднее время пребывания заявки в системе массового обслуживания (как в очереди, так и под обслуживанием) равно:
Тсмо= m+1 при p ?1 2м