3. 3. Марковские смо.

3.1. Простейший поток.

Заявки на обслуживание поступают в СМО в случайные моменты времени. Важнейшая характеристика потока заявок (или потока требований) – интенсивность  - среднее число заявок в единицу времени. В марковских СМО рассматриваются так называемые простейшие потоки заявок, которые удовлетворяющие трём требованиям: они должны быть стационарными, ординарными и обладать свойством “отсутствия последействия”.

Поток требований называется стационарным, если его вероятностные характеристики не зависят от времени и, в частности, интенсивность  является константой. Поток требований будет потоком без последействия, если для любых двух непересекающихся участков времени число требований, поступивших в один интервал, не зависит от числа требований, поступивших в другой интервал. Наконец, поток требований ординарный, если вероятность поступления двух и более требований за время Δt при Δt0 является бесконечно малой величиной (), т.е. требования поступают поодиночке, а не группами.

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

Обозначим через X(τ) случайную величину, равную числу требований, поступивших за отрезок времени [ t, t+τ ] (по условию, она не зависит от t), через Y – случайное время ожидания поступления очередного требования. Тогда, очевидно, =P{X()=m}. Нам надо показать, что =, аP{Y‹ t} = 1- .

Выберем промежуток времени [ t, t+τ ]. Так как поток стационарен, то интенсивность λ не зависит от t. Разобьём промежуток времени на большое число k частей одинаковой длины Δt = τ / k. Так как интенсивность λ – это среднее число требований в единицу времени, то, по свойству математического ожидания, среднее число требований, поступивших за время Δt, равно M(X(Δt)) = λ Δt. С другой стороны, M(X(Δt)) = =; так как поток ординарен, то при малых Δt p_j(Δt) = () приj › 1 и тогда

M(X(Δt)) = p₁(Δt)+ (). Сравнивая два выражения дляM(X(Δt)), получаем

λ Δt = p₁(Δt)+ (). Таким образом,p₁(Δt) = λΔt + (). Так каки p_j(Δt)=() приj›1, то p₀(Δt)=1-p₁(Δt)+()=1-λΔt+ ().

В силу того, что поток без последействия, число требований, поступивших в непересекающиеся отрезки времени Δt, суть величины независимые. Число требований, поступивших за весь отрезок времени τ, равно сумме числа требований по всем k отрезкам Δt и, таким образом, оно равно числу “успехов” (требований) в k испытаниях Бернулли с вероятностью “успеха” (поступления требования) p₁(Δt) и вероятностью “неуспеха” (отсутствия требования) p₀(Δt). Так как

k p₁(Δt)=k(λΔt +())=k(λ τ / k+())= λ τ+( τ/)()= λ τ+ τ(1)→ λ τ при k →, то, по теореме Пуассона, вероятность того, что случайная величина, равная числу требований, поступивших за отрезок времени [t, t+τ ] X() имеет распределение Пуассона с параметром λτ , т.е.=.

Найдём теперь закон распределения случайного интервала времени между двумя соседними требованиями Y. Функция распределения (t) случайной величины Y равна

(t)=P{Y‹ t}=1-P{Y≥t}=1-=1-.

Поскольку 1-- это функция распределения случайной величины, имеющей экспоненциальное распределение, тоY имеет экспоненциальное распределение. Напомним, что экспоненциальное распределение – единственное, обладающее свойством ”отсутствия последействия”, т.е. для случайного интервала времени, имеющего экспоненциальное распределение, условная вероятность того, что он продлится ещё не менее чем τ, если он продолжался уже время t, не зависит от t, а равна безусловной вероятности того, что он продлится не менее чем τ. Напомним также, что для случайной величины Y, имеющей экспоненциальное распределение, произведение среднего значения M(Y) на интенсивность λ равна 1 и тогда λ=1/ M(Y) и M(Y)=1/ λ.

В марковских СМО предполагается, что входной поток заявок на обслуживание является пуассоновским и что время обслуживания заявки одним каналом обслуживания имеет экспоненциальное распределение с параметром μ, не зависящим от времени. Тогда вероятность того, что время обслуживания заявки находится в промежутке [t, t+Δ] не зависит от t и равно, как мы видели, μΔt +(). Будем понимать подсостоянием СМО количество заявок, находящихся в СМО. Тогда вероятность перехода системы из состояния S_i (i заявок в системе) в состояние S_j (j заявок в системе) за время равна(), если› 1. Таким образом, марковский процесс, описывающий СМО, будет процессом размножения и гибели.

2. Формула Литтла.

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

A(t)={число поступающих в промежутке времени (0, t) требований }

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

B(t)={число исходящих в промежутке времени (0, t) требований }

Время

???????

Рис. 3.1. Поступления и уходы.

На рис. 3.1 приведены примеры функциональных зависимостей этих двух вероятностных процессов от времени.

Ясно, что число N (t) требований в системе в момент времени t должно удовлетворять равенству

N(t) = A(t) - B(t).

С другой стороны, площадь между двумя рассматриваемыми кривыми, взятая от начальной точки до некоторой фиксированной точки t, представляет собой общее время, проведенное всеми требованиями в системе за время (0, t) (измеренное в единицах «требование — время»); обозначим эту накопленную величину C(t):

C(t)={общее время, проведенное всеми требованиями в системе за время (0, t)}.

Пусть λ (t) означает среднюю интенсивность (требований в единицу времени) поступления требований в систему в промежутке времени (0,t), т. е. λ(t)=A(t)/t. Определим также величину _(0,t) как время, проведенное одним требованием в системе, усредненное по всем требованиям, находя­щимся в системе в течение времени (0, t). Так как C(t) равно общему времени, проведенному всеми требованиями в системе вплоть до момента t, то _(0,t) определяется отношением _(0,t)= C(t)/A(t). Наконец, определим величину как среднее число требований в системе в промежутке времени (0,t); эта величина может быть получена как отношение накопленного числа C(t) к длине t про­межутка времени наблюдения: =C(t)/t.

Из последних трех уравнений следует, что = λ (t)_(0,t).

Предположим теперь, что рассматриваемая система массового обслуживания такова, что при t существуют пределы: ,=.

Если указанные два предела существуют, то существует также предел для , который обозначим через . Последний предел соответственно задает среднее число требований в системе:

= λ (3.1) .

Этот результат, называемый формулой Литтла, и является именно тем соотношением, которое мы искали. Оно устанавливает, что среднее число требований в системе равно произведению интенсив­ности поступления требований в систему на среднее время пре­бывания требования в системе. Приведенное доказательство не зависит ни от каких-нибудь частных ограничений, накладыва­емых на вид распределения входящего потока или на вид распределения времени обслуживания, ни от числа обслужи­вающих приборов, ни от конкретного характера дисциплины обслуживания в системе.