Типовые математические модели. Смо с отказами определения и формулы

При решении задач управления, в том числе и управления войсками, часто возникает ряд однотипных задач:

• оценка пропускной способности направления связи, железнодорожного узла, госпиталя и т. п.;
• оценка эффективности ремонтной базы;
• определение количества частот для радиосети и др.

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

Элементами СМО являются:

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

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

Как правило, на практике имеют дело с так называемыми рекуррентными потоками, - потоками, обладающими свойствами:

• стационарности;
• ординарности;
• ограниченного последействия.

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

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

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

здесь - интенсивность потока.

Название потока - пуассоновский - происходит от того, что для этого потока вероятность появления заявок за интервал определяется законом Пуассона:

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

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

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

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

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

где - количество радиостанций, уже находящихся в мастерской на ремонте.

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

Важной характеристикой входного потока является коэффициент вариации :

где - математическое ожидание длины интервала;

Среднеквадратическое отклонение случайной величины (длины интервала) .

Для простейшего потока

Для большинства реальных потоков .

При поток регулярный, детерминированный.

Коэффициент вариации - характеристика, отражающая степень неравномерности поступления заявок.

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

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

• линии связи;
• мастера ремонтных органов;
• взлетно-посадочные полосы;
• транспортные средства;
• причалы;
• парикмахеры, продавцы и др.

Основная характеристика канала - время обслуживания. Как правило, время обслуживания - величина случайная.

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

где - интенсивность обслуживания, ;

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

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

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

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

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

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

• СМО с отказами;
• СМО с ожиданием.

СМО с ожиданием характеризуются наличием очередей. Очередь может иметь ограниченную или неограниченную емкость: .

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

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

Нередко встречаются СМО, в которых заявки имеют ограниченное время пребывания в очереди независимо от ее емкости. Такие СМО также относят к СМО смешанного типа.

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

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

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

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

Краткая теория

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

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

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

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

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

Рассмотрим классическую задачу Эрланга.

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

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

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

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

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

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

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

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

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

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

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

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

где – предельные вероятности состояний

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

Пример решения задачи

Условие задачи

Контроль готовой продукции фирмы осуществляют три контролера. Если изделие поступает на контроль, когда все контролеры заняты проверкой готовых изделий, то оно остается непроверенным. Среднее число изделий, выпускаемых фирмой, составляет 20 изд./ч. Среднее время на проверку одного изделия - 7 мин.

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

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

Решение задачи

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

За единицу измерения времени выберем час. Будем считать, что контроль работает в установившемся режиме. По условию задачи

–число каналов обслуживания

Изделий в час –интенсивность потока заявок

Изделий в час –интенсивность потока обслуживания

Вычислим –относительные интенсивности переходов из состояние в состояние:

Вычислим :

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

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

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

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

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

Вычислим, сколько контролеров нужно поставить, чтобы вероятность обслуживания составила не менее 97%:

Таким образом, чтобы вероятность обслуживания составляла не менее 97%, необходимо иметь 6 контролеров.

Средняя стоимость решения контрольной работы 700 - 1200 рублей (но не менее 300 руб. за весь заказ). На цену сильно влияет срочность решения (от суток до нескольких часов). Стоимость онлайн-помощи на экзамене/зачете - от 1000 руб. за решение билета.

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

Примеры близких по теме задач

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

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

Метод множителей Лагранжа
На странице рассмотрено нахождение условного экстремума методом множителей Лагранжа. Показано построение функции Лагранжа на примере решения задачи нелинейного программирования. Решенную задачу предваряет краткая теория.

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

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

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!

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

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

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

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

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

В связи с тем что потоки заявок в системе рассчитаны для средних суток, то расчеты длины очереди L и среднего времени ожидания обслуживания Тож, как и другие качественные параметры, будут сделаны неверно, так как интенсивность потока в различные часы суток различна и может меняться до 5 раз. Конечно, можно рассчитать эти параметры за каждый час отдельно, но и это будет неверно, так как СМО будет находиться в постоянном переходном процессе. В этом случае входной поток будет нестационарным и с последействием, так как математическое ожидание числа заказов в единицу времени будет меняться в 3- 5 раз, а число заказов, поступивших, например, в 18 часов, зависит от того, сколько их было фактически за каждый предыдущий час.  

Пример 3.1. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей Л = 1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслуживании являются простейшими.  

Параметр потока обслуживания л и приведенная интенсивность потока автомобилей р определены в примере 3.2  

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

О Пример. В пункте химчистки имеется три аппарата для чистки. Интенсивность потока посетителей А, = 6 (посетителей в час). Интенсивность обслуживания посетителей одним аппаратом i = 3 (посетителей в час). Среднее количество посетителей, покидающих очередь, не дождавшись обслуживания, VBS (посетитель в час). Найти абсолютную пропускную способность пункта.  

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

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

СМОЬ СМО2 и СМО3 представляют собой пг, п2- и п3- канальные системы с неограниченной очередью и интенсивностью потоков обслуживании // , ju2 и //з, соответственно. Время повторного обслуживания заявки в  

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

Производительность канала -интенсивность простейшего потока обслуживании П0б (среднее число заявок, обслуживаемое каналом за единицу времени при непрерывной работе) in П0б = ju = onst 100 заявок/день  

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

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

Полученные выше результаты относились к ситуации, когда интенсивность k потока заявок на восстановление не зависит от числа k находящихся в ремонтном органе необслуженных заявок. В противном случае говорят о замкнутых системах обслуживания. При ограниченном числе R источников заявок обычно считают, что А/ = А(Л - А). Методы расчета марковских систем подобного вида хорошо известны (формулы Энгсета). Рассчитывать немарковские системы значительно сложнее. Особенно труден анализ системы, где интенсивность отказов зависит от объема ЗИПа s (запас s рассматривается как холодный резерв, не подверженный отказам). Между тем этот случай достаточно типичен. Если считать, что в рабочей системе установлены R источников заявок, то интенсивность отказов будет оставаться постоянной и равной АЛ, пока в системе восстановления не скопится k > s заявок. Тогда интенсивность потока заявок начнет убывать по закону А = X. Методика расчета подобной СМО вида M/G/l/(R + s) была предложена автором в статье , оказалась весьма громоздкой и к тому же неприменимой для многоканальных систем восстановления. Однако ап-проксимационные методы, описанные в главе 3, без труда обобщаются и на этот случай. Здесь мы отметим особенности его реализации  

Найдем способ расчета стационарных вероятностей состояний одношналъной системы с указанной зависимостью интенсивности потока от числа заявок в ней и произвольным распределением длительности обслуживания B(t).  

Сам К.Эрланг изучал эту задачу в следующих предположениях поток требований - пуассоновский с интенсивностью J длительность обслуживания распределена по показательному закону , причем средняя продолжительность обслуживания. При названных предположениях К.Эрланг показал, что если число обслуживающих устройств равно /7 , то при стационарном пуас-соновском

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

Интенсивность потока обслуживания равна m . Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что СМО не может вместить более N заявок, т.е. заявки, не попавшие в ожидание, покидают СМО. Состояния СМО имеют следующую интерпретацию:

Канал свободен;

Канал занят, очереди нет;

Канал занят, одна заявка в очереди;

..............................

Канал занят, n-1 заявка в очереди;

Канал занят, N-1 заявка в очереди.

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

, n=0,

...................................

-( , 0

...................................

, n=N,

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

Система уравнений имеет следующее решение::

,

Если , n=1, 2, ..., N,

Выполнение условия стационарности r < 1 не обязательно, поскольку число допускаемых в СМО заявок контролируется путем введения ограничения на длину очереди. Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):
1) вероятность отказа в обслуживании заявки:

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

3) абсолютная пропускная способность СМО:

4) среднее число находящихся в СМО заявок:

;

5) среднее время пребывания заявки в СМО:

;

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

;

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

;

Задача 1 . Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3. Если все стоянки заняты, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность l = 0.85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем составляет 1.05 час. Требуется определить вероятностные характеристики поста диагностики, работающего в стационарном режиме.
Решение :
1) Интенсивность прибытия автомобилей на обслуживание:

> lambda:=0.85;

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

> t:=1.05:mu:=1/t;

3) Найдем приведенную интенсивность потока автомобилей как отношение интенсивностей l и m , т.е..

> rho:=lambda/mu;

4) Вычислим финальные вероятности системы:

> N:=4:P:=(1-rho)/(1-rho^(N+1));P:=rho*P;P:=rho^2*P;P:=rho^3*P;P:=rho^4*P;

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

> P:=P;

Отсюда следует, что пост диагностики не обслуживает автомобили в среднем в 15.8% случаев.
6) Относительная пропускная способность поста диагностики:

> q:=1-P;

7) Абсолютная пропускная способность поста диагностики (автомобиля в час):

> A:=lambda*q;

8) Среднее число автомобилей в СМО:

> L[s]:=rho*(1-(N+1)*rho^N+N*rho^(N+1))/((1-rho)*(1-rho^(N+1)));

9) Среднее время пребывания автомобиля в СМО:

> W[s]:=L[s]/(lambda*(1-P[N]));

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

> W["q"]:=W[s]-1/mu;

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

> L["q"]:=lambda*(1-P[N])*W["q"];

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

> p:=proc(k) global t_och1,t_och2,t_och3,sm_t_obs,post,otk,obsl:local t1,t_okon,t,rn_post,och,per:
t_och1:=0:t_och2:=0:t_och3:=0:post:=0:otk:=0:obsl:=0:t_okon:=0:sm_t_obs:=0:och:=0:rn_post:=rand(1..1200):
for t from 1 by 1 to k do
t1:=rn_post():
if och=1 then t_och1:=t_och1+1 fi:
if och=2 then t_och2:=t_och2+1 fi:
if och=3 then t_och3:=t_och3+1 fi:
if t1>=1 and t1<=17 and t_okon=0 and och>=0 and och<=3 then per:=1 fi:
if t1>=1 and t1<=17 and t_okon>0 and och>=0 and och<3 then per:=2 fi:
if t1>=1 and t1<=17 and t_okon>0 and och=3 then per:=3 fi:
if t1>17 and t_okon>0 then per:=4 fi:
if t1>17 and t_okon=0 and och>0 then per:=5 fi:
if per=1 then t_okon:=stats(): sm_t_obs:=sm_t_obs+t_okon:obsl:=obsl+1:post:=post+1 fi:
if per=2 then t_okon:=t_okon-1:obsl:=obsl+1:och:=och+1:post:=post+1 fi:
if per=3 then t_okon:=t_okon-1:otk:=otk+1:post:=post+1 fi:
if per=4 then t_okon:=t_okon-1 fi:
if per=5 then t_okon:=stats(): sm_t_obs:=sm_t_obs+t_okon:och:=och-1 fi od end:

Принятые обозначения:
t_och1,t_och2,t_och3 - количество минут, когда в очереди 1, 2 и 3 машины соответственно;
sm_t_obs - затрачено всего минут на обслуживание;
post - прибыло машин на обслуживание; otk - количество отказов в обслуживании; obsl - обслужено машин;
t_obsl - продолжительность обслуживания машины, инициализируется как случайная величина, распределенная по закону Пуассона с математическим ожиданием 65 минут (1 час 5 минут);
t1 - случайная величина, с одинаковой вероятностью принимающая целые значения из интервала от 1 до 12000. Если t1>=0 и t1<=17, то считаем, что на пункт диагностики поступила заявка (интенсивность 0.85 заявки в час = 17/12000 заявки в минуту);
t - параметр цикла (количество минут).
Проведем опыт продолжительностью в 5000 минут:
> p(5000);print("Поступило на обслуживание автомобилей ",post);print("Обслужено ",obsl); print("Отказано в обслуживании ",otk); print("Затрачено на обслуживание ",sm_t_obs,"мин."); print(t_och1," мин. 1 машина в очереди");print(t_och2,"мин. 2 машины в очереди"); print(t_och3," мин. 3 машины в очереди");

Повторите опыт 50 раз в цикле, найдите оценки характеристик СМО, сравните их с теоретическими значениями.

Задача 2 :
1) Модифицируйте процедуру для вычисления числовых характеристик СМО. Задайте продолжительность опыта в 1000 минут и повторите опыт, например, 5 раз. Затем вычислите средние значения каждой характеристики СМО. Сравните опытные данные с вероятностными характеристиками СМО.
2) Смоделируйте работу СМО для случая, когда автомобиль обслуживается ровно 1 час 5 минут, а все остальные параметры остаются прежними. Сравните полученные данные с результатами предыдущего пункта.
3) Так как интенсивность поступления заявок равна 0.85 машины в час, то в среднем промежуток времени между поступлениями заявок составляет 1/0.85=100/85 часа, или около 71 минуты. Задайте интервал между поступлениями заявок с помощью функции stats() и проведите ряд испытаний работы СМО. Сравните средние значения характеристик, полученных опытным путем, с вероятностными характеристиками.
4) Задайте интенсивность обслуживания в 70 минут, а число стоянок для машин равной 4, и проведите испытания работы поста диагностики. Повторите опыт для случая, когда интенсивность обслуживания составляет 60 минут, а число стоянок 2. Как изменятся характеристики поста диагностики?
5) Смоделируйте работу поста диагностики при условии, что число стоянок не ограниченно.