Пусть система имеет один канал обслуживания, на который поступает простейший поток заявок с интенсивностью l. Поток обслуживаний имеет интенсивность m. Заявка, заставшая систему занятой, сразу же покидает её.

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

Система при любом t > 0 может находиться в двух состояниях: S 0 – канал свободен; S 1 – канал занят. Переход из S 0 в S 1 связан с появлением заявки и немедленным началом её обслуживания. Переход из состояния S 1 в S 0 осуществляется, как только очередное обслуживание завершится (рис. 4.5).

Рис. 4.5. Граф состояний одноканальной СМО с отказами

(среднее число заявок, обслуживаемых в единицу времени)

Шт/ед. времени,

где l – интенсивность потока заявок (величина, обратная среднему промежутку времени между поступающими заявками ); m – интенсивность потока обслуживаний (величина, обратная среднему времени обслуживания ).

(средняя доля заявок, обслуживаемых системой)

Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной)

Очевидны следующие соотношения: Q = 1 – P отк и P отк = 1 – Q .

Пример. Технологическая система состоит из одного станка. На станок поступают заявки на изготовление деталей в среднем через 0,5 часа ( = 0,5 ч.). Среднее время изготовления одной детали равно = 0,6 ч. Если при поступлении заявки на изготовление детали станок занят, то она (деталь) направляется на другой станок. Найти абсолютную и относительную пропускную способности системы и вероятность отказа по изготовлению детали.

ч –1 ; ч –1 ;

дет/ч; .

Т. е. в среднем примерно 46 % деталей обрабатываются на этом станке.

.

Т. е. в среднем примерно 54 % деталей направляются на обработку на другие станки.

4.4.2. N-канальная СМО с отказами (задача Эрланга)

Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале 20 века датским математиком Эрлангом.

Пусть в системе имеется n каналов, на которые поступает поток заявок с интенсивностью l. Поток обслуживаний имеет интенсивность m. Заявка, заставшая систему занятой, сразу же покидает ее.

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

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

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

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

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

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

Граф состояний СМО представлен на рис. 4.6.

Из состояния S 0 в состояние S 1 систему переводит поток заявок с интенсивностью l (как только приходит заявка, система переходит из S 0 в S 1). Если система находилась в состоянии S 1 и пришла еще одна заявка, то она переходит в состояние S 2 и т. д.

Рис. 4.6. Граф состояний N-канальной СМО с отказами

Пусть система находится в состоянии S 1 (работает один канал). Он производит m обслуживаний в единицу времени. Поэтому дуга перехода из состояния S 1 в состояние S 0 нагружена интенсивностью m. Пусть теперь система находится в состоянии S 2 (работают два канала). Чтобы ей перейти в S 1 , нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равна 2m и т. д.

Выходные характеристики (характеристики эффективности) данной СМО определяются следующим образом.

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

, шт/ед. времени,

где n – количество каналов СМО; р 0 – вероятность нахождения СМО в начальном состоянии, когда все каналы свободны (финальная вероятность нахождения СМО в состоянии S 0).

Для того, чтобы написать формулу для определения р 0 , рассмотрим рис. 4.7. Граф, представленный на рисунке, называют еще графом состояний для схемы «гибели и размножения».

Рис. 4.7. Граф состояний для схемы «гибели и размножения»

S 1 , когда один канал занят

Вероятность того, что СМО находится в состоянии S 2 , т.е. когда два канала заняты

.

Вероятность того, что СМО находится в состоянии S n , т.е. когда все каналы заняты

.

Вероятность нахождения СМО в начальном состоянии р 0

Применительно к n -канальной СМО с отказами

.

При этом ; ; .

Относительная пропускная способность

.

Абсолютная пропускная способность А = lQ .

Вероятность отказа

.

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

.

При этом .

Пример № 1. Имеется технологическая система (участок), состоящая из трех одинаковых станков. В систему поступают для обработки детали в среднем через 0,5 часа (). Среднее время изготовления одной детали = 0,6 ч. Если при поступлении заявки на изготовление детали все станки заняты, то деталь направляется на другой участок таких же станков. Необходимо найти финальные вероятности состояний системы и характеристики (показатели эффективности) данной СМО.

Интенсивность потока заявок

,

т. е. в среднем две заявки на обработку деталей в час.

.

Граф состояний системы представлен на рис. 4.8.

Возможные состояния системы: S 0 – в СМО (на участке) нет ни одной заявки; S 1 – в СМО (на участке) одна заявка; S 2 – в СМО (на участке) две заявки; S 3 – в СМО (на участке) три заявки (заняты все три станка).

Вероятность того, что все станки свободны:

.

Вероятность того, что один станок занят

.

Вероятность того, что два станка заняты

.

Вероятность того, что все три станка заняты

.

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

дет./ч.

Относительная пропускная способность

;

Вероятность отказа

.

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

.

Таким образом, в среднем в этой системе обрабатывается 1,82 дет./ч (примерно 91 % направляемых деталей), при этом примерно 9 % деталей направляется для обработки на другие участки. Одновременно в среднем работает в основном один станок (). Но из-за случайных характеристик потока заявок иногда работают одновременно все три станка (р з = 0,09), отсюда 9 % отказов.

Пример № 2. Пусть , Р отк £ 0,03 (т. е. £ 3 %). Найти оптимальное число каналов n опт, обеспечивающее минимум затрат на систему, при условии достижения требуемого уровня ее безотказной работы.

Целевая функция (затраты на СМО) запишется:

y = cn ® min,

где c – постоянная величина.

; D и расходы на эксплуатацию R . Чтобы решить эту задачу, необходимо найти оптимальное число каналов n опт, обеспечивающее максимум целевой функции P = D – R ® max, т. е. нужно максимизировать прибыль в единицу времени.

Модели управления запасами

Управление запасами – это поддержание оптимальной величины текущего остатка запасов с целью:

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

Обеспечения нормальной ритмичности производственно-финансового цикла.

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

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

Путем однократного создания запаса на весь рассматриваемый период времени;

Посредством создания запаса для каждой единицы времени этого периода.

Эти два случая соответствуют избыточному запасу (по отношению к единице времени) и недостаточному запасу (по отношению к полному периоду времени).

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

При недостаточном запасе удельные капитальные вложения снижаются, но частота размещения заказов и риск дефицита при этом возрастают.

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

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

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!

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

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

Граф состояний СМО в этом случае имеет вид, показанный на рис. 2

Рисунок 5.2 – Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)

Состояния СМО имеют следующую интерпретацию:

S0 - «канал свободен»;

S1 - «канал занят» (очереди нет);

S2 - «канал занят» (одна заявка стоит в очереди);

Sn - «канал занят» (п - 1 заявок стоит в очереди);

SN - «канал занят» (N - 1 заявок стоит в очереди).

Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:

(10)

п - номер состояния.

Решение приведенной выше системы уравнений (10) для на­шей модели СМО имеет вид

(11)

(12)

Следует отметить, что выполнение условия стационарности

для данной СМО не обязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превы­шать N - 1), а не соотношением между интенсивностями входного потока, т. е. не отношением λ/μ=ρ

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N - 1):

вероятность отказа в обслуживании заявки:

(13)

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

(14)

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

среднее число находящихся в системе заявок:

(16)

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

(17)

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

(18)

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

(19)

Рассмотрим пример одноканальной СМО с ожиданием.

Пример 2. Специализированный пост диагностики представ­ляет собой одноканальную СМО. Число стоянок для автомоби­лей, ожидающих проведения диагностики, ограниченно и равно 3[(N - 1) = 3]. Если все стоянки заняты, т. е. в очереди уже нахо­дится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток ав­томобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность λ = 0,85 (автомобиля в час). Вре­мя диагностики автомобиля распределено по показательному зако­ну и в среднем равно 1,05 час.

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

Решение

1. Параметр потока обслуживаний автомобилей:

2. Приведенная интенсивность потока автомобилей определя­ется как отношение интенсивностей λ, и μ, т. е.

3. Вычислим финальные вероятности системы

4. Вероятность отказа в обслуживании автомобиля:

5. Относительная пропускная способность поста диагностики:

6. Абсолютная пропускная способность поста диагностики

(автомобиля в час).

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

8. Среднее время пребывания автомобиля в системе:

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

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

Работу рассмотренного поста диагностики можно считать удов­летворительной, так как пост диагностики не обслуживает автомо­били в среднем в 15,8% случаев (Р отк = 0,158).

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

Стационарный режим функционирования данной СМО суще­ствует при t →∞ оо для любого n = 0, 1, 2, ... и когда λ < μ. Система алгебраических уравнений, описывающих работу СМО при t →∞ для любого n = 0, 1, 2, ... , имеет вид

(20)

Решение данной системы уравнений имеет вид

где ρ = λ/μ < 1.

Характеристики одноканальной СМО с ожиданием, без огра­ничения на длину очереди, следующие:

Среднее число находящихся в системе клиентов (заявок) на обслуживание:

(22)

средняя продолжительность пребывания клиента в системе:

(23)

среднее число клиентов в очереди на обслуживании:

(24)

средняя продолжительность пребывания клиента в очереди:

(25)

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

Требуется определить финальные значения следующих вероят­ностных характеристик:

вероятности состояний системы (поста диагностики);

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

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

Среднее число автомобилей в очереди на обслуживании;

Среднюю продолжительность пребывания автомобиля в очереди.

1. Параметр потока обслуживания μ и приведенная интенсив­ность потока автомобилей ρ определены в примере 2:

μ= 0,952; ρ = 0,893.

2. Вычислим предельные вероятности системы по формулам

Р 0 = 1 - ρ = 1 - 0,893 = 0,107;

Р 1 = (1 - ρ) . ρ = (1 - 0,893)*0,893 = 0,096;

Р 2 = (1 - ρ) . ρ 2 = (1 - 0,893)*0,8932 = 0,085;

Р з = (1 - ρ) . ρ 3 = (1 - 0,893)*0,8933 = 0,076;

Р 4 = (1 - ρ) . ρ 4 = (1 - 0,893)* 0,8934 = 0,068;

Р 5 = (1 - ρ) . ρ 5 = (1 - 0,893)*0,8935 = 0,061 и т. д.

Следует отметить, что Р 0 определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаива­ет). В нашем примере она составляет 10,7%, так как Р 0 = 0,107.

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

4. Средняя продолжительность пребывания клиента в системе:

5. Среднее число автомобилей в очереди на обслуживание:

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

7. Относительная пропускная способность системы:

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

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

А = λ* q = 0,85 * 1 = 0,85.

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

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

m=λ*P N

В нашем примере при N = 3 + 1 = 4 и ρ = 0,893

m=λ*P 0 *ρ 4 =0.85*0.248*0.8934=0.134 автомобиля в час.

При 12-часовом режиме работы поста диагностики это эквива­лентно тому, что пост диагностики в среднем за смену (день) будет терять 12 * 0,134 = 1,6 автомобиля. Снятие ограничения на длину очереди позволяет увеличить ко­личество обслуженных клиентов в нашем при мере в среднем на 1,6 автомобиля за смену (12 ч. работы) поста диагностики. Ясно, что ре­шение относительно расширения площади для стоянки автомоби­лей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей кли­ентов при наличии всего трех мест для стоянки этих автомобилей.

4.4 Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания

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

Процесс массового обслуживания, описываемый данной моде­лью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняет­ся l/μ. Входной и выходной потоки являются пуассоновскими. Ре­жим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих ка­налов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения. Конечная цель исполь­зования n параллельно включенных обслуживающих каналов за­ключается в повышении (по сравнению с одноканальной систе­мой) скорости обслуживания требований за счет обслуживания од­новременно n клиентов.

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

Состояния данной СМО имеют следующую интерпретацию:

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

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

……………………….

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

……………………….

S n - заняты все n каналов, заявка получает отказ в обслужива­нии.

Уравнения Колмогорова для вероятностей состояний системы Р 0 , …, P k ,…, Р n будут иметь следующий вид:

(26)

Начальные условия решения системы таковы:

P 0 (0)=1, P 1 (0)=P 2 (0)=…=P k (0)=…=P n (0)=0.

Стационарное решение системы имеет вид:

(27)

Формулы для вычисления вероятностей P k называются форму­лами Эрланга.

Определим вероятностные характеристики функционирования многоканальной СМО с отказами в стационарном режиме:

Вероятность отказа:

(28)

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

Вероятность того, что заявка будет принята к обслуживанию (она же - относительная пропускная способность системы q) допол­няет Р отк до единицы:

(29)

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

A=λ*q=λ*(1-P отк); (30)

Среднее число каналов, занятых обслуживанием следующее:

(31)

Оно характеризует степень загрузки системы.

Пример 4. Пусть n-канальная СМО представляет собой вы­числительный центр (ВЦ) с тремя (n = 3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступаю­щих на ВЦ, имеет интенсивность λ = 1 задаче в час. Средняя про­должительность обслуживания t обсл = 1,8 час. Поток заявок на ре­шение задач и поток обслуживания этих заявок являются простей­шими.

Требуется вычислить финальные значения:

Вероятности состояний ВЦ;

Вероятности отказа в обслуживании заявки;

Относительной пропускной способности ВЦ;

Абсолютной пропускной способности ВЦ;

Среднего числа занятых ПЭВМ на ВЦ.

Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.

1. Определим параметр μ потока обслуживании:

ρ=λ/μ=1/0.555=1.8

3. Предельные вероятности состояний найдем по формулам Эр-
ланга (27):

P 1 =1.8*0.186=0.334;

P 2 =1.62*0.186=0.301;

P 3 =0.97*0.186=0.180.

4. Вероятность отказа в обслуживании заявки

P отк =P 3 =0.180

5. Относительная пропускная способность ВЦ

q = 1 - P отк = 1 - 0.180 = 0,820.

6. Абсолютная пропускная способность ВЦ

А = λ q = 1 0,820 = 0,820.

7. Среднее число занятых каналов - ПЭВМ

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех - остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно счи­тать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (P 3 =0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.

Определим, сколько нужно использовать ПЭВМ, чтобы сокра­тить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу (28):

Составим следующую таблицу:

n
P 0	0,357	0,226	0,186	0,172	0,167	0,166
P отк	0,643	0,367	0,18	0,075	0,026	0,0078

Анализируя данные таблицы, следует отметить, что расшире­ние числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение за­дач на 99,22%, так как при п = 6 вероятность отказа в обслужива­нии (Р отк) составляет 0,0078.

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

Процесс массового обслуживания при этом характери­зуется следующим: входной и выходной потоки являются пуассоновскими с интенсивностями λ и μ соответственно; параллельно обслуживаться могут не более С клиентов. Система имеет С кана­лов обслуживания. Средняя продолжительность обслуживания одного клиента равна

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

(32)

Решение системы уравнений (32) имеет вид

(33) (34)

(35)

Решение будет действительным, если выполняется следующее условие:

Вероятностные характеристики функционирования в стационар­ном режиме многоканальной СМО с ожиданием и неограниченной оче­редью определяются по следующим формулам:

Вероятность того, что в системе находится n клиентов на обслу­живании, определяется по формулам (33) и (34);

Среднее число клиентов в очереди на обслуживание

(36)

Среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди)

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

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

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

Пример 5. Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неис­правных механизмов, прибывающих в мастерскую, - пуассоновский и имеет интенсивность λ= 2,5 механизма в сутки, среднее время ремонта одного механизма распределено по показательному закону и равно t = 0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской мо­жет расти практически неограниченно.

Требуется вычислить следующие предельные значения вероят­ностных характеристик системы:

Вероятности состояний системы;

Среднее число заявок в очереди на обслуживание;

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

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

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

1. Определим параметр потока обслуживаний

μ = 1/t=1/0,5 = 2.

2. Приведенная интенсивность потока заявок

ρ = λ/μ = 2,5/2,0 = 1,25,

при этом λ/μ *с= 2,5/2 * 3 = 0,41.

Поскольку λ/μ * с <1 , то очередь не растет безгранично и в сис­теме наступает предельный стационарный режим работы.

3. Вычислим вероятности состояний системы:

4. Вероятность отсутствия очереди у мастерской

5. Среднее число заявок в очереди на обслуживание

6. Среднее число находящихся в системе заявок

L s = L q + ρ = 0,111 + 1,25 = 1,361.

7. Средняя продолжительность пребывания механизма в очереди на обслуживание

8. Средняя продолжительность пребывания механизма в мас­терской (в системе)

Использование теории массового обслуживания при организации сервиса машин

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

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

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

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

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

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

· вероятность немедленного обслуживания заявки;

· вероятность отказа в обслуживании;

· среднее число обслуженных заявок и заявок, получивших отказ;

· среднее время ожидания обслуживания; средняя длина очереди; относительная и абсолютная пропускная способность системы;

· убытки от простоя заявок в очереди и незанятых каналов обслуживания и другие.

Виды систем массового обслуживания

Различают два основных вида систем массового обслуживания:

1. Системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и покидает систему;

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

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

Одноканальная система с отказами.

Рассмотрим простейший случай, когда СМО имеет в своем распоряжении всего один канал обслуживания (п =1) и работает с отказами. Состояние данной системы можно изобразить графически в виде графа состояний: где х 0 - состояние системы, когда канал не занят; х 1 - состояние системы, когда канал занят; Р - вероятности перехода системы из одного состояния в другое (Р 00 ∆t не поступит ни одной заявки; Р 10 ∆t заявка будет обслужена; P 01 - вероятность того, что за время ∆t поступит заявка; Р 11 - вероятность того, что за время ∆t заявка не обслужится).

Р 01

х 1

х 0

Р 11

Р 00

Р 10

х 0

х 1

Рис. 5.1. Граф состояний одноканальной СМО с отказами

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

где Р(к) - вероятность того, что за время ∆t поступит к заявок (к = 0,1,2,…); λ - плотность или интенсивность заявок, то есть среднее число заявок в единицу времени; ∆t - отрезок времени, за который рассматривается вероятность поступления заявок;

Вероятность того, что за время ∆t не поступит ни одной заявки (к = 0) составит

. (5.2)

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

, (5.3)

где μ - интенсивность обслуживания, то есть среднее число обслуживаний в единицу времени μ = 1/М t об ; М t об - среднее время обслуживания заявки.

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

При этом вероятность того, что за время ∆t заявка не будет обслужена, составит

Сравнивая выражения (5.2) и (5.5) видим, что время между двумя заявками распределено по показательному закону. Это позволяет моделировать случайные моменты времени поступления заявок на обслуживание.

Выражения (5.2) и (5.4) могут быть преобразованы с использованием разложения в ряд Маклорена

Отбрасывая члены ряда второго порядка и выше для выражений (5.2) и (5.4) запишем

Канал может быть в состоянии х 0 в двух случаях:

1. в момент t х 0 , а за время Δt не пришло ни одной заявки;

2. в момент t система находилась в состоянии х 1 , а за время ∆t канал освободился и система перешла в состояние х 0 .

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

Вероятность указанных выше событий (1 и 2) равна произведению вероятностей событий в них входящих.

Раскрывая скобки и группируя переменные, получаем

. (5.10)

Аналогично и для

(5.11)

Уравнения (5.10) и (5.11) называются разностными. Переходя к пределу при ∆t→ 0, получаем систему дифференциальных уравнений Эрланга

, (5.12)

. (5.13)

Приведенная система дифференциальных уравнений Эрланга является частным случаем системы дифференциальных уравнений Колмогорова.

Для установившегося режима (λ = const) производные равны нулю, поэтому система дифференциальных уравнений (5.12) и (5.13) преобразуется в систему алгебраических уравнений, в частности для одноканальной системы с отказами получим

, откуда . (5.14)

Рассматривая выражение (5.14), формулируем следующее важное мнемоническое правило: «Что вытекает, то и втекает». Для каждого состояния сумма членов, соответствующая выходящим стрелкам, равна сумме членов, соответствующих входящим. Каждый член равен интенсивности потока событий, переводящих систему по данной стрелке, умноженной на вероятность того состояния, из которого выходит стрелка.

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

Мнемоническое правило остается справедливым и для многоканальной системы с отказами и с ожиданием в очереди.

Из равенства (5.14) с учетом того, что Р 0 +Р 1 = 1, получаем

, откуда

, (5.15)

при этом , (5.16)

где α= λ/μ - приведенная плотность или загрузка системы.

Пример: Исследуется работа СТОА с отказами. Станция имеет один подъемник (канал, п = 1). На станцию поступает простейший пуассоновский поток заявок с плотностью λ = 5 автомобилей в час. Время обслуживания распределено по показательному закону и характеризуется средней продолжительностью М t об = 0,333 ч на автомобиль. Определить показатели эффективности станции за 10 - часовой рабочий день.

1. Плотность или интенсивность обслуживания μ = 1/ М t об = 1/0,333= 3 автомобиля в ч.

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

= 0,375

Следовательно, 37,5% прибывающих автомобилей будет поставлено на немедленное обслуживание.

3. Находим абсолютную пропускную способность станции

λ∙ Р 0 = 5∙0,375 = 1,875 авт. в ч,

а за десять ч 18,75 автомобиля.

4. Определим вероятность отказа

Р отк = 1- Р 0 = 1 - 0,375 = 0,625.

Следовательно, 62,5% прибывающих автомобилей получают отказ.

5. Находим номинальную или максимально возможную пропускную способность за 10 часовой рабочий день

= 3 · 10 = 30 автомобиля в день.

Как видим, абсолютная пропускная способность примерно в 1,5 раза меньше номинальной. Это расхождение объясняется случайным характером потока заявок и случайным временем обслуживания заявок.

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

Одноканальная смо с отказами

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

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

Система при любом t > 0 может находиться в двух состояниях:S 0 – канал свободен;S 1 – канал занят. Переход изS 0 вS 1 связан с появлением заявки и немедленным началом ее обслуживания. Переход изS 1 вS 0 осуществляется, как только очередное обслуживание завершится (рис.4).

Рис.4. Граф состояний одноканальной СМО с отказами

Выходные характеристики (характеристики эффективности) этой и других СМО будут даваться без выводов и доказательств.

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

где – интенсивность потока заявок (величина, обратная среднему промежутку времени между поступающими заявками -);

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

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

Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной):

Очевидны следующие соотношения: и.

Пример . Технологическая система состоит из одного станка. На станок поступают заявки на изготовление деталей в среднем через 0,5 часа. Среднее время изготовления одной детали равно. Если при поступлении заявки на изготовление детали станок занят, то она (деталь) направляется на другой станок. Найти абсолютную и относительную пропускную способности системы и вероятность отказа по изготовлению детали.

Т.е. в среднем примерно 46 % деталей обрабатываются на этом станке.

.

Т.е. в среднем примерно 54 % деталей направляются на обработку на другие станки.

N – канальная смо с отказами (задача Эрланга)

Это одна из первых задач теории массового обслуживания. Она возникла из практических нужд телефонии и была решена в начале 20 века датским математиком Эрлангом.

Дано : в системе имеетсяn – каналов, на которые поступает поток заявок с интенсивностью. Поток обслуживаний имеет интенсивность. Заявка, заставшая систему занятой, сразу же покидает ее.

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

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

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

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

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

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

Граф состояний СМО представлен на рис. 5

Рис.5 Граф состояний для n – канальной СМО с отказами

Почему граф состояний размечен именно так? Из состояния S 0 в состояниеS 1 систему переводит поток заявок с интенсивностью(как только приходит заявка, система переходит изS 0 вS 1). Если система находилась в состоянииS 1 и пришла еще одна заявка, то она переходит в состояниеS 2 и т.д.

Почему такие интенсивности у нижних стрелок (дуг графа)? Пусть система находится в состоянии S 1 (работает один канал). Он производитобслуживаний в единицу времени. Поэтому дуга перехода из состоянияS 1 в состояниеS 0 нагружена интенсивностью. Пусть теперь система находится в состоянииS 2 (работают два канала). Чтобы ей перейти вS 1 , нужно, чтобы закончил обслуживание первый канал, либо второй. Суммарная интенсивность их потоков равнаи т.д.

Выходные характеристики (характеристики эффективности) данной СМО определяются следующим образом.

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

где n – количество каналов СМО;

–вероятность нахождения СМО в начальном состоянии, когда все каналы свободны (финальная вероятность нахождения СМО в состоянии S 0);

Рис.6. Граф состояний для схемы «гибели и размножения»

Для того, чтобы написать формулу для определения , рассмотрим рис.6

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

Кстати, остальные финальные вероятности состояний СМО запишутся следующим образом.

S 1 , когда один канал занят:

Вероятность того, что СМО находится в состоянии S 2 , т.е. когда два канала заняты:

Вероятность того, что СМО находится в состоянии S n , т.е. когда все каналы заняты.

Теперь для n – канальной СМО с отказами

Относительная пропускная способность:

Напомним, что это средняя доля заявок, обслуживаемых системой. При этом

Вероятность отказа :

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

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