Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. МНОГОКАНАЛЬНАЯ СМО С ОЖИДАНИЕМ
  2. ОДНОКАНАЛЬНАЯ СМО С ОТКАЗАМИ
  3. СМО с ожиданием

Рассмотрим сначала простейшую из всех возможных СМО с ожи­данием – одноканальную систему (n = 1), на которую поступает поток заявок с интенсивностью λ; интенсивность обслуживания μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслужен­ных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Рис.4

 

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

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

S0 – канал свободен,

S1 – канал занят, очереди нет,

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

...........

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

...........

 

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

Граф состояний СМО показан на рис.4. Интенсивности потоков событий, переводящих в систему по стрелкам слева направо, все равны λ, а справа налево – μ. Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево – поток «ос­вобождений» занятого канала, имеющий интенсивность μ (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

Изображенная на рис.4 схема представляет собой схему «гибели и размножения». Пользуясь общим решением, данным для схемы ги­бели и размножения в предыдущем разделе, напишем выражения предельных ве­роятностей состояний:

(5.1)

Вводя обозначение ρ = λ/μ, перепишем формулы (5.1) в виде:

(5.2)

 

Заметим, что в знаменателе последней формулы (5.2) стоит геомет­рическая прогрессия с первым членом 1 и знаменателем ρ; суммируя эту прогрессию, находим:

(5.3)

Таким образом, формулы (5.2) окончательно примут вид:

(5.4)

Обратим внимание на то, что формула (5.3) справедлива только при ρ ≠ 1 (при ρ =1 она дает неопределенность вида 0/0). Но сумму геометрической прогрессии со знаменателем ρ =1 найти еще проще чем по формуле (5.3): она равна m + 2, и в этом случае р0 = 1/(m +2). Заметим, что тот же результат мы могли бы получить более сложным способом, раскрывая неопределенность (5.3) по пра­вилу Лопиталя.

Определим характеристики СМО: вероятность отказа Pотк, от­носительную пропускную способность q, абсолютную пропускную спо­собность А, среднюю длину очереди , среднее число заявок, связанных с системой .

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

Pотк = (5.5)

Находим относительную пропускную способность:

q = 1– Pотк = (5.6)

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

A = λ q.

Найдем среднее число заявок, находящихся в очереди; определим эту величину как математическое ожидание дискретной случайной ве­личины R – числа заявок, находящихся в очереди:

= M[R].

С вероятностью р2 в очереди стоит одна заявка, с вероятностью р3 две заявки, вообще с вероятностью рk в очереди стоят k – 1 заявок, на­конец, с вероятностью рm+1 в очереди стоят m заявок. Среднее число заявок в очереди получим, умножая число заявок в очереди на соот­ветствующую вероятность и складывая результаты:

= 1 ·р2+2· р3 + … + (k –1) · рk + … + m·рm+1 =

= 1 ·ρ2р0 + 2 ·ρ3р0 + … + (k –1) ρkр0 +… + m·ρm+1р0. (5.7)

Вынесем в этом выражении ρ2р0 за скобки:

= ρ2р0 [1+ 2 ρ + … + (k –1) ρk-2 + … + m-1 ]. (5.8)

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

= ρ + ρ2 + … + ρk-1 + … + ρm

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

(5.9)

Продифференцируем (5.9) по ρ:

Итак, выражение для суммы, стоящей в скобках в правой части (5.8), найдено:

1+ 2 ρ + … + (k –1) ρk-2 + … + m-1 = (5.10)

Подставляя его в (5.8), получим:

= ρ2р0

Учитывая выражение для р0 из (5.4), имеем:

или, окончательно,

(5.11)

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

K = R + Ω

где R – число заявок в очереди, Ω – число заявок под обслужива­нием.

По теореме сложения математических ожиданий

= M[K] = M[R] + M[ Ω ] = +

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

Величину мы только что нашли; найдем величину . Так как канал у нас один, то случайная величина Ω, может принимать только два значения: 0 или 1. Значение 0 она принимает, если канал свобо­ден; вероятность этого равна

Значение 1 она принимает, если канал занят; вероятность этого равна

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

= 0· p0 + 1·(1- p0) =

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

= + (5.12)

где величина определяется по формуле (5.11).

Выведем выражение еще для одной существенной характеристики СМО с ожиданием: среднего времени ожидания заявки в очереди. Обо­значим ож. Пусть заявка проходит в систему в какой-то момент времени. С вероятностью р0 канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероят­ностью p1 она придет в систему во время обслуживания какой-то заяв­ки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени l/μ (среднее время обслуживания одной заявки). С вероятностью р2 в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно 2/μ, и т. д. Вообще, с вероятностью pk пришедшая заявка застанет в системе k заявок и будет ждать в среднем k /μ единиц времени; здесь k может быть любым целым числом до m. Что же касается k = m + 1, т. е. случая, когда вновь приходящая заявка застает канал обслужи­вания, занятым и еще m заявок в очереди (вероятность этого рm+1), то время ожидания в этом случае также равно нулю, потому что заявка не становится в очередь (и не обслуживается) Поэтому среднее время ожидания будет:

ож =

Подставляя сюда выражения для p1,..., рm, получаем:

ож =

 

Преобразуем сумму в скобках, пользуясь формулой (5.10):

ож =

 

или, выражая р0 через ρ:

ож = (5.13)

 

Сравнивая это выражение с формулой (5.11), замечаем, что

ож = , (5.14)

 

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

Выведем еще формулу для среднего времени пребывания заявки в системе. Обозначим Tсист случайную величину – время пребыва­ния заявки в СМО. Эта случайная величина складывается из двух сла­гаемых (тоже случайных):

Tсист = Tож + Θ

где Tож – время ожидания заявки в очереди, Θ – случайная вели­чина, равная времени обслуживания Тоб, если заявка обслуживается, и нулю, если она не обслуживается (получает отказ). По теореме сложения математических ожиданий:

сист = M[ Tсист ] = M[ Tож ] + M[Θ],

но, в наших обозначениях, M[ Tож ] = ож, а M[Θ] = q об = q /μ. Отсю­да находим: сист = ож + q /μ, или, с учетом формулы (5.4),

сист = (5.15)

Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с од­ним каналом обслуживания (одной колонкой). Площадка при станции допу­скает пребывание в очереди на заправку не более трех машин одновременно m =3). Если в очереди уже находится три машины, очередная прибывшая к станции, в очередь не становится, а проезжает мимо. Поток машин, прибывающих для заправки, имеет интенсивность λ = 1 (машина в ми­нуту). Процесс заправки продолжается в среднем 1,25 мин. Определить:

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

- относительную и абсолютную пропускную способности GM0;

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

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

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

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


Решение. Находим приведенную интенсивность потока заявок:

μ= 1/1,25 = 0,8; ρ=λ/μ = 1/0,8=1,25.

По формулам (5.4):

p0 = , p1 = 1,25·0,122 0,125,

p2 = 1,25· p1 0,191, p3 = 1,25· p2 0,238,

 

p4 = 1,25· p3 0,297

 

Вероятность отказа Ротк 0,297.

Относительная пропускная способность СМО q = 1 – Ротк = 0,703.

Абсолютная пропускная способность СМО А = λ q = 0,703 (машины в мин.)

Среднее число машин в очереди находим по формуле (5.11)

т. е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.

Прибавляя к этой величине среднее число машин, находящихся под об­служиванием

получаем среднее число машин, связанных с АЗС:

= + 2,44

Среднее время ожидания машины в очереди, по формуле (5.14) равно

ож = = l,56 (мин).

Прибавляя к этой величине M[Θ] = q /μ = 0,703/0,8 0,88, получим сред­нее время, которое машина проводит на АЗС:

сист = 1,56 + 0,88 = 2,44 (мин).

 

 

До сих пор мы рассматривали работу одноканальной СМО с ожи­данием при ограниченном числе m мест в очереди.

Теперь снимем это ограничение, т. е. устремим m к бесконечности. При этом число возможных состояний системы станет бесконечным, и граф состояний примет вид, показанный на рис. 5.

Рис.5

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

Заметим, что при этом знаменатель в последней формуле (5.2) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится только, когда прогрес­сия бесконечно убывающая, т, е. при ρ < 1. Можно со­вершенно строго доказать, что ρ < 1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим; при ρ ≥ 1 такого режима не существует, и очередь при t →∞ растет до бесконечности.

Предположим, что

ρ = λ/μ < 1,

т. е. что предельный режим существует. Устремим в формулах (5.4) m к ∞ и выведем формулы для предельных вероятностей состояний в СМО без ограничений по длине очереди. Получим:

(5.16)

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q = 1, A = λ q =λ. Среднее число заявок в очереди получим из (5.11) при m →∞:

(5.17)

Среднее число заявок в системе по формуле (5.12) при m →∞ будет равно

= + ρ = . (5.18)

Среднее время ожидания ож также получим из формулы (5.14) при m →∞:

ож = (5.19)

или, в другой форме:

ож = (5.20)

Среднее время пребывания заявки в СМО равно среднему времени ожидания плюс среднее время обслуживания обсл = 1/μ:

сист = (5.21)

 

Пример 2. На железнодорожную сортировочную горку прибывают соста­вы с интенсивностью l = 2 (состава в час). Среднее время, в течение которого горка обрабатывает состав, равно 0,4 часа. Составы, прибывшие в момент, когда горка занята, становятся в очередь и ожидают в парке прибытия, где имеются три запасных пути, на каждом из которых может ожидать один состав. Состав, прибывший в момент, когда все три запасных пути в парке прибытия заняты, становится в очередь на внешний путь. Все потоки событий – простейшие.

Найти:

- среднее число составов, ожидающих очереди (как в парке прибытия, так и вне его);

- среднее время ожидания состава в парке прибытия и на внешних путях;

- среднее время нахождения состава на сортировочной станции (включая ожидание и обслуживание);

- вероятность того, что прибывший состав займет место на внешних путях;

Решение. В нашем случае l = 2, μ = 1/0,4 = 2,5, ρ = λ/μ = 2/2,5 = 0,8 < 1, и СМО в среднем «справляется» с поступающим на нее потоком зая­вок.

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

Среднее число составов, ожидающих очереди на внешних путях, подсчи­таем так: с вероятностью р5 вне парка прибытия будет ожидать один состав, с ве­роятностью р6 – два состава и т д., с вероятностью pk (k > 5) – (k – 4) состава.

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

= 1 p5 + 2 p6 + … + (k –4) pk + … = 1(1– ρ) ρ 5 + 2(1– ρ) ρ 6 + … +

+ … + (k – 4)(1– ρ) ρk + … = (1 – ρ) ρ 5 [1 + 2 ρ + 3 ρ2 + … ]

Формулу для бесконечной суммы в скобках получаем предельным переходом (при m →∞) из формулы (5.10):

1 + 2 ρ + 3 ρ2 + …= . (5.22)

Подставляя сюда ρ = 0,8, получим:

= 1,64.

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

p4 + p5 + p6 + … = (1 – ρ) ρ 4 + (1 – ρ) ρ 5 + (1 – ρ) ρ 6 + … =

= (1 – ρ) ρ 4 (1 + ρ + ρ2 + …) = ρ4 = 0,84 0,41

 

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

Для ρ = 0,8, μ = 2,5, получаем, что среднее время ожидания в парке прибытия равно

=0,78 (час) 47 (мин)

Что же касается среднего времени ожидания на внешних путях, то оно равно

т. е. для наших численных данных,

0,4×0,41/0,2=0,82 (час) 49 (мин).

Среднее время пребывания состава на сортировочной станции (считая ожи­дание и обслуживание) будет равно:

сист = 0,82 + 0,78 + 0,4 = 2 (час).

 


Дата добавления: 2015-07-08; просмотров: 186 | Нарушение авторских прав


Читайте в этой же книге: ЗАДАЧИ ТЕОРИИ МАССОВОГО ОБСЛУЖИВАНИЯ | КЛАССИФИКАЦИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ И ИХ ОСНОВНЫЕ ХАРАКТЕРИСТИКИ | ОДНОКАНАЛЬНАЯ СМО С ОТКАЗАМИ | СМО С ОГРАНИЧЕННЫМ ВРЕМЕНЕМ ОЖИДАНИЯ |
<== предыдущая страница | следующая страница ==>
МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ| МНОГОКАНАЛЬНАЯ СМО С ОЖИДАНИЕМ

mybiblioteka.su - 2015-2024 год. (0.028 сек.)