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

31.01.2024

В коммерческой деятельности чаще встречаются СМО с ожиданием (очередью).

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

Граф этой СМО представлен на рис. 3.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения--гибели», с тем отличием, что при наличии только одного канала.

Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны

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

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

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

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

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

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

Для описания случайного процесса СМО можно воспользоваться изложенными ранее правилами и формулами. Напишем выражения, определяющие предельные вероятности состояний:

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

с= (1- с)

Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2).

Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании.

Действительно, выражение для предельной вероятности р0в случае т = 0 имеет вид:

pо = м / (л+м)

И в случае л =м имеет величину р0= 1 / 2.

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

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

Поэтому вероятность отказа определяется вероятностью появлением

Состояния Sm+1:

Pотк = pm+1 = сm+1 * p0

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

Q = 1- pотк = 1- сm+1 * p0

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

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

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

1 - в очереди стоит одна заявка,
2 - в очереди две заявки,

т-в очереди все места заняты

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

Таблица 1. Закон распределения дискретной случайной величины

Математическое ожидание этой случайной величины равно:

Lоч = 1* p2 +2* p3 +...+ m* pm+1

В общем случае при p ?1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:

Lоч = p2 * 1- pm * (m-m*p+1) * p0

В частном случае при р = 1, когда все вероятности pkоказываются равными, можно воспользоваться выражением для суммы членов числового ряда

1+2+3+ m = m(m+1)

Тогда получим формулу

L"оч= m(m+1) * p0 = m(m+1) (p=1).

Применяя аналогичные рассуждения и преобразования, можно показать, что среднее время ожидания обслуживания заявки а очереди определяется формулами Литтла

Точ = Lоч/А (при р? 1) и Т1оч= L"оч /А(при р = 1).

Такой результат, когда оказывается, что Точ ~ 1/ л, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина Lоч является функцией от л и м и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.

Заявка, поступившая в СМО в момент времени, когда все каналы заняты, получает отказ, и, следовательно, время ее «ожидания» в СМО равно нулю. Это приводит в общем случае (при р? 1) к уменьшению Точростом л, поскольку доля таких заявок с ростом л увеличивается.

Если отказаться от ограничения на длину очереди, т.е. устремить m--> >?, то случаи р < 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду

При достаточно большом к вероятностьpk стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А --л Q -- л следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:

Lоч =p2 1-p

а среднее время ожидания по формуле Литтла

Точ = Lоч/А

В пределе р << 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t > ?). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки.

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

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

Lсмо= m+1 ;2

Тсмо= Lсмо; при p ?1

A тогда среднее время пребывания заявки в системе массового обслуживания (как в очереди, так и под обслуживанием) равно:

Тсмо= m+1 при p ?1 2м

Среди СМО с очередью различают замкнутые и разомкнутые системы.

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

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

Рассмотрим одноканальную СМО с очередью, на которую не наложены никакие ограничения. Интенсивность входного потока требований равна λ , а интенсивность обслуживания μ . Необходимо найти предельные вероятности состояний и показатели эффективности СМО. Система может находиться в одном из состояний S 0 , S 1 , S 2 ,..., S k по числу требований, находящихся в ней:

S 0 - канал свободен;

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

S 2 - канал занят, одно требование стоит в очереди;

S k - канал занят, (к –1) требований стоят в очереди.

Граф состояний СМО имеет вид:

λ λ λ λ λ

μ μ μ μ μ

Если a <1, т.е. среднее число поступающих требований меньше среднего числа обслуженных требований, то предельные вероятности существуют и очередь не может расти бесконечно. Если a ≥1, то очередь растет до бесконечности. Итак, предполагаем что a <1.

Предельные вероятности состояний определяются по формулам: (6.16)

Вероятность того, что канал обслуживания свободен, т.е. система находится в состоянии ; (6.17)

Вероятность того, что канал занят, но очереди нет;

Вероятность того, что канал занят и очереди 1 требование и т.д.

Вероятность того, что СМО находится в состоянии

Среднее число требований в системе определяется по формуле:

Средняя длина очереди L оч :

Среднее время пребывания в системе Т сист :

Среднее время пребывания в очереди Т оч :

Вероятность того, что канал занят

Пример: На АЗС с одной бензоколонкой прибывают на заправку автомобили с интенсивностью 24 машины в час, а среднее время заправки одного автомобиля составляет 2 минуты. Определить показатели эффективности работы АЗС.

Решение: n =1, l =24 автом/час, t =2мин. Находим величину Значения l и t имеют различную временную размерность, поэтому преобразуем одно из них.

l =24 автом/час=24 автом/60мин=0,4автом/мин.

Тогда, a =0,4×2=0,8.

Так как a <1, то очередь на заправку не может возрастать бесконечно и предельные вероятности существуют.

1. Вероятность того, что бензоколонка свободна находим по формуле (6.17): P 0 =1–a= 1–0,8=0,2.

2. Вероятность того, что бензоколонка занята заправкой автомобилей, находим по формуле (6.22): P зан =a =0,8.

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

4. Среднее время ожидания заправки вычисляется по формуле (6.21):

5. Среднее число автомобилей, находящихся на АЗС, вычисляется по формуле (6.18):

6. Среднее время пребывания автомобиля на АЗС вычисляется по формуле (6.20):

Из вычислений видно, что эффективность работы АЗС хорошая.

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

На n одинаковых каналов поступает простейший поток заявок интенсивностью λ . Если в момент поступления заявки все каналы заняты, то эта заявка становится в очередь и ждет начала облуживания. Время обслуживания каждой заявки является случайной величиной, которая подчиняется экспоненциальному закону распределения с параметром μ .

Расчетные формулы
Вероятность того, что все каналы свободны

Вероятность того, что занято k каналов, при условии, что общее число заявок, находящихся на обслуживании, не превосходит числа каналов,

Вероятность того, что в системе находится k заявок, в случае, когда их число больше числа каналов,

Вероятность того, что все каналы заняты,

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

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

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

Пример
Автозаправочная станция с двумя колонками обслуживает пуассоновский поток машин с интенсивностью λ=0,8 машин в минуту. Время обслуживания одной машины подчиняется показательному закону со средним значением 2 минуты. В данном районе нет другой АЗС, так что очередь перед АЗС может расти практически неограниченно. Найдите:
1) среднее число занятых колонок;
2) вероятность отсутствия очереди у АЗС;
3) вероятность того, что придется ждать начала обслуживания;
4) среднее число машин в очереди;
5) среднее время ожидания в очереди;
6) среднее время пребывания машины на АЗС;
7) среднее число машин на АЗС.
Решение . По условию задачи n=2, λ=0.8; μ=1/t обсл =0.5; ρ=λ/μ=1.6
Поскольку ρ /n =0,8<1, то очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы системы массового обслуживания.
Находим вероятности состояний СМО:

Среднее число занятых колонок:
N зан =n-N 0 = 2-(2·p 0 +1·p 1) = 2-2·0.1111 - 0.1778 = 1.6
Вероятность отсутствия очереди у АЗС:

Вероятность того, что придется ждать начала обслуживания равна вероятности того, что все колонки заняты:
p 0 +p 1 +p 2 = 0.1111+0.1778+0.1422 = 0.4311
Среднее число машин в очереди:

Среднее время ожидания в очереди:
Среднее время пребывания машины на АЗС:
t преб =t обсл +t ож = 2+3.5556 = 5.5556 мин.
Среднее число машин на АЗС:
N зан +L оч = 1.6+2.8444 = 4.4444
Рассмотрим одноканальную СМО с ожиданиями, в которой число каналов равно единице n = 1, интенсивность поступления заявок – λ, интенсивность обслуживания равна μ. Заявка, поступившая в тот момент времени, когда канал занят, становится в очередь и ждет обслуживания. Количество мест в очереди ограничено и равно m . Если все места в очереди заняты, то заявка покидает очередь не обслуженной. Проанализируем состояние системы:

S 0 – канал свободен;
S 1 – канал занят;
S 2 – канал занят, одна заявка в очереди;
S k – канал занят, (k–1) заявок в очереди;
S m + 1 – канал занят, в очереди m заявок.

Изобразим граф состояний такой СМО (рис. 25).

Рис. 25
По формулам Эрланга найдем вероятности событий, состоящих в том, что СМО находится в состоянии S 1 , S 2 , …, S m+1:
(28)

При этом вероятность того, что заявка, прибывшая в систему, найдет ее свободной, равна
. (29)
Отношение интенсивности поступления заявок λ к интенсивности обслуживания заявок μ есть приведенная интенсивность μ, т.е.

ρ=λ/μ
Произведем замену в формулах (28) и (29) отношения λ/&mu на ρ, тогда выражения примут вид:

(30)
Вероятность Р 0 будет вычисляться по следующей формуле:
p 0 = -1 . (31)
Выражение для вероятности P 0 есть геометрическая прогрессия, сумма которой будет равна

.
Таким образом, формулы (30) и (31) позволяют определить вероятность любого события, которое может произойти в системе, т. е. определить вероятность нахождения системы в любом состоянии.
Формула для P 0 справедлива для случая, когда ρ ≠ 1 . В случае, когда ρ = 1 , т. е. интенсивность поступления заявок равна интенсивности их обслуживания, используется другая формула для вычисления вероятности того, что система свободна:

,
где m – это количество заявок, находящихся в очереди.

Определим характеристики эффективности одноканальной СМО :

вероятность того, что очередная заявка, прибывшая в систему, получит отказ Р отк;
абсолютную пропускную способность А ,
относительную пропускную способность Q ,
число занятых каналов k ,
среднее число заявок в очереди r ,
среднее число заявок, связанных с СМО, z .

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

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

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

A=Q·λ (34)
Таким образом, по формулам (32), (33), (34) можно вычислить основные показатели эффективности для любой системы массового обслуживания. теперь выведем выражения для вычисления характеристик, присущих лишь данной СМО.
Среднее число заявок в очереди r определим как математическое ожидание дискретной случайной величины, где R – число заявок в очереди.
♦ Р 2 – это вероятность того, что в очереди на обслуживание находится одна заявка;
♦ Р 3 – вероятность того, что в очереди две заявки;
♦ Р k – вероятность того, что в очереди (k–1) заявка;
♦ Р m + 1 – вероятность того что в очереди m заявок.
Тогда среднее число заявок в очереди можно вычислить следующим образом:
r =1·P 2 +2·P 3 + ... +(k-1)·P k + ... +m·P m+1 . (35)
Подставим в формулу (35) найденные ранее значения вероятностей, вычисленные в формуле (30):
r =1·ρ 2 ·p 0 +2·ρ 3 ·p 0 + ... +(k-1)·ρ k ·p 0 + ... +m·ρ m+1 ·p 0 . (35)
Вынесем за скобку вероятность P 0 и Р 2 , тогда получим итоговую формулу для вычисления среднего числа заявок в очереди на обслуживание:
r =ρ 2 ·p 0 (1+2·ρ+ ... +(k-1)·ρ k-2 + ... +m·ρ m-1)
Выведем формулу для среднего числа заявок, связанных с СМО, z , т. е. число заявок в очереди, находящихся на обслуживании. Рассмотрим общее число заявок, связанных с СМО, z как сумму двух величин среднего числа заявок в очереди r и числа занятых каналов k :

z = r +k .
Так как канал один, то число занятых каналов k может принимать значения 0 или 1. Вероятность того, что k = 0, т.е. система свободна, соответствует вероятности Р 0 , значение которой можно найти по формуле (31). Если k = 1, т.е. канал занят обслуживанием заявки, но места в очереди еще есть, то вероятность этого события можно вычислить по формуле

.
Следовательно, z будет равно:

. (37)

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

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью l. Интенсивность потока обслуживания равна m (т. е. в среднем непрерывно занятый канал будет выдавать m. обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживании является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.
Граф состояний СМО в этом случае имеет вид, показанный на Рис. 3.2.

Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)
Состояния СМО имеют следующую интерпретацию:
S 0 - канал свободен
S 1 - канал занят (очереди нет);
S 2 - канал занят (одна заявка стоит в очереди);
………………………………
S n - канал занят (n - 1 заявок стоит в очереди);
……………………………
S N - канал занят (N - 1 заявок стоит в очереди).
Стационарный провес в данной системе будет описываться следующей системой алгебраических уравнений :

п - номер состояния.
Решение приведенной выше системы уравнений (3.10) для нашей модели СМО имеет вид

Следует отметить, что выполнение условия стационарности для данной СМО необязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превышать N - 1), а не соотношением между интенсивностями входного потока, т. е. не отношением
l/m = p
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N - 1):

Рассмотрим пример одноканальной СМО с ожиданием.
Пример 3.2. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограничено и равно 3 [(N - 1) = 3]. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность l = 0,85 (автомобиля в час). Время диагностики автомобиля распределено по показательному закону и в среднем равно 1,05 час.
Требуется определить вероятностные характеристики поста диагностики, работающего в стационарном режиме.
Решение
1. Параметр потока обслуживании автомобилей:

2. Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей l и m, т. е.

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

P 1 =ρ·P 0 = 0.893·0.248 = 0.221
P 2 =ρ 2 ·P 0 = 0.893 2 ·0.248 = 0.198
P 3 =ρ 3 ·P 0 = 0.893 3 ·0.248 = 0.177
P 4 =ρ 4 ·P 0 = 0.893 2 ·0.248 = 0.158
4. Вероятность отказа в обслуживании автомобиля:
P отк =P 4 =ρ 4 ·P 0 ≈ 0.158
5. Относительная пропускная способность поста диагностики:
q=1-P отк = 1-0.158 = 0.842
6. Абсолютная пропускная способность поста диагностики
A=λ·q = 0.85·0.842 = 0.716 (автомобиля в час)
7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

8. Среднее время пребывания автомобиля в системе:
9. Средняя продолжительность пребывания заявки в очереди на обслуживание:
W q =W S -1/μ = 2.473-1/0.952 = 1.423 часа
10. Среднее число заявок в очереди (длина очереди): L q = А,(1 - P N) W q = 0,85
L q =λ(1-P N)·W q = 0.85·(1-0.158)·1.423 = 1.02
Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обслуживает автомобили в среднем в 15,8% случаев (Р отк = 0,158). В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей - абсолютной А и относительной Q пропускной способности, вероятности отказа P отк. , среднего числа занятых каналов (для многоканальной системы) будем рассматривать также следующие: L сист. - среднее число заявок системе; Т сист. - среднее время пребывания заявки в системе; L оч. - среднее число заявок в очереди (длина очереди); Т оч. - среднее время пребывания заявки в очереди; Р зан.. - вероятность того, что канал занят (степень загрузки канала).

Одноканальная система с неограниченной очередью

На практике часто встречаются одноканальные СМО с неограниченной очередью (например, телефон-автомат с одной будкой).
Рассмотрим задачу.
Имеется одноканальная СМО с очередью, на которую не наложены никакие ограничения (ни по длине очереди, ни по времени ожидания). Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ. Необходимо найти предельные вероятности состояний и показатели эффективности СМО.
Система может находиться в одном из состояний S 0 , S 1 , S 2 , …, S k , по числу заявок, находящихся в СМО: S 0 - канал свободен; S 1 - канал занят (обслуживает заявку), очереди нет, S 2 - канал занят, одна заявка стоит в очереди; ... S k - канал занят, (k-1) заявок стоят в очереди и т.д.
Граф состояний СМО представлен на рис. 8.

Рис. 8
Это процесс гибели и размножения, но с бесконечным числом состояний, в котором интенсивность потока заявок равна λ, а интенсивность потока обслуживании μ.
Прежде чем записать формулы предельных вероятностей, необходимо быть уверенным в их существовании, ведь в случае, когда время t→∞, очередь может неограниченно возрастать. Доказано, что если ρ<1, т.е. среднее число приходящих заявок меньше среднего числа обслуженных заявок (в единицу времени), то предельные вероятности существуют. Если ρ≥1, очередь растет до бесконечности.

Для определения предельных вероятностей состояний воспользуемся формулами (16), (17) для процесса гибели и размножении (здесь мы допускаем известную нестрогость, так как ранее эти формулы были получены для случая конечного числа состояний системы). Получим(32)
Так как предельные вероятности существуют лишь при ρ < 1, то геометрический ряд со знаменателем
ρ < 1, записанный в скобках в формуле (32), сходится к сумме, равной . Поэтому
p 0 =1-ρ, (33)
и с учетом соотношений (17)
p 1 =ρ·p 0 ; p 2 =ρ 2 ·p 0 ; ... ; p k =ρ k ·p 0 ; ...
найдем предельные вероятности других состояний
p 1 =ρ·(1-ρ); p 2 =ρ 2 ·(1-ρ); ... ; p k =ρ k ·(1-ρ); ... (34)
Предельные вероятности p 0 , p 1 , p 2 , …, p k ,… образуют убывающую геометрическую профессию со знаменателем р < 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Среднее число заявок в системе L сист. определим по формуле математического ожидания, которая с учетом (34) примет вид
(35)
(суммирование от 1 до ∞, так как нулевой член 0·p 0 =0).
Можно показать, что формула (35) преобразуется (при ρ < 1) к виду
(36)
Найдем среднее число заявок в очереди L оч. Очевидно, что
L оч =L сист -L об (37)
где L об. - среднее число заявок, находящихся под обслуживанием.
Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):
L оч =0·p 0 +1·(1-p 0)
т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:
L оч =P зан =1-p 0 , (38)
В силу (33)
L оч =P зан ρ, (39)
Теперь по формуле (37) с учетом (36) и (39)
(40)
Доказано, что при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе (очереди) равна среднему числу заявок в системе (в очереди), деленному на интенсивность потока заявок, т.е.
(41)
(42)
Формулы (41) и (42) называются формулами Литтла. Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих ее: оба потока заявок имеют одну и ту же интенсивность λ.
На основании формул (41) и (42) с учетом (36) и (40) среднее время пребывания заявки в системе определится по формуле:
(43)
а среднее время пребывания заявки в очереди
(44)

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

Стационарный режим функционирования данной СМО существует при t→∞ для любого п=0,1,2,… и когда l < m.Система алгебраических уравнений, описывающих работу СМО при t®¥ для любого n = 0, 1, 2...., имеет вид
Решение данной системы уравнений имеет вид
P n =(1-ρ)·ρ n , n=0,1,2,... (3.21)
где ρ=λ/μ < 1
Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:
среднее число находящихся в системе клиентов (заявок) на обслуживание:
средняя продолжительность пребывания клиента в системе:

Пример 3.3. Вспомним о ситуации, рассмотренной в пример 3.2, где речь идет о функционировании поста диагностики. Пусть рассматриваемый пост диагностики располагает неограниченны» количеством площадок для стоянки прибывающих на обслуживание автомобилей, т. е. длина очереди не ограничена.
Требуется определить финальные значения следующих вероятностных характеристик:

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

Решение
1. Параметр потока обслуживания m и приведенная интенсивность потока автомобилей р определены в примере 3.2:
m = 0,952; p = 0,893.
2. Вычислим предельные вероятности системы по формулам
P 0 =1-ρ = 1-0.893 = 0.107
P 1 =(1-ρ)·ρ = (1-0.893)·0.893 = 0.096
P 2 =(1-ρ)·ρ 2 = (1-0.893) 2 ·0.893 = 0.085
P 3 =(1-ρ)·ρ 3 = (1-0.893) 3 ·0.893 = 0.076
P 4 =(1-ρ)·ρ 4 = (1-0.893) 4 ·0.893 = 0.068
P 5 =(1-ρ)·ρ 5 = (1-0.893) 5 ·0.893 = 0.061
и т.д.
Следует отметить, что Р о определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 10,7%, так как Р о = 0,107.
3. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):
4. Средняя продолжительность пребывания клиента в системе:

6. Средняя продолжительность пребывания автомобиля в очереди-
7. Относительная пропускная способность системы:
т. е. каждая заявка, пришедшая в систему, будет обслужена.
8. Абсолютная пропускная способность: А = lq = 0,85·1 = 0,85
Следует отметить, что предприятие, осуществляющее диагностику автомобилей, прежде всего интересует количество клиентов, которое посетит пост диагностики при снятии ограничения на длину очереди.
Допустим, в первоначальном варианте количество мест для стоянки прибывающих автомобилей было равно трем (см. пример 3.2). Частота m возникновения ситуаций, когда прибывающий на пост диагностики автомобиль не имеет возможности присоединиться к очереди:

т = l P N

В нашем примере при N = 3 + 1 = 4 и р = 0,893,
m = l Р о р 4 = 0,85·0,248·0,8934·0,134 автомобиля в час.
При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12·0,134 = 1,6 автомобиля.
Снятие ограничения на длину очереди позволяет увеличить количество обслуженных клиентов в нашем примере в среднем на 1,6 автомобиля за смену (12 ч. работы) поста диагностики. Ясно, что решение относительно расширения площади для стоянки автомобилей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей клиентов при наличии всего трех мест для стоянки этих автомобилей.

Многоканальная СМО с неограниченной очередью

Рассмотрим задачу. Имеется n-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность λ, а поток обслуживании - интенсивность μ. Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.

Система может находиться в одном из состояний S 0 , S 1 , S 2 ,…, S k ,…, S n ,…, - нумеруемых по числу заявок, находящихся в СМО: S 0 - в системе нет заявок (все каналы свободны); S 1 - занят один канал, остальные свободны; S 2 - заняты два канала, остальные свободны;..., S k - занято k каналов, остальные свободны;..., S n - заняты все n каналов (очереди нет); S n+1 - заняты все n каналов, в очереди одна заявка;..., S n+r - заняты все n каналов, r заявок стоит в очереди,....

Граф состояний системы показан на рис. 9. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживаний (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины m до nm, так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем n, интенсивность потока обслуживании сохраняется равной nm.

среднее число заявок в очереди
, (50)
среднее число заявок в системе
L сист =L оч +ρ, (51)
Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (42) и (41).
Замечание. Для СМО с неограниченной очередью при r < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа P отк = 0, относительная пропускная способность Q =1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. А =l.

СМО с ограниченной очередью

СМО с ограниченной очередью. СМО с ограниченной очередью отличаются от рассмотренных выше задач лишь тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка поступает в момент, когда все места в очереди заняты, она покидает СМО необслуженной, т.е. получает отказ.
Очевидно: для вычисления предельных вероятностей состояний и показателей эффективности таких СМО может быть использован тот же подход, что и выше, с той разницей, что суммировать надо не бесконечную прогрессию (как, например, мы делали при выводе формулы (33)), а конечную.
Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (44) и (43).
СМО с ограниченным временем ожидания. На практике часто встречаются СМО с так называемыми "нетерпеливыми" заявками. Такие заявки могут уйти из очереди, если время ожидания превышает некоторую величину. В частности, такого рода заявки возникают в различных технологических системах, в которых задержка с началом обслуживания может привести к потере качества продукции, в системах оперативного управления, когда срочные сообщения теряют ценность (или даже смысл), если они не поступают на обслуживание в течение определенного времени.

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

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

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

Предельные вероятности:

, , . . . , , ,…, ,… (10)

Вероятность того, что заявка окажется в очереди:

(11)

(13)

Среднее время нахождения в очереди:

(15)

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

Рассмотрим пример решения задачи многоканальной СМО с ожиданием.

Задача . В магазине к кассам поступает поток покупателей с интенсивностью 81 человек в час. Средняя продолжительность обслуживания кассиром одного покупателя tобсл = 2 мин. Определить предельные вероятности состояний и характеристики обслуживания узла расчета.

По условию λ=81(чел./час)= 81/60=1,35 (чел./мин.). По формулам (1, 2):

= λ/μ= λ * tобсл = 1,35 * 2 = 2,7

<1, т.е. при n > = 2,7. Таким образом, минимальное количество кассиров n =3.

Найдем характеристики обслуживания СМО при n=3.

Вероятность того, что в кассах отсутствуют покупатели, по формуле (9):

= (1+2,7+2,7 /2!+2,7 /3!+2,7 /3!(3-2,7)) = 0,025

В среднем 2,5 % времени кассиры будут простаивать.

Вероятность того, что в кассах будет очередь, определим по формуле (11):

P = (2,7 /3!(3-2,7))0,025 = 0,735

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

L = (2,7 /(3*3!(1-2,7/3) ))*0,025 = 7,35 (чел.)

T =7,35/1,35 = 5,44 (мин.)

Определим среднее число покупателей в кассах по формуле (15):

L =7,35+2,7=10,05 (чел.)

Среднее время нахождения покупателей в кассах находится по формуле (16):

T =10,05/1,35=7,44 (мин)

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

Коэффициент (доля) занятых обслуживанием кассиров вычисляется по следующей формуле:

Абсолютная пропускная способность узла расчета A=1,35 (чел./мин), или 81 (чел./час), т.е. 81 покупатель в час. Анализ характеристик обслуживания свидетельствует о значительной перегрузке касс при наличии трех кассиров.

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

Имеется n-канальная СМО с ограниченной очередью. Число заявок в очереди ограничено числом m. Если заявка поступает в момент, когда в очереди уже m заявок, она не обслуживается. Такая СМО характеризуется следующими показателями :

Предельные вероятности:

(17)

, , . . . , , ,…, (18)

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

(19)

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

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

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

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

(23)

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

Пример оптимизации СМО

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

Задача.

Определить оптимальное количество причалов в порту с минимальными затратами, если известно, что за год было обслужено 270 судов. Разгрузка одного судна длится в среднем 12 часов. Пеня за простой судна в порту составляет 100 тыс.р./сут.. Затраты на причал 150 тыс.р./сут. Расчеты приведены в таблице.

Решение.

По условию

λ=270(судов/год)=270/360=0,75(судов/сут.),

tобсл=12ч=12/24=0,5 сут.

По формулам (1, 2):

= λ/μ= λ * tобсл = 0,75 * 0,5 = 1,5

Очередь не будет возрастать до бесконечности при условии /n <1, т.е. при n > = 1,5. Таким образом, минимальное количество причалов n =2.

Найдем характеристики обслуживания СМО порта при количестве причалов n=2.

Вероятность того, что в порту отсутствуют суда, вычислим по формуле (9):

В среднем 1,4 % времени причалы будут простаивать.

Среднее число судов, находящихся в очереди рассчитывается по формуле (13):

Среднее время ожидания в очереди вычисляется по формуле (14):

T =1,93/0,75 = 2,57 (сут.)

Определим среднее число судов в порту по формуле (15):

L =1,93+1,5=3,43 (судна)

Среднее время нахождения судов в порту находится по формуле (16):

T =3,43 /0,75 =4,57 (сут)

Среднее число занятых причалов (12) =1,5.

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

Найдем суммарную пеню за простой судов в порту в сутки. Для этого перемножим пеню за простой судна в порту и среднее число судов в очереди:

= * L .

Определим затраты по обслуживанию причалов в сутки: = *n.

Для двух причалов в сутки

Суммарные затраты составят: С= + =193+300=493(ден.ед.)

Суммарные затраты по условию задачи должны быть минимальны.

Рассчитаем суммарные затраты для количества причалов n = 2, 3, 4. Расчеты приведены в таблице. Как видно из таблицы, минимальные затраты достигаются при n = 3. Следовательно, для минимизации затрат необходимо 3 причала.

Таблица 1.- Расчет оптимального числа причалов

Показатель	Количество причалов

Интенсивность потока судов	0,75	0,75	0,75
Интенсивность обслуживания судов	0,5	0,5	0,5
Интенсивность нагрузки причала	1,5	1,5	1,5
Вероятность, что все причалы свободны	0,14	0,21	0,22
Среднее число судов в очереди	1,93	0,24	0,04
Среднее время пребывания судна в очереди, сут.	2,57	0,32	0,06
Среднее число судов в порту	3,43	1,74	1,54
Среднее время пребывания судна в порту, сут	4,57	2,32	2,06
Пеня за простой судна в порту, ден.ед./сут. ()	100,00	100,00	100,00
Затраты по обслуживанию причала в сутки, ден.ед./сут. ()	150,00	150,00	150,00
Суммарная пеня за простой судов в порту в сутки, ден.ед. ()	192,86	23,68	4,48
Суммарные затраты по обслуживанию причалов в сутки, ден.ед. ()	300,00	450,00	600,00
Суммарные затраты, ден.ед.(С)	492,86	473,68	604,48

Варианты заданий

Таблица 2 - Варианты заданий

Номер варианта

Задача
Номер варианта

Задача

1. В парикмахерской в зависимости от сложности стрижки, мастер выполняет работу в среднем за 30 мин. Посетители приходят в среднем через 25 мин. За каждый час работы мастер зарабатывает 300 ден.ед.. Очередь ограничена до 4 человек. Если в очереди больше 4 человек, клиент уходит, и потери за час составляют 150 ден.ед. Определить предельные вероятности состояний и характеристики обслуживания. Определить оптимальное количество мастеров.

2. Автомобили подъезжают на АЗС со средней частотой 2 автомобиля за 5 минут. Заправка автомобиля в среднем длится 3 минуты. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество колонок, чтобы средняя длина очереди не превышала 3 авт.

3. Рассматривается круглосуточная работа пункта проведения профилактического осмотра автомашин. На осмотр и выявление дефектов каждой машины затрачивается в среднем 30 минут. На осмотр поступает в среднем 36 машин в сутки. Если машина, прибывшая в пункт осмотра, не застает ни одного канала свободным, она покидает пункт осмотра не обслуженной. Определить вероятности состояний и характеристики обслуживания профилактического пункта осмотра. Определить количество каналов, чтобы относительная пропускная способность была не меньше 0,8.

4. В срочной мастерской по починке обуви в зависимости от сложности ремонта мастеру требуется в среднем 15 мин. Посетители приходят в среднем через каждые 14 мин. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество мастеров, чтобы средняя длина очереди не превышала 5 заказов.

5. В справочной оператор дает справку в среднем за 4 мин. Звонки поступают каждые 3мин. Если операторы заняты, то звонок не обслуживается. Определить вероятности состояний и характеристики обслуживания справочной. Определить количество каналов, чтобы относительная пропускная способность была не меньше 0,75.

6. В зависимости от количества продуктов у покупателя кассиру в магазине требуется в среднем на один чек 2 мин. Покупатели подходят к кассе с интенсивностью 81 человек/час. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество кассиров, чтобы средняя длина очереди не превышала 4 покупателей.

7. Диспетчеру в АТП в зависимости от типа автомобиля требуется в среднем на выдачу одного маршрутного листа 20 минут. Заявки на автомобили поступают в среднем через каждые 30 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество диспетчеров, чтобы средняя длина очереди не превышала 2 заявок.

8. Требуется оценить работу АТС. Если все линий связи заняты, то абонент выбывает из системы. Звонки поступают с интенсивностью 2 вызов/мин.. Продолжительность разговоров распределена экспоненциально, и в среднем равна 1,5 мин. Определить предельные вероятности и показатели эффективности системы. Определить количество операторов, чтобы относительная пропускная способность АТС была не меньше 0,9.

9. В банке в зависимости от сложности запроса клиента кассиру требуется в среднем 10 минут. Клиенты подходят к нему в среднем через каждые 12 минут. Кассир зарабатывает 15000 ден.ед. за месяц. Очередь ограничена до 6 человек. Если в очереди больше 6 человек, клиент уходит, и потери за час составляют 200 ден.ед. Определить предельные вероятности состояний и характеристики обслуживания. Определить оптимальное количество кассиров.

10. В среднем на одну транзакцию у банкомата уходит 2 минуты. Клиенты подходят к нему в среднем через каждые 20 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество банкоматов, чтобы средняя длина очереди не превышала 2 человек.

11. В магазине продавцу в зависимости от покупателя требуется в среднем на одну покупку 10 мин. Покупатели подходят к нему в среднем через каждые 5 мин. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество продавцов, чтобы средняя длина очереди не превышала 5 человек.

12. В отделе заказов мебельной фабрики менеджеру по продажам в зависимости от заказа клиента требуется в среднем на оформление одного заказа 25 минут. Клиенты приходят в среднем через каждые 30 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество менеджеров, чтобы средняя длина очереди не превышала 3 человек.

Порядок выполнения работы

1.Рассчитайте в системе Excel показатели системы массового обслуживания по формулам, приведенным в методичке. Количество каналов обслуживания n=1, 2, 3...k перебирается для нахождения оптимального значения по варианту. Предполагается, что входные потоки и обслуживание соответствуют пуассоновскому распределению.

2.Проведите анализ полученных результатов.

3.Составьте отчет.

1) Цель работы;

2) постановка задачи;

3) результаты расчетов, проведенных в Excel;

4) выводы по выполнению работы.

Контрольные вопросы

1. Что включает в себя понятие система массового обслуживания?

2. Какие существуют виды систем массового обслуживания?

3. Что относится к основным характеристикам и показателям эффективности систем массового обслуживания?

4. Укажите основные свойства (характеристики) входящего потока требований?

5. Перечислите основные особенности и характеристики систем массового обслуживания с ожиданием?

6. Каковы основные характеристики СМО с отказами?

7. Приведите примеры различных видов СМО?

Библиографический список

1. Афанасьев М.Ю. Исследование операций в экономике: модели, задачи, решения. / М.Ю. Афанасьев, Б.П. Суворов.- М.:ИНФРА, 2003.-444с.

2. Вентцель Е.С. Исследование операций. Задачи, приниципы, методология./ Е.С. Вентцель.-М.: Высшая школа, 2001.-208с.

3. Зайченко Ю.П. Исследование операций./ Ю.П. Зайченко.- К.: Вища школа, 1975.-320с.

4. Конюховский П.В. Математические методы исследования операций. / П.В. Конюховский.- СПб.: Питер, 2001.-192с.

5. Кремер Н.Ш., Путко Б.А. Исследование операций в экономике./ Н.Ш. Кремер, Б.А. Бутко, И.М. Тришин.- М.:Банки и биржи, ЮНИТИ, 1997.-407с.

1. Кудрявцев Е.М. GPSS World.Основы имитационного моделирования различных систем.- М.: ДМК Пресс, 2004.- 320 с.

2. Советов В.Я., Яковлев С.А. Моделирование систем. - М.: Высшая школа, 1985

3. Советов В.Я., Яковлев С.А. Моделирование систем: курсовое проектирование. - М.: Высшая школа, 1989

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

Алгоритм рассмотрения СМО с неограниченной очередью.

Постановка задачи.

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

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

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

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

Мы рассмотрим здесь классическую задачу теории массового обслуживания в тех условиях, в каких она была рассмотрена и решена К.Эрлангом. на n одинаковых приборов поступает простейший поток требований интенсивности. Если в момент поступления имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь прибывшее требование становится в очередь за всеми теми требованиями, которые поступили раньше и ещё не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживанию очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент времени не более одного требования. Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x). Предполагается, что при x0.

где - постоянная.

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

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

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

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

А так как всегда и

и, следовательно,

Требуемое доказано.

Несомненно, что в реальной обстановке показательное время обслуживания является, как правило, лишь грубым приближением к действительности. Так, нередко время обслуживания не может быть меньше, чем некоторая определенная величина. Пред-положение же (1) приводит к тому, что значительная доля тре-бовании нуждается лишь в кратковременной операции, близкой к 0. Позднее перед нами возникает задача освобождения от излишнего ограничения, накладываемого предположением (1). Необходимость этого была ясна уже самому Эрлангу, и он в ряде работ делал усилия найти иные удачные распределения для дли-тельности обслуживания. В частности, им было предложено так называемое распределение Эрланга, плотность распределения ко-торого дается формулой

где > 0, a k -- целое положительное число.

Распределение Эрланга представляет собой распределение суммы k- независимых слагаемых, каждое из которых имеет рас-пределение (1).

Обозначим для случая распределения (1) через время обслуживания требования. Тогда средняя длительность обслуживания равна

Это равенство даст нам способ оценки параметра по опытным данным. Как легко вычислить, дисперсия длительности обслуживания равна

Процесс обслуживания как марковский случайный процесс.

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

В каждый момент рассматриваемая система может находить-ся в одном из следующих состоянии: в момент t в системе на-ходятся k требовании (k=0, 1, 2, ...). Если krn, то в систе-ме находятся и обслуживаются k требований, а m-k - приборов свободны. Если km, то m требований обслуживаются, а k-m находятся в очереди и ожидают обслуживания. Обозначим через состояние, когда в системе находятся k требований. Таким образом, система может находиться в состояниях .. . Обозначим через -- вероятность того, что система в мо-мент t окажется в состоянии .

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

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

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

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

Составление уравнений.

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

Найдём сначала вероятность того, что и момент t.+h все приборы свободны. Это может произойти следующими способами:

в момент t все приборы были свободны и за время h новых требований не поступало;

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

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

Вероятность первого из указанных событий равна

вероятность второго события

Таким образом

Отсюда очевидным образом приходим уравнению

Перейдём теперь к составлению уравнений для при 1. Рассмотрим отдельно два различных случая: 1 и. Пусть в начале 1. Перечислим только существенные состояния, из которых можно прийти в состояние в момент t+h. Эти состояния таковы:

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

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

В момент t система находилась в состоянии, за время h новых требований не поступило, но одно требование было обслужено. Вероятность этого равна

Все остальные мыслимые возможности перехода в состояние за промежуток времени h имеют вероятность, равную о(h).

Собрав воедино найденные вероятности, получаем следующее равенство:

Несложные преобразования приводят от этого равенства к такому уравнению для 1;

Подобные же рассуждения для приводят к уравнению

Для определения вероятностей получили бесконечную систему дифференциальных уравнений (2)-(5). Её реше-ние представляет несомненные технические трудности.

Определение стационарного решения.

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

при .

Сказанное позволяет заключить, что уравнения (3), (4), (5) для стационарных вероятностей принимают следующий вид:

К этим уравнениям добавляется нормирующее условие

Для решения полученной бесконечной алгебраической системы введём обозначения:

Система уравнений (6)-(8) в этих обозначениях принимает такой вид:

Отсюда заключаем, что при всех

Введём для удобства записи обозначение

Уравнение (10) позволяет заключить, что

При из (11) находим, что

и, следовательно, при

Остаётся найти. Для этого в (9) подставляем выражения из (12) и (13). В результате

так как бесконечная сумма, стоящая в квадратных скобках, сходится только при условии, что

то при этом предположении находим равенство

Если условие (14) не выполнено, т.е. если, то ряд, стоящий в квадратной скобке уравнения для определения , расходится и, значит, должно быть равно 0. Но при этом, как следует из (12) и (13), при всех оказывается.

Методы теории цепей Маркова позволяют заключить, что при с течением времени очередь стремится к по ве-роятности.

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

Пусть врач успевает удовлетворительно осмотреть больного и заполнить его историю болезни в среднем за 15 минут. Планирующие органы из этого обычно делают вывод: за четырёхчасовый рабочий день врач должен принимать 16 человек. Однако больные приходят в случайные моменты времени. В ре-зультате при таком подсчете пропускной способности врача к нему неизбежно скапливается очередь, так как при проведен-ном подсчете принимается равным 1. Те же заключения от-носятся и к расчету числа коек в больницах, числа работа-ющих касс в магазинах, числа официантов в ресторанах и т. д. К сожалению, некоторые экономисты совершают такую же ошибку и при расчете погрузочных средств в карьерах, числе приемщиков на элеваторах, числе причалов в морских портах и пр.

Во всем дальнейшем мы предполагаем, что условие (14) выполнено.

Некоторые подготовительные результаты.

Для задачи с ожиданием основной характеристикой качества обслуживания является длительность ожидания требованием начала обслуживания. Длительность ожидания представляет собой случайную величину, которую обозначим буквой. Рассмотрим сейчас только задачу опреде-ления распределения вероятностей длительности ожидания в уже установившемся процессе обслуживания. Обозначим далее через вероятность того, что длительность ожидания превзойдёт t, и через вероятность неравенства, указанного в скобке при условии, что в момент поступления требования, для которого подсчитывается длительность ожидания, в очереди уже находится k требований. В силу формулы полной вероятности имеем равенство

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

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

Эта формула для m=1 принимает особенно простой вид:

В формуле (19) может принимать любое значение от 0 до m (исключительно). Так что в формуле (20) < 1, а в (21) <2.

Определение функции распределения длительности ожи-дания.

Если в момент поступления требования в очереди уже находились k-m требований, то, поскольку обслуживание про-исходит в порядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены k-m+ 1 требований. Пусть означает вероятность того, что за промежуток вре-мени длительности t после поступления интересующего тре-бования закончилось обслуживание ровно s требований. Ясно, что при имеет место равенство

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

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

и, следовательно,

Но вероятности известны:

Очевидными преобразованиями приводим правую часть по-следнего равенства к виду

Из формул (18) и (19) следует, что поэтому при m0

Само собой разумеется, что при t0

Функция имеет в точке t=1 разрыв непрерывности, равный вероятности застать все приборы занятыми.

Средняя длительность ожидания.

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

Несложные вычисления приводят к формуле

Дисперсия величины равна

Формула (23) даёт среднюю длительность ожидания одного требования. Найдем среднюю потерю времени требованиями, пришедшими в систему обслуживания в течение промежутка времени T. За время T в систему поступает требований и среднем; общая потеря ими времени па ожидание в среднем равна

Приведем небольшие арифметические подсчеты, которые про-демонстрируют нам, как быстро возрастают суммарные потери времени па ожидание с изменением величины. При этом мы ограничиваемся случаем Т=1 и рассматриваем лишь самые малые значения т: т =1 и т=2.

При т =1 в силу (20)

При р=0,1; 0,3; 0,5; 0,9 значение а приблизительно равно 0,011; 0,267; 0,500; 1,633; 8,100.

При m=2 в силу (24)

При =0,1; 1,0; 1,5; 1,9 значение а приблизительно равно 00003; 0,333; 1,350; 17,537.

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