Теория массового обслуживания

Работу  системы обслуживания характеризуют  такие показатели. Как время ожидания начала обслуживания, длина очереди, возможность получения отказа в  обслуживании, возможность простоя  каналов обслуживания, стоимость  обслуживания и в конечном итоге  удовлетворение качеством обслуживания, которое еще включает показатели коммерческой деятельности. Чтобы улучшить качество функционирования системы  обслуживания, необходимо определить, каким образом распределить поступающие  заявки между каналами обслуживания, какое количество каналов обслуживания необходимо иметь, как расположить  или сгруппировать каналы обслуживания или обслуживающие аппараты для  улучшения показателей коммерческой деятельности. Для решения перечисленных  задач существует эффективный метод  моделирования, включающий и объединяющий достижения разных наук, в том числе  математики.

 

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

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

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

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

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

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

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

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

 

 

 

Где, величина а = пр - среднее число событий, попадающих на промежуток времени t, которое можно определить через интенсивность потока событий X следующим образом: a= λ τ

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

 

 

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

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

 

 

 

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

 

 

 

Для малых  ∆t можно получить приближенную формулу, получаемую заменой функции e^-Xt, только двумя членами разложения в ряд по степеням ∆t, тогда вероятность попадания на малый промежуток времени ∆t хотя бы одного события составляет:

 

 

 

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

^,

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

 

_^;

  ^;

 

 

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

 

 

 

где λ - интенсивность поступления потока заявок, среднее число событий в СМО за единицу времени, например[чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] .

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

 

 

 

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

 

 

 

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

 

 

 

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

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

 

  ,

 

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

 

 

 

где, t _обс - среднее время обслуживания заявок.

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

Кроме понятия  простейшего потока событий часто  приходится пользоваться понятиями  потоков других типов. Поток событий  называется потоком Пальма, когда  в этом потоке промежутки времени  между последовательными событиями  T₁, T₂, ..., Т_k ..., Т_n являются независимыми, одинаково распределенными, случайными величинами, нов отличие от простейшего потока не обязательно распределенными по показательному закону. Простейший поток является частным случаем потока Пальма.

Важным  частным случаем потока Пальма является так называемый поток Эрланга.

Этот  поток получается «прореживанием»  простейшего потока. Такое «прореживание» производится путем отбора по определенному  правилу событий из простейшего  потока.

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

Можно получить потоки Эрланга любого к-го порядка. Очевидно, простейший поток есть поток Эрланга первого порядка.

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

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

Перечисленные выше характеристики к, τ, λ, L_оч, Т_оч, v, t_обс, µ, р, Р_k являются наиболее общими для СМО, которые являются обычно лишь некоторой частью целевой функции, поскольку необходимо учитывать еще и показатели коммерческой деятельности.

 

1.3 Графы состояний СМО

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

λ ₀₁ λ ₁₂

 

 λ₁₀ λ₂₁

Рис. 1.3. Размеченный граф состояний СМО

 

Система может находиться в одном из трех состояний: S₀ -канал свободен, простаивает, S₁ — канал занят обслуживанием, S₂- канал занят обслуживанием и одна заявка в очереди. Переход системы из состояния S₀ в S_l происходит под воздействием простейшего потока заявок интенсивностью λ ₀₁ а из состояния S_l в состояние S₀ систему переводит поток обслуживания с интенсивностью λ ₀₁. Граф состояний системы обслуживания с проставленными интенсивностями потоков у стрелок называется размеченным. Поскольку пребывание системы в том или ином состоянии носит вероятностный характер, то вероятность:p_i(t) того, что система будет находиться в состоянии S_i в момент времени t, называется вероятностью i-го состояния СМО и определяется числом поступивших заявок k на обслуживание.

Случайный процесс, происходящий в системе, заключается  в том, что в случайные моменты  времени t₀, t_1, t₂,..., t_k,..., t_n система оказывается в том или другом заранее известном дискретном состоянии последовательно. Такая. случайная последовательность событий называется Марковской цепью, если для каждого шага вероятность перехода из одного состояния S_t в любое другое Sj не зависит от того, когда и как система перешла в состояние S_t. Описывается марковская цепь с помощью вероятности состояний, причем они образуют полную группу событий, поэтому их сумма равна единице. Если вероятность перехода не зависит от номера к, то марковская цепь называется однородной. Зная начальное состояние системы обслуживания, можно найти вероятности состояний для любого значения к-числа заявок поступивших на обслуживание.

 

4. Случайные процессы

     Переход СМО из одного состояния в другое происходит случайным образом и представляет собой случайный процесс. Работа СМО — случайный процесс с дискретными состояниями, поскольку его возможные состояния во времени можно заранее перечислить. Причем переход из одного состояния в другое, происходит скачкообразно, в случайные моменты времени, по этому он называется процессом с непрерывным временем. Таким образом, работа СМО представляет собой случайный процесс с дискретными состояниями и непрерывным; временем. Например, в процессе обслуживания оптовых покупателей на фирме «Кристалл» в Москве можно фиксировать заранее все возможные состояния простейших. СМО, которые входят в весь цикл, коммерческого обслуживания от момента заключения договора на поставку ликероводочной продукции, ее оплаты, оформления документов, отпуска и получения продукции, догрузки и вывоза со склада готовой продукции.