Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лекции по теории вероятностей.doc
Скачиваний:
165
Добавлен:
02.05.2014
Размер:
3.94 Mб
Скачать

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

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

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

Дисциплина очереди. Это описательная характеристика. Требование, поступившее в систему, обслуживается в порядке очереди – дисциплина очереди:первым пришел первым обслужен. Другая дисциплина очереди:последним пришелпервым обслужен- это обслуживание по приоритету. Наконец, обслуживание требований может бытьслучайным.

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

По окончании обслуживания требование покидает систему.

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

Таким образом, основные элементы системы массового обслуживания укладываются в следующую схему (рис. 30):

Рис. 30

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

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

,

где вероятность того, что за времяtв СМО поступит ровноkтребований, - среднее число требований, поступающих в СМО в единицу времени.

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

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

Каждый прибор, в любой момент времени t0, может обслуживать не более одного требования. Обслуженное требование покидает СМО. Требуется проанализировать эффективность работы системы.

Решение. Обозначим через- вероятность того, что в момент времениt в системе находитсяkтребований.

Пусть t– достаточно малый промежуток времени. Вероятность того, что в СМО за времяtне поступит ни одного требования:

Вероятность того, что в СМО за времяtпоступит одно требование:

Вероятность того, что за время tв СМО поступит два или более требований:

Вероятность того, что за времяtтребование будет обслужено:

Вероятность того, что за времяtбудет обслужено два или более требования:

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

=;

=;

=

Вероятность того, что за время tпроизойдет более одного события (например, поступит требование и какое – нибудь обслужится), есть бесконечно малая более высокого порядка, чемt - 0 (t).

Для 0 kn– 1 имеем разностное уравнение

. (95)

При получении уравнения мы воспользовались формулой полной вероятности и свойствами пуассоновского процесса.

В словесной формулировке это звучит так: вероятность того, что в момент времени (t+t) в системе находитсяк требований (kn– 1) равна вероятности того, что в моментtв системе находилоськ требований и ни одного требования не поступило и не было обслужено, или вероятность того, что в момент времениtв системе находилось (k-1) требование и за времяtпоступило одно требование в систему, или вероятность того, что в момент времениt в системе находилось (k+1) требование на обслуживании и за времяtодно из (k+1) требований было обслужено, или вероятность того, что за времяt произошло более одного события.

Преобразуем уравнение (95) к виду:

Разделив обе части наtи переходя к пределу, получим

1к n-1. (96)

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

Таким образом, для кn, имеем уравнение

.

Производя выкладки, аналогичные уравнению (95), получим

. (97)

Заметим, что при к= 0, вероятность

Учитывая это, окончательно имеем систему уравнений:

(98)

Пусть начальные условия имеют вид:

(99)

Решение системы (98), с начальными условиями (99), слишком громоздко [8], однако решение для стационарного режима оказывается простым.

В самом деле, если (/n)1, то СМОэргодична, то есть0 существует, но тогда.

Тем самым система (98) сводится к системе однородных алгебраических уравнений:

(100)

Чтобы система (100) имела единственное решение, добавим условие нормировки:

(101)

Для решения системы (100), с условием (101), введем обозначения

(102)

В новых обозначениях, система (100) примет вид:

Отсюда следует, что

Возвращаясь к обозначениям (102), получаем

Выразим все вероятности через Р0. Имеем прик = 1

При 1кn

. (103)

При к n,

.

или

(104)

Для нахождения Р0, воспользуемся условием нормировки (101):

.

После элементарных преобразований, получим

.

Учитывая, что имеем

(105)

Окончательно получаем:

,

Замечание. Условие1, означает, что входящий поток меньше, чем суммарный выходящий, иначе ряд в (105) был бы расходящимся, то есть система не была бы эргодична.

Если Ркизвестны, то многие показатели эффективности можно вычислить путем элементарных алгебраических операций, например,

или

;

  1. ,

;

  1. tож– среднее время, в течение которого требование ждет начала обслуживания,

;

  1. А– средняя длина очереди,

где

  1. В- среднее число обслуживаемых требований,

  1. R- среднее число требований в системе,

R = A +B;

  1. L– среднее время пребывания требования в системе,

/;

10)- коэффициент загрузки системы,

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

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

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

Суть метода. Функционирование системыSпредставляется в виде связного графа ее состоянийПереход системы из состоянияCiв состояниеСjграфически осуществляется по направленным отрезкам с заданнымиинтенсивностямипереходов. Если переход невозможен, то=0.

В стационарном режиме действует принцип равновесия: сумма «входов»

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

Рассмотрим применение метода декомпозиции на примере следующей задачи из теории надежности процесса гибели ирожденияс конечным числом состояний [8].

Пусть имеем однородный марковский процесс с конечным числом состояний ,к= 0, 1, …,n. Если в моментt процесс находится в состоянииCк, то за бесконечно малое времяtон с вероятностьюперейдет в состояние, с вероятностьюперейдет в состояниеи с вероятностьюостанется в состоянии. Если процесс находится, в моментt, в состоянии, то за времяtон может остаться в состоянииили перейти в состояние; если же процесс находится в моментtв состоянии, то за времяtон может остаться в состоянииили перейти в состояние. Обозначим через- вероятность того, что в момент времениtпроцесс находится в состояниик,к= 0, 1, 2, …,n. Представим наш процесс в виде графической схемы (рис. 31).

Рис. 31

Очевидно, что процесс эргодический, следовательно . В силу условия равновесия, для стационарного режима, имеем (по каждому состоянию)

,,

для 1 кn-1, .

Таким образом, получаем однородную систему алгебраических уравнений:

(106)

которая имеет единственное решение, если добавить условие нормировки

(107)

Окончательно получаем:

Учитывая (107) находим

Упражнение. Записать граф – схему СМО предыдущей задачи, составить уравнения равновесия и получить значения вероятностейк= 0,1,2,… .

Замечание. Система уравнений вида (98) является частным случаем предельного перехода привуравнениях Колмогорова – Чепмена для однородных во времени марковских процессах [2], которые имеют вид:

(108)

где .

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

(109)

Из системы (109), с точностью до обозначений, предельным переходом легко получить систему (98).