СМО с ожиданием

В качестве показателей эффективности СМО с ожиданием (или очередью) кроме четырех вышеперечисленных применяются и следующие: среднее число заявок в системе (L_сист.); среднее время пребывания заявки в системе (Т_cист.); среднее число заявок в очереди или длина очереди (L_оч.); среднее время пребывания заявки в очереди (Т_оч); вероятность того, что канал занят или степень загрузки канала (Р_зан.).

СМО с ожиданием могут быть с неограниченной или ограниченной очередью. СМО с неограниченной очередью могут быть одно – или многоканальными.

Рассмотрим одноканальную систему с неограниченной очередью.

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

Система может находиться в одном из состояний S₀, S₁, S₂,..., S_k(рис. 7.3), по числу заявок, находящихся в СМО: S₀ - канал свободен; S₁ - канал занят (обслуживает заявку), очереди нет; S₂ - канал занят, одна заявка стоит в очереди;... S_k - канал занят, (k-l) заявок стоят в очереди и т.д.

Рис. 7.3

Это процесс гибели и размножения, но с бесконечным числом состояний, в котором интенсивность потока заявок равна λ, а интенсивность потока обслуживании μ.

Доказано, что если ρ < 1, т.е. среднее число приходящих заявок меньше среднего числа обслуженных заявок (в единицу времени), то предельные вероятности существуют. Если ρ ≥ 1, очередь растет до бесконечности.

Предельные вероятности состояний можно определить по формулам:

(7.13)

Правая часть в формуле (7.13) представляет собой геометрический ряд со знаменателем ρ < 1, равный . Поэтому p₀ = 1-ρ (7.14)

Предельные вероятности р₀, р₁, p₂,..., р_k,... образуют убывающую геометрическую прогрессию со знаменателем <1, следовательно, вероятность p₀ - наибольшая. Это означает, что если СМО справляется с потоком заявок (при <1), то наиболее вероятным будет отсутствие заявок в системе.

Среднее число заявок в системе L_сист. можно определить по формуле математического ожидания:

L_сист.= (7.15)

(суммирование от 1 до , так как нулевой член 0 р₀=0).

При <1формула (7.15) преобразуется к виду

L_сист.= . (7.16)

Среднее число заявок в очереди (L_оч) очевидно равно

L_оч.=L_сист.+L_об, (7.17)

где L_об. - среднее число заявок, находящихся под обслуживанием.

Среднее число заявок под обслуживанием представляет собой математическое ожидание числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):

L_об.=0

Откуда

L_об. = 1-р₀ или L_об. = ρ. (7.18)

На основе формул (7.16), (7.17) и (7.18) получим,

L_оч.= (7.19)

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

T_сист.= T_оч.= (7.20)

Формулы (7.20) называются формулами Литтла. Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих ее: оба потока заявок имеют одну и ту же интенсивность .

Подставляя в формулу (7.20) значения L_сист. и L_оч. из (7.16) и (7.19) получим формулы для определения времени пребывания заявки в системе и среднего времени пребывания заявки в очереди -

T_сист.= T_оч.= (7.21)

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

Система может находиться в одном из состояний S₀, S₁, S₂,..., S_k,..., S_n,..., нумеруемых по числу заявок, находящихся в СМО: S₀ - в системе нет заявок (все каналы свободны); S₁ - занят один канал, остальные свободны; S₂ - заняты два канала, остальные свободны;..., S_k — занято k каналов, остальные свободны;..., S_n - заняты все n каналов (очереди нет); S_n+1 - заняты все п каналов, в очереди одна заявка;.... S_n+r - заняты все п каналов, r заявок стоит в очереди,....

Граф состояний системы показан на рис. 7.4. В отличие от предыдущей СМО, интенсивность потока обслуживании (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины до n , так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем п, интенсивность потока обслуживании сохраняется равной n .

Можно показать, что при /n < 1 предельные вероятности существуют. Если /n 1, очередь растет до бесконечности.

Как и в случае одноканальной СМО с очередью, можно получить формулы для определения:

а) вероятности того, что заявка окажется в очереди,

P_оч.= (7.22)

б) среднего числа занятых каналов

(7.23)

в) среднего числа заявок в очереди

L_оч.= (7.24)

г) среднего числа заявок в системе

L_сист.=L_оч.+ . (7.25)

Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе находятся по формулам Литтла (7.20).

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

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

На практике часто встречаются СМО с так называемыми "нетерпеливыми" заявками, т.е. СМО с ограниченным временем ожидания. Такие заявки могут уйти из очереди, если время ожидания превышает некоторую величину.

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

Методика определения показателей эффективности СМО с ограниченным временем отличается от выше рассмотренной не значительно.

Понятие о статистическом моделировании СМО (методе Монте-Карло)

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

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

Идея метода Монте-Карло состоит в том, что вместо аналитического описания СМО производится "розыгрыш" случайного процесса, проходящего в СМО, с помощью специально организованной процедуры. В результате такого "розыгрыша" получается каждый раз новая, отличная от других, реализация случайного процесса. Это множество реализаций можно использовать как некий искусственно полученный статистический материал, который обрабатывается обычными методами математической статистики. После такой обработки могут быть получены приближенно любые характеристики обслуживания.

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

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

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

[1] Ronald H. Ballou, Business Logistics Management (New Jersey, 1992). P.414.