2. Простейшие системы массового обслуживания и их характеристики

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

Характеристики эффективности рассматриваемых СМО мы будем вводить по ходу изложения.

1. п -канальная СМО с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания;

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

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

Q — относительную пропускную способность, т. е. среднюю долю пришедших заявок, обслуживаемых системой;

Р_отк — вероятность отказа, т. е. того, что заявка покинет СМО не обслуженной;

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

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

S₀ — в СМО нет ни одной заявки,

S₁ — в СМО находится одна заявка (один канал занят, остальные свободны),

S_k — в СМО находится k заявок (k каналов заняты, остальные свободны),

S_n — в СМО находится п заявок (все n каналов заняты).

Граф состояний СМО соответствует схеме гибели в размножения (рис. 7.1). Разметим этот граф — проставим у стрелок интенсивности потоков событий. Из S₀ в S₁ систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S₀ в S₁). Тот же поток заявок переводит систему из любого левого состояния в соседнее правое.

Рисунок 7.1 – Граф состояний n-канальной СМО с отказами

Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии S₁ (работает один канал). Он производит μ обслуживаний в единицу времени. Проставляем у стрелки S₁ → S₀ интенсивность μ. Теперь представим себе, что система находится в состоянии S₂ (работают два канала). Чтобы ей перейти в S₁, нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами — kμ. Проставляем эти интенсивности у нижних стрелок на рис. 7.1.

Обозначим λ/μ = ρ и будем называть величину р «приведенной интенсивностью потока заявок». Ее смысл—среднее число заявок, приходящее за среднее время обслуживания одной заявки. А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (7.1), (7.2) для финальных вероятностей в схеме гибели и размножения:

(7.1)

(7.2)

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

Таким образом, финальные вероятности найдены. По ним мы вычислим характеристики эффективности СМО. Сначала найдем Р_отк. — вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все п каналов были заняты, значит,

Р_отк = р_n = (7.3)

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

Q = 1 – P_отк. = 1 - (7.4)

Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ, на Q:

A = λQ = λ (7.5)

Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0, 1, ..., п и вероятностями этих значений р₀ р₁, ..., р_n:

k = 0 · р₀ + 1 · p₁ + 2 · р₂ + ... + п · р_n (7.6)

Подставляя сюда выражения (20.5) для р_k, (k = 0, 1, ..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще. В самом деле, нам известна абсолютная пропускная способность А. Это не что иное, как интенсивность потока обслуженных системой заявок. Среднее число занятых каналов равно

k = A/μ, (7.7)

или, k = (7.8)

Пример 1. Имеется станция связи с тремя каналами (n = 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t_об = 2 (мин.), все потоки событий (как и во всем этом параграфе) — простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P_отк, k. Ответы: p₀ = 1/13, p₁ = 3/13, p₂ = 9/26, р₃ = 9/26 ≈ 0,346,

А ≈ 0,981, Q ≈ 0,654, P_отк ≈ 0,346, k ≈ 1,96.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 7.2 – Граф состояний одноканальной СМО с неограниченной очередью

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

Но вернемся к нашей одноканальной СМО с неограниченной очередью. Подсчитать финальные вероятности состояний можно по формуле 7.9:

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

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

Найдем среднее число заявок в СМО L_сист. :

L_сист = . (7.10)

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

W_сист = (7.11)

Найдем среднее число заявок в очереди L_оч.:

L_оч = (7.12)

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

(7.13)

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

Пример 2. Одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 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а.

3. re-канальная СМО с неограниченной очередью. Совершенно аналогично задаче 2, но более сложная, решается задача об n-канальной СМО с неограниченной очередью. Нумерация состояний — опять по числу заявок, находящихся в системе:

S₀ — в СМО заявок нет (все каналы свободны),

S₁ — занят один канал, остальные свободны,

S₂ — занято два канала, остальные свободны,

S_k — занято k каналов, остальные свободны,

S_n — заняты все п каналов (очереди нет),

S_n+1 — заняты все n каналов, одна заявка стоит в очереди,

S_n+r — заняты вес п каналов, r заявок стоит в очереди,

Сообщим без доказательства естественное условие существования финальных вероятностей: ρ/n<1. Если ρ/n ≥ 1, очередь растет до бесконечности.

Если условие ρ/n < 1 выполнено, финальные вероятности существуют и определяются следующим образом:

(7.14)

Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов k = λ/μ, = ρ (это вообще справедливо для любой СМО с неограниченной очередью). Найдем среднее число заявок в системе L_сист и среднее число заявок в очереди L_оч. Из них легче вычислить второе, по формуле

L_оч = (7.15)

Прибавляя к нему среднее число заявок под обслуживанием (оно же — среднее число занятых каналов) k = ρ, получим:

L_сист = L_оч + ρ. (7.16)

Деля выражения для L_оч и L_сист на λ, по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:

(7.17)

Пример 3. Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В. Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В одинакова: λ_А = λ_В = 0,45 (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью λ_А + λ_В = 0,9. Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания, Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А и в В, создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна — только в пункт А, другая — только в пункт В. Разумность этого предложения вызывает споры — кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий — простейшие (на качественной стороне выводов это не скажется).

Рассмотрим два варианта организации продажи билетов — существующий и предлагаемый.

Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью λ = 0,9; интенсивность потока обслуживании μ = 1/2 = 0,5; ρ = λ/μ = l,8. Так как ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р₀ ≈ 0,0525. Среднее, число заявок в очереди находим по формуле (20.23): L_оч ≈ 7,68; среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно W_оч ≈ 8,54 (мин.).

Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью λ = 0,45; μ. по-прежнему равно 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L_оч = 8,1.

Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля L_оч на λ = 0,45, получим W_оч ≈ 18 (минут).

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

Ошибки нет. Дело в том, что в нашем примере обе СМО работают на пределе своих возможностей; стоит немного увеличить время обслуживания (т. е. уменьшить μ), как они уже перестанут справляться с потоком пассажиров, и очередь начнет неограниченно возрастать. А «лишние простои» кассира в каком-то смысле равносильны уменьшению его производительности μ.

Таким образом, кажущийся сначала парадоксальным (или даже просто неверным) результат вычислений оказывается на поверку правильным и объяснимым.

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

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

- замкнутую СМО с одним каналом и m источниками заявок. Для конкретности поставим задачу в следующей форме: один рабочий обслуживает т станков, каждый из которых время от времени требует наладки (исправления). Интенсивность потока требований каждого работающего станка равна λ. Если станок вышел из строя в момент, когда рабочий свободен, он сразу же поступает на обслуживание. Если он вышел из строя в момент, когда рабочий занят, он становится в очередь и ждет, пока рабочий освободится. Среднее время наладки станка t_об = 1/μ. Интенсивность потока заявок, поступающих к рабочему, зависит от того, сколько станков работает. Если работает k станков, она равна kλ. Найти финальные вероятности состояний, среднее число работающих станков и вероятность того, что рабочий будет занят. Заметим, что и в этой СМО финальные вероятности будут существовать при любых значениях λ и μ = 1/t_об, так как число состояний системы конечно.

3. Усложненные постановки задач теории массового обслуживания

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

1. n-канальная СМО с отказами, с простейшим потоком заявок и произвольным распределением времени обслуживания. В предыдущем вопросе мы рассмотрели формулы Эрланга для финальных вероятностей состояний СМО с отказами. В 1959 г. Б. А. Севастьянов доказал, что эти формулы справедливы не только при показательном, но и при произвольном распределении времени обслуживания.

2. Одноканальная СМО с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания. Если на одноканальную СМО с неограниченной очередью поступает простейший поток заявок с интенсивностью λ, а время обслуживания имеет произвольное распределение с математическим ожиданием t_об = 1/μ. и коэффициентом вариации v_μ, то среднее число заявок в очереди равно

(7.18)

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

(7.19)

где, как и ранее, ρ = λ/μ., a v_μ — отношение среднего квадратического отклонения времени обслуживания к его математическому ожиданию. Формулы (7.18), (7.19) носят название формул Полячека — Хинчина.

Деля L_оч, и L_сист на λ, получим, согласно формуле Литтла, среднее время пребывания заявки в очереди и среднее время пребывания в системе:

(7.20)

(7.21)

Возьмем другой частный случай — когда время обслуживания вообще не случайно и v_μ = 0. Тогда среднее число заявок в очереди уменьшается вдвое по сравнению с простейшим случаем. Это и естественно: если обслуживание заявки протекает более организованно, «регулярно», то СМО работает лучше, чем при плохо организованном, беспорядочном обслуживании.

3. Одноканальная СМО с произвольным потоком заявок и произвольным распределением времени обслуживания. Рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный рекуррентный поток заявок с интенсивностью λ и коэффициентом вариации v_λ интервалов между заявками, заключенным между нулем и единицей: 0 < v_λ < 1. Время обслуживания Т_об также имеет произвольное распределение со средним значением t_об = 1/μ и коэффициентом вариации v_μ, тоже заключенным между нулем и единицей. Для этого случая точных аналитических формул получить не удается, можно только приближенно оценить среднюю длину очереди, ограничить ее сверху и снизу.

Доказано, что в этом случае

(7.22)

Если входящий поток - простейший, то обе оценки - верхняя и нижняя - совпадают, и получается формула Полячека — Хинчина. Для грубо приближенной оценки средней длины очереди М.А. Файнбергом получена очень простая формула:

(7.23)

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

L_сист = L_оч + ρ. (7.24)

Что касается средних времен пребывания заявки в очереди и в системе, то они вычисляются через L_оч и L_сист по формуле Литтла делением на λ.

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

Возникает естественный вопрос: а как же обстоит дело с многоканальными немарковскими СМО? Точных аналитических методов для таких систем не существует. Единственное, что мы всегда можем найти, это среднее число занятых каналов k = ρ. Что касается L_оч, L_сист, W_оч, W_сист, то для них таких общих формул написать не удается.