Многоканальная смо с неограниченным ожиданием. Одноканальная смо с неограниченной очередью
Многоканальная СМО с неограниченной очередью
Рассмотрим задачу. Имеется 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 заявок, т.е. заявка, заставшая в момент своего прихода в СМО m +1 заявок (m ожидающих в очереди и одну, находящуюся на обслуживании), покидает СМО.
Система уравнений, описывающих процесс в этой системе, имеет решение:
(0‑1)
Знаменатель первого выражения представляет собой геометрическую прогрессию с первым членом 1 и знаменателем ρ, откуда получаем
При ρ = 1 можно прибегнуть к прямому подсчету
(0‑8)
Среднее число находящихся в системе заявок.
Поскольку среднее число находящихся в системе заявок
(0‑9)
где - среднее число заявок, находящихся под обслуживанием, то зная остается найти . Т.к. канал один, то число обслуживаемых заявок может равняться либо 0, либо 1 с вероятностями P 0 и P 1=1- P 0 соответственно, откуда
(0‑10)
и среднее число находящихся в системе заявок равно
(0‑11)
Среднее время ожидания заявки в очереди .
т.е., среднее время ожидания заявки в очереди равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Среднее время пребывания заявки в системе.
Время пребывания заявки в системе складывается из времени ожидания заявки в очереди и времени обслуживания. Если загрузка системы составляет 100%, то =1/μ, в противном случае = q / μ . Отсюда
(0‑13)
Содержание работы .
Подготовка инструментария эксперимента .
Выполняется аналогично в соответствии с общими правилами.
Расчет на аналитической модели .
1. В приложение Microsoft Excel подготовьте таблицу следующего вида.
2. В столбцах для параметров СМО таблицы запишите исходные данные, которые определяются по правилу:
m=1,2,3
(максимальная длина очереди).
Для каждого значения m необходимо найти теоретические и экспериментальные значения показателей СМО для таких пар значений:
= <порядковый номер в списке группы>
3. В столбцы с показателями аналитической модели впишите соответствующие формулы.
Эксперимент на имитационной модели .
1. Установите режим запусков с экспоненциально распределенным временем обслуживания, задав значение соответствующего параметра равным 1.
2. Для каждой комбинации m , и осуществите запуск модели.
3. Результаты запусков внесите в таблицу.
4. Внесите в соответствующие столбцы таблицы формулы для расчета среднего значения показателя P отк , q и А.
Анализ результатов .
1. Проанализируйте результаты, полученные теоретическим и экспериментальным способами, сравнив результаты между собой.
2. Для m=3 постройте на одной диаграмме графики зависимости P отк от на теоретически и экспериментально полученных данных.
Оптимизация параметров СМО .
Решите задачу оптимизации размера числа мест в очереди m для прибора со средним временем обслуживания = с точки зрения получения максимальной прибыли. В качестве условий задачи возьмите:
- доход от обслуживания одной заявки равным 80 у.е./час,
- стоимость содержания одного прибора равным 1у.е./час.
1. Для расчетов целесообразно создать таблицу:
Первый столбец заполняется значениями чисел натурального ряда (1,2,3…).
Все клетки второго и третьего столбцов заполняются значениями и.
В клетки столбцов с четвертого по девятый переносятся формулы для столбцов таблицы раздела 0.
В столбцы с исходными данными разделов Доход, Расход, Прибыль внесите значения (см. выше).
В столбцах с вычисляемыми значениями разделов Доход, Расход, Прибыль запишите расчетные формулы:
- число заявок в единицу времени
N r =A
- суммарный доход в единицу времени
I S = I r *N r
- суммарный расход в единицу времени
E S =E s + E q *(n-1)
- прибыль в единицу времени
P = I S - E S
где
I r - доход от одной заявки ,
E s - расход на эксплуатацию одного прибора ,
E q - расход на эксплуатацию одного места в очереди .
Графики для P отк ,
- таблицу с данными для нахождения наилучшего m и значение m опт,
- график зависимости прибыли в единицу времени от m .
Контрольные вопросы :
1) Дайте краткое описание одноканальной модели СМО с ограниченной очередью.
2) Какими показателями характеризуется функционирование одноканальной СМО с отказами?
3) Как рассчитывается вероятность p 0 ?
4) Как рассчитываются вероятности p i ?
5) Как найти вероятность отказа обслуживания заявки?
6) Как найти относительную пропускную способность?
7) Чему равна абсолютная пропускная способность?
8) Как подсчитывается среднее число заявок в системе?
9) Приведите примеры СМО с ограниченной очередью.
Задачи .
1) Порт имеет один грузовой причал для разгрузки судов. Интенсивность потока составляет 0,5 заходов в сутки. Среднее время разгрузки одного судна 2 суток. Если в очереди на разгрузку стоят 3 судна, то приходящее судно направляется для разгрузки на другой причал. Найти показатели эффективности работы причала.
2) В справочную железнодорожного вокзала поступают телефонные запросы с интенсивностью 80 заявок в час. Оператор справочной отвечает на поступивший звонок в среднем 0,7 мин. Если оператор занят, клиенту выдается сообщение "Ждите ответа", запрос становится в очередь, длина которой не превышает 4 запросов. Дайте оценку работы справочной и вариант ее реорганизации
На практике довольно часто встречаются одноканальные СМО с очередью (врач, обслуживающий пациентов; телефон-автомат с одной будкой; ЭВМ, выполняющая заказы пользователей). В теории массового обслуживания одноканальные СМО с очередью также занимают особое место (именно к таким СМО относится большинство полученных до сих пор аналитических формул для немарковских систем). Поэтому мы уделим одноканальной СМО с очередью особое внимание.
Пусть имеется одноканальная СМО с очередью, на которую не наложено никаких ограничений (ни по длине очереди, ни по времени ожидания). На эту СМО поступает поток заявок с интенсивностью λ; поток обслуживаний имеет интенсивность μ, обратную среднему времени обслуживания заявки 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а.
Рассмотрим теперь одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Рассмотрим систему с ограниченной очередью . Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N -требований (заявок), из которых одна обслуживается, а (N -1) ожидают, Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются.
Обозначим - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:
Здесь - приведенная интенсивность потока. Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна: 
.
С учетом этого можно обозначить
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):
вероятность отказа в обслуживании заявки:
относительная пропускная способность системы:
абсолютная пропускная способность:
А =q ∙λ;
среднее число находящихся в системе заявок:
среднее время пребывания заявки в системе:
;
средняя продолжительность пребывания клиента (заявки) в очереди:
W q =W s - 1/μ;
среднее число заявок (клиентов) в очереди (длина очереди):
L q =λ(1-P N )W q .
Рассмотрим пример одноканальной СМО с ожиданием.
Пример 9.2 . В зону таможенного контроля в пункте пропуска автомобили въезжают по системе электронной очереди. Каждое окно оформления прибытия/убытия представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих оформления, ограниченно и равно 3, то есть (N -1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль в зону таможенного контроля не пропускается, т.е. в очередь на обслуживание не становится. Поток автомобилей, прибывающих на оформление имеет интенсивность λ =0,85 (автомобиля в час). Время оформления автомобиля распределено по показательному закону и в среднем равно =1,05 час. Требуется определить вероятностные характеристики окна оформления прибытия/убытия пункта пропуска, работающего в стационарном режиме.
Решение.
Интенсивность потока обслуживаний автомобилей:
.
Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей λ и μ, т.е.
.
Вычислим вероятности нахождения п заявок в системе:
;
P 1 =ρ∙P 0 =0,893∙0,248=0,221;
P 2 =ρ 2 ∙P 0 =0,893 2 ∙0,248=0,198;
P 3 =ρ 3 ∙P 0 =0,893 3 ∙0,248=0,177;
P 4 =ρ 4 ∙P 0 =0,893 4 ∙0,248=0,158.
Вероятность отказа в обслуживании автомобиля:
P отк =Р 4 = ρ 4 ∙P 0 ≈0,158.
Относительная пропускная способность окна оформления:
q =1–P отк =1-0,158=0,842.
Абсолютная пропускная способность окна оформления
А =λ∙q =0,85∙0,842=0,716 (автомобиля в час).
Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):
.
Среднее время пребывания автомобиля в системе:
часа.
Средняя продолжительность пребывания заявки в очереди на обслуживание:
W q =W s -1/μ=2,473-1/0,952=1,423 часа.
Среднее число заявок в очереди (длина очереди):
L q =λ∙(1-P N)∙W q = 0,85∙(1-0,158)∙1,423=1,02.
Работу рассмотренного окна оформления можно считать удовлетворительной, так как не обслуживается в среднем 15,8% случаев (Р отк =0,158).
Рассмотрим простейшую СМО с ожиданием - одноканальную систему , в которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (т. е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Система с ограниченной длиной очереди. Предположим сначала, что количество мест в очереди ограничено числом , т. е. если заявка пришла в момент, когда в очереди уже стоят заявок, она покидает систему необслуженной. В дальнейшем, устремив к бесконечности, мы получим характеристики одноканальной СМО без ограничений длины очереди.
Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):
Канал свободен;
Канал занят, очереди нет;
Канал занят, одна заявка стоит в очереди;
Канал занят, заявок стоят в очереди;
Канал занят, т заявок стоят в очереди.
ГСП показан на рис. 5.8. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны , а справа налево - . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево - поток «освобождений» занятого канала, меющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).
Рис. 5.8. Одноканальная СМО с ожиданием
Изображенная на рис. 5.8 схема представляет собой схему размножения и гибели. Используя общее решение (5.32)-(5.34), напишем выражения для предельных вероятностей состояний (см. также (5.40)):
или с использованием :
Последняя строка в (5.45) содержит геометрическую прогрессию с первым членом 1 и знаменателем р; откуда получаем:
в связи с чем предельные вероятности принимают вид:
Выражение (5.46) справедливо только при (при она дает неопределенность вида ). Сумма геометрической прогрессии со знаменателем равна , и в этом случае
Определим характеристики СМО: вероятность отказа , относительную пропускную способность , абсолютную пропускную способность , среднюю длину очереди , среднее число заявок, связанных с системой , среднее время ожидания в очереди , среднее время пребывания заявки в СМО
Вероятность отказа. Очевидно, заявка получает отказ только в случае, когда канал занят и все т мест в очереди тоже:
Относительная пропускная способность:
Абсолютная пропускная способность:
Средняя длина очереди. Найдем среднее число заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины - числа заявок, находящихся в очереди:
С вероятностью в очереди стоит одна заявка, с вероятностью - две заявки, вообще с вероятностью в очереди стоят заявок, и т. д., откуда:
Поскольку , сумму в (5.50) можно трактовать как производную по от суммы геометрической прогрессии:
Подставляя данное выражение в (5.50) и используя из (5.47), окончательно получаем:
Среднее число заявок, находящихся в системе. Получим далее формулу для среднего числа заявок, связанных с системой (как стоящих в очереди, так и находящихся на обслуживании). Поскольку , где - среднее число заявок, находящихся под обслуживанием, а известно, то остается определить . Поскольку канал один, число обслуживаемых заявок может равняться (с вероятностью ) или 1 (с вероятностью ), откуда:
и среднее число заявок, связанных с СМО, равно
Среднее время ожидания заявки в очереди. Обозначим его ; если заявка приходит в систему в какой-то момент времени, то с вероятностью канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероятностью она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени (среднее время обслуживания одной заявки). С вероятностью в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно , и т. д.
Если же , т. е. когда вновь приходящая заявка застает канал обслуживания занятым и заявок в очереди (вероятность этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:
если подставить сюда выражения для вероятностей (5.47), получим:
Здесь использованы соотношения (5.50), (5.51) (производная геометрической прогрессии), а также из (5.47). Сравнивая это выражение с (5.51), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Среднее время пребывания заявки в системе. Обозначим матожидание случайной величины - время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди и среднего времени обслуживания . Если загрузка системы составляет 100 %, очевидно, , в противном же случае
Пример 5.6. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).
Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно . Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.
Определить:
вероятность отказа;
относительную и абсолютную пропускную способности АЗС;
среднее число машин, ожидающих заправки;
среднее число машин, находящихся на АЗС (включая обслуживаемую);
среднее время ожидания машины в очереди;
среднее время пребывания машины на АЗС (включая обслуживание).
иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Находим вначале приведенную интенсивность потока заявок:
По формулам (5.47):
Вероятность отказа .
Относительная пропускная способность СМО
Абсолютная пропускная способность СМО
Машины в мин.
Среднее число машин в очереди находим по формуле (5.51)
т. е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.
Прибавляя к этой величине среднее число машин, находящихся под обслуживанием
получаем среднее число машин, связанных с АЗС.
Среднее время ожидания машины в очереди по формуле (5.54)
Прибавляя к этой величине , получим среднее время, которое машина проводит на АЗС:
Системы с неограниченным ожиданием . В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода в ранее полученных выражениях (5.44), (5.45) и т. п.
Заметим, что при этом знаменатель в последней формуле (5.45) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится, когда прогрессия бесконечно убывающая, т. е. при .
Может быть доказано, что есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что .
Если , то соотношения (5.47) принимают вид:
При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому ,
Среднее число заявок в очереди получим из (5.51) при :
Среднее число заявок в системе по формуле (5.52) при
Среднее время ожидания получим из формулы
(5.53) при :
Наконец, среднее время пребывания заявки в СМО есть
Многоканальная СМО с ожиданием
Система с ограниченной длиной очереди . Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди .
Состояния системы нумеруются по числу заявок, связанных системой:
нет очереди:
Все каналы свободны;
Занят один канал, остальные свободны;
Заняты каналов, остальные нет;
Заняты все каналов, свободных нет;
есть очередь:
Заняты все n каналов; одна заявка стоит в очереди;
Заняты все n каналов, r заявок в очереди;
Заняты все n каналов, r заявок в очереди.
ГСП приведен на рис. 5.9. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью , по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна , умноженному на число занятых каналов.
Рис. 5.9. Многоканальная СМО с ожиданием
Граф типичен для процессов размножения и гибели, для которой решение ранее получено (5.29)-(5.33). Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).
Таким образом, все вероятности состояний найдены.
Определим характеристики эффективности системы.
Вероятность отказа. Поступившая заявка получает отказ, если заняты все каналов и все мест в очереди:
Относительная пропускная способность дополняет вероятность отказа до единицы:
Абсолютная пропускная способность СМО:
Среднее число занятых каналов. Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.
Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем заявок в единицу времени, а СМО в целом обслуживает в среднем заявок в единицу времени. Разделив одно на другое, получим:
Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:
Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (5.50), (5.51)-(5.53)), используя соотношение для нее, получаем:
Среднее число заявок в системе:
Среднее время ожидания заявки в очереди. Рассмотрим ряд ситуаций, различающихся тем, в каком состоянии застанет систему вновь пришедшая заявка и сколько времени ей придется ждать обслуживания.
Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:
Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (5.59) только множителем , т. е.
Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО, отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:
Системы с неограниченной длиной очереди . Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более заявок.
Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при .
Вероятности состояний получим из формул (5.56) предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при . Допустив, что и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:
Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:
Среднее число заявок в очереди получим при из (5.59):
а среднее время ожидания - из (5.60):
Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:
Среднее число заявок, связанных с СМО, определяется как среднее число заявок в очереди плюс среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов):
Пример 5.7. Автозаправочная станция с двумя колонками () обслуживает поток машин с интенсивностью (машин в минуту). Среднее время обслуживания одной машины
В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.
Поскольку , очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (5.61) находим вероятности состояний:
Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО на интенсивность обслуживания :
Вероятность отсутствия очереди у АЗС будет:
Среднее число машин в очереди:
Среднее число машин на АЗС:
Среднее время ожидания в очереди:
Среднее время пребывания машины на АЗС:
СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом заявок, одновременно находящихся в очереди). В такой СМО заявка, раз ставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).
Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.
Предположим, что имеется канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением , таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью заявок стоят в очереди и т. д.
Граф состояний и переходов системы показан на рис. 5.10.
Рис. 5.10. СМО с ограниченным временем ожидания
Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживании всех каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят заявок, то суммарная интенсивность потока уходов будет равна .
Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения ) запишем:
Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.
Если длина очереди не ограничена и заявки «терпеливы» (не уходят из очереди), то стационарный предельный режим существует только в случае (при соответствующая бесконечная геометрическая прогрессия расходится, что физически соответствует неограниченному росту очереди при ).
Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок, не суммируя бесконечного ряда (5.63). Из (5.64) получаем:
а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины , принимающей значения с вероятностями :
В заключение заметим, что если в формулах (5.62) перейти к пределу при (или, что то же, при ), то при получатся формулы (5.61), т. е. «нетерпеливые» заявки станут «терпеливыми».