Теория массового обслуживания. Примеры задач для многоканальных смо
Рассмотрим способы моделирования на ЭВМ потоков заявок, поступающих в систему массового обслуживания. Сначала остановимся на достаточно простом и вместе с тем наиболее распространенном случае, когща в систему поступает ординарный стационарный поток однородных событий с ограниченным последействием (поток типа Пальма).
Любой поток типа Пальма может быть задан функцией плотности случайных интервалов между последовательными моментами - поступления заявок. Для моделирования его на ЭВМ достаточно построить необходимое число реализаций потока, т. е. таких неслучайных последовательностей моментов
поступления заявок в систему, интервалы между которыми являлись бы возможными значениями случайных величин описываемых функцией плотности
Процедура построения последовательности состоит в следующем. Сначала формируется Функция плотности может быть определена через по формуле Пальма (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).
Рассмотрим одноканальную систему
массового обслуживания (СМО) с ожиданием.
Пусть входящий поток заявок на обслуживание -
простейший поток с интенсивностью l
.
Интенсивность потока обслуживания равна m . Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что СМО не может вместить более N заявок, т.е. заявки, не попавшие в ожидание, покидают СМО. Состояния СМО имеют следующую интерпретацию:
Канал свободен;
Канал занят, очереди нет;
Канал занят, одна заявка в очереди;
..............................
Канал занят, n-1 заявка в очереди;
Канал занят, N-1 заявка в очереди.
Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:
, n=0,
...................................
-( , 0 ................................... n - номер состояния. Система уравнений имеет следующее
решение:: Если , n=1, 2, ..., N, Выполнение условия стационарности r
< 1 не обязательно, поскольку
число допускаемых в СМО заявок контролируется
путем введения ограничения на длину очереди.
Определим характеристики одноканальной СМО с
ожиданием и ограниченной длиной очереди, равной
(N-1): 2) относительная пропускная способность
СМО: 3) абсолютная пропускная способность
СМО: 4) среднее число находящихся в СМО
заявок: 5) среднее время пребывания заявки в СМО: 6) средняя продолжительность пребывания
клиента (заявки) в очереди: 7) среднее число заявок в очереди (длина
очереди): Задача 1
. Специализированный пост
диагностики представляет собой одноканальную
СМО. Число стоянок для автомобилей, ожидающих
проведения диагностики, ограниченно и равно 3.
Если все стоянки заняты, то очередной автомобиль,
прибывший на диагностику, в очередь на
обслуживание не становится. Поток автомобилей,
прибывающих на диагностику, распределен по
закону Пуассона и имеет интенсивность l
= 0.85 (автомобиля в час). Время
диагностики автомобиля распределено по
показательному закону и в среднем составляет 1.05
час. Требуется определить вероятностные
характеристики поста диагностики, работающего в
стационарном режиме. > 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% случаев. > 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: Принятые обозначения: Повторите опыт 50 раз в цикле, найдите
оценки характеристик СМО, сравните их с
теоретическими значениями. Задача 2
: Следовательно, 13% в течение часа канал будет не занят, время простоя равно t пр = 7.5 мин.
Для определения оптимального число линий связи, достаточное для того, чтобы вероятность отказа не превышала 0.04, воспользуемся формулой:
1. Коммерческая фирма занимается посреднической деятельностью по продаже автомобилей и осуществляет часть переговоров по 3 телефонным линиям. В среднем поступает 75 звонков в час. Среднее время предварительных переговоров справочного характера составляет 2 мин. 2. Пункт по ремонту квартир работает в режиме отказа и состоит из двух бригад. Интенсивность потока заявок λ, производительность пункта μ. Определить вероятность того, что оба каналы свободны, один канал занят, оба канала заняты, вероятность отказа, относительную и абсолютную пропускные способности, средне число занятых бригад. 3. В вычислительный центр коллективного пользования с тремя ЭВМ поступают заказы от предприятий на вычислительные работы. Если работают все три ЭВМ, то вновь поступающий заказ не принимается, и предприятие вынуждено обратиться в другой вычислительный центр.
Среднее время работы с одним заказом составляет 3 ч. Интенсивность потока заявок 0,25 (1/ч). Найти предельные вероятности состояний и показатели эффективности работы вычислительного центра. 2. В мини-маркет поступает поток покупателей с интенсивностью 6 покупателей в 1 мин., которых обслуживают три контролера-кассира с интенсивностью 2 покупателя в 1 мин. длина очереди ограничена 5 покупателями. 3. На плодоовощную базу в среднем через 30 мин. прибывают автомашины с плодоовощной продукцией. Среднее время разгрузки одной машины составляют 1.5 ч. Разгрузку производят две бригады. На территории базы у дебаркадера могут находиться в очереди в ожидании разгрузки не более 4 автомашин. 4. На автомойку в среднем за час приезжают 9 автомобилей, но если в очереди уже находятся 4 автомобиля, вновь подъезжающие клиенты, как правило, не встают в очередь, а проезжают мимо. Среднее время мойки автомобиля составляет 20 мин., а мест для мойки всего два. Средняя стоимость мойки автомобиля составляет 70 руб. Определите среднюю величину потери выручки автомойки в течение дня. 5. Магазин получает овощи из теплиц. Автомобили с грузом прибывают с интенсивностью λ
машин в день. Подсобные помещения позволяют обрабатывать и хранить товар, привезенный m
автомобилями. В магазине работают n
фасовщиков, каждый из которых в среднем может обрабатывать товар с одной машины в течении t обсл.
часов. Продолжительность рабочего дня при сменной работе составляет 12 часов. Определить емкость подсобных помещений при заданной вероятности Р* обсл. полной обработки товаров. 6. Имеется автозаправочная станция с 2-мя колонками. В очереди не может быть больше 3-х машин. Интенсивность и среднее время заправки равны 2.1 и 0.55. Найти вероятность простоя системы.
1. Построить две модели многоканальной системы массового обслуживания – с бесконечной и ограниченной очередью. Вычислить Р 0 – вероятность простаивания всех каналов обслуживания, n w – среднее число клиентов, ожидающих обслуживания, t w – среднее время ожидания обслуживания, W – вероятность обязательного пребывания в очереди. 2. В расчетном узле магазина самообслуживания работают 3 кассы. интенсивность входного потока составляет 5 покупателей в минуту. интенсивность обслуживания каждого контролера-кассира составляет 2 покупателя минуту. Рекомендации к решению задачи:
здесь n = 3; λ = 5 ед. в мин.; μ = 2 ед. в мин.
3. В аудиторскую фирму поступает простейший поток заявок на обслуживание с интенсивностью λ = 1,5 заявки в день. Время обслуживания распределено по показательному закону и равно в среднем трем дням. Аудиторская фирма располагает пятью независимыми бухгалтерами, выполняющими аудиторские проверки (обслуживание заявок). Очередь заявок не ограничена. Дисциплина очереди не регламентирована. Определите вероятностные характеристики аудиторской фирмы как системы массового обслуживания, работающей в стационарном режиме. 4. В мастерской по ремонту холодильников работает n мастеров. В среднем в течение дня поступает в ремонт λ холодильников. Поток заявок пуассоновский. Время ремонта подчиняется экспоненциальному закону распределения вероятностей, в среднем в течение дня при семичасовом рабочем дне каждый из мастеров ремонтирует μ холодильников.
В качестве показателей эффективности СМО с отказами будем рассматривать: 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=\frac{\mu}{\lambda+\mu},\quad p_1=\frac{\lambda}{\lambda+\mu}\,
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),
Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность системы 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
; Вероятность отказа (когда заняты все три ЭВМ), таким образом, 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%.
. При оценке эффективности работы вычислительного центра необходимо сопоставить доходы от выполнения заявок с потерями от простоя дорогостоящих ЭВМ (с одной стороны, у нас высокая пропускная способность СМО, а с другой стороны - значительный простой каналов обслуживания) и выбрать компромиссное решение. Поток заявок явл
пуассоновским, если выполняются 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
(освободить)
–
освобождение
прибора транзактом, по истечении времени
обслуживания.
, n=N,
,
1) вероятность отказа в обслуживании заявки:
;
;
;
;
Решение
:
1) Интенсивность прибытия автомобилей на
обслуживание:
6) Относительная пропускная способность поста
диагностики:
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 машины в очереди");
1) Модифицируйте процедуру для вычисления
числовых характеристик СМО. Задайте
продолжительность опыта в 1000 минут и повторите
опыт, например, 5 раз. Затем вычислите средние
значения каждой характеристики СМО. Сравните
опытные данные с вероятностными
характеристиками СМО.
2) Смоделируйте работу СМО для случая, когда
автомобиль обслуживается ровно 1 час 5 минут, а
все остальные параметры остаются прежними.
Сравните полученные данные с результатами
предыдущего пункта.
3) Так как интенсивность поступления заявок равна
0.85 машины в час, то в среднем промежуток времени
между поступлениями заявок составляет 1/0.85=100/85
часа, или около 71 минуты. Задайте интервал между
поступлениями заявок с помощью функции stats() и проведите ряд испытаний работы СМО.
Сравните средние значения характеристик,
полученных опытным путем, с вероятностными
характеристиками.
4) Задайте интенсивность обслуживания в 70 минут, а
число стоянок для машин равной 4, и проведите
испытания работы поста диагностики. Повторите
опыт для случая, когда интенсивность
обслуживания составляет 60 минут, а число стоянок
2. Как изменятся характеристики поста
диагностики?
5) Смоделируйте работу поста диагностики при
условии, что число стоянок не ограниченно.
k = 5; λ = 0.6; t = 3.5, α = 0.04.
Решение
. Исчисляем показатели обслуживания многоканальной СМО:
Интенсивность потока обслуживания:
μ = 1/3.5 = 0.29
1. Интенсивность нагрузки
.
ρ = λ t обс = 0.6 3.5 = 2.1
Интенсивность нагрузки ρ=2.1 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
3. Вероятность, что канал свободен
(доля времени простоя каналов).
Вероятность того, что обслуживанием:
занят 1 канал:
p 1 = ρ 1 /1! p 0 = 2.1 1 /1! 0.13 = 0.26
заняты 2 канала:
p 2 = ρ 2 /2! p 0 = 2.1 2 /2! 0.13 = 0.28
заняты 3 канала:
p 3 = ρ 3 /3! p 0 = 2.1 3 /3! 0.13 = 0.19
заняты 4 канала:
p 4 = ρ 4 /4! p 0 = 2.1 4 /4! 0.13 = 0.1
заняты 5 канала:
p 5 = ρ 5 /5! p 0 = 2.1 5 /5! 0.13 = 0.0425 (вероятность того, что все линии связи заняты)
4. Доля заявок, получивших отказ
.
Значит, 4% из числа поступивших заявок не принимаются к обслуживанию.
5. Вероятность обслуживания поступающих заявок
.
В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:
p отк + p обс = 1
Относительная пропускная способность: Q = p обс.
p обс = 1 - p отк = 1 - 0.0425 = 0.96
Следовательно, 96% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.
6. Среднее число занятых линий связи
n з = ρ p обс = 2.1 0.96 = 2.01 линии.
Среднее число простаивающих каналов
.
n пр = n - n з = 5 - 2.01 = 3 канала.
7. Коэффициент занятости каналов обслуживанием
.
K 3 = n 3 /n = 2.01/5 = 0.4
Следовательно, система на 40% занята обслуживанием.
8. Абсолютная пропускная способность
.
A = p обс λ = 0.96 0.6 = 0.57 заявок/мин.
9. Среднее время простоя СМО
.
t пр = p отк t обс = 0.0425 3.5 = 0.15 мин.
12. Среднее число обслуживаемых заявок
.
L обс = ρ Q = 2.1 0.96 = 2.01 ед.
Для наших данных:
где 
Подбирая количество линий связей, находим, что при k=6, p отк = 0.0147 < 0.04, p 0 = 0.12
Скачать решениеМногоканальная СМО с ограниченной длиной очереди
Решение
:
Интенсивность потока обслуживания равна μ = 1/0.55 = 1.82. Отсюда, интенсивность нагрузки составит ρ = λ t обс = 2.1 0.55 = 1.16. Заметим, что интенсивность нагрузки ρ=1.16 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
Поскольку 1.16<2, то процесс обслуживания будет стабилен.
Вероятность простоя системы выражается следующей формулой:
Следовательно, 28% в течение часа канал будет не занят, время простоя равно t пр = 0.28*60 мин. = 16.9 мин.
Многоканальная СМО с неограниченной очередью
В качестве количества заявок в очереди можно указать, например, m = 4. тогда будут рассчитаны соответствующие вероятность появления данных заявок.
Требуется определить: 1) вероятность того, что все мастера свободны от ремонта холодильников, 2) вероятность того, что все мастера заняты ремонтом, 3) среднее время ремонта одного холодильника, 4) в среднем время ожидания начала ремонта для каждого холодильника, 5) среднюю длину очереди, которая определяет необходимое место для хранения холодильника, требующего ремонта, 6) среднее число мастеров, свободных от работы.Одноканальная система (СМО) с отказами
т.е. система вырождается в одно уравнение. Учитывая нормировочное условие p_0+p_1=1
, найдем из (18) предельные вероятности состояний
которые выражают среднее относительное время пребывания системы в состоянии S_0
(когда канал свободен) и S_1
(когда канал занят), т.е. определяют соответственно относительную пропускную способность Q
системы и вероятность отказа P_{\text{otk}}:
Многоканальная система (СМО) с отказами
называется приведенной интенсивностью потока заявок
или интенсивностью нагрузки канала
. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Теперь
где p_k
- предельные вероятности состояний, определяемых по формулам (25), (26).
т.е. в стационарном режиме работы вычислительного центра в среднем 47,6% времени нет ни одной заявки, 35,7% - имеется одна заявка (занята одна ЭВМ), 13,4% - две заявки (две ЭВМ), 3,3% времени - три заявки (заняты три ЭВМ).
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!
