Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Другое / Конспекты / Конспект урока "Теория систем массового обслуживания"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Другое

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

библиотека
материалов

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


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

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

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

С отказами

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

С очередью

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

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

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

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

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

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

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

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















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

  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



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


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

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

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