Потоки событий. Уравнения Колмогорова

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

Основные понятия и классификация систем массового

Обслуживания

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

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

Требованием (клиентом, заявкой) в СМО называется каж­дый отдельный запрос на выполнение какой-либо работы. Обслуживание — это выполнение работы по удовлетворе­нию поступившего требования. Объект, выполняющий обслужи­вание требований, называется обслуживающим устройством (прибором) или каналом обслуживания.

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

СМО классифицируются по разным признакам.

1. По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

2. В зависимости от условий ожидания требованием нача­ла обслуживания различают СМО с потерями (отказами) и СМО с ожиданием.

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

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

Для СМО с ожиданием основными характеристиками яв­ляются математические ожидания длины очереди и времени ожидания. Примером системы с ожиданием может служить процесс восстановления телевизоров в ремонтной мастерской.

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

В качестве характеристик эффективности может приме­няться вероятность отказа как в системах с потерями (или харак­теристики времени ожидания) и в системах с ожиданием.

3. По дисциплине обслуживания СМО делятся на систе­мы с приоритетом в обслуживании и на системы без приоритета в обслуживании.

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

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

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

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

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

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

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

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

 

Потоки событий. Уравнения Колмогорова

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

Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона, то есть вероятность поступления за время t, ровно k требований задается форму­лой:

P _k = e^-λt

где λ – параметр потока (интенсивность – среднее число требований, поступивших в систему за единицу времени).

Простейший поток обладает тремя основными свойствами: ординарностью, стационарностью и отсутствием последействия.

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

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

Отсутствие последействия означает, что число требований, поступивших в систему до момента t, не определяет того, сколько требований поступит в систему за время t + t.

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

Вероятность того, что на временном интервале t = τ не поступит ни одного требования p ₀ определяется как:

p ₀ = e^-λτ.

Тогда вероятность того, что на этом же временном интервале появится хотя бы одно требование определяется соотношением

p (t) = 1 – p ₀ = 1 – e^-λτ.

Вероятность попадания на элементарный временной интервал, т.е. когда τ = Δt, хотя бы одного события (требования) потока, можно определить, заменив функцию e^-λτ двумя первыми числами её разложения в ряд Маклорена по степеням Δt. Действительно:

p (Δt) = 1 – e^-λΔt ≈ λ Δt.

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

р (t <T)=F(t)=1 – е^{- t},

т.е. вероятность того, что время обслуживания не превосходит некоторой величины t, где μ – интенсивность потока обслуживания тре­бований в системе (среднее число требований, обслуженных в единицу времени).

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

p (Δt) = 1 – e^-Δt ≈ μλ Δt.

При анализе случайных процессов с дискретными состояниями пользуются графиком состояний, где прямоугольником изображаются состояния, а переходы из состояния в состояние – стрелками. У стрелок обычно проставляются значения интенсивностей λ_ij (μ_ij) перехода системы из состояния S _i в состояние S _j, которые происходят под воздействием простейших потоков событий.

Рассмотрим систему, которая может находиться в двух состояниях: S₀– система исправна; S₁ – система находится в состоянии отказа и ремонтируется (рис. 8.1).

 

 

Рис. 8.1. Граф системы

Будем характеризовать состояние системы (S₀,S₁) вероятностями состояния р ₀ (t) и р ₁ (t). Очевидно, что

р ₀ (t) + р ₁ (t) = 1.

Найдем вероятность того, что система в момент (t+Δt) будет находиться в состоянии S₀.

Это возможно, во-первых, в том случае, если система в момент времени t с вероятностью р ₀(t) находилась в состоянии S₀ и за время Δt из него не вышла. Вероятность выхода системы за время Δt из состояния S₀ в состояние S₁ определяется как λ· Δt. Противоположная вероятность (что система не выйдет из S₀) определяется как (1 – λΔt). Вероятность того, что система, находившаяся в состоянии S₀ с вероятностью р ₀(t), за время Δt не выйдет из него, равна по теореме умножения вероятностей

р ₀(t) (1 – λΔt).

 

 

Во-вторых, система в момент времени t находилась с вероятностью р ₁(t) в состоянии S₁ и за интервал времени Δt с вероятностью μ · Δt перешла в состояние S₀, т.е.

р ₁(t)· μΔt.

Вероятность р ₀(t + Δt) нахождения системы в состоянии S₀ момент времени (t + Δt) по какому-либо из двух рассмотренных способов равна сумме рассмотренных вероятностей

р ₀(t + Δt) = р ₀(t) (1 – λΔt)+ р ₁(t) μΔt

Преобразуем соотношение к виду

Переходя к пределу при Δt→ 0, получим

По аналогии составляется уравнение, описывающее вероятность того, что система в момент (t + Δt) будет находиться в состоянии S₁, но проще это найти из условия нормирования

р ₀ (t) + р ₁ (t) = 1.

С учетом этого условия система уравнений для двух состояний графа имеет вид

Задав начальные условия, можно решить систему уравнений и найти систему функций времени р_i (t), где i – номер состояния.

Для достаточно большого значения t распределение вероятностей стабилизируется и практически не зависит от времени, т.е.

Тогда система уравнений упрощается (стационарный режим)

 

Откуда вероятности состояний установившегося процесса определяются как

В частности, если μ =2; λ =1, то Р₀=0,67; Р₁=0,33. Таким образом, в среднем система будет находиться в рабочем состоянии 67%, а в состоянии ремонта 33% времени.

В общем случае система уравнений Колмогорова может быть составлена по следующему алгоритму.

1. В левой части каждого уравнения стоит производная вероятности i -го состояния.

2. В правой части каждого уравнения стоит:

2.1. Сумма произведений вероятностей всех состояний, из которых идут стрелки в i -е состояние, на интенсивности соответствующих потоков событий.

2.2. Минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i -го состояния.

Система Колмогорова состоит из независимых уравнений и условия нормирования.

 

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

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

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

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

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

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

 

Замкнутая СМО с ожиданием

Поскольку система замкнутая, то к постановке задачи сле­дует добавить условие: поток поступающих требований ограни­чен, т.е. в системе обслуживания одновременно не может нахо­диться больше m требований (m – число обслуживаемых объек­тов).

Такую систему можно классифицировать как многоканальную СМО (n – каналов) и ограниченной данной очереди l, причем n +l = m.

Граф состояний такой системы изображен на рис. 8.2.

 

 

Рис. 8.2. Граф состояний многоканальной СМО с ограниченной очередью

 

Состояния данной системы означают:

S₀ – отсутствие требований в системе;

S₁ – одно требование обслуживается, очереди нет;

S₂ – два требования обслуживаются, очереди нет;

…………………………………………………….

S_n – n требований обслуживаются, очереди нет;

S _{n+ 1} – n требований обслуживаются, одно требование стоит в очереди;

…………………………………………………….

S _n+l – n требований обслуживаются, l требований стоят в очереди.

Система уравнений вероятностей состояний в стационарном режиме для цепочки S₀ – S_n будет:

Для цепочки состояний S _{n+ 1} – S _n+l система уравнений стационарного режима будет:

В качестве основных критериев, характеризующих качество функционирования рассматриваемой системы, выберем: 1) от­ношение средней длины очереди к наибольшему числу требова­ний, находящихся одновременно в обслуживающей системе – коэффициент простоя обслуживаемого объекта; 2) отношение среднего числа незанятых обслуживающих каналов к их общему числу – коэффициент простоя обслуживаемого канала.

Рассмотрим расчет необходимых вероятностных характе­ристик (показателей качества функционирования) замкнутой СМО.

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

P _k = α_k P₀, (1 k n),

где α_k = или α_k = ;

;

– интенсивность поступления требований в си­стему от одного источника;

_об – средняя продолжительность обслуживания одного требования;

т – наибольшее возможное число требований, находящих­ся в обслуживающей системе одновременно (m=n+l);

п – число обслуживающих аппаратов;

Р₀ – вероятность того, что все обслуживающие аппараты свободны.

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

P_k= _kP₀, (n k m),

где _k = ( _об) ^k или α_k = .

3. Вероятность того, что все обслуживающие аппараты сво­бодны, определяется из условия

4. Среднее число требований, ожидающих начала обслужи­вания (средняя длина очереди):

.

5. Коэффициент простоя требования в ожидании обслужи­вания:

a₁= .

 

6. Вероятность того, что все обслуживающие аппараты заняты:

P_отк = .

7. Среднее число требований, находящихся в обслуживающей системе (обслуживаемых и ожидающих обслуживания):

A₂= = .

8. Коэффициент полного простоя требований на обслуживании и в ожидании обслуживания:

a₂= .

9. Среднее время простоя требования в очереди на обслуживание:

T_ож= a ₁ / .

10. Среднее число свободных обслуживающих аппаратов:

A₃= .

11. Коэффициент простоя обслуживающих аппаратов:

a₃ = .

12. Вероятность того, что число требований, ожидаю­щих обслуживания, больше некоторого числа В (вероятность того, что в очереди на обслуживание находится более В тре­бований):

P_-B = = .

Рассмотрим пример расчета характеристик замкнутой СМО.

Пример 8.1. Оптовый склад строительных материалов обслу­живает шесть предприятий-потребителей материалов. Каждый из потребителей направляет на склад автомашину за мате­риалами в среднем один раз в смену (продолжительность сме­ны 8 ч). На складе имеется один автопогрузчик, который исполь­зуется только для погрузки материалов на прибывающие авто­машины. Прибывшая на склад автомашина становится в оче­редь, если автопогрузчик занят погрузкой другой автомашины. Обработка статистических данных о продолжительности погруз­ки одной автомашины и проверка соответствующей гипотезы по­казали, что продолжительность погрузки одной автомашины подчиняется показательному закону распределения и составля­ет в среднем 48 мин (0,1 смены). Статистическое исследование потока автомашин показа­ло, что число автомашин, поступающих на склад в единицу вре­мени, подчиняется пуассоновскому закону распределения. Требуется провести расчет характеристик функционирова­ния приведенной производственной системы как СМО.

Решение. Рассчитаем основные параметры системы для условий задачи.

Вероятность того, что все обслуживающие ап­параты свободны (на складе нет автомашин) определяется как P₀, λ= 1, μ= 0,1.

Вероятность того, что на складе одна автомашина:

P ₁ = 0,1 P ₀ = 0,6 P ₀,

а вероятность того, что на складе две автомашины (одна под погрузкой, а другая в очереди):

P ₂ = 0,1² P ₀ = 0,3 P₀.

Рассчитывая аналогично, получим: Р ₃=0,12 Р ₀; Р ₄ =0,036 Р ₀; Р ₅ = 0,0072 Р ₀; Р ₆ = 0,0007 Р ₀. Так как сумма вероятнос­тей нахождения системы в любом из состояний равна 1, т.е.

=1,

то P ₀(1 + 0,6 + 0,3 + 0,12 + 0,036 + 0,0072 + 0,0007) = 2,0639; Р ₀ = 1.

Отсюда находим Р ₀ = 0,4845.

Дальнейшие расчеты затруднений не вызывают. Напри­мер, средняя длина очереди равна

А ₁ =(2 - 1) Р ₂ + (3 - 1) Р ₃ + (4 - 1) Р ₄ + (5 - 1) Р ₅ + (6 - 1) Р ₆; А = 0,3296.