Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Другое / Конспекты / Конспект урока "Теория систем массового обслуживания"

Конспект урока "Теория систем массового обслуживания"

  • Другое

Поделитесь материалом с коллегами:

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


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

Классификация СМО по способу обработки входного потока заявок.

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

С отказами

(без очереди)

С очередью

Неограниченная очередь

Ограниченная очередь

С приоритетом

В порядке поступления

Относительный приоритет

Абсолютный приоритет

По времени обслуживания

По длине очереди















Классификация по способу функционирования:

  1. открытыми, т.е. поток заявок не зависит от внутреннего состояния СМО;

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

Классификация систем массового обслуживания

Первое деление (по наличию очередей):

  1. СМО с отказами;

  2. СМО с очередью.

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

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

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

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

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

Кроме этого СМО делятся на открытые СМО и замкнутые СМО.

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

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

Размеченный граф состояний одноканальной СМО представлен на рисунке 1.

hello_html_ma02f700.png

Рисунок 1 – Граф состояний одноканальной СМО

Здесь hello_html_m7f3ca9e6.gif и hello_html_m2f48edc4.gif – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы So обозначает, что канал свободен, а S1 – что канал занят обслуживанием заявки.

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

hello_html_m20346bfd.gif

где po(t) и p1(t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей po и p1 получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

hello_html_41ef23ed.gif (1)

hello_html_726f5cfa.gif (2)

Вероятность p0 по своему смыслу есть вероятность обслуживания заявки pобс, т. к. канал является свободным, а вероятность р1 по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки ротк, т. к. канал занят обслуживанием предыдущей заявки.

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



Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна hello_html_m7f3ca9e6.gif, а интенсивность обслуживания заявки каждым каналом равна hello_html_m2f48edc4.gif. Размеченный граф состояний системы изображён на рисунке 2.

hello_html_ec36c1e.png

Рисунок 2 – Граф состояний многоканальной СМО с отказами

Состояние S0 означает, что все каналы свободны, состояние Sk (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью hello_html_m7f3ca9e6.gif независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина hello_html_m111474dc.gif характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

hello_html_26691432.gif (4)

hello_html_2f32249a.gif (5)

Формулы (4) и (5) называются формулами Эрланга – основателя теории массового обслуживания.

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

hello_html_58853095.gif (6)

Относительную пропускную способность СМО:

hello_html_7b9b28b4.gif (7)

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

hello_html_4c6a4a7.gif

Так как каждый занятый канал в единицу времени обслуживает в среднем hello_html_m2f48edc4.gif заявок, то hello_html_4ef9d412.gif можно найти по формуле:

hello_html_m7e950d8d.gif

Одноканальная система массового обслуживания с ограниченной длиной очереди

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 3.

S0

hello_html_10cc5a3c.png

Рисунок 3 – Граф состояний одноканальной СМО с ограниченной очередью

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

S0 – канал обслуживания свободен,

S1 – канал обслуживания занят, но очереди нет,

S2 – канал обслуживания занят, в очереди одна заявка,

Sk+1 – канал обслуживания занят, в очереди k заявок,

Sm+1 – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рисунок 3 является частным случаем системы рождения и гибели, если принять hello_html_82ddce5.gif и

hello_html_3dd42553.gif (8)

hello_html_6a3ce717.gif (9)

hello_html_m5daeb0ab.gif (10)



Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии Sm+1, т.е. вероятность отказа в обслуживании заявки равна:

hello_html_45f894ae.gif

hello_html_m78db2b07.gif

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

hello_html_6f25e801.gif

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

hello_html_73ec4caa.gif

Среднее число заявок, стоящих в очереди Lоч, находится по формуле

hello_html_m21b22d21.gif

и может быть записано в виде:

hello_html_m21896cec.gif (11)

При hello_html_m3a1a943a.gif формула (11) принимает вид:

hello_html_m63069f74.gif

hello_html_7763454.gifсреднее число заявок, находящихся в СМО, находится по формуле:

hello_html_m7b68a4e4.gif

и может быть записано в виде:

hello_html_m47076b32.gif (12)

При hello_html_m3a1a943a.gif, из (12) получим:

hello_html_715ecbe8.gif

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

hello_html_m279af9ba.gif hello_html_m361a0e8a.gif Одноканальная система массового обслуживания с неограниченной очередью

Примером такой СМО может служить директор предприятия, вынужденный рано или поздно решать вопросы, относящиеся к его компетенции, или, например, очередь в булочной с одним кассиром. Граф такой СМО изображён на рисунке 4.

hello_html_m128e412a.png

Рисунок 4 – Граф состояний одноканальной СМО с неограниченной очередью

Рассмотрим случай, когда hello_html_58a65c56.gif.

hello_html_mb1dae9a.gif

hello_html_6e7379bb.gif

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

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

Среднее число заявок в очереди получим при hello_html_m581ade66.gif: hello_html_11de8151.gif

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

hello_html_674f87f5.gif

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

hello_html_387051b2.gif

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

hello_html_m279af9ba.gif hello_html_m361a0e8a.gif

Многоканальная система массового обслуживания с ограниченной очередью



Пусть на вход СМО, имеющей hello_html_m38f93f73.gif каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью hello_html_m7f3ca9e6.gif. Интенсивность обслуживания заявки каждым каналом равна hello_html_m2f48edc4.gif, а максимальное число мест в очереди равно hello_html_5c77245.gif.

Граф такой системы представлен на рисунке 5.

hello_html_762b5c26.png

Рисунок 5 – Граф состояний многоканальной СМО с ограниченной очередью

hello_html_19d9c3e1.gifвсе каналы свободны, очереди нет;

hello_html_m57f710f5.gifзаняты l каналов (l = 1, n), очереди нет;

hello_html_m4b9f6e90.gif- заняты все n каналов, в очереди находится i заявок (i = 1, m).

hello_html_192ea950.gif

hello_html_m60927f5.gif

Выражения для финальных вероятностей:

hello_html_m1b3df817.gif (13)

hello_html_71d17bd2.gif

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m – 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди pоч равна сумме соответствующих вероятностей hello_html_m609885c8.gif:

hello_html_m6e509cdf.gif (14)

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

hello_html_949eb1e.gif

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

hello_html_7a3c37c3.gif

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

hello_html_m1ee88c1a.gif

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

hello_html_2f4c0c71.gif (15)

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

hello_html_m562779ac.gif

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

hello_html_m46c529cf.gif

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

hello_html_m279af9ba.gif

hello_html_m361a0e8a.gif

Многоканальная система массового обслуживания с неограниченной очередью

Граф такой СМО изображен на рисунке 6 при hello_html_m3a1b9694.gif.

hello_html_m75f40f.png

Рисунок 6 – Граф состояний многоканальной СМО с неограниченной очередью

Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:

hello_html_m2674a5cf.gif

hello_html_mb37fc16.gif

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

hello_html_502649b0.gif

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

hello_html_m2d4bbd02.gif

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

hello_html_4ffc7ba3.gif

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

hello_html_m4172476b.gif

Среднее число обслуживаемых заявок определяется формулой: hello_html_5f5e4727.gif

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

Отличие такой СМО от других СМО, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром hello_html_1d922471.gif, где hello_html_1059af24.gif – среднее время ожидания заявки в очереди, а hello_html_78ba07fc.gif – имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 7.

hello_html_79904ee9.png

Рисунок 7 – Граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди

Выражения для финальных вероятностей

hello_html_67625c7e.gif

hello_html_597531cc.gif

hello_html_72d97f74.gif,

где hello_html_m29fb6c97.gif. Вероятность образования очереди определяется формулой:

hello_html_m60bfb245.gif

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

hello_html_m6bcd5323.gif

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

hello_html_f140545.gif

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

hello_html_e93833b.gif

Среднее число заявок, находящихся в очереди находится по формуле

hello_html_2781b4db.gif

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

hello_html_m6bb71f18.gif

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

hello_html_m793c1a9f.gif



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

Одноканальная СМО с ожиданием

Рассмотрим простейшую СМО с ожиданием — одноканальную систему (n - 1), в которую поступает поток заявок с интенсивностью http://masteroid.ru/files/matm/tmp178-2171.jpg; интенсивность обслуживания http://masteroid.ru/files/matm/tmp178-2172.jpg (т.е. в среднем непрерывно занятый канал будет выдавать http://masteroid.ru/files/matm/tmp178-2173.jpg обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

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

http://masteroid.ru/files/matm/tmp178-2174.jpgканал свободен;

http://masteroid.ru/files/matm/tmp178-2175.jpgканал занят, очереди нет;

http://masteroid.ru/files/matm/tmp178-2176.jpgканал занят, одна заявка стоит в очереди;

http://masteroid.ru/files/matm/tmp178-2177.jpgканал занят, k-1 заявок стоят в очереди;

http://masteroid.ru/files/matm/tmp178-2178.jpgканал занят, т-заявок стоят в очереди.

ГСП показан на рис. 8. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны http://masteroid.ru/files/matm/tmp178-2179.jpg, а справа налево — http://masteroid.ru/files/matm/tmp178-2180.jpg. Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево — поток «освобождений» занятого канала, имеющий интенсивность http://masteroid.ru/files/matm/tmp178-2182.jpg (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

http://masteroid.ru/files/matm/tmp178-2181.jpg

Рис. 8. Одноканальная СМО с ожиданием

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

http://masteroid.ru/files/matm/tmp178-2197.jpg (21).

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

http://masteroid.ru/files/matm/tmp178-2198.jpg (22).

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

http://masteroid.ru/files/matm/tmp178-2199.jpg.

Средняя длина очереди.

http://masteroid.ru/files/matm/tmp178-2201.jpg.

С вероятностьюhttp://masteroid.ru/files/matm/tmp178-2202.jpgв очереди стоит одна заявка, с вероятностьюhttp://masteroid.ru/files/matm/tmp178-2203.jpg— две заявки, вообще с вероятностьюhttp://masteroid.ru/files/matm/tmp178-2204.jpgв очереди стоят k-1 заявок, и т.д., откуда:

http://masteroid.ru/files/matm/tmp178-2205.jpg (23).

Поскольку http://masteroid.ru/files/matm/tmp178-2206.jpg, сумму в (23) можно трактовать как производную по http://masteroid.ru/files/matm/tmp178-2207.jpg от суммы геометрической прогрессии:

http://masteroid.ru/files/matm/tmp178-2208.jpg.

Подставляя данное выражение в (23) и используя http://masteroid.ru/files/matm/tmp178-2209.jpg из (20), окончательно получаем:

http://masteroid.ru/files/matm/tmp178-2210.jpg(24).

Среднее число заявокhttp://masteroid.ru/files/matm/tmp178-2217.jpg.

http://masteroid.ru/files/matm/tmp178-2218.jpg(25).

Среднее время ожидания заявки в очереди.

http://masteroid.ru/files/matm/tmp178-2226.jpg,

если подставить сюда выражения для вероятностей (20), получим:

http://masteroid.ru/files/matm/tmp178-2227.jpg(26).

http://masteroid.ru/files/matm/tmp178-2229.jpg (27).

Среднее время пребывания заявки в системе. http://masteroid.ru/files/matm/tmp178-2234.jpg.

Отсюда:

http://masteroid.ru/files/matm/tmp178-2235.jpg.





Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).

Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно (m = 3). Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность http://masteroid.ru/files/matm/tmp178-2236.jpg=1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.

Определить:

вероятность отказа;

относительную и абсолютную пропускную способности АЗС;

среднее число машин, ожидающих заправки;

среднее число машин, находящихся на АЗС (включая обслуживаемую);

среднее время ожидания машины в очереди;

среднее время пребывания машины на АЗС (включая обслуживание).

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

Системы с неограниченным ожиданием.

В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода http://masteroid.ru/files/matm/tmp178-2248.jpg в ранее полученных выражениях (17), (18) и т.п.

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q=1, http://masteroid.ru/files/matm/tmp178-2255.jpg.

Среднее число заявок в очереди получим из (24) при http://masteroid.ru/files/matm/tmp178-2256.jpg:

http://masteroid.ru/files/matm/tmp178-2257.jpg.

Среднее число заявок в системе по формуле (25) при http://masteroid.ru/files/matm/tmp178-2258.jpg:

http://masteroid.ru/files/matm/tmp178-2259.jpg.

Среднее время ожиданияhttp://masteroid.ru/files/matm/tmp178-2260.jpgполучим из формулы (26) приhttp://masteroid.ru/files/matm/tmp178-2261.jpg:

http://masteroid.ru/files/matm/tmp178-2262.jpg.

Наконец, среднее время пребывания заявки в СМО есть:

http://masteroid.ru/files/matm/tmp178-2263.jpg.




Многоканальная СМО с ожиданием

Система с ограниченной длиной очереди. Рассмотрим http://masteroid.ru/files/matm/tmp178-2264.jpgканальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью http://masteroid.ru/files/matm/tmp178-2265.jpg; интенсивность обслуживания (для одного канала) http://masteroid.ru/files/matm/tmp178-2266.jpg; число мест в очереди http://masteroid.ru/files/matm/tmp178-2267.jpg

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

нет очереди:

http://masteroid.ru/files/matm/tmp178-2268.jpgвсе каналы свободны;

http://masteroid.ru/files/matm/tmp178-2269.jpgзанят один канал, остальные свободны;

http://masteroid.ru/files/matm/tmp178-2270.jpgзаняты http://masteroid.ru/files/matm/tmp178-2271.jpg-каналов, остальные нет;

http://masteroid.ru/files/matm/tmp178-2272.jpgзаняты все http://masteroid.ru/files/matm/tmp178-2273.jpg-каналов, свободных нет;

есть очередь:

http://masteroid.ru/files/matm/tmp178-2274.jpgзаняты все n-каналов; одна заявка стоит в очереди;

http://masteroid.ru/files/matm/tmp178-2275.jpgзаняты все n-каналов, r-заявок в очереди;

http://masteroid.ru/files/matm/tmp178-2276.jpgзаняты все n-каналов, r-заявок в очереди.

ГСП приведен на рис. 9. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью http://masteroid.ru/files/matm/tmp178-2277.jpg, по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна http://masteroid.ru/files/matm/tmp178-2278.jpg, умноженному на число занятых каналов.

http://masteroid.ru/files/matm/tmp178-2279.jpg

Рис. 9. Многоканальная СМО с ожиданием


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

http://masteroid.ru/files/matm/tmp178-2283.jpg (29)

Относительная пропускная способность дополняет вероятность отказа до единицы:

http://masteroid.ru/files/matm/tmp178-2284.jpg

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

http://masteroid.ru/files/matm/tmp178-2285.jpg (30)

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

http://masteroid.ru/files/matm/tmp178-2288.jpg.

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

http://masteroid.ru/files/matm/tmp178-2289.jpg (31)

где http://masteroid.ru/files/matm/tmp178-2290.jpg.

Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (23), (24) — (26)), используя соотношение для нее, получаем:

http://masteroid.ru/files/matm/tmp178-2291.jpg

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

http://masteroid.ru/files/matm/tmp178-2292.jpg

Среднее время ожидания заявки в очереди.

http://masteroid.ru/files/matm/tmp178-2300.jpg (32)


Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди только множителем http://masteroid.ru/files/matm/tmp178-2301.jpg, т. е.

http://masteroid.ru/files/matm/tmp178-2302.jpg.

Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО http://masteroid.ru/files/matm/tmp178-2303.jpg.

Системы с неограниченной длиной очереди. Мы рассмотрели http://masteroid.ru/files/matm/tmp178-2304.jpgканальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m-заявок.

Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при http://masteroid.ru/files/matm/tmp178-2305.jpg.

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

http://masteroid.ru/files/matm/tmp178-2311.jpg

Среднее число заявок в очереди получим при http://masteroid.ru/files/matm/tmp178-2312.jpg из (31):

http://masteroid.ru/files/matm/tmp178-2313.jpg,

а среднее время ожидания — из (32): http://masteroid.ru/files/matm/tmp178-2314.jpg.

Среднее число занятых каналов http://masteroid.ru/files/matm/tmp178-2316.jpg.

Среднее число заявок http://masteroid.ru/files/matm/tmp178-2317.jpg.

Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью http://masteroid.ru/files/matm/tmp178-2318.jpg=0,8 (машин в минуту). Среднее время обслуживания одной машины:

http://masteroid.ru/files/matm/tmp178-2319.jpg

В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.

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

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

Пуассоновский «поток уходов» с интенсивностью: http://masteroid.ru/files/matm/tmp178-2333.jpg

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

нет очереди:

http://masteroid.ru/files/matm/tmp178-2334.jpgвсе каналы свободны;

http://masteroid.ru/files/matm/tmp178-2335.jpgзанят один канал;

http://masteroid.ru/files/matm/tmp178-2336.jpgзаняты два канала;

http://masteroid.ru/files/matm/tmp178-2337.jpgзаняты все n-каналов;

есть очередь:

http://masteroid.ru/files/matm/tmp178-2338.jpgзаняты все n-каналов, одна заявка стоит в очереди;

http://masteroid.ru/files/matm/tmp178-2339.jpgзаняты все n-каналов, r-заявок стоят в очереди и т. д.

Граф состояний и переходов системы показан на рис. 10.

http://masteroid.ru/files/matm/tmp178-2340.jpg

Рис. 10. СМО с ограниченным временем ожидания

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок http://masteroid.ru/files/matm/tmp178-2341.jpg. Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов http://masteroid.ru/files/matm/tmp178-2342.jpgплюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна http://masteroid.ru/files/matm/tmp178-2343.jpg.

Среднее число заявок в очереди: http://masteroid.ru/files/matm/tmp178-2354.jpg (35)

На каждую из этих заявок действует «поток уходов» с интенсивностью http://masteroid.ru/files/matm/tmp178-2355.jpg. Значит, из среднего числа http://masteroid.ru/files/matm/tmp178-2356.jpg-заявок в очереди в среднем будет уходить, не дождавшись обслуживания, http://masteroid.ru/files/matm/tmp178-2357.jpg-заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться http://masteroid.ru/files/matm/tmp178-2358.jpg-заявок. Относительная пропускная способность СМО будет составлять: http://masteroid.ru/files/matm/tmp178-2359.jpg

Среднее число занятых каналов http://masteroid.ru/files/matm/tmp178-2360.jpg по-прежнему получаем, деля абсолютную пропускную способность А на http://masteroid.ru/files/matm/tmp178-2361.jpg: http://masteroid.ru/files/matm/tmp178-2362.jpg (36)

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

http://masteroid.ru/files/matm/tmp178-2364.jpg,

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

http://masteroid.ru/files/matm/tmp178-2367.jpg.

Замкнутые СМО

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

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

Пусть n - число каналов обслуживания, s - число потенциальных заявок, n<s, hello_html_6bc7a4a8.gif - интенсивность потока заявок каждого потенциального требования, μ - интенсивность обслуживания:

ρ=hello_html_570b6741.gif.

Вероятность простоя системы определяется формулой

Р0=hello_html_m7ec6f1f0.gif.

Финальные вероятности состояний системы:

Pk=hello_html_m647324ea.gif при kk=hello_html_m185ecaf4.gif при hello_html_m447350ce.gif.

Через эти вероятности выражается среднее число занятых каналов

hello_html_mb0ec533.gif=P1+2P2+…+n(Pn+Pn+1+…+Ps) или

hello_html_mb0ec533.gif=P1+2P2+…+(n-1)Pn-1+n(1-P0-P1-…-Pn-1).

Через hello_html_mb0ec533.gif находим абсолютную пропускную способность системы:

A=hello_html_mb0ec533.gifhello_html_m558618cb.gif,

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

М=s-hello_html_74729d68.gif=s-hello_html_696d6210.gif.

Пример 1. На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью hello_html_6bc7a4a8.gif =4 заявки в минуту, время обслуживания заявки одним каналом tобсл=1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?

Пример 2. На вход трехканальной СМО с неограниченной очередью поступает поток заявок с интенсивностью hello_html_6bc7a4a8.gif=4 заявки в час, среднее время обслуживания одной заявки t=1/μ=0,5 ч. Найти показатели эффективности работы системы.

Для рассматриваемой системы n=3, hello_html_6bc7a4a8.gif=4, μ=1/0,5=2, ρ=hello_html_6bc7a4a8.gif/μ=2, ρ/n=2/3<1.

Задача 3:

Два рабочих обслуживают группу из четырех станков. Остановки работающего станка происходят в среднем через 30 мин. Среднее время наладки составляет 15 мин. Время работы и время наладки распределено по экспоненциальному закону.

Найдите среднюю долю свободного времени для каждого рабочего и среднее время работы станка.

Найдите те же характеристики для системы, в которой:

а) за каждым рабочим закреплены два станка;

б) два рабочих всегда обслуживают станок вместе, причем с двойной интенсивностью;

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



24


Автор
Дата добавления 22.11.2015
Раздел Другое
Подраздел Конспекты
Просмотров492
Номер материала ДВ-179279
Получить свидетельство о публикации
Похожие материалы

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