Элементы системы массового обслуживания. Описание простейшего потока заявок (пуассоновского потока)

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

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

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

Наиболее полное и исчерпывающее описание входного потока возможно с помощью вероятностных характеристик, например, c помощью закона распределения моментов поступления заявок , j = 1, 2,..., или промежутков времени между моментами поступления заявок j = 1, 2…, . Свойство стационарности означает, что описывающий поток вероятностный закон распределения не зависит от начального момента . Ординарность предполагает, что вероятность появления более чем одной заявки в достаточно малом промежутке времени t является бесконечно малой величиной. Наконец, свойство отсутствия последействия означает, что происходящие в произвольных двух непересекающихся промежутках времени Dt₁ и Dt₂ события не влияют друг на друга.

Для аналитического описания простейшего потока заявок рассмотрим промежуток времени (0, t) и через N(t) обозначим количество поступающих за этот промежуток заявок с вероятностью (t) = {N(t) = n}, n = 0, 1,… Важной характеристикой простейшего потока является его интенсивность - среднее число поступающих заявок за единицу времени. Согласно свойству ординарности, вероятность появления одной заявки за достаточно малый промежуток времени Dt равна величине lDt, а вероятность появления более одной заявки за этот же промежуток времени, которую мы обозначим через бесконечно малая величина, такая, что

Lim v(Dt)/Dt = 0. (1.1)

Dt ® 0

Наша задача заключается в нахождении закона изменения (t), n = 0,1,…, в промежутке времени (0, t). Значения (0) = 1 и (0) = 0, n = 1, 2,… очевидны. Рассмотрим сложное событие с вероятностью , заключающееся в том, что в промежутке времени (0, t) заявок нет и за время они также не поступали. Эти составные события имеют вероятности (t) и соответственно, поэтому учитывая их независимость, для величины получим выражение

P₀(t +Dt ) = P₀(t)(1 -l Dt). (1.2)

Переписав (1.2) в виде разделив обе части последнего на и осуществив переход к пределу при получим дифференциальное уравнение

dP₀(t)/dt = -lP₀(t). (1.3)

Чтобы найти его решение, умножим обе его части на e^l^t, в результате чего получим соотношение

e^l^t dP₀(t)/dt + l e^l^t P₀(t) = d(e^l^t P₀(t))/dt = 0, (1.4)

откуда следует, что , или же где c - постоянная интегрирования. Так как постоянная с будет равна единице, тогда для P₀(t) получим

P₀(t) = e^-^l^t, t ³ 0. (1.5)

Для получения закона изменения (t), n ³ 1, рассмотрим сложное событие с вероятностью означающее поступление за промежуток времени (0, ровно п заявок. Учитывая независимость составных событий, эта вероятность равна

P_n(t +Dt ) = P_n(t)(1 -l Dt) + P_n_{- 1}(t)(l Dt) + v(Dt), n ³ 1 . (1.6)

Первое слагаемое в правой части этого выражения есть вероятность события, когда в момент времени t поступили n заявок и за промежуток времени (t, t + Dt) новых заявок не было. Второе же слагаемое равно вероятности события, когда в момент t поступили n - 1 заявок, а за последующий промежуток времени поступила одна заявка. Слагаемое есть вероятность всех остальных маловероятных событий. Если в (1.6) вновь перенести величину (t) в левую часть, разделить обе части на Dt и перейти к пределу при с учетом (1.1) получим дифференциальное уравнение

dP_n(t)/dt = - l P_n(t) + l P_n_{- 1}(t), n ³ 1. (1.7)

Когда n = 1, подставляя в (1.7) выражение для из (1.5), умножая обе части на e^l^t, после несложных преобразований получим

d(e^l^t P₁(t)/dt = l. (1.8)

Интегрирование этого уравнения по t дает выражение

e^l^t P₁(t) = lt + c, (1.9)

откуда с учетом условия и, следовательно, c = 0, получим окончательную формулу для :

P₁(t) = lt e^- ^l^t, (1.10)

Покажем, опираясь на метод математической индукции, что для n ≥ 1 имеет место соотношение

P_n(t) = (lt)ⁿ e^- ^l^t/n!, n = 1, 2, … , (1.11)

известное как распределение Пуассона для целочисленной случайной величины N(t). При n = 1 из (1.11) следует (1.5). Пусть (1.11) верно для n -1, т.е.

P_n_{- 1}(t) = (lt)^{n - 1} e^- ^l^t/(n – 1)!. (1.12)

Подставляя выражение для в дифференциальное уравнение (1.7.), получим уравнение

dP_n(t)/dt + l P_n(t) = l(lt)^{n - 1} e^- ^l^t/(n – 1)!. (1.13)

Представляя (1.13) в виде

d(e^l^tP_n(t))/dt = l(lt)^{n - 1}/(n – 1)!, (1.14)

и интегрируя последнее выражение по t получим

e^l^tP_n(t) = (lt)ⁿ/n! + c. (1.15)

Учитывая условие (0) = 0, n = 1, 2,…, из (1.15) получим c = 0 и P_n(t)) = (lt)ⁿe^- ^l^t/ n!. Следовательно, формула (1.11) верна для любого n = 1, 2,… Математическое ожидание и дисперсия случайной величины N(t) равны друг другу и составляют

M{N(t)} = nP_n(t) = lt,

D{N(t)} = M{(N(t) - lt)²} = (n -lt)² P_n(t) = lt.

Рекомендуем студентам самостоятельно убедиться в справедливости этих формул.

Важной характеристикой простейшего потока с распределением (1.11) является то, что промежутки времени между моментами поступления заявок, q_j = t_j – t_j_{– 1}, j = 1, 2, …, , представляют собой независимые и одинаково распределенные по экспоненциальному закону случайные величины, функция плотности распределения которых равна

f(q) = d(1 – P₀(q)/dq = le^-^l^q, q ³ 0. (1.16)

где совпадает с выражением из (1.5), полагая в нем . Первые два момента этого распределения равны M{ } = D{ }= ².

В теории массового обслуживания часто рассматривается другой, важный для аналитических исследований поток Эрланга, который подчиняется распределению

f(q) = (ln)(lnq)^{n – 1}e^-^lⁿ^q/(n – 1)!, q ³ 0. (1.17)

Первые два момента этого распределения равны M{ } = D{ } = ². При n = 1 из (1.17) следует распределение (1.16). При n → ∞ дисперсия стремиться к нулю, и распределение Эрланга описывает строго периодический процесс, для которого величины постоянны и равны величине 1/ .

Важность распределения (1.17) обусловлена тем, что путем соответствующего подбора значений параметров п и с его помощью можно достаточно надежно аппроксимировать другие распределения, которые встречаются в практике. Кроме того, в ряде случаев возникновения необходимости моделирования и организации обслуживания неоднородных потоков событий (заявок, например), которые характеризуются набором признаков { }, j = 1, 2,…, таких, как принадлежность к тому или иному источнику иликлассу, приоритет и т.д. Иногда приходится учитывать также изменение интенсивности потока во времени. В общем случае эта величина определяется как предел при где – вероятность наступления ровно одного события в промежутке времени ( ). Для стационарного потока справедливо условие