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

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

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

Граф этой СМО представлен на рис. 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м

Для СМО с отказами :

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

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

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

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

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

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

Рассмотрим примеры некоторых СМО.

2.5.1. Многоканальная СМО с отказами

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

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

Описание состояний:

Все инспекторы свободны;

Занят один инспектор;

Заняты два инспектора;

Заняты три инспектора.

Граф состояний системы приведен на рис. 2.11 .

На графе: - интенсивность потока грузовых автомобилей; - интенсивность проверок документов одним автоинспектором.

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

Решение

Искомая часть вероятности - вероятности занятости всех трех инспекторов. Поскольку граф состояний представляет типовую схему "гибели и размножения", то найдем , используя зависимости (2.2).

Пропускную способность этого поста автоинспекторов можно характеризовать относительной пропускной способностью :

Пример 2.6 . Для приема и обработки донесений от разведгруппы в разведотделе объединения назначена группа в составе трех офицеров. Ожидаемая интенсивность потока донесений - 15 донесений в час. Среднее время обработки одного донесения одним офицером - . Каждый офицер может принимать донесения от любой разведгруппы. Освободившийся офицер обрабатывает последнее из поступивших донесений. Поступающие донесения должны обрабатываться с вероятностью не менее 95 %.

Определить, достаточно ли назначенной группы из трех офицеров для выполнения поставленной задачи.

Решение

Группа офицеров работает как СМО с отказами, состоящая из трех каналов.

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

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

Поскольку граф состояний - это схема "гибели и размножения", то для нее имеются готовые выражения для предельных вероятностей состояния:

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

В примере .

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

Так как вероятность отказа в обработке донесений составляет более 34 % (), то необходимо увеличить личный состав группы. Увеличим состав группы в два раза, то есть СМО будет иметь теперь шесть каналов, и рассчитаем :

Таким образом, только группа из шести офицеров сможет обрабатывать поступающие донесения с вероятностью 95 %.

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

Пример 2.7 . На участке форсирования реки имеются 15 однотипных переправочных средств. Поток поступления техники на переправу в среднем составляет 1 ед./мин, среднее время переправы одной единицы техники - 10 мин (с учетом возвращения назад переправочного средства).

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

Решение

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

Среднее число работающих переправочных средств:

Коэффициенты использования и простоя переправы:

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

Коэффициенты использования переправы после 50 прогонов практически совпадают: .

Максимальная длина очереди 15 ед., среднее время пребывания в очереди около 10 мин.

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

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

Среднее число занятых колонок:
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
Среднее число машин в очереди:

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

Рис. 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)

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

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

Для определения предельных вероятностей состояний воспользуемся формулами (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)

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

Пример 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. Средняя продолжительность пребывания клиента в системе:

т = 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 ч. работы) поста диагностики. Ясно, что решение относительно расширения площади для стоянки автомобилей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей клиентов при наличии всего трех мест для стоянки этих автомобилей.

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

Система может находиться в одном из состояний 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.

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

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

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

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

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

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

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

С отказами

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

С очередью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

нет очереди:

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

- занят один канал, остальные свободны;

- заняты -каналов, остальные нет;

- заняты все -каналов, свободных нет;

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

- заняты все n-каналов; одна заявка стоит в очереди;

- заняты все n-каналов, r-заявок в очереди;

- заняты все n-каналов, r-заявок в очереди.

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

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

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

(29)

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

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

(30)

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

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

(31)

где .

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

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

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

(32)

Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди только множителем , т. е.

.

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

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

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

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

Среднее число заявок в очереди получим при из (31):

,

а среднее время ожидания - из (32): .

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

Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:

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

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

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

Пуассоновский «поток уходов» с интенсивностью:

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

нет очереди:

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

- занят один канал;

- заняты два канала;

- заняты все n-каналов;

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

- заняты все n-каналов, одна заявка стоит в очереди;

- заняты все n-каналов, r-заявок стоят в очереди и т. д.

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

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

Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .

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

На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:

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

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

В замкнутой СМО циркулирует одно и то же конечное число потенциальных требований. Пока потенциальное требование не реализовалось в качестве требования на обслуживание, считается, что оно находится в блоке задержки. В момент реализации оно поступает в саму систему. Например, рабочие обслуживают группу станков. Каждый станок является потенциальным требованием, превращаясь в реальное в момент своей поломки. Пока станок работает, он находится в блоке задержки, а с момента поломки до момента окончания ремонта - в самой системе. Каждый рабочий является каналом обслуживания. = =P 1 + 2 P 2 +…+(n- 1 )P n- 1 +n( 1 -P На вход трехканальной СМО с отказами поступает поток заявок с интенсивностью =4 заявки в минуту, время обслуживания заявки одним каналом t обсл =1/μ =0,5 мин. Выгодно ли с точки зрения пропускной способности СМО заставить все три канала обслуживать заявки сразу, причем среднее время обслуживания уменьшается втрое? Как это скажется на среднем времени пребывания заявки в СМО?

Пример 2 . /μ=2, ρ/ n =2/3<1.

Задача 3:

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

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

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

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

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

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