Одноканальная смо с неограниченной очередью без времени. Конспект урока "теория систем массового обслуживания"

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

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

Граф такой системы представлен на рисунке 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) и равно:

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

Sq - все каналы свободны, k = 0;

S - занят только один канал (любой), k = 1;

*5*2 - заняты только два канала (любых), k = 2;

S n - заняты все п каналов, k = п.

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

S n + - заняты все п каналов и одна заявка стоит в очереди, k = п + 1;

S n +2 - заняты все п каналов и две заявки стоят в очереди, k = п + 2;

S n+m - заняты все п канатов и все т мест в очереди, k = n + m.

Граф состояний и-канальной СМО с очередью, ограниченной т местами, представлен на рис. 5.18.

Переход СМО в состояние с большими номерами определяется потоком поступающих заявок с интенсивностью

Рис. 5.18

тогда как по условию в обслуживании этих заявок принимают участие п одинаковых каналов с интенсивностью потока обслуживания, равной р для каждого канала. При этом полная интенсивность потока обслуживания возрастает с подключением новых каналов вплоть до такого состояния S n , когда все п каналов окажутся занятыми. С появлением очереди интенсивность обслуживания более не увеличивается, так как она уже достигла максимального значения, равного пх.

Запишем выражения для предельных вероятностей состояний

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

Образование очереди возможно, когда вновь поступившая заявка застанет в системе не менее п требований, т.е. когда в системе будет находиться п, п + 1, п + 2, (п + т - 1) требований. Эти события независимы, поэтому вероятность того, что все каналы заняты, равна сумме соответствующих вероятностей р ю Рп+ьРп+ 2 > ->Рп+т- 1- Поэтому вероятность образования очереди равна

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

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

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

Среднее число занятых каналов

Среднее число простаивающих каналов

Коэффициент занятости (использования) каналов

Коэффициент простоя каналов

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

в случае если р/п = 1, эта формула принимает другой вид:

Среднее время ожидания в очереди определяется формулами Литтла

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

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

Решение

п = 3; т = 5; X = 6; р = 2; р = Х/х = 3; р/п = 1.

Находим предельные вероятности состояний СМО:

Доля времени простоя контролеров-кассиров

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

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

Вероятность того, что заняты все три канала,

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

Вероятность отказа в обслуживании наступает при k = т + п = = 5 + 3 = 8 и составляет р$ = р ОТК = 0,127.

Относительная и абсолютная пропускные способности СМО соответственно равны Q = 1 - р отк = 0,873 и Л = 0,873А. = 5,24 (поку- пателя/мин).

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

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

Система обслуживания минимаркета заслуживает высокой оценки, поскольку средняя длина очереди, среднее время пребывания покупателя в очереди составляют малые величины.

Пример 5.22. Па плодоовощную базу в среднем через 30 мин прибывают автомашины с плодоовощной продукцией. Среднее время разгрузки одной машины составляет 1,5 ч. Разгрузку производят две бригады грузчиков. На территории базы у дебаркадера могут находиться в очереди в ожидании разгрузки не более четырех автомашин. Определим показатели и дадим оценку работы СМО.

Решение

СМО двухканальная, п = 2 с ограниченным числом мест в очереди m = 4, интенсивность входящего потока л. = 2 авт/ч, интенсивность обслуживания ц = 2/3 авт/ч, интенсивность нагрузки р = А./р = 3, р/п = 3/2 = 1,5.

Определяем характеристики СМО:

Вероятность того, что все бригады не загружены, когда нет автомашин,

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

Среднее число автомашин в очереди

Доля времени простоя грузчиков очень мала и составляет всего 1,58% рабочего времени, а вероятность отказа велика - 36% заявок из числа поступивших получают отказ в разгрузке, обе бригады практически заняты полностью, коэффициент занятости близок к единице и равен 0,96, относительная пропускная способность мала - всего 64% из числа поступивших заявок будут обслужены, средняя длина очереди - 2,6 автомашины, следовательно, СМ О нс справляется с выполнением заявок на обслуживание и необходимо увеличить число бригад грузчиков и шире использовать возможности дебаркадера.

Пример 5.23. Коммерческая фирма получает но кольцевому завозу ранние овощи из теплиц пригородного совхоза в случайные моменты времени с интенсивностью 6 ед. в день. Подсобные помещения, оборудование и трудовые ресурсы позволяют обработать и хранить продукцию в объеме 2 ед. В фирме работают четыре человека, каждый из которых в среднем может обработать продукцию одного завоза в течение 4 ч. Продолжительность рабочего дня при сменной работе составляет 12 ч. Какова должна быть емкость складского помещения, чтобы полная обработка продукции была бы не менее 97% из числа осуществляемых поставок?

Решение

Решим задачу путем последовательного определения показателей СМО для различных значений емкости складского помещения т = 2, 3, 4, 5 и т.д. и сравнения на каждом этапе расчетов вероятности обслуживания с заданной величиной р 0 ()С = 0,97.

Определяем интенсивность нагрузки:

Находим вероятность, или долю времени, простоя для т = 2:

Вероятность отказа в обслуживании, или доля потерянных заявок,

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

Поскольку полученная величина меньше заданной величины 0,97, то продолжаем вычисления для т = 3. Для этой величины показатели состояний СМО имеют значения

Вероятность обслуживания и в этом случае меньше заданной величины, поэтому продолжаем вычисления для следующего т = 4, для которого показатели состояния имеют такие значения: р$ = 0,12; Ротк = 0,028; Pofc = 0,972. Теперь полученная величина вероятности обслуживания удовлетворяет условию задачи, поскольку 0,972 > 0,97, следовательно, емкость складского помещения необходимо увеличить до объема 4 ед.

Для достижения заданной вероятности обслуживания можно подобрать таким же образом оптимальное количество человек на обработке овощей, проводя последовательно вычисления показателей СМО для п = 3, 4, 5 и т.д. Компромиссный вариант решения можно найти путем сравнения и сопоставления для разных вариантов организаций СМО затрат, связанных как с увеличением числа работающих, так и с созданием специального технологического оборудования но обработке овощей на коммерческом предприятии.

Таким образом, модели массового обслуживания в сочетании с экономическими методами постановки задач позволяют проводить анализ существующих СМО, разрабатывать рекомендации по их реорганизации для повышения эффективности работы, а также определять оптимальные показатели вновь создаваемых СМО.

Пример 5.24. На автомойку в среднем за час приезжают девять автомобилей, но если в очереди уже находятся четыре автомобиля, вновь подъезжающие клиенты, как правило, не встают в очередь, а проезжают мимо. Среднее время мойки автомобиля составляет 20 мин, а мест для мойки всего два. Средняя стоимость мойки автомобиля составляет 70 руб. Определите среднюю величину потери выручки автомойки в течение дня.

Решение

X = 9 авт/ч; = 20 мин; п = 2;т = 4.

Находим интенсивность нагрузки Определяем долю времени простоя автомойки

Вероятность отказа

Относительная пропускная способность равна Абсолютная пропускная способность Среднее число автомобилей в очереди

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

Среднее время ожидания в очереди

Среднее время пребывания автомашины на мойке

Таким образом, 34% заявок не будут обслужены, потеря за 12 ч работы одного дня составит в среднем 2570 руб. (12*9* 0,34 70), т.е. 52% от всей выручки, поскольку р отк = 0,52 р 0 ^ с.

относительная пропускная способность, или вероятность обслуживания, абсолютная пропускная способность среднее число занятых бригад коэффициент занятости работой бригад грузчиков

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

Пусть на каналы обслуживания поступает простейший поток требований интенсивностью λ. Поток обслуживания, поступающий с одного канала, также простейший и имеет интенсивность μ. Число мест в очереди ограничено и равно т.

По числу заявок, находящихся в системе, обозначим состояния системы:

S 0 - состояние простоя;

S п - состояние системы, когда все каналы заняты обслуживанием;

S п+1 - все каналы заняты, одна заявка находится в очереди;

S п+т - в очереди т заявок.

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

λ λ λ λ λ λ

……. …….

S 0 S 1 S 2 S n S n+m

μ 2μ 3μ ………. nμ nμ …… nμ

Рисунок 7: Многоканальная СМО с ограниченной очередью.

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

Откуда получим формулы Эрланга для многоканальной системы с ограниченной очередью:

Последние т слагаемых в скобках представляют собой сумму т первых членов геометрической прогрессии со знаменателем ρ/n которая равна:

Таким образом, для вычисления р 0 получим формулу:

Формулы для вероятностей предельных состояний будут иметь вид:

Приведем формулы для расчета основных показателей эффективности работы системы.

Число каналов, которые необходимо иметь, чтобы система справлялась с потоком заявок, определим из условия

В этом случае выполняется соотношение ρ < 1.

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

Отсюда вероятность обслуживания (а также и относительная пропускная способность системы) равны вероятности противоположного события:

Абсолютная пропускная способность - число заявок, обслуженных системой в единицу времени:

Так как каждый канал обслуживает μзаявок в единицу времени, то среднее число занятых каналов можно вычислить:

Среднее время обслуживания каналом одной заявки:

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

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

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

Многоканальную СМО с ограниченной очередью можно рассмотреть в Mathcad.

Пример :

Площадка АЗС вмещает не более 3-х машин одновременно, и если она занята, то очередная машина, прибывшая к станции, в очередь не становится. Интенсивность потока обслуживания λ=0,5 машин в минуту. Интенсивность потока обслуживания μ=0,4 машины в минуту. Определить все характеристики СМО.

Фрагмент решения задачи в Mathcad.

Продолжение задачи в Mathcad.

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен на рис. 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м

Назначение сервиса СМО . Онлайн-калькулятор предназначен для расчета следующих показателей одноканальных СМО:

вероятность отказа канала, вероятность свободного канала, абсолютная пропускная способность;
относительная пропускная способность, среднее время обслуживания, среднее время простоя канала.

Инструкция . Для решения подобных задач в онлайн режиме выберите модель СМО. Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Для одноканальной СМО с ограниченной длиной очереди можно указать длину очереди m , а для одноканальной СМО с неограниченной очередью - число заявок в очереди (для расчета вероятности нахождения этих заявок в очереди). см. пример решения . . Полученное решение сохраняется в файле Word .

Классификация одноканальных систем массового обслуживания

Пример №1 . Авто заправочная станция имеет одну бензоколонку. Предполагается что простейший поток автомашин поступает на станцию с интенсивностью λ=11 автомашин/ч. Время обслуживания заявки случайная величина которая подчиняется экспоненциальному закону с параметром μ=14 автомашин/ч. Определить среднее число автомашин на станции.

Пример №2 . Имеется пункт проведения профилактического осмотра машин с одной группой проведения осмотра. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,4 часа. На осмотр поступает в среднем 328 машин в сутки. Потоки заявок и обслуживаний - простейшие. Если машина, прибывшая в пункт осмотра не застает ни одного канала свободным, она покидает пункт осмотра необслуженной. Определить предельные вероятности состояний и характеристики обслуживания пункта профилактического осмотра.
Решение. Здесь α = 328/24 ≈ = 13.67, t = 0.4. Эти данные необходимо ввести в калькулятор.