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

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

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

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

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

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

W _оч — среднее время пребывания заявки в очереди,

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

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности:

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

Рис. 20.2.

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

S ₀ — канал свободен,

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

S ₂ — канал занят, одна заявка стоит в очереди,

S _k — канал занят, k — 1 заявок стоят в очереди,

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

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

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

p ₀ = [1 + λ/μ + (λ/μ)² +... + (λ/μ)^k +.. ]^-1 =

= (1 + р + р² +... + р^k +….)^-1. (20.11)

Ряд в формуле (20.11) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится — это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р₀, p₁,..., p_k,... существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ² +... + ρ^k +... = ,

откуда

p ₀ = 1 - ρ. (20.12)

Вероятности р₁, р₂,..., р_k,... найдутся по формулам:

p₁ = ρ p₀, p₂ = ρ² p₀,…,p_k = ρ p₀,...,

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

p₁ = ρ (1 - ρ), p₂ = ρ² (1 - ρ),..., p_k = ρ ^k (1 - ρ),...(20.13)

Как видно, вероятности p₀, p₁,..., p_k,... образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р₀ — вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.

Найдем среднее число заявок в СМО L _сист.. Тут придется немного повозиться. Случайная величина Z — число заявок в системе — имеет возможные значения 0, 1, 2,.... k,... с вероятностями p₀, р₁, р₂,..., p_k,... Ее математическое ожидание равно

L _сист = 0 · p₀ + 1 · p ₁ + 2 · p ₂ +…+ k · p _k +…= (20.14)

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

Подставим в формулу (20.14) выражение для p_k (20.13):

L _сист. =

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

L _сист. = ρ (1-ρ)

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

L _сист. = ρ (1-ρ)

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

L _сист. = ρ (1-ρ) (20.15)

Но сумма в формуле (20.15) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и знаменателем ρ; эта сумма

равна , а ее производная .Подставляя это выражение в (20.15), получим:

L _сист = . (20.16)

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

W _сист = (20.17)

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

Р _зан = 1 - р ₀ = ρ. (20.18)

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

L_об = ρ, (20.19)

отсюда

L _оч = L _сист – ρ =

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

L_оч = (20.20)

По формуле Литтла (19.13) найдем среднее время пребывания заявки в очереди:

(20.21)

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

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