Смо с отказами определения и формулы. Интенсивность потока обслуживания

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

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

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

Процедура построения последовательности состоит в следующем. Сначала формируется Функция плотности может быть определена через по формуле Пальма (4.4). Тогда, исходя из наличия в ЭВМ электронного или алгоритмического датчика случайных чисел с равномерным распределением в интервале (0,1), приступаем к формированию Для этого одним из способов, рассмотренных в главе П, преобразуем случайное число в случайное число имеющее функцию плотности Получив полагаем

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

Рассмотрим некоторые примеры, часто встречающиеся при решении практических задач методом статистического моделирования.

Пример 1. Простейший (пауссоновский) поток.

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

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

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

После несложных вычислений получаем:

Отсюда следует, что функция плотности первого интервала для простейшего потока имеет тот же вид, что и Этим свойством в общем случае, не обладают другие потоки типа Пальма.

Таким образом, для формирования реализаций простейшего потока необходимо иметь последовательность случайных чисел имеющих показательное распределение (4.6) с параметром К. Методику получения такой последовательности мы рассматривали в главе II. В соответствии с (2.15) случайные числа могут быть получены по формуле

где - случайные числа с равномерным распределением в интервале (0,1).

Последовательность моментов поступления заявок будет следующей:

Пример 2. Поток с равномерным распределением интервалов

Функция плотности рассматриваемого потока имеет вид равномерного распределения:

Можно показать, что среднее значение (математическое ожидание) случайной величины равно Поэтому среднее число заявок, поступивших в единицу времени (интенсивность потока):

Определим функцию плотности для первого интервала. По формуле Пальма аналогично формуле (4.11):

Заметим, что среднее значение длительности первого интервала может быть получено как математическое ожидание случайной величины, имеющей функцию плотности (4.16):

Перейдем к формированию первого интервала Для этого, имея случайные числа с равномерным законом распределения в интервале (0,1), необходимо получить случайное число соответствующее функции плотности (4.16). Преобразуем соотношение (4.16) следующим образом. Подставим в него вместо величины ее значение из равенства (4.15). Тогда можно записать функцию плотности

Необходимо отметить, что потоки, рассмотренные в примерах 1 и 2, отличаются благоприятной особенностью: интегралы в формуле Пальма и формулах преобразования случайных чисел берутся в конечном виде. В общем случае эти интегралы могут оказаться неберущимися. Кроме того, функции плотности иногда задаются таблично по (результатам обработки статистического материала. На практике в такого рода ситуациях пользуются приближенными методами. Интеграл в формуле Пальма вычисляется обычно для заданного набора численными методами. Это не оказывается существенно на объеме вычислений, так как формула Пальма применяется только один раз для данного потока. Преобразование случайных чисел выполняется, как правило, методом кусочной аппроксимации функции плотности в соответствии с соотношениями (2.23), (2.24) и (2.25).

В качестве показателей эффективности СМО с отказами будем рассматривать:

1) A - абсолютную пропускную способность СМО , т.е. среднее число заявок, обслуживаемых в единицу времени;

2) Q - относительную пропускную способность , т.е. среднюю долю пришедших заявок, обслуживаемых системой;

3) P_{\text{otk}} - вероятность отказа , т.е. того, что заявка покинет СМО необслуженной;

4) \overline{k} - среднее число занятых каналов (для многоканальной системы).

Одноканальная система (СМО) с отказами

Рассмотрим задачу. Имеется один канал, на который поступает поток заявок с интенсивностью \lambda . Поток обслуживании имеет интенсивность \mu . Найти предельные вероятности состояний системы и показатели ее эффективности.

Примечание. Здесь и в дальнейшем предполагается, что все потоки событий, переводящие СМО из состояния в состояние, будут простейшими. К ним относится и поток обслуживании - поток заявок, обслуживаемых одним непрерывно занятым каналом. Среднее время обслуживания обратно по величине интенсивности \mu , т.е. \overline{t}_{\text{ob.}}=1/\mu .

Система S (СМО) имеет два состояния: S_0 - канал свободен, S_1 - канал занят. Размеченный граф состояний представлен на рис. 6.

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

\begin{cases}\lambda\cdot p_0=\mu\cdot p_1,\\\mu\cdot p_1=\lambda\cdot p_0,\end{cases}

т.е. система вырождается в одно уравнение. Учитывая нормировочное условие p_0+p_1=1 , найдем из (18) предельные вероятности состояний

P_0=\frac{\mu}{\lambda+\mu},\quad p_1=\frac{\lambda}{\lambda+\mu}\,

которые выражают среднее относительное время пребывания системы в состоянии S_0 (когда канал свободен) и S_1 (когда канал занят), т.е. определяют соответственно относительную пропускную способность Q системы и вероятность отказа P_{\text{otk}}:

Q=\frac{\mu}{\lambda+\mu}\,

P_{\text{otk}}=\frac{\lambda}{\lambda+\mu}\,.

Абсолютную пропускную способность найдем, умножив относительную пропускную способность Q на интенсивность потока отказов

A=\frac{\lambda\mu}{\lambda+\mu}\,.

Пример 5. Известно, что заявки на телефонные переговоры в телевизионном ателье поступают с интенсивностью \lambda , равной 90 заявок в час, а средняя продолжительность разговора по телефону мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

Решение. Имеем \lambda=90 (1/ч), \overline{t}_{\text{ob.}}=2 мин. Интенсивность потока обслуживании \mu=\frac{1}{\overline{t}_{\text{ob.}}}=\frac{1}{2}=0,\!5 (1/мин) =30 (1/ч). По (20) относительная пропускная способность СМО Q=\frac{30}{90+30}=0,\!25 , т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит P_{\text{otk}}=0,\!75 (см. (21)). Абсолютная пропускная способность СМО по (29) A=90\cdot0.\!25=22,\!5 , т.е. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок.

Многоканальная система (СМО) с отказами

Рассмотрим классическую задачу Эрланга . Имеется n каналов, на которые поступает поток заявок с интенсивностью \lambda . Поток обслуживании имеет интенсивность \mu . Найти предельные вероятности состояний системы и показатели ее эффективности.

Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе): S_0,S_1,S_2,\ldots,S_k,\ldots,S_n , где S_k - состояние системы, когда в ней находится k заявок, т.е. занято k каналов.

Граф состояний СМО соответствует процессу гибели и размножения и показан на рис. 7.

Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью \lambda . Интенсивность же потока обслуживании, переводящих систему из любого правого состояния в соседнее левое состояние, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S_2 (два канала заняты), то она может перейти в состояние S_1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживании будет 2\mu . Аналогично суммарный поток обслуживании, переводящий СМО из состояния S_3 (три канала заняты) в S_2 , будет иметь интенсивность 3\mu , т.е. может освободиться любой из трех каналов и т.д.

В формуле (16) для схемы гибели и размножения получим для предельной вероятности состояния

P_0={\left(1+ \frac{\lambda}{\mu}+ \frac{\lambda^2}{2!\mu^2}+\ldots+\frac{\lambda^k}{k!\mu^k}+\ldots+ \frac{\lambda^n}{n!\mu^n}\right)\!}^{-1},

где члены разложения \frac{\lambda}{\mu},\,\frac{\lambda^2}{2!\mu^2},\,\ldots,\,\frac{\lambda^k}{k!\mu^k},\,\ldots,\, \frac{\lambda^n}{n!\mu^n} , будут представлять собой коэффициенты при p_0 в выражениях для предельных вероятностей p_1,p_2,\ldots,p_k,\ldots,p_n . Величина

\rho=\frac{\lambda}{\mu}

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

P_0={\left(1+\rho+\frac{\rho^2}{2!}+\ldots+\frac{\rho^k}{k!}+\ldots+\frac{\rho^n}{n!}\right)\!}^{-1},

P_1=\rho\cdot p,\quad p_2=\frac{\rho^2}{2!}\cdot p_0,\quad \ldots,\quad p_k=\frac{\rho^k}{k!}\cdot p_0,\quad \ldots,\quad p_n=\frac{\rho^n}{n!}\cdot p_0.

Формулы (25) и (26) для предельных вероятностей получили названия формул Эрланга в честь основателя теории массового обслуживания.

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

P_{\text{otk}}= \frac{\rho^n}{n!}\cdot p_0.

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

Q=1- P_{\text{otk}}=1-\frac{\rho^n}{n!}\cdot p_0.

Абсолютная пропускная способность:

A=\lambda\cdot Q=\lambda\cdot\left(1-\frac{\rho^n}{n!}\cdot p_0\right)\!.

Среднее число занятых каналов \overline{k} есть математическое ожидание числа занятых каналов:

\overline{k}=\sum_{k=0}^{n}(k\cdot p_k),

где p_k - предельные вероятности состояний, определяемых по формулам (25), (26).

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

\overline{k}=\frac{A}{\mu}

Или, учитывая (29), (24):

\overline{k}=\rho\cdot\left(1-\frac{\rho^n}{n!}\cdot p_0\right)\!.

Пример 6. В условиях примера 5 определить оптимальное число телефонных номеров в телевизионном ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок не менее 90 заявок на переговоры.

Решение. Интенсивность нагрузки канала по формуле (25) \rho=\frac{90}{30}=3 , т.е. за время среднего (по продолжительности) телефонного разговора \overline{t}_{\text{ob.}}=2 мин. поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) n=2,3,4,\ldots и определим по формулам (25), (28), (29) для получаемой n-канальной СМО характеристики обслуживания. Например, при n=2 имеем

З_0={\left(1+3+ \frac{3^2}{2!}\right)\!}^{-1}=0,\!118\approx0,\!12;\quad Q=1-\frac{3^2}{2!}\cdot0,\!118=0,\!471\approx0,\!47;\quad A=90\cdot0,\!471=42,\!4 и т.д.

Значение характеристик СМО сведем в табл. 1.

По условию оптимальности Q\geqslant0,\!9 , следовательно, в телевизионном ателье необходимо установить 5 телефонных номеров (в этом случае Q=0,\!9 - см. табл. 1). При этом в час будут обслуживаться в среднем 80 заявок (A=80,\!1) , а среднее число занятых телефонных номеров (каналов) по формуле (30) \overline{k}=\frac{80,\!1}{30}=2,\!67 .

Пример 7. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр. Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра.

Решение. По условию n=3,~\lambda=0,\!25 (1/ч), \overline{t}_{\text{ob.}} =3 (ч). Интенсивность потока обслуживании \mu=\frac{1}{\overline{t}_{\text{ob.}}}=\frac{1}{3}=0,\!33 . Интенсивность нагрузки ЭВМ по формуле (24) \rho=\frac{0,\!25}{0,\!33}=0,\!75 . Найдем предельные вероятности состояний:

– по формуле (25) p_0={\left(1+0,\!75+ \frac{0,\!75^2}{2!}+ \frac{0,\!75^3}{3!}\right)\!}^{-1}=0,\!476 ;

– по формуле (26) p_1=0,!75\cdot0,\!476=0,\!357;~p_2=\frac{0,\!75^2}{2!}\cdot0,\!476=0,\!134;~p_3=\frac{0,\!75^3}{3!}\cdot0,\!476=0,\!033 ;

т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).

Вероятность отказа (когда заняты все три ЭВМ), таким образом, P_{\text{otk}}=p_3=0,\!033 .

По формуле (28) относительная пропускная способность центра Q=1-0,\!033=0,\!967 , т.е. в среднем из каждых 100 заявок вычислительный центр обслуживает 96,7 заявок.

По формуле (29) абсолютная пропускная способность центра A=0,\!25\cdot0,\!967=0,\!242 , т.е. в один час в среднем обслуживается. 0,242 заявки.

По формуле (30) среднее число занятых ЭВМ \overline{k}=\frac{0,\!242}{0,\!33}=0,\!725 , т.е. каждая из трех ЭВМ будет занята обслуживанием заявок в среднем лишь на \frac{72,\!5}{3}= 24,\!2%. .

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

В вашем браузере отключен Javascript.
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!

Задача 1. На диспетчерский пульт поступает поток заявок, который является потоком Эрланга второго порядка. Интенсивность потока заявок равна 6 заявок в час. Если диспетчер в случайный момент оставляет пульт, то при первой же очередной заявке он обязан вернуться к пульту. Найти плотность распределения времени ожидания очередной заявки и построить ее график. Вычислить вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут. Решение . Поскольку поток Эрланга второго порядка является стационарным потоком с ограниченным последействием, то для него справедлива формула Пальма

где f1(θ)- плотность распределения вероятностей для времени ожидания первого ближайшего события;
λ - интенсивность потока;
- порядок потока;
(θ) - функция распределения вероятностей для времени между двумя соседними событиями потока Эрланга - го порядка (Э).
Известно, что функция распределения для потока Э имеет вид

. (2)

По условиям задачи поток заявок является Эрланговским порядка =2. Тогда из (1) и (2) получим
.
Из последнего соотношения при λ=6 будем иметь

f1(θ)=3е-6θ(1+6 θ), θ≥0. (3)

Построим график функции f1(θ) . При θ <0 имеем f1(θ) =0 . При θ =0 , f1(0)=3 . Рассмотрим предел

При вычислении предела для раскрытия неопределенности типа использовано правило Лопиталя . По результатам исследований строим график функции f1(θ) (Рис. 1).

Обратим внимание на размерности времени в тексте задачи: для интенсивности это заявки в час, для времени-минуты. Перейдем к одним единицам времени: 10 мин=1/6 час, 20 мин=1/3 час. Для этих значений можно вычислить f1(θ) и уточнить характер кривой

Эти ординаты указаны на графике над соответствующими точками кривой.
Из курса теории вероятностей известно, что вероятность попадания случайной величины Х в отрезок [α, β] численно равна площади под кривой плотности распределения вероятностей f(х) . Эта площадь выражается определенным интегралом

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

Этот интеграл легко вычисляется по частям, если положить
U=1+6θ и dV=е-6θ dθ . Тогда dU=6 dθ и V= .
Используя формулу получим

Ответ: вероятность того, что диспетчер сможет отсутствовать от 10 до 20 минут равна 0,28.

Задача 2. Дисплейный зал имеет 5 дисплеев. Поток пользователей простейший. Среднее число пользователей, посещающих дисплейный зал за сутки, равно 140. Время обработки информации одним пользователем на одном дисплее распределено по показательному закону и составляет в среднем 40 минут. Определить, существует ли стационарный режим работы зала; вероятность того, что пользователь застанет все дисплеи занятыми; среднее число пользователей в дисплейном зале; среднее число пользователей в очереди; среднее время ожидания свободного дисплея; среднее время пребывания пользователя в дисплейном зале. Решение. Рассматриваемая в задаче СМО относится к классу многоканальных систем с неограниченной очередью. Число каналов =5. Найдем λ-интенсивность потока заявок: где (час.) - среднее время между двумя последовательными заявками входящего потока пользователей. Тогда польз./час.

Найдем -интенсивность потока обслуживания: , где М[Т обсл.]=40 мин=0,67 часа - среднее время обслуживания одного пользователя одним дисплеем,

тогда польз/час.

Таким образом, классификатор данной системы имеет вид СМО (5, ∞; 5,85; 1,49).
Вычислим коэффициент загрузки СМО . Известно, что для СМО такого класса стационарный режим существует, если отношение коэффициента загрузки системы к числу каналов меньше единицы. Находим это отношение
.
Следовательно, стационарный режим существует. Предельное распределение вероятностей состояний вычисляется по формулам

Поскольку =5, имеем

Вычислим Р*- вероятность того, что пользователь застанет все дисплеи занятыми. Очевидно, она равна сумме вероятностей таких событий: все дисплеи заняты, очереди нет (р5); все дисплеи заняты, один пользователь в очереди (р6); все дисплеи заняты, два пользователя в очереди (р7) и так далее. Поскольку для полной группы событий сумма вероятностей этих событий равна единице, то справедливо равенство

Р*=р5+р6+р7+…=1 - ро - р1 - р2 - р3 - р4.

Найдем эти вероятности: ро =0,014; р1 =3,93*0,014; р2 =7,72*0,014; р3 =10,12*0,014; р4 =9,94*0,014.
Вынося за скобки общий множитель, получим
Р*=1-0,0148*(1+3,93+7,72+10,12+9,94)=1-0,014*32,71=1-0,46=0,54.
Используя формулы для вычисления показателей эффективности? найдем:

• 1. среднее число пользователей в очереди

2. среднее число пользователей в дисплейном зале

3. среднее время ожидания свободного дисплея

4. среднее время пребывания пользователя в дисплейном зале

Ответ: стационарный режим работы дисплейного зала существует и характеризуется следующими показателями Р* =0,54; пользователя; пользователя; ; .

Задача 3. В двухканальную систему массового обслуживания (СМО) с отказами поступает стационарный пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону с параметром λ=5 заявок в минуту. Длительность обслуживания каждой заявки равна 0,5 мин. Методом Монте-Карло найти среднее число обслуженных заявок за время 4 мин. Указание: провести три испытания. Решение. Изобразим статистическое моделирование работы заданной СМО с помощью временных диаграмм. Введем следующие обозначения для временных осей:
Вх -входящий поток заявок, здесь ti -моменты поступления заявок; Ti -интервалы времени между двумя последовательными заявками. Очевидно, что ti =ti -1 +Т i .
К1-первый канал обслуживания;
К2-второй канал обслуживания; здесь жирные линии на временной оси обозначают интервалы занятости канала. Если оба канала свободны, то заявка становится под обслуживание в канал К1, в случае его занятости заявка обслуживается каналом К2.
Если заняты оба канала, то заявка покидает СМО необслуженной.
Вых ОБ-выходящий поток обслуженных заявок.
Вых ПТ-выходящий поток потерянных заявок за счет отказов СМО (случай занятости обоих каналов).
Статистические испытания продолжаются в течение временного интервала . Очевидно, что любое превышение времени tmax влечет за собой сброс заявки в выходящий поток Вых ПТ. Так на рис. 3 заявка №10, пришедшая в систему в момент t10 , не успевает обслужиться до момента tmax , так как t10+Тобсл.>tmax . Следовательно, она не принимается свободным каналом К1 на обслуживание и сбрасывается в Вых ПТ, получая отказ.

Рис. 3

Из временных диаграмм видно, что необходимо научиться моделировать интервалы Т i . Применим метод обратных функций. Поскольку случайная величина Тi распределена по показательному закону с параметром λ =5, то плотность распределения имеет вид f (τ)=5е-5τ . Тогда значение F(Ti) функции распределения вероятностей определяется интегралом

.

Известно, что область значений функции распределения F (T ) есть отрезок . Выбираем из таблицы случайных чисел число и определяем Т i из равенства , откуда . Однако, если . Поэтому можно сразу получать из таблицы случайных чисел реализации . Следовательно,
е-5Т i = ri , или –5Т i = lnri , откуда . Результаты вычислений удобно заносить в таблицу.
Для проведения испытания №1 были взяты случайные числа из приложения 2, начиная с первого числа первой строки. Далее выборка осуществлялась по строкам. Проведем еще два испытания.
Обратите внимание на выборку случайных чисел из таблицы приложения 2, если в испытании №1 последнее случайное число для заявки №16 было 0,37 (первое случайное число во второй строке), то испытание №2 начинается со следующего за ним случайного числа 0,54. Испытание №2 содержит последним случайное число 0,53 (пятое число в третьей строке). Следовательно, третье испытание начнется с числа 0,19. Вообще в пределах одной серии испытаний случайные числа из таблицы выбираются без пропусков и вставок по определенному порядку, например, по строкам.

Таблица 1. ИСПЫТАНИЕ №1

№ зая-вки i	Сл. число ri		-ln ri Тi	Момент поступления заявки ti=ti-1+Ti	Момент окончания обслужив. ti+0,50		Счетчик заявок
					К1

Таблица 2 ИСПЫТАНИЕ №2

№ зая-вки i	Сл. число ri		-ln ri Т i	Момент поступления заявки ti=ti-1+Ti	Момент окончания обслужив. ti+0,50		Счетчик заявок

Таблица №3 ИСПЫТАНИЕ №3

№ зая-вки i		Сл. число ri		-ln ri Т i	Момент поступления заявки ti=ti-1+Ti	Момент окончания обслужив. ti+0,50		Счетчик заявок
						К1

Таким образом, по результатам трех испытаний число обслуженных заявок составило соответственно: х1 =9, х2 =9, х3 =8. Найдем среднее число обслуженных заявок:

Ответ: среднее число заявок, обслуженных СМО за 4 минуты, равно 8,6(6).

Примеры решения задач систем массового обслуживания

Требуется решить задачи 1–3. Исходные данные приведены в табл. 2–4.

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

n – число каналов в СМО;

λ – интенсивность входящего потока заявок П вх;

v – интенсивность выходящего потока заявок П вых;

μ – интенсивность потока обслуживания П об;

ρ – показатель нагрузки системы (трафик);

m – максимальное число мест в очереди, ограничивающее длину очереди заявок;

i – число источников заявок;

p к – вероятность k-го состояния системы;

p о – вероятность простаивания всей системы, т. е. вероятность того, что все каналы свободны;

p сист – вероятность принятия заявки в систему;

p отк – вероятность отказа заявке в принятии ее в систему;

р об – вероятность того, что заявка будет обслужена;

А – абсолютная пропускная способность системы;

Q – относительная пропускная способность системы;

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

Об – среднее число заявок под обслуживанием;

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

Оч – среднее время ожидания заявки в очереди;

Об – среднее время обслуживания заявки, относящееся только к обслуженным заявкам;

Сис – среднее время пребывания заявки в системе;

Ож – среднее время, ограничивающее ожидание заявки в очереди;

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

Абсолютная пропускная способность СМО А – среднее число заявок, которое может обслужить система за единицу времени.

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

При решении задач массового обслуживания необходимо придерживаться нижеприведенной последовательности:

1) определение типа СМО по табл. 4.1;

2) выбор формул в соответствии с типом СМО;

3) решение задачи;

4) формулирование выводов по задаче.

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

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

Граф состояний для схемы гибели и размножения имеет вид, показанный на рис. 19.1. Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S 1 , S 2 ,…,S n-1) связано прямой и обратной стрелкой с каждым из соседних состояний - правым и левым, а крайние состояния (S 0 , S n) - только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

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

Пользуясь графом рис. 19.1, составим и решим алгебраические уравнения для финальных вероятностей состоянии), существование вытекает из того, что из каждого состояния можно перейти в каждое другое, в число состояний конечно). Для первого состояния S 0 имеем:

(19.1)

Для второго состояния S 1:

В силу (19.1) последнее равенство приводится к виду

где k принимает все значения от 0 до п. Итак, финальные вероятности p 0 , p 1 , ..., р n удовлетворяют уравнениям

(19.2)

кроме того, надо учесть нормировочное условие

p 0 + p 1 + p 2 +…+ p n =1. (19.3)

Решим эту систему уравнений. Из первого уравнения (19.2)выразим p 1 через р 0 :

p 1 = p 0. (19.4)

Из второго, с учетом (19.4), получим:

(19.5)

Из третьего, с учетом (19.5),

(19.6)

и вообще, для любого k (от 1 до n ):

(19.7)

Обратим внимание на формулу (19.7). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния S k), а в знаменателе - произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до S k).

Таким образом, все вероятности состояний р 0 , p 1 , ..., р n выражены через одну из них (р 0). Подставим эти выражения в нормировочное условие (19.3). Получим, вынося за скобку р 0:

отсюда получим выражение для р 0 :

(скобку мы возвели в степень -1, чтобы не писать двухэтажных дробей). Все остальные вероятности выражены через р 0 (см. формулы (19.4) - (19.7)). Заметим, что коэффициенты при р 0 в каждой из них представляют собой не что иное, как последовательные члены ряда, стоящего после единицы в формуле (19.8). Значит, вычисляя р 0 , мы уже нашли все эти коэффициенты.

Полученные формулы очень полезны при решении простейших задач теории массового обслуживания.

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

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

Обозначим: X(t} - число заявок, прибывших в СМО до момента t. Y (t ) - число заявок покинувших СМО

до момента t. И та, и другая функции являются случайными и меняются скачком (увеличиваются на единицу) в моменты приходов заявок (X (t )) и уходов заявок (Y(t)). Вид функций X(t) и Y(t) показан на рис. 19.2; обе линии - ступенчатые, верхняя - X(t), нижняя-Y(t). Очевидно, что для любого момента t их разность Z (t ) = X(t) - Y(t) есть не что иное, как число заявок, находящихся в СМО. Когда линии X(t) и Y(t) сливаются, в системе нет заявок.

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

L сист. = . (19.9) о

Но этот интеграл представляет собой не что иное, как площадь фигуры, заштрихованной на рис. 19.2. Разглядим хорошенько этот рисунок. Фигура состоит из прямоугольников, каждый из которых имеет высоту, равную единице, и основание, равное времени пребывания в системе соответствующей заявки (первой, второй и т. д.). Обозначим эти времена t 1 , t 2 ,... Правда, под конец промежутка Т некоторые прямоугольники войдут в заштрихованную фигуру не полностью, а частично, но при достаточно большом Т эти мелочи не будут играть роли. Таким образом, можно считать, что

(19.10)

где сумма распространяется на все заявки, пришедшие за время Т.

Разделим правую и левую часть (.19.10) на длину интервала Т. Получим, с учетом (19.9),

L сист. = . (19.11)

Разделим и умножим правую часть (19.11) на интенсивность X:

L сист. = .

Но величина Тλ есть не что иное, как среднее число заявок, пришедших за время ^ Т. Если мы разделим сумму всех времен t i на среднее число заявок, то получим среднее время пребывания заявки в системе W сист. Итак,

L сист. = λW сист. ,

W сист. = . (19.12)

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

Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди ^ W оч и среднее число заявок в очереди L оч:

W оч = . (19.13)

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

Формулы Литтла (19.12) и (19.13) играют большую роль в теории массового обслуживания. К сожалению, в большинстве существующих руководств эти формулы (доказанные в общем виде сравнительно недавно) не приводятся 1).

§ 20. Простейшие системы массового обслуживания и их характеристики

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

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

1) В популярной книжке дан несколько иной, по сравнению с вышеизложенным, вывод формулы Литтла. Вообще, знакомство с этой книжкой («Беседа вторая») полезно для первоначального ознакомления с теорией массового обслуживания.

В данном параграфе показательное распределение времени обслуживания будет само собой разуметься, как всегда для «простейшей» системы.

Характеристики эффективности рассматриваемых СМО мы будем вводить по ходу изложения.

^ 1. п -канальная СМО с отказами (задача Эрланга). Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания;

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

^ А - абсолютную пропускную способность, т. е. среднее число заявок, обслуживаемых в единицу времени;

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

^ Р отк - вероятность отказа, т. е. того, что заявка покинет СМО не обслуженной;

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

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

S 0 - в СМО нет ни одной заявки,

S 1 - в СМО находится одна заявка (один канал занят, остальные свободны),

S k - в СМО находится k заявок (k каналов заняты, остальные свободны),

S n - в СМО находится п заявок (все n каналов заняты).

Граф состояний СМО соответствует схеме гибели в размножения (рис. 20.1). Разметим этот граф - проставим у стрелок интенсивности потоков событий. Из S 0 в S 1 систему переводит поток заявок с интенсивностью λ (как только приходит заявка, система перескакивает из S 0 в S 1). Тот же поток заявок переводит

Систему из любого левого состояния в соседнее правое (см. верхние стрелки на рис. 20.1).

Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии ^ S 1 (работает один канал). Он производит μ обслуживании в единицу времени. Проставляем у стрелки S 1 → S 0 интенсивность μ. Теперь представим себе, что система находится в состоянии S 2 (работают два канала). Чтобы ей перейти в S 1 , нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживании равна 2μ; проставляем ее у соответствующей стрелки. Суммарный поток обслуживании, даваемый тремя каналами, имеет интенсивность 3μ, k каналами - kμ. Проставляем эти интенсивности у нижних стрелок на рис. 20.1.

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

Члены разложения будут представлять собой коэффициенты при р 0 в выражениях для p 1

Заметим, что в формулы (20.1), (20.2) интенсивности λ и μ входят не по отдельности, а только в виде отношения λ/μ. Обозначим

λ/μ = ρ (20.3)

И будем называть величину р «приведенной интенсивностью потока заявок». Ее смысл-среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:

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

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

Р отк = р n = . (20.6)

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

Q = 1 – P отк. = 1 - (20.7)

Абсолютную пропускную способность получим, умножая интенсивность потока заявок λ, на Q:

A = λQ = λ . (20.8)

Осталось только найти среднее число занятых каналов k. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями 0, 1, ..., п и вероятностями этих значений р 0 р 1 , ..., р n:

k = 0 · р 0 + 1 · p 1 + 2 · р 2 + ... + п · р n .

Подставляя сюда выражения (20.5) для р k , (k = 0, 1, ..., п) и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для k. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это - не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый i .шал в единицу времени обслуживает в среднем |л заявок. Значит, среднее число занятых каналов равно

k = A/μ, (20.9)

или, учитывая (20.8),

k = (20.10)

Рекомендуем читателю самостоятельно решить пример. Имеется станция связи с тремя каналами (n = 3), интенсивность потока заявок λ = 1,5 (заявки в минуту); среднее время обслуживания одной заявки t об = 2 (мин.), все потоки событий (как и во всем этом параграфе) - простейшие. Найти финальные вероятности состояний и характеристики эффективности СМО: А, Q, P отк, k. На всякий случай сообщаем ответы: p 0 = 1/13, p 1 = 3/13, p 2 = 9/26, р 3 = 9/26 ≈ 0,346,

А ≈ 0,981, Q ≈ 0,654, P отк ≈ 0,346, k ≈ 1,96.

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

Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же «неленивому и любопытному читателю» придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.

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

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

L сист. - среднее число заявок в системе,

W сист. - среднее время пребывания заявки в системе,

^ L оч - среднее число заявок в очереди,

W оч - среднее время пребывания заявки в очереди,

P зан - вероятность того, что канал занят (степень загрузки канала).

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности:

в силу того, что очередь неограниченна, каждая заявка рано или поздно будет обслужена, поэтому А = λ, по той же причине Q = 1.

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

S 0 - канал свободен,

S 1 - канал занят (обслуживает заявку), очереди нет,

S 2 - канал занят, одна заявка стоит в очереди,

S k - канал занят, k - 1 заявок стоят в очереди,

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

Прежде всего спросим себя, а существуют ли в этом случае финальные вероятности? Ведь число состояний системы бесконечно, и, в принципе, при t → ∞ очередь может неограниченно возрастать! Да, так оно и есть: финальные вероятности для такой СМО существуют не всегда, а только когда система не перегружена. Можно доказать, что если ρ строго меньше единицы (ρ< 1), то финальные вероятности существуют, а при ρ ≥ 1 очередь при t → ∞ растет неограниченно. Особенно «непонятным» кажется этот факт при ρ = 1. Казалось бы, к системе не предъявляется невыполнимых требований: за время обслуживания одной заявки приходит в среднем одна заявка, и все должно быть в порядке, а вот на деле - не так. При ρ = 1 СМО справляется с потоком заявок, только если поток этот - регулярен, и время обслуживания - тоже не случайное, равное интервалу между заявками. В этом «идеальном» случае очереди в СМО вообще не будет, канал будет непрерывно занят и будет регулярно выпускать обслуженные заявки. Но стоит только потоку заявок или потоку обслуживании стать хотя бы чуточку случайными - и очередь уже будет расти до бесконечности. На практике этого не происходит только потому, что «бесконечное число заявок в очереди» - абстракция. Вот к каким грубым ошибкам может привести замена случайных величин их математическими ожиданиями!

Но вернемся к нашей одноканальной СМО с неограниченной очередью. Строго говоря, формулы для финальных вероятностей в схеме гибели и размножения выводились нами только для случая конечного числа состояний, но позволим себе вольность - воспользуемся ими и для бесконечного числа состояний. Подсчитаем финальные вероятности состояний по формулам (19.8), (19.7). В нашем случае число слагаемых в формуле (19.8) будет бесконечным. Получим выражение для р 0:

p 0 = -1 =

= (1 + р + р 2 + ... + р k +… .) -1 . (20.11)

Ряд в формуле (20.11) представляет собой геометрическую прогрессию. Мы знаем, что при ρ < 1 ряд сходится - это бесконечно убывающая геометрическая прогрессия со знаменателем р. При р ≥ 1 ряд расходится (что является косвенным, хотя и не строгим доказательством того, что финальные вероятности состояний р 0 , p 1 , ..., p k , ... существуют только при р<1). Теперь предположим, что это условие выполнено, и ρ <1. Суммируя прогрессию в (20.11), имеем

1 + ρ + ρ 2 + ... + ρ k + ... = ,

p 0 = 1 - ρ. (20.12)

Вероятности р 1 , р 2 , ..., р k , ... найдутся по формулам:

p 1 = ρp 0 , p 2 = ρ 2 p 0 ,…,p k = ρp 0 , ...,

Откуда, с учетом (20.12), найдем окончательно:

p 1 = ρ (1 - ρ), p 2 = ρ 2 (1 - ρ), . . . , p k = ρ k (1 - ρ), . . .(20.13)

Как видно, вероятности p 0 , p 1 , ..., p k , ... образуют геометрическую прогрессию со знаменателем р. Как это ни странно, максимальная из них р 0 - вероятность того, что канал будет вообще свободен. Как бы ни была нагружена система с очередью, если только она вообще справляется с потоком заявок (ρ<1), самое вероятное число заявок в системе будет 0.

Найдем среднее число заявок в СМО ^ L сист . . Тут придется немного повозиться. Случайная величина Z - число заявок в системе - имеет возможные значения 0, 1, 2, .... k, ... с вероятностями p 0 , р 1 , р 2 , ..., p k , ... Ее математическое ожидание равно

L сист = 0 · p 0 + 1 · p 1 + 2 · p 2 +…+k · p k +…= (20.14)

(сумма берется не от 0 до ∞, а от 1 до ∞, так как нулевой член равен нулю).

Подставим в формулу (20.14) выражение для p k (20.13):

L сист. =

Теперь вынесем за знак суммы ρ (1-ρ):

L сист. = ρ (1-ρ)

Тут мы опять применим «маленькую хитрость»: k ρ k -1 есть не что иное, как производная по ρ от выражения ρ k ; значит,

L сист. = ρ (1-ρ)

Меняя местами операции дифференцирования п суммирования, получим:

L сист. = ρ (1-ρ) (20.15)

Но сумма в формуле (20.15) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом ρ и знаменателем ρ; эта сумма

равна , а ее производная .Подставляя это выражение в (20.15), получим:

L сист = . (20.16)

Ну, а теперь применим формулу Литтла (19.12) и найдем среднее время пребывания заявки в системе:

W сист = (20.17)

Найдем среднее число заявок в очереди L оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L оч равно среднему числу заявок в системе L сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (если канал свободен), либо единицей (если он занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (мы ее обозначили Р зан). Очевидно, Р зан равно единице минус вероятность р 0 того, что канал свободен:

Р зан = 1 - р 0 = ρ. (20.18)

Следовательно, среднее число заявок под обслуживанием равно

^ L об = ρ, (20.19)

L оч = L сист – ρ =

и окончательно

L оч = (20.20)

По формуле Литтла (19.13) найдем среднее время пребывания заявки в очереди:

(20.21)

Таким образом, все характеристики эффективности СМО найдены.

Предложим читателю самостоятельно решить пример: одноканальная СМО представляет собой железнодорожную сортировочную станцию, на которую поступает простейший поток составов с интенсивностью λ = 2 (состава в час). Обслуживание (расформирование)

состава длится случайное (показательное) время со средним значением t об = 20 (мин.). В парке прибытия станции имеются два пути, на которых могут ожидать обслуживания прибывающие составы; если оба пути заняты, составы вынуждены ждать на внешних путях. Требуется найти (для предельного, стационарного режима работы станции): среднее, число составов l сист, связанных со станцией, среднее время W сист пребывания состава при станции (на внутренних путях, на внешних путях и под обслуживанием), среднее число L оч составов, ожидающих очереди на расформирование (все равно, на каких путях), среднее время W оч пребывания состава на очереди. Кроме того, попытайтесь найти среднее число составов, ожидающих расформирования на внешних путях L внеш и среднее время этого ожидания W внеш (две последние величины связаны формулой Литтла). Наконец, найдите суммарный суточный штраф Ш, который придется заплатить станции за простои составов на внешних путях, если за один час простоя одного состава станция платит штраф а (руб.). На всякий случай сообщаем ответы: L сист. = 2 (состава), W сист. = 1 (час), L оч = 4/3 (состава), W оч = 2/3 (часа), L внеш = 16/27 (состава), W внеш = 8/27 ≈ 0,297 (часа). Средний суточный штраф Ш за ожидание составов на внешних путях получим, перемножая среднее число составов, прибывающих на станцию за сутки, среднее время ожидания состава на внешних путях и часовой штраф а : Ш ≈ 14,2а .

^ 3. re-канальная СМО с неограниченной очередью. Совершенно аналогично задаче 2, но чуточку более сложно, решается задача об n -канальной СМО с неограниченной очередью. Нумерация состояний - опять по числу заявок, находящихся в системе:

S 0 - в СМО заявок нет (все каналы свободны),

S 1 - занят один канал, остальные свободны,

S 2 - занято два канала, остальные свободны,

S k - занято k каналов, остальные свободны,

S n - заняты все п каналов (очереди нет),

S n+1 - заняты все n каналов, одна заявка стоит в очереди,

S n+r - заняты вес п каналов, r заявок стоит в очереди,

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

λ λ λ λ λ λ λ λ λ

μ 2μ kμ (k+1)μ nμ nμ nμ nμ nμ

есть схема гибели и размножения, но с бесконечным числом состояний. Сообщим без доказательства естественное условие существования финальных вероятностей: ρ/n <1. Если ρ/n ≥ 1, очередь растет до бесконечности.

Предположим, что условие ρ/n < 1 выполнено, и финальные вероятности существуют. Применяя все те же формулы (19.8), (19.7) для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для р 0 будет стоять ряд членов, содержащих факториалы, плюс сумма бесконечно убывающей геометрической прогрессии со знаменателем ρ/n . Суммируя ее, найдем

(20.22)

Теперь найдем характеристики эффективности СМО. Из них легче всего находится среднее число занятых каналов k == λ/μ, = ρ (это вообще справедливо для любой СМО с неограниченной очередью). Найдем среднее число заявок в системе L сист и среднее число заявок в очереди L оч. Из них легче вычислить второе, по формуле

L оч =

выполняя соответствующие преобразования по образцу задачи 2

(с дифференцированием ряда), получим:

L оч = (20.23)

Прибавляя к нему среднее число заявок под обслуживанием (оно же - среднее число занятых каналов) k = ρ, получим:

L сист = L оч + ρ. (20.24)

Деля выражения для L оч и L сист на λ, по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:

(20.25)

А теперь решим любопытный пример. Железнодорожная касса по продаже билетов с двумя окошками представляет собой двухканальную СМО с неограниченной очередью, устанавливающейся сразу к двум окошкам (если одно окошко освобождается, ближайший в очереди пассажир его занимает). Касса продает билеты в два пункта: А и В. Интенсивность потока заявок (пассажиров, желающих купить билет) для обоих пунктов А и В одинакова: λ А = λ В = 0,45 (пассажира в минуту), а в сумме они образуют общий поток заявок с интенсивностью λ А + λ В = 0,9. Кассир тратит на обслуживание пассажира в среднем две минуты. Опыт показывает, что у кассы скапливаются очереди, пассажиры жалуются на медленность обслуживания, Поступило рационализаторское предложение: вместо одной кассы, продающей билеты и в А и в В, создать две специализированные кассы (по одному окошку в каждой), продающие билеты одна - только в пункт А , другая - только в пункт В. Разумность этого предложения вызывает споры - кое-кто утверждает, что очереди останутся прежними. Требуется проверить полезность предложения расчетом. Так как мы умеем считать характеристики только для простейших СМО, допустим, что все потоки событий - простейшие (на качественной стороне выводов это не скажется).

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

Вариант I (существующий). На двухканальную СМО поступает поток заявок с интенсивностью λ = 0,9; интенсивность потока обслуживании μ = 1/2 = 0,5; ρ = λ/μ = l,8. Так как ρ/2 = 0,9<1, финальные вероятности существуют. По первой формуле (20.22) находим р 0 ≈ 0,0525. Среднее, число заявок в очереди находим по формуле (20.23): L оч ≈ 7,68; среднее время, проводимое заявкой в очереди (по первой из формул (20.25)), равно W оч ≈ 8,54 (мин.).

Вариант II (предлагаемый). Надо рассмотреть две одноканальные СМО (два специализированных окошка); на каждую поступает поток заявок с интенсивностью λ = 0,45; μ. по-прежнему равно 0,5; ρ = λ/μ = 0,9<1; финальные вероятности существуют. По формуле (20.20) находим среднюю длину очереди (к одному окошку) L оч = 8,1.

Вот тебе и раз! Длина очереди, оказывается, не только не уменьшилась, а увеличилась! Может быть, уменьшилось среднее время ожидания в очереди? Посмотрим. Деля L оч на λ = 0,45, получим W оч ≈ 18 (минут).

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

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

Ну, ладно,- готов согласиться читатель,- увеличение можно объяснить, но почему оно такое существенное? Нет ли тут ошибки в расчете?

И на этот вопрос мы ответим. Ошибки нет. Дело в том, что в нашем примере обе СМО работают на пределе своих возможностей; стоит немного увеличить время обслуживания (т. е. уменьшить μ), как они уже перестанут справляться с потоком пассажиров, и очередь начнет неограниченно возрастать. А «лишние простои» кассира в каком-то смысле равносильны уменьшению его производительности μ.

Таким образом, кажущийся сначала парадоксальным (или даже просто неверным) результат вычислений оказывается на поверку правильным и объяснимым.

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

Размышляя над последней задачей, читатель может поставить вопрос так: ведь если касса продает билеты только в один пункт, то, естественно, время обслуживания должно уменьшиться, ну, не вдвое, а хоть сколько-нибудь, а мы считали, что оно по-прежнему в среднем равно 2 (мин.). Предлагаем такому придирчивому читателю ответить на вопрос: а насколько надо его уменьшить, чтобы «рационализаторское предложение» стало выгодным? Снова мы встречаемся хотя и с элементарной, но все же задачей оптимизации. С помощью ориентировочных расчетов даже на самых простых, марковских моделях удается прояснить качественную сторону явления - как выгодно поступать, а как - невыгодно. В следующем параграфе мы познакомимся с некоторыми элементарными немарковскими моделями, которые еще расширят наши возможности.

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

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

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

^ 5. Замкнутая СМО с одним каналом и m источниками заявок. Для конкретности поставим задачу в следующей форме: один рабочий обслуживает т станков, каждый из которых время от времени требует наладки (исправления). Интенсивность потока требований каждого работающего станка равна λ. Если станок вышел из строя в момент, когда рабочий свободен, он сразу же поступает на обслуживание. Если он вышел из строя в момент, когда рабочий занят, он становится в очередь и ждет, пока рабочий освободится. Среднее время наладки станка t об = 1/μ. Интенсивность потока заявок, поступающих к рабочему, зависит от того, сколько станков работает. Если работает k станков, она равна k λ. Найти финальные вероятности состояний, среднее число работающих станков и вероятность того, что рабочий будет занят.

Заметим, что и в этой СМО финальные вероятности

будут существовать при любых значениях λ и μ = 1/t об, так как число состояний системы конечно.

Поток заявок явл пуассоновским, если выполняются 3 условия:

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

Рассмотрим некоторые свойства (виды) потоков событий.

Поток событий называется стационарным , если его вероятностные характеристики не зависят от времени.

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

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

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

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

Вероятность события (приход заявки) на малом интервале времени пропорциональна длине этого интервала.

Вер-ть 2 событий на малом интервале пренебрежимо мала.

Вер-ть поступления заявки не зависит от предыдущих событий.

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

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

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

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

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

простейшую СМО с ожиданием - одноканальная система в которую поступает поток заявок с с опр интенсивностью Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

Условия в реальном объекте, необходимые для использования МКУ для их представления в модели:

Объекты должны иметь одинаковую функцию распределения времени обслуживания

Одинаковые параметры этой функции.

В отличие от прибора, емкость кот всегда равна единице, емкость МКУ д.б. определена программистом. Для этого применяется специ­альная команда STORAGE (ОПРЕДЕЛИТЬ МКУ).

ИмяКоманды STORAGE A

Поле ИмяКоманды - символьное имя МКУ, а поле А - его емкость (количество каналов обслуживания), операнд А м.б. задан только в виде положительного целого числа.

Пр: MKU1 STORAGE 5 TRAKT STORAGE 30 (емкость МКУ с именем MKU1 определена равной 5, МКУ с именем TRAKT - 30).

Событие, связанное с занятием каналов обслуживания, моделируется бло­ком ENTER (ВОЙТИ), а событие, состоящее в освобождении каналов, - блоком LEAVE (ВЫЙТИ).

А – имя МКУ. В – кол-во единиц емкости МКУ, кот должен занять (освободить) транзакт. По умолч =1.

Пр: 1) ENTER BLOK3 (войти в МКУ с именем BLOK3);

2)LEAVE SEANS,3 (освободить 3 единицы емкости МКУ с именем SEANS).

Между блоками ENTER и LEAVE может находиться любое кол-во бло­ков. В частности, задержка на время обслуживания в МКУ имитируется при помощи блока ADVANCE.

Если кол-во единиц емкости, заданных операндом В блока LEAVE, превышает кол-во занятых в данный момент времени каналов МКУ, интерпретатор останавливает моделирование и выдает сообщение об ошибке.

В отношении транзактов, ожидающих занятия МКУ, действует правило «первый соответствующий с пропусками».

При входе транзакта в блок LEAVE интерпретатор приостанавливает его продвижение, позволяя очередному транзакту из цепи задержки этого МКУ войти в блок ENTER, и только после этого продвигает вышедший из МКУ транзакт в модели. Транзакт, вышедший из цепи задержки МКУ, пе­реводится в ЦТС и становится в ней последним в своем приоритетном классе.

МКУ имеют следующие СЧА: S - текущее содержимое МКУ; R -свободная емкость МКУ; SR - коэффициент использования в долях 1000; SA - целая часть среднего содержимого МКУ; SM - максимальное содержимое МКУ; SC - число занятий МКУ; ST - целая часть среднего времени занятия МКУ.

Для проектирования одноканальных устройств используют болоки Seize , Release

SEIZE A (занять) - занятие прибора транзактом. А - имя точки входа в устройство.

RELEASE A (освободить) – освобождение прибора транзактом, по истечении времени обслуживания.