Системный анализ СМО

Вышеприведенные формулы получены при допущении экспоненциального закона распределения времени обслуживания для значительного упрощения исследования систем массового обслуживания. Это равносильно допущению об отсутствии памяти (отсутствие последействия), присущее экспоненциальному рас­пределению вероятностных состояний системы. Для более точного исследования поведения системы S в неустановившемся (переходном) режиме это допущение неправильно. Как правило, нестационарную фазу поведения даже относительно простой системы удается исследовать лишь в результате весьма трудоемкого анализа с использованием сложных математических методов.

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

В системах с конеч­ным числом допустимых состояний стационарность достигается при условии, что эти состояния принадлежат к одному неприводи­мому классу (т. е. образуют множество сообщающихся состояний). В системах с бесконечным числом возможных состояний в большинстве случаев для статистического равновесия требует­ся, чтобы коэффициент нагрузки системы a удовлетворял условию a £ 1.

Наиболее простая система типа М/М/1 есть модель системы, имеющей лишь один обслуживающий прибор, характеризующаяся пуассоновским распределением продолжительностей интервалов времени между последовательными поступ­лениями требований и экспоненциальным распределением длитель­ностей обслуживания.

Для этой простой системы вероятность её нахождения в j-том состоянии:

Р_j = (1 - a ) a^j j = 0, 1, 2,...,

Среднее значение длины очереди L и дисперсия относительно среднего значения:

E[L] = a/(1 -a) ; Var [L] = a/(1-a)²

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

E [T] = a/m(1 -a) Var [T] = a(2-a)/m² /(1 - a)²

Если вместо одного обслуживающего прибора СМО насчитывает s приборов, то для такой СМО, обозначаемой как М/М/s , вероятность нахождения СМО в j-ом состоянии:

P_j = P₀ (sa)^j /j!0 £ j £ s где P₀ = [ å₀^s-1 (sa)^j /j! +(sa)/s! /(1 - a) ] ^-1

P₀ (sa)^j / s^j-s / s! j ³ s

Для такой СМО средняя длина очереди и средняя продолжительность ожидания обслуживания определяются соотношениями:

Е [L] = sa + aP_s / (1 - a)² ; E [T] = P_s / sm (1 - a)²

В реальности часто встречаются СМО, в которых последовательность L(t) , т.е. длина очереди, ограничена сверху. Конечные очереди имеют место либо в системах с отказами, либо в системах с ограниченным объемом пространства, отводимого для ожидания. В первом случае требованиям, поступающим в мо­мент, когда все обслуживающие приборы заняты, в обслуживании отказывают и, таким образом, обслуживающая система их теряет. Во втором случае поступающие требования имеют возможность дожидаться обслуживания лишь при условии, что количество уже находящихся в системе требований не превышает некоторого фиксированного числа.

Рассмотрим подробнее случай, когда поток поступающих требований на обслуживание является пуассоновским с параметром l , а длительности обслуживания распределены по экспоненциальному закону с их средним значением равным 1/m . Пусть число обслуживающих приборов равняется s. Обозначим через {P_j} предельное распределение вероятностей числа имеющихся в системе требований. Для системы с отказами справедлива формула, полученная Эрлангом, которую можно записать:

P_j = (1/j!) a^j / å^s_k=0 (1/k!) a^k j = 0, 1, 2,..., s

где a = l/m . В частности, эта формула даёт выражение для P_s , т. е. для вероятности возникновения «затора» в потоке требований, или вероятности потери требования на обслуживание, которое называют формулой Эрланга для вероятности отказа. Это формула имеет весьма универсальный характер и не зависит от типа потока заявок.

Для модели типа М/М/1 с конечной очередью в случае, когда в систе­ме обслуживания может одновременно находиться не более q требований, предельное распределение {P_j} длины очереди L (t) имеет следующий вид:

Р_j = (1 — a)a^j /(1 - a^q+1 ) j = 0, 1, 2, . . , q

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

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

Рассмотренные выше системы массового обслуживания харак­теризуются простой дисциплиной очереди и элементарной струк­турой. В реальных условиях многие обслуживающие системы оказываются гораздо сложнее. Каждую из многочисленных модифика­ций модельного описания процесса массового обслуживания мож­но связать с вариациями одного из трёх элементов СМО:

1) Входного потока (процесс на входе СМО). Здесь возможны следующие варианты: групповые поступления требований; ожида­ние вне системы; поступление требований согласованными пото­ками; зависимость входного потока от состояния системы; поступ­ления по графику, но с опозданиями и т. д.

2) Механизма обслуживания. Возможными вариантами являются: ограниченная вместимость пространства ожидания; прибор, кото­рый обслуживает клиентов, находящихся на определенных местах, передвигается; непрерывно работающие системы (даже при отсут­ствии клиентов); обслуживание осуществляется фиксированными «порциями»; обслуживающие приборы функционируют последо­вательно; обслуживание осуществляется последовательно, а вме­стимость пространств для ожидания между приборами ограничена (или не ограничена); обслуживающие приборы функционируют параллельно; поступающие требования не имеют права на ожида­ние (системы, отказывающие в обслуживании при загруженности всех обслуживающих приборов); число обслуживающих приборов изменяется в зависимости от состояния системы; приборы функ­ционируют по согласованному регламенту; приборы реализуют специфические и невзаимозаменяемые процедуры; сеть с обслу­живающими приборами, функционирующими как последовательно, так и параллельно, и т. д.

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