Обобщенная стационарная модель СМО

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

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

Предполагается, что интервалы D t_з и D t_о имеют экспоненциальное распределение (а = М; b = М). При этом СМО рассматривается как единое целое – структура каналов и режимы их функционирования (в частности, дисциплина очереди) не раскрываются. Вместо этого, пользуясь допущением о стационарности и характеризуя состояния системы только одним параметром – числом n заявок в системе, введем следующие обобщенные характеристики:

р_n – вероятность того, что в системе находится ровно n заявок. Благодаря допущению о стационарности полную группу вероятности р ₀, р ₁,…, р_n, … р _¥ правомерно отнести к любому интервалу времени (в рамках стационарной части процесса обслуживания) и даже к бесконечно малому отрезку времени – к произвольной точке t.

l_n – интенсивность поступления заявок в систему при условии, что в системе находится ровно n заявок;

m_n – интенсивность выходного потока заявок при условии, что в системе находится ровно n заявок.[11]

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

Целью теоретического анализа такой обобщенной модели СМО является установление функциональной зависимости вероятностей р_n от параметров l_n и m_n.

Для наглядности анализа приведем диаграмму переходов меду состояниями в рассматриваемой системе (рис.4.1.). На рисунке затененные кружки – это состояния системы; дуги, оснащенные интенсивностями, – возможные переходы в системе.

l ₀ l ₁ l_{n -1} l_n

m ₁ m ₂ m_n m_{n +1}

Рис.4.1.

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

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

I_вх = l_{n -1} p_{n -1} + m_{n +1} p_{n +1} и I_вых = (l_n + m_n) p_n,

то, приравнивая указанные интенсивности, получим уравнение баланса:

l_{n -1} p_{n -1} + m_{n +1} p_{n +1} и I_вых = (l_n + m_n) p_n, n = 1, 2, ….

Для n =0 уравнение баланса будет иметь вид (см. диаграмму):

l ₀ p ₀ = m ₁ p ₁.

Уравнения баланса решают рекуррентно, выражая вероятности p_n, n = 1, 2, … через вероятность p ₀. Из последнего уравнения получаем:

.

Для n = 2:

.

По индукции можно доказать, что:

. (4.1)

Значение p ₀ можно определить из уравнения

. (4.2)

Соотношения (4.1) и (4.2) могут быть применены к любой конкретной СМО, удовлетворяющей сформулированным выше допущениям. Сами же вероятности p_n, n = 0, 1, … позволяют рассчитать все практически важные функциональные характеристики СМО. Укажем некоторые из таких характеристик:

L_s – среднее число находящихся в системе заявок (не забывайте, что речь идет об установившейся – стационарной фазе процесса);

L_q – среднее число заявок в очереди;

W_s – средняя продолжительность пребывания заявки в системе;

W_q – средняя продолжительность пребывания заявки в очереди;

– среднее количество занятых каналов.

Укажем на некоторые связи перечисленных характеристик с вероятностями p_n.

L_s = ; L_q = . (4.3)

Зависимость между L_s и W_s, а также между L_q и W_q задается, так называемыми, формулами Литтла:

L_s = l_эффW_s; L_q = l_эффW_q, (4.4)

где эффективная интенсивность l_эфф поступления клиентов в систему может быть определена через исходную интенсивность l и другие параметры системы. Далее мы рассмотрим конкретные примеры. Здесь же отметим, что l_эфф = l, если все прибывающие заявки могут попасть в систему ("зал ожидания" не заполнен до предела), и l_эфф < l в противном случае.

Если интенсивность обслуживания характеризовать одним параметром m, то, учитывая, что 1/ m - это среднее время обслуживания заявки, получим соотношение:

W_s = W_q + 1/ m. (4.5)

Домножая последнее соотношение на l_эфф и используя формулу Литтла, получим:

L_s = L_q + l_эфф / m. (4.6)

По определению разность между средним числом находящихся в системе заявок L_s и средним числом заявок в очереди L_q равна среднему числу занятых каналов, поэтому:

= L_s - L_q = l_эфф / m. (4.7)

Введенные выше понятия поясним на конкретном примере.

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

· если на стоянке есть свободное основное место, то прибывающий клиент сразу занимает это место;

· если все основные места были заняты, а на дополнительных местах есть хотя бы один клиент, то он немедленно занимает освобождающееся основное место;

· если все основные места были заняты, но есть свободное дополнительное место, то прибывающий клиент, немедленно его занимает. Время пребывания клиента на дополнительном месте принципиально не ограничено (ограничено только тем, что он может перейти на основное место);

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

Пусть среднее время пребывания клиента на основном месте стоянки – 30 минут. Исходная интенсивность входного потока l = 6 автомобилей в час.

А н а л и з с и с т е м ы.

В системе с = 5 каналов обслуживания. Общая емкость системы – 8 мест, таким образом система может находиться в 9 состояниях: n = 0, 1, …, 8, где n – число автомобилей, находящихся в системе.

В соответствии с принятыми допущениями интенсивности входного потока:

l_n = 6, n = 0, 1, …, 8.

Максимальная интенсивность обслуживания клиентов одним каналом m = 60/30 = 2 автомобиля в час.

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

m_n =

nm = 2 n автомобилей в час, n = 0, 1, …, 5;

5 m = 10 автомобилей в час, n = 6, …, 8.

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

С учетом (4.1) и (4.2) можно определить вероятности отдельных состояний системы:

p ₀

р_n =

3 ⁿ / n!, n = 1, …, 5;

p ₀3 ⁿ /(5!5 ^{n -5}), n = 6, …, 8;

p ₀ = 0,04812.

Эффективную интенсивность l_эфф поступления автомобилей на стоянку можно определит по схеме, иллюстрируемой рис.4.2.

Система

Источник l l_эфф

клиентов

l_потери

Рис. 4.2.

Приезжающий автомобиль может поступить на стоянку с интенсивностью l_эфф или уехать с интенсивностью l_потери. Поскольку прибывший автомобиль уезжает, если система находится в состоянии n = 8, то вероятность такого события равна p ₈ = 0,02105 (см. формулы выше). Следовательно,

l_потери = lp ₈ = 0,1263 автомобилей в час;

l_эфф = l - l_потери = 5,8737 автомобилей в час.

Среднее количество автомобилей в системе в соответствии с (4.3):

L_s = 0 p ₀ + … + 8 p ₈ = 3,1286.

Средняя продолжительность пребывания автомобиля в системе в соответствии с (4.4):

W_s = L_s / l_эфф = 0,53265 часа.

Средняя продолжительность пребывания автомобиля в очереди (на дополнительном месте) в соответствии с (4.5):

W_q = W_s - 1/ m = 0,03265 часа.

Среднее количество занятых каналов в соответствии с (4.7):

= l_эфф / m. = 9,9368 мест.

Используя полученные результаты, рассмотрим различные частные случаи СМО.

4.1.2. Модель СМО (M /M/1):(GD /¥/¥)

Итак, рассмотрим пуассоновскую модель с одним каналом (с =1), произвольной дисциплиной очереди, без ограничений на емкости источника и системы.

Предполагается, что клиенты поступают с постоянной интенсивностью l.

Имеем: l_n = l; m_n = m, n = 0, 1, …. Поскольку отсутствуют ограничения на емкость очереди и, следовательно, все прибывающие клиенты остаются в очереди, то l_эфф = l, l_потери = 0.

Обозначим r = l / m. Тогда выражения для вероятности n -го состояния системы имеет вид (см. (4.1)):

р_n = rⁿp ₀, n = 1, 2, …. (4.8)

Для p ₀ имеем тождество p ₀(1 + r + r ² + …) = 1. Его решение

p ₀ = 1 - r (4.9)

имеет смысл только, если r < 1. Это означает, что для достижения системой стационарного режима функционирования необходимо, чтобы интенсивность поступления клиентов в систему была строго меньше интенсивности обслуживания. Если l ³ m, то вероятности р_n стационарных состояний не существуют.

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

L_s = ; W_s = ; W_q = ; L_q = ; = r. (4.10)

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

Рассмотрим теперь вопрос о распределении, например, времени обслуживания клиента в системе. Здесь уже необходимо фиксировать дисциплину очереди. Рассмотрим дисциплину FCFS.

Пусть в системе уже находится n клиентов. Тогда время t, которое проведет в системе вновь прибывший клиент (время обслуживания), будет определяться так:

t = t ₁' + t ₂ + … + t_n + t_{n +1}, (4.11)

где t ₁' – время, необходимое для завершения обслуживания клиента, который уже находится в канале обслуживания;

t ₂, …, t_n - интервалы времени, необходимые для обслуживания n -1 клиента;

t_{n +1} - время обслуживания только что прибывшего клиента.

Обозначим w (t | n +1) – плотность вероятности для случайной величины t при условии, что на момент прибытия очередного клиента в системе уже есть n клиентов.

Поскольку время облуживания клиента в канале имеет экспоненциальное распределение, все величины из правой части (4.11), включая t ₁' имеют экспоненциальное распределение с параметром m. Следовательно, величина t, определенная через (4.11), будет иметь гамма-распределение (учтена целочисленность одного из параметров – (n +1)):

w (t | n +1) = .

Усредняя эти плотности вероятности по различным состояниям системы, получим:

w (t) = = , t >0.

{Студенты должны самостоятельно проделывать вывод последней формулы}

Таким образом, время обслуживания клиента t также имеет экспоненциальное распределение с параметром m_ож = m (1 - r), что строго соответствует полученной ранее формуле для среднего времени W_s обслуживания клиента в системе (см. (4.10)).

4.1.3. Модель СМО (M /M/1):(GD / N /¥)

Эта модель отличается от предыдущей ограничением на емкость системы: система вмещает не более N клиентов, соответственно, максимальная длина очереди равна N –1.

Таким образом, формально можем положить:

l_n =

l, n = 0, 1, … N –1,

0, n ³ N.

m_n = m, n = 0, 1, …

(4.12)

р_n =

r ⁿp ₀, n £ N,

0, n > N.

Соответственно, уравнение для p ₀ имеет вид p ₀(1 + r + … + r^N) = 1. Таким образом:

(4.13)

р ₀ =

, r ¹1,

, r =1,

В этой модели значение параметра r = l / m не обязательно должно быть меньше 1, поскольку поступление клиентов в систему ограничивается ее конечной емкостью. Таким образом, в данном случае интенсивность поступления клиентов в систему естественно характеризовать величиной

l_эфф = l (1 – р_N).

Следует ожидать, что l_эфф будет меньше m. {Почему?}

С учетом (4.3), (4.12) и (4.13) среднее число клиентов в системе равно:

(4.14)

L_s =

, r ¹1,

, r =1,

{Студенты должны самостоятельно проделывать вывод последней формулы. Первую формулу из (4.14) можно получить с помощью суммы для арифметико-геометрической прогрессии: [12]. Возможны иные подходы.}

Зная значения L_s и l_эфф можно получить значения других функциональных характеристик.

4.1.4. Модель СМО (M /M/ с):(GD /¥/¥)

Эта модель обобщает модель из п. 4.1.2 по параметру с (число каналов обслуживания).

Пусть l - интенсивность поступления клиентов в систему, m - интенсивность обслуживания клиентов одним каналом.

Так как нет ограничений на число клиентов в системе, то l_эфф = l.

Наличие параллельных каналов обслуживания приводит к возрастанию фактической интенсивности обслуживания (здесь также лучше говорить об интенсивности выходного потока): если n £ с, то интенсивность равна nm; если n > с, то интенсивность равна cm. Используя принятые выше обозначения, можно записать:

m_n =

nm, n £ с,

cm, n > с,

l_n = l, n = 0, 1, ….

Соответственно,

(4.15)

p_n =

, n £ с,

, n > с,

Если предположить, что r / c <1, то можно получить следующую формулу для p ₀:

. (4.16)

Используя (4.15) и (4.16), можно рассчитать функциональные характеристики. Например, среднее число клиентов в очереди:

L_q = .

Остальные характеристики определяются в соответствии с общими формулами {проделать самостоятельно}.

4.1.5. Модель СМО (M /M/ с):(GD / N /¥), c £ N

Эта модель обобщает модель из п. 4.1.3 по параметру с (число каналов обслуживания).

Максимальная длина очереди в системе равна N – c.

Пусть l - интенсивность поступления клиентов в систему, m - интенсивность обслуживания клиентов одним каналом.

Приведем некоторые расчетные соотношения для параметров и характеристик системы.

l_n =

l, 0£ n £ N,

0, n > N.

m_n =

nm, 0£ n < с,

cm, c £ n £ N.

p_n =

, 1£ n < с,

, c £ n £ N.

р ₀ =

;

.

L_q =

;

.

l_эфф = l (1 – р_N).

4.1.6. Модель СМО (M /M/¥):(GD /¥/¥)

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

Полагается, что интенсивность поступления клиентов в систему l постоянна, а также постоянна интенсивность m обслуживания клиентов одним каналом.

В обозначениях общей модели можно записать:

l_n = l; m_n = nm, n = 0, 1, …,

Следовательно: .

Из равенства следует, что .

Откуда получаем: , n = 0, 1, ….

Таким образом вероятности состояний системы в этой модели совпадают с вероятностями распределения Пуассона с математическим ожиданием L_s = r. Кроме того в этой системе, очевидно L_q = W_q = 0.

4.1.7. Модель СМО (M /M/ R):(GD / K / K)

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

Интенсивность поломок, отнесенная к одному станку, равна l. Один механик ремонтирует сломанные станки с интенсивностью m станков в единицу времени. Предполагается, что моменты времени поломок и время ремонта подчиняются распределению Пуассона.

Основное отличие от предыдущих моделей – ограниченность мощности источника заявок.

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

l_n =

(K – n) l, 0£ n < K,

0, n ³ K.

m_n =

nm, 0£ n < R,

Rm, R £ n < K,

0, n ³ K.

Пользуясь этим формулами, из общей модели можно получить следующие соотношения для вероятностей состояния системы:

p_n =

, 0£ n £ R,

, R £ n £ K.

p ₀ =

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

Значение l_эфф можно получить как математическое ожидание величины l (K – n), где n – дискретная случайная величина с распределением { p ₀, p ₁, …}:

l_эфф = М [ l (K – n)] = l (K – L_s)/

4.2. Модель СМО (M / G /1):(GD /¥/¥). Формула Поллачека-Хинчина

Непуассоновские системы сложны для теоретического исследования. В таких моделях, как правило, не получаются замкнутые выражения для функциональных характеристик. Одно из немногих исключений – это система, рассматриваемая в данном пункте при условии, что время обслуживания имеет произвольное распределение, но известны математическое ожидание M [ t_об ] и дисперсия D [ t_об ] этой случайной величины.

Мы приведем без доказательства формулу (Поллачека-Хинчина) для вычисления среднего числа L_s находящихся в системе заявок[13]. Пусть l - интенсивность входного потока заявок. При выполнении условия l M [ t_об ] < 1 можно показать, что

L_s = l M [ t_об ] + , l M [ t_об ] < 1.

Поскольку l_эфф = l, то остальные функциональные характеристики могут быть получены по общим соотношениям (см. п. 4.1.1). В то же время, не удается получить в замкнутой форме выражения для вероятностей состояний p_n.

Приложение

P-процентное значение t_p нормально распределенной величины t
(P=100p, где p - доверительная вероятность)

Для нормально распределенной со стандартным отклонением 1 случайной величины t значение t_p удовлетворяет условию "| t | не превосходит t_p с вероятностью p “ и является решением уравнения Ф(t) = p, где Ф(t) - интеграл вероятности.

p	tp	p	tp
0,80	1,28	0,98	2,33
0,85	1,44	0,99	2,58
0,90	1,65	0,999	3,29
0,95	1,96	0,9999	3,89

P-процентное значение t_{p , v} величины t, распределенной по закону
Стъюдента с v степенями свободы.

Для случайной величины t, распределенной по закону Стъюдента с v степенями свободы, значение t_{p , v} удовлетворяет условию "| t | не превосходит t_{p , v} с вероятностью p " и является решением уравнения , где - плотность вероятности для распределения Стъюдента.

n	tp при различных значениях p
	p =0,80	0,90	0,95	0,98	0,99	0,999
	1,53	2,13	2,78	3,75	4,60	8,61
	1,48	2,01	2,57	3,37	4,03	6,86
	1,44	1,94	2,45	3,14	3,71	5,96
	1,42	1,90	2,37	3,00	3,50	5,41
	1,40	1,86	2,31	2,90	3,36	5,04
	1,38	1,83	2,26	2,82	3,25	4,78
	1,37	1,81	2,23	2,76	3,17	4,59
	1,37	1,78	2,18	2,68	3,06	4,32
	1,35	1,76	2,15	2,62	2,98	4,14
	1,34	1,75	2,12	2,58	2,92	4,02
	1,33	1,73	2,10	2,55	2,88	3,92
	1,33	1,73	2,09	2,53	2,85	3,85
	1,32	1,71	2,06	2,49	2,79	3,72
	1,31	1,70	2,04	2,46	2,75	3,65
	1,30	1,68	2,02	2,42	2,70	3,55
	1,30	1,67	2,00	2,39	2,66	3,46
	1,29	1,66	1,98	2,36	2,62	3,37
¥	1,28	1,65	1,96	2,33	2,58	3,29

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

О с н о в н а я

1. Х.Таха. Введение в исследование операций, 3- изд.: В 2-х книгах. Пер. с англ. – М., Мир, 1985.

2. Х.Таха. Введение в исследование операций, 6- изд.: Пер. с англ. – М., Издательский дом "Вильямс", 2001.

3. Прицкер А. Введение в имитационное моделирование и язык СЛАМ II: Пер. с англ. – М.: Мир, 1987.

Д о п о л н и т е л ь н а я

4. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. – 2-е изд., перераб. и доп. – М, ЮНИТИ-ДАНА, 2003. – 573 с.

5. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов / Под ред. В.С.Зарубина, А.П.Карпенко. – М.: Изд. МГТУ им. Н.Э.Баумана, 2000.

6. Исследование операций в 2-х томах. Пер. с англ. Под ред. Дж. Моудера, С.Элмаграби. – М.: Мир, 1981.

7. Р.Шеннон. Имитационное моделирование систем – искусство и наука. – М.: Мир, 1978.

8. Михайлов Г.А. Оптимизация весовых методов Монте-Карло. – М.: Наука. Гл. ред. физ.-мат. лит., 1987.

9. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – 2-е изд. перераб. и доп. – М.: Наука. – 1987. 336с.

[1] Сокращенный повтор материалов из курса "Теория игр и исследование операций" с некоторыми новыми дополнениями.

[2] [3], с.15.

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

[4] См. Х.Таха. Введение в исследование операций, изд. 3, кн.2, М.: Мир, 1985. с.203.

[5] См. [3], с.59 и далее.

[6] В качестве синонима термина "прогон модели" применяют термины "история", "реализация" и др.

[7] Обратите внимание на то, что определение величины не совпадает с определением критического значения t_α/2 статистики Стюдента в предыдущем разделе.

[8] Иногда этот метод называют регенеративным, а точки начала отдельных циклов – точками регенерации [3].

[9] Х.Таха, кн.2, стр. 351 и далее. А.Прицкер, стр. 550 и далее.

[10] Все материалы данного раздела взяты из книги [2].

[11] Напомним, что интенсивность – это количество событий (число поступающих в систему или выходящих из системы) в единицу времени.

[12] И.С.Градштейн, И.М.Рыжик. Таблицы интегралов, сумм и произведений. М., 1971, с.15.

[13] Эта формула является следствием общей теории систем вида (M / G /1) – см., например, [9], с.179.

Дата добавления: 2014-01-11