Решение управленческой задачи методами теории массового обслуживания

Поток Пуассона служит для  моделирования различных реальных потоков: несчастных случаев, потока заряженных частиц из космоса, отказов оборудования и других. Так же возможно применение для анализа финансовых механизмов, таких как поток платежей и  других реальных потоков. Для построения моделей различных систем обслуживания и анализа их пригодности. Использование потоков Пуассона значительно упрощает решение задач систем массового обслуживания, связанных с расчетом их эффективности³.

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

P_{m, n}= a^m_e^-a ; (m=0,n),

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

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

n= λ t; p= τ/t,

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

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

F(t)=P(T<t).

По условию в течение  времени T не должно произойти ни одного события, а на интервале времени t должно появиться хотя бы одно событие. Эта вероятность вычисляется с помощью вероятности противоположного события на промежутке времени (0; t), куда не попало ни одного события, т.е. m = 0, тогда F(t)=1-P₀=1-(a⁰*e^-a)0!=1-e^-Xt,t≥0

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

P(T<∆t)=1-e^{-λ t} ≈1-[1- λ Δt+1/2(λ Δt)²-1/6(λ Δt)³] ≈ λ Δt

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

f(t)= λ e- λ^t , при t≥0

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

М(Т)= λ ^∞∫₀ t*e^-λt*dt=1/ λ ; D(T)=1/ λ² ; σ(T)=1/ λ .

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

P_k(t)=( λt)^k/ k! *e^{-λ t},

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

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

ƒ(t)= λ e^{-λ t}.

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

ƒ (t_оч)=V*e^{-v t}_оч ,

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

v=1/Т_оч ,  

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

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

ƒ(t _обс)=µ*е ^{µ t} _обс ,

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

µ=1/ t _обс [чел/мин; руб./час; чеков/час; докум./день; кг./час; т./год] ,

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

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

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

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

 

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

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

                

Рис. 2. Граф состояний одноканальной системы с неограниченной очередью

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

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

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

Различают случайные процессы:

• дискретный во времени;
• с непрерывным временем;
• с непрерывным состоянием;
• с дискретным состоянием;

Случайный процесс X(t) называется процессом дискретным во времени, если система, в которой он протекает, меняет свои состояния только в моменты времени t₁, t₂,…,t_n, число которых конечно или счетно⁵.

Случайный процесс называется процессом с непрерывным временем, если в моменты возможных переходов системы из состояния в состояние не фиксировано заранее, а случайно.

Случайный процесс называется процессом с непрерывными состояниями, если значением случайного процесса является непрерывная случайная величина⁶.

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

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

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

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

Такие случайные процессы называются процессами без последствия, или марковскими. В марковских процессах, для каждого момента времени (t₀) вероятность любого состояния (t > t₀) системы S_i, в будущем (t >t₀) зависит только от ее состояния в настоящем (при t = t₀) и не зависит от того, когда и каким образом система пришла в это состояние, т.е. оттого, как развивался процесс в прошлом.

Марковские случайные  процессы делятся на два класса: процессы с дискретными и непрерывными состояниями. Процесс с дискретными  состояниями возникает в системах, обладающих только некоторыми фиксированными состояниями, между которыми возможны скачкообразные переходы в некоторые, заранее не известные моменты времени. Рассмотрим пример процесса с дискретными состояниями. В офисе фирмы имеются два телефона. Возможны следующие состояния у этой системы обслуживания: S_o—телефоны свободны; S_l — один из телефонов занят; S₂— оба телефона заняты.

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

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

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

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

Для описания процессов с  непрерывным временем используется модель в виде так называемой марковской цепи с дискретными состояниями  системы, или непрерывной марковской цепью.

 

 

 

 

 

 

 

 

 

 

 

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

3.1. Одноканальная СМО с отказами в обслуживании

Простейшей из всех задач  теории массового обслуживания является модель одноканальной СМО с отказами (потерями).

При этом система массового  обслуживания состоит только из одного канала (n = 1) и на нее поступает  пуассоновский поток заявок с  интенсивностью λ, зависящей, в общем случае, от времени: λ = λ(t)