Смо с m приборами и ограниченной очередью. Многоканальная смо с ограниченной длиной очереди. Эксперимент на имитационной модели

Многоканальная СМО с неограниченной очередью

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

Система может находиться в одном из состояний S0, S1, S2, …, Sk .., Sn, …, нумеруемых по числу заявок, находящихся в СМО: S0 — в системе нет заявок (все каналы свободны); S — занят один канал, остальные свободны; S2– заняты два канала, остальные свободны; Sk — занято k каналов, остальные свободны; Sn — заняты все n каналов (очереди нет); Sn+1 — заняты все п каналов, в очереди одна заявка; Sn+r — заняты все п каналов, r заявок стоит в очереди.

Граф состояний системы показан на рисунке 7. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживаний (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины м до n??, так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем n, интенсивность потока обслуживании сохраняется равной nм.

Рисунок 7 – Граф состояний многоканальной СМО

Можно показать, что при с/n < 1 предельные вероятности существуют. Если с/n ? 1, очередь растет до бесконечности. Используя формулы (20) и (21) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью

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

Для n-канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:

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

среднее число заявок в системе

Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (48) и (49).

Замечание. Для СМО с неограниченной очередью при с < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа Ротк = 0, Q=1, а равна интенсивности входящего потока заявок, т.е. А = л.

СМО с ограниченной очередью

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

Одноканальная СМО с ограниченной длиной очереди

Предельные вероятности:

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

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

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

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

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

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

Многоканальная СМО с ограниченной очередью

Предельные вероятности:

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

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

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

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

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

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

Все каналы свободны, ;

Занят только один канал (любой), ;

• – заняты только два канала (любых), ;
• – заняты все каналов, .

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

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

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

Заняты все каналов и все мест в очереди,

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

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

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

Образование очереди возможно, когда вновь поступившая заявка застанет в системе не менее требований, т.е. когда в системе будет находиться требований.

Эти события независимы, поэтому вероятность того, что все каналы заняты, равна сумме соответствующих вероятностей

Поэтому вероятность образования очереди равна:

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

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

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

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

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

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

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

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

В случае если, эта формула принимает другой вид –

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

В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.

Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:

S 0 – система свободна и находится в состоянии простоя;

S 1 – обслуживается одна заявка, канал занят, очереди нет;

S 2 – одна заявка обслуживается, одна в очереди;

S m +1 – одна заявка обслуживается,т в очереди.

Граф состояний такой системы показан на рисунке номер 5:

S 0 S 1 S 2 S m+1

μ μ μ ………. μ μ

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

В формуле для р 0 найдем сумму конечного числа членов геометрической прогрессии:

(52)

С учетом формулы для ρ получим выражение:

В скобках находится (m+2) элементов геометрической прогрессии с первым членом 1 и знаменателем ρ. По формуле суммы (m+2) членов прогрессии:

(54)

(55)

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

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

(57)

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

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

(59)

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

(60)

(61)

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

(62)

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

Пример :

На стоянке обслуживается 3 машины с интенсивностью потока 0,5 и средним временем обслуживания 2,5 минуты. Определить все показатели системы.

6 Многоканальная смо с неограниченной очередью

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

По числу заявок, находящихся в системе, обозначим состояния системы: S 0 ,S 1 ,S 2 ,…,S k ,… S n , гдеS k – состояние системы, когда в ней находитсяkзаявок (максимальное число заявок под обслуживанием -n). Граф состояний такой системы изображается в виде схемы на рисунке номер 6:

λ λ λ λ λ λ λ

……. …….

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

μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ

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

Интенсивность потока обслуживаний меняется в зависимости от состояния системы: kμпри переходе из состоянияS k в состояниеS k -1 так как может освободиться любой изkканалов; после того, как все каналы заняты обслуживанием, интенсивность потока обслуживаний остается равнойпμ, при поступлении в систему следующих заявок.

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

(63)

Отсюда формулы для финальных вероятностей выражаются через

Для нахождения р 0 получим уравнение:

Для слагаемых в скобках, начиная с (n+ 2)-го, можно применить формулу нахождения суммы бесконечно убывающей геометрической прогрессии с первым членоми знаменателем ρ/n:

(66)

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

(67)

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

Система будет справляться с потоком заявок, если

выполнено условие

, (68)

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

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

(69)

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

(70)

Если система справляется с потоком заявок, то в стационарном режиме интенсивность выходящего потока равна интенсивности потока поступающих в систему заявок, так как обслуживаются все заявки:

ν=λ . (71)

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

(72)

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

. (73)

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

(74)

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

(75)

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

(76)

Тогда среднее число заявок в системе:

(77)

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

(78)

(79)

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

Пример 1 :

Салон-парикмахерская имеет 5 мастеров. В час пик интенсивность потока клиентов равна 6 человек. В час. Обслуживание одного клиента длится в среднем 40 минут. Определить среднюю длину очереди, считая ее неограниченной.

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

Пример 2:

В железнодорожной кассе имеются 2 окна. Время на обслуживания одного пассажира 0,5 минут. Пассажиры подходят к кассе по 3 человека. Определить все характеристики системы.

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

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

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

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

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

На практике довольно часто встречаются одноканальные СМО с очередью (врач, обслуживающий пациентов; телефон-автомат с одной будкой; ЭВМ, выполняющая заказы пользователей). В теории массового обслуживания одноканальные СМО с очередью также занимают особое место (именно к таким СМО относится большинство полученных до сих пор аналитических формул для немарковских систем). Поэтому мы уделим одноканальной СМО с очередью особое внимание.

Пусть имеется одноканальная СМО с очередью, на которую не наложено никаких ограничений (ни по длине очереди, ни по времени ожидания). На эту СМО поступает поток заявок с интенсивностью λ; поток обслуживаний имеет интенсивность μ, обратную среднему времени обслуживания заявки tоб. Требуется найти финальные вероятности состояний СМО, а также характеристики ее эффективности:

Lсист – среднее число заявок в системе,

Wсист – среднее время пребывания заявки в системе,

Lоч – среднее число заявок в очереди,

Woч – среднее время пребывания заявки в очереди,

Рзан – вероятность того, что канал занят (степень загрузки канала).

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности: в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, поэтому А=λ, по той же причине Q = 1.

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

S0 – канал свободен,

S1 – канал занят (обслуживает заявку), очереди нет,

S2 – канал занят, одна заявка стоит в очереди,

Sk – канал занят, k – 1 заявок стоят в очереди.

Теоретически число состояний ничем не ограничено (бесконечно). Граф состояний имеет вид, показанный на рис. 4.11. Это – схема гибели и размножения, но с бесконечным числом состояний. По всем стрелкам поток заявок с интенсивностью λ переводит систему слева направо, а справа налево – поток обслуживаний с интенсивностью μ.

Рис. 4.11. Граф состояний СМО в виде схемы гибели и размножения с бесконечным числом состояний

Прежде всего, спросим себя, а существуют ли в этом случае финальные вероятности? Ведь число состояний системы бесконечно, и, в принципе, при t→∞ очередь может неограниченно возрастать! Да, так оно и есть: финальные вероятности для такой СМО существуют не всегда, а только когда система не перегружена. Можно доказать, что если р строго меньше единицы (р<1), то финальные вероятности существуют, а при р ≥ 1 очередь при t →∞ растет неограниченно. Особенно «непонятным» кажется этот факт при р = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При р = 1 СМО справляется с потоком заявок, только если поток этот - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом «идеальном» случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживаний стать хотя бы немного случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что «бесконечное число заявок в очереди» - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!

Но вернемся к нашей одноканальной СМО с неограниченной очередью. Строго говоря, формулы для финальных вероятностей в схеме гибели и размножения выводились нами только для случая конечного числа состояний, но воспользуемся ими и для бесконечного числа состояний. Подсчитаем финальные вероятности состояний по формулам (4.21), (4.20). В нашем случае число слагаемых в формуле (4.21) будет бесконечным. Получим выражение для р0:

откуда

Вероятности р1, р2, …, рk, … найдутся по формулам:

откуда, с учетом (4.38), найдем окончательно:

p 1 = ρ(1 – ρ), = ρ2(1- ρ), . . ., pk = ρ4(1- ρ), . . . (4.39)

Как видно, вероятности р0, р1, …, pk, … образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р0 – вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (р <1), самое вероятное число заявок в системе будет 0.

Найдем среднее число заявок в СМО Lсист. Случайная величина Z – число заявок в системе – имеет возможные значения 0, 1, 2, …, k, … с вероятностями р0, р1, p2, …, рk, … Ее математическое ожидание равно

(сумма берется не от 0 до ∞, а от 1 до ∞, так как нулевой член равен нулю).

Подставим в формулу (4.40) выражение для рk (4.39):

Теперь вынесем за знак суммы р (1 – р):

Тут мы опять применим «маленькую хитрость»: kpk-1 есть не что иное, как производная по р от выражения рk; значит,

Меняя местами операции дифференцирования и суммирования, получим:

Ну, а теперь применим формулу Литтла (4.25) и найдем среднее время пребывания заявки в системе:

Найдем среднее число заявок в очереди Lоч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди Lоч равно среднему числу заявок в системе Lсист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Рзан). Очевидно, Рзан равно единице минус вероятность р0 того, что канал свободен:

и окончательно

Таким образом, все характеристики эффективности СМО найдены.

Предложим читателю самостоятельно решить пример: одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 2 (состава в час). Обслуживание (расформирование) состава длится случайное (показательное) время со средним значением tоб = 20 (мин.). В парке прибытия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внешних путях. Требуется найти (для предельного, стационарного режима работы станции): среднее число составов Lсист, связанных со станцией, среднее время Wсист пребывания состава при станции (на внутренних путях, на внешних путях и под обслуживанием), среднее число Lоч составов, ожидающих очереди на расформирование (все равно, на каких путях), среднее время Wоч пребывания состава на очереди. Кроме того, попытайтесь найти среднее число составов, ожидающих расформирования на внешних путях Lвнеш и среднее время этого ожидания Wвнеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: Lcист = 2 (состава), Wсист = i (час), Lоч = 4/3 (состава), Wоч = 2/3 (часа), Lвнеш = 16/27 (состава), Wвнеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а: Ш ≈ 14,2а.