Моделирование систем массового обслуживания

Потоки событий

Переходы CMC) из одного состояния в другое происходят под воздействием вполне определенных событий — поступления заявок и их обслуживания. Последовательность появления событий, следующих одно за другим в случайные моменты времени, формирует так называемый поток событий. Примерами таких потоков в коммерческой деятельности являются потоки различной природы — товаров, денег, документов, транспорта, клиентов, покупателей, телефонных звонков, переговоров. Поведение системы обычно определяется не одним, а сразу несколькими потоками событий. Например, обслуживание покупателей в магазине определяется потоком покупателей и потоком обслуживания; в этих потоках случайными являются моменты появления покупателей, время ожидания в очереди и время, затрачиваемое на обслуживание каждого покупателя. При этом основной характерной чертой потоков является вероятностное распределение времени между соседними событиями. Существуют различные потоки, которые отличаются своими характеристиками.

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

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

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

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

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

Рассмотрим на оси времени некоторый промежуток времени т. Допустим, вероятность попадания случайного события на этот промежуток р> а полное число возможных событий 77. При наличии свойства ординарности потока событий вероятность р должна быть достаточно малой величиной, а 77 — достаточно большим числом, поскольку рассматриваются массовые явления. В этих условиях для вычисления вероятности попадания на промежуток времени т некоторого числа событий т можно воспользоваться формулой Пуассона

где величина а = пр — среднее число событий, попадающих на промежуток времени т, которое можно определить через интенсивность потока событий X следующим образом:

Размерность интенсивности потока X есть среднее число событий в единицу времени. Между п и X, р и т имеется следующая связь:

где t — весь промежуток времени, на котором рассматривается действие потока событий.

Необходимо определить распределение интервала времени Т между событиями в таком потоке. Поскольку это случайная величина, найдем ее функцию распределения. Как известно из теории вероятностей, интегральная функция распределения F (t) есть вероятность того, что величина Т будет меньше времени t

По условию в течение времени Т не должно произойти ни одного события, а на интервале времени t должно появиться хотя бы одно событие. Эта вероятность вычисляется с помощыо вероятности противоположного события на промежутке времени (0; t), куда не попало ни одного события, т. е. т = 0, тогда.

Для малых At можно получить приближенную формулу, получаемую заменой функции е^_Х/ только двумя членами разложения в ряд по степеням At, тогда вероятность попадания на малый промежуток времени At хотя бы одного события составляет.

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

Пользуясь полученной функцией плотности распределения, можно получить числовые характеристики случайной величины Т: математическое ожидание М (7), дисперсию D (T) и среднее квадратическое отклонение а (Г):

Отсюда можно сделать следующий вывод: средний интервал времени Т между любыми двумя соседними событиями в простейшем потоке в среднем равен 1/Х и его среднее квадратическое отклонение также равно 1 /А, где X — интенсивность потока, т. е. среднее число событий, происходящих в единицу времени. Закон распределения случайной величины, обладающей такими свойствами М (Т) = Т_} называется показательным (или экспоненциальным), а величина X является параметром этого показательного закона. Таким образом, для простейшего потока математическое ожидание интервала времени между соседними событиями равно его среднему квадратическому отклонению.

В этом случае вероятность того, что число заявок, поступающих на обслуживание за промежуток времени t, равно k, определяется по закону Пуассона

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

Для такого потока заявок время между двумя соседними заявками Т распределено экспоненциально с плотностью вероятности.

Случайное время ожидания в очереди начала обслуживания ?_оч тоже можно считать распределенным экспоненциально.

где v — интенсивность потока прохода очереди, определяемая средним числом заявок, проходящих на обслуживание в единицу времени.

где Т_оч — среднее время ожидания обслуживания в очереди.

Выходной поток заявок связан с потоком обслуживания в канале, где длительность обслуживания t₀^_c является тоже случайной величиной и подчиняется во многих случаях показательному закону распределения с плотностью вероятности

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

Важной характеристикой СМО, объединяющей показатели X и р, является интенсивность нагрузки р = Х/х, которая показывает степень согласования входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.

Кроме понятия простейшего потока событий иногда приходится пользоваться понятиями потоков других типов. Например, поток событий называется потоком Пальма, когда в потоке промежутки времени между последовательными со-

бытиями Ti, T_2y…, Tk,…, T_n являются независимыми, одинаково распределенными, случайными величинами, но в отличие от простейшего потока не обязательно распределенными по показательному закону. Простейший поток является частным случаем потока Пальма.

Важным частным случаем потока Пальма является так называемый поток Эрланга. Этот поток получается «прореживанием» простейшего потока. Такое «прореживание» производится путем отбора, но определенному правилу событий из простейшего потока. Например, условившись учитывать только каждое второе событие из образующих простейший поток, мы получим поток Эрланга второго порядка. Если брать только каждое третье событие, то образуется поток Эрланга третьего порядка и т. д. Можно получить потоки Эрланга любого k-ro порядка. Очевидно, простейший поток есть поток Эрланга первого порядка.

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

Поскольку моменты времени ?, и интервалы времени поступления заявок т, затем продолжительность операций обслуживания t₀б_с и время ожидания в очереди t₀₄, а также длина очереди /_оч — случайные величины, то, следовательно, характеристики состояния СМО носят вероятностный характер, и для их описания следует применять методы и модели теории массового обслуживания.

Перечисленные выше характеристики k, х, A., L₀₄, Г_оч, v, t₀^_c, р, р, Pk являются наиболее общими для СМО, которые являются обычно лишь некоторой частью целевой функции, поскольку необходимо учитывать еще и показатели коммерческой деятельности.