В этом параграфе мы рассмотрим некоторые простейшие СМО и выведем выражения для их характеристик (показателей эффективности). При этом мы продемонстрируем основные методические приемы, характерные для элементарной, «марковской» теории массового обслуживания. Мы не будем гнаться за количеством образцов СМО, для которых будут выведены конечные выражения характеристик; данная книга - не справочник по теории массового обслуживания (такую роль гораздо лучше выполняют специальные руководства). Наша цель - познакомить читателя с некоторыми «маленькими хитростями», облегчающими путь сквозь теорию массового обслуживания, которая в ряде имеющихся (даже претендующих на популярность) книг может показаться бессвязным набором примеров.
Все потоки событий, переводящие СМО из состояния в состояние, в данном параграфе мы будем считать простейшими (не оговаривая это каждый раз специально). В их числе будет и так называемый «поток обслуживаний». Под ним разумеется поток заявок, обслуживаемых одним непрерывно занятым каналом.
В этом потоке интервал между событиями, как и всегда в простейшем потоке, имеет показательное распределение (во многих руководствах вместо этого говорят: «время обслуживания - показательное», мы и сами в дальнейшем будем пользоваться таким термином). В данном параграфе показательное распределение времени обслуживания будет само собой разуметься, как всегда для «простейшей» системы.
Характеристики эффективности рассматриваемых СМО мы будем вводить по ходу изложения.
1. n-канальная СМО с отказами (задача Эрланга).
Здесь мы рассмотрим одну из первых по времени, «классических» задач теории массового обслуживания; эта задача возникла из практических нужд телефонии и была решена в начале нашего века датским математиком Эрлангом. Задача ставится так: имеется каналов (линий связи), на которые поступает поток заявок с интенсивностью К. Поток обслуживаний имеет интенсивность (величина, обратная среднему времени обслуживания ). Найти финальные вероятности состояний СМО, а также характеристики ее эффективности:
А - абсолютную пропускную способность, т. е. среднее число заявок, обслуживаемых в единицу времени;
Относительную пропускную способность, т. е. среднюю долю пришедших заявок, обслуживаемых системой;
Ротк - вероятность отказа, т. е. того, что заявка покинет СМО необслуженной;
к - среднее число занятых каналов.
Решение. Состояния системы S (СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):
В СМО нет ни одной заявки,
В СМО находится одна заявка (один канал занят, остальные свободны),
В СМО находится к заявок каналов заняты, остальные свободны),
В СМО находится заявок (все каналов заняты).
Граф состояний СМО соответствует схеме гибели и размножения (рис. 20.1). Разметим этот граф - проставим у стрелок интенсивности потоков событий, Из систему переводит поток заявок с интенсивностью X (как только приходит заявка, система перескакивает из ).
Тот же поток заявок переводит систему из любого левого состояния в соседнее, правое (см. верхние стрелки на рис. 20.1).
Проставим интенсивности у нижних стрелок. Пусть система находится в состоянии (работает один канал). Он производит обслуживании в единицу времени. Проставляем у стрелки интенсивность Теперь представим себе, что система находится в состоянии (работают два канала). Чтобы ей перейти в нужно, чтобы либо закончил обслуживание первый канал, либо второй; суммарная интенсивность их потоков обслуживаний равна проставляем ее у соответствующей стрелки. Суммарный поток обслуживаний, даваемый тремя каналами, имеет интенсивность к каналами - Проставляем эти интенсивности у нижних стрелок на рис. 20.1.
А теперь, зная все интенсивности, воспользуемся уже готовыми формулами (19.7), (19.8) для финальных вероятностей в схеме гибели и размножения. По формуле (19.8) получим:
Члены разложения будут представлять собой коэффициенты при в выражениях для
Заметим, что в формулы (20.1), (20.2) интенсивности Яиц входят не по отдельности, а только в виде отношения Обозначим
и будем называть величину «приведенной интенсивностью потока заявок». Ее смысл - среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (20.1), (20.2) в виде:
Формулы (20.4), (20.5) для финальных вероятностей состояний называются формулами Эрланга - в честь основателя теории массового обслуживания. Большинство других формул этой теории (сегодня их больше, чем грибов в лесу) не носит никаких специальных имен.
Таким образом, финальные вероятности найдены. По ним мы вычислим характеристики эффективности СМО. Сначала найдем - вероятность того, что пришедшая заявка получит отказ (не будет обслужена). Для этого нужно, чтобы все каналов были заняты, значит,
Отсюда находим относительную пропускную способность - вероятность того, что заявка будет обслужена:
Абсолютную пропускную способность получим, умножая интенсивность потока заявок X на
Осталось только найти среднее число занятых каналов к. Эту величину можно было бы найти «впрямую», как математическое ожидание дискретной случайной величины с возможными значениями и вероятностями этих значений
Подставляя сюда выражения (20.5) для и выполняя соответствующие преобразования, мы, в конце концов, получили бы верную формулу для к. Но мы выведем ее гораздо проще (вот она, одна из «маленьких хитростей»!) В самом деле, нам известна абсолютная пропускная способность А. Это - не что иное, как интенсивность потока обслуженных системой заявок. Каждый занятый канал в единицу времени обслуживает в среднем заявок. Значит, среднее число занятых каналов равно
И какая доля каналов при этом будет простаивать?
Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе с тем, каждая обслуженная заявка приносит какой-то доход. Умножая этот доход на среднее число заявок А, обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и раеходы, связанные с содержанием каналов. Что перевесит - увеличение доходов или расходов? Это зависит от условий операции, от «платы за обслуживание заявки» и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее эффективное экономически. Мы такой задачи решать не будем, предоставляя все тому же «неленивому любопытному читателю» придумать пример и решить. Вообще, придумывание задач больше развивает, чем решение уже поставленных кем-то.
2.2 Многоканальная СМО с ожиданием
Система с ограниченной длиной очереди. Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди .
Состояния системы нумеруются по числу заявок, связанных системой:
нет очереди:
Все каналы свободны;
Занят один канал, остальные свободны;
Заняты -каналов, остальные нет;
Заняты все -каналов, свободных нет;
есть очередь:
Заняты все n-каналов; одна заявка стоит в очереди;
Заняты все n-каналов, r-заявок в очереди;
Заняты все n-каналов, r-заявок в очереди.
ГСП приведен на рис. 17. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью , по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна , умноженному на число занятых каналов.
Рис. 17. Многоканальная СМО с ожиданием
Граф типичен для процессов размножения и гибели, для которой решение ранее получено. Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).
Таким образом, все вероятности состояний найдены.
Определим характеристики эффективности системы.
Вероятность отказа. Поступившая заявка получает отказ, если заняты все n-каналов и все m-мест в очереди:
(18)
Относительная пропускная способность дополняет вероятность отказа до единицы:
Абсолютная пропускная способность СМО:
(19)
Среднее число занятых каналов. Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.
Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем -заявок в единицу времени, а СМО в целом обслуживает в среднем А-заявок в единицу времени. Разделив одно на другое, получим:
Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:
(20)
Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (11), (12) - (14)), используя соотношение для нее, получаем:
Среднее число заявок в системе:
Среднее время ожидания заявки в очереди. Рассмотрим ряд ситуаций, различающихся тем, в каком состоянии застанет систему вновь пришедшая заявка и сколько времени ей придется ждать обслуживания.
Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все n-каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» -каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди -заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже m-заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:
(21)
Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (20) только множителем , т. е.
.
Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО, отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:
.
Системы с неограниченной длиной очереди. Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более m-заявок.
Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при .
Вероятности состояний получим из формул предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при >1. Допустив, что <1 и устремив в формулах величину m к бесконечности, получим выражения для предельных вероятностей состояний:
(22)
Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:
Среднее число заявок в очереди получим при из (20):
,
а среднее время ожидания - из (21):
.
Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:
.
Среднее число заявок, связанных с СМО, определяется как среднее число заявок в очереди плюс среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов):
Пример 2. Автозаправочная станция с двумя колонками (n = 2) обслуживает поток машин с интенсивностью =0,8 (машин в минуту). Среднее время обслуживания одной машины:
В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.
Поскольку<1, очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (22) находим вероятности состояний:
и т. д.
Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО А==0,8 на интенсивность обслуживания =0,5:
Вероятность отсутствия очереди у АЗС будет:
Среднее число машин в очереди:
Среднее число машин на АЗС:
Среднее время ожидания в очереди:
Среднее время пребывания машины на АЗС:
СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом m-заявок, одновременно находящихся в очереди). В такой СМО заявка, разраставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).
Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.
Предположим, что имеется n-канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением, таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью:
Если этот поток пуассоновский, то процесс, протекающий в СМО, будет марковским. Найдем для него вероятности состояний. Нумерация состояний системы связывается с числом заявок в системе - как обслуживаемых, так и стоящих в очереди:
нет очереди:
Все каналы свободны;
Занят один канал;
Заняты два канала;
Заняты все n-каналов;
есть очередь:
Заняты все n-каналов, одна заявка стоит в очереди;
Заняты все n-каналов, r-заявок стоят в очереди и т. д.
Граф состояний и переходов системы показан на рис. 23.
Рис. 23. СМО с ограниченным временем ожидания
Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживания всех n-каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят r-заявок, то суммарная интенсивность потока уходов будет равна .
Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения , запишем:
(24)
Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.
Если длина очереди не ограничена и заявки «терпеливы» (не уходят из очереди), то стационарный предельный режим существует только в случае (при соответствующая бесконечная геометрическая прогрессия расходится, что физически соответствует неограниченному росту очереди при ).
Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок . Это следует из того, что ряд для в знаменателе формулы (24) сходится при любых положительных значениях и .
Для СМО с «нетерпеливыми» заявками понятие «вероятность отказа» не имеет смысла - каждая заявка становится в очередь, но может и не дождаться обслуживания, уйдя раньше времени.
Относительная пропускная способность, среднее число заявок в очереди. Относительную пропускную способность q такой СМО можно подсчитать следующим образом. Очевидно, обслужены будут все заявки, кроме тех, которые уйдут из очереди досрочно. Подсчитаем, какое в среднем число заявок покидает очередь досрочно. Для этого вычислим среднее число заявок в очереди:
На каждую из этих заявок действует «поток уходов» с интенсивностью . Значит, из среднего числа -заявок в очереди в среднем будет уходить, не дождавшись обслуживания, -заявок в единицу времени и всего в единицу времени в среднем будет обслуживаться -заявок. Относительная пропускная способность СМО будет составлять:
Среднее число занятых каналов по-прежнему получаем, деля абсолютную пропускную способность А на :
(26)
Среднее число заявок в очереди. Соотношение (26) позволяет вычислить среднее число заявок в очереди , не суммируя бесконечного ряда (25). Из (26) получаем:
а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины Z, принимающей значения 0, 1, 2,..., n с вероятностями ,:
В заключение заметим, что если в формулах (24) перейти к пределу при (или, что то же, при ), то при 
Очередь длины k, остается в ней с вероятностью Pk и не присоединяется к очереди с вероятностью gk=1 - Pk,". именно так обычно ведут себя люди в очередях. В системах массового обслуживания, являющихся математическими моделями производственных процессов, возможная длина очереди ограничена постоянной величиной (емкость бункера, например). Очевидно, это частный случай общей постановки. Некоторые...
В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей - абсолютной А и относительной 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), сходится к сумме, равной . Поэтому
(33)
и с учетом соотношений (17)
найдем предельные вероятности других состояний
(34)
Предельные вероятности p 0 , p 1 , p 2 , …, p k ,… образуют убывающую геометрическую профессию со знаменателем р < 1, следовательно, вероятность р 0 - наибольшая. Это означает, что если СМО справляется с потоком заявок (при ρ < 1), то наиболее вероятным будет отсутствие заявок в системе.
Среднее число заявок в системе L сист. определим по формуле математического ожидания, которая с учетом (34) примет вид
(35)
(суммирование от 1 до ∞, так как нулевой член 0p 0 =0).
Можно показать, что формула (35) преобразуется (при ρ < 1) к виду
(36)
Найдем среднее число заявок в очереди L оч. Очевидно, что
(37)
где L об. - среднее число заявок, находящихся под обслуживанием.
Среднее число заявок под обслуживанием определим по формуле математического ожидания числа заявок под обслуживанием, принимающего значения 0 (если канал свободен) либо 1 (если канал занят):
т.е. среднее число заявок под обслуживанием равно вероятности того, что канал занят:
(38)
В силу (33)
(39)
Теперь по формуле (37) с учетом (36) и (39)
(40)
Доказано, что при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе (очереди) равна среднему числу заявок в системе (в очереди), деленному на интенсивность потока заявок,
т.е.
(41)
(42)
Формулы (41) и (42) называются формулами Литтла.
Они вытекают из того, что в предельном, стационарном режиме среднее число заявок, прибывающих в систему, равно среднему числу заявок, покидающих
ее:
оба потока заявок имеют одну и ту же интенсивность λ.
На основании формул (41) и (42) с учетом (36) и (40) среднее время пребывания заявки в системе определится по формуле:
(43)
а среднее время пребывания заявки в очереди
(44)
Многоканальная СМО с неограниченной очередью
. Рассмотрим задачу. Имеется 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.
Рис. 9
Можно показать, что при r/n < 1 предельные вероятности существуют. Если r/n > 1, очередь растет до бесконечности. Используя формулы (16) и (17) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью
(45)
(46)
(47)
Вероятность того, что заявка окажется в очереди,
(48)
Для n-канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:
среднее число занятых каналов
(49)
среднее число заявок в очереди
(50)
среднее число заявок в системе
(51)
Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (42) и (41).
Замечание.
Для СМО с неограниченной очередью при r < 1 любая заявка, пришедшая в систему, будет обслужена,
т.е. вероятность отказа P отк = 0, относительная пропускная способность
Q =
1, а абсолютная пропускная способность равна интенсивности входящего потока заявок, т.е. А =
l.
СМО с ограниченной очередью
СМО с ограниченной очередью. СМО с ограниченной очередью отличаются от рассмотренных выше задач лишь тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного т). Если новая заявка поступает в момент, когда все места в очереди заняты, она покидает СМО необслуженной, т.е. получает отказ.Очевидно: для вычисления предельных вероятностей состояний и показателей эффективности таких СМО может быть использован тот же подход, что и выше, с той разницей, что суммировать надо не бесконечную прогрессию (как, например, мы делали при выводе формулы (33)), а конечную.
Среднее время пребывания заявки в очереди и в системе, как и ранее, определяем по формулам Литтла (44) и (43).
СМО с ограниченным временем ожидания. На практике часто встречаются СМО с так называемыми "нетерпеливыми" заявками. Такие заявки могут уйти из очереди, если время ожидания превышает некоторую величину. В частности, такого рода заявки возникают в различных технологических системах, в которых задержка с началом обслуживания может привести к потере качества продукции, в системах оперативного управления, когда срочные сообщения теряют ценность (или даже смысл), если они не поступают на обслуживание в течение определенного времени.
В простейших математических моделях таких систем предполагается, что заявка может находиться в очереди случайное время, распределенное по показательному закону с некоторым параметром υ, т.е. можно условно считать, что каждая заявка, стоящая в очереди на обслуживание, может покинуть систему с интенсивностью υ.
Соответствующие показатели эффективности СМО с ограниченным временем получаются на базе результатов, полученных для процесса гибели и размножения.
В заключение отметим, что на практике часто встречаются замкнутые системы обслуживания , у которых входящий поток заявок существенным образом зависит от состояния самой СМО. В качестве примера можно привести ситуацию, когда на ремонтную базу поступают с мест эксплуатации некоторые машины: понятно, что чем больше машин находится в состоянии ремонта, тем меньше их продолжает эксплуатироваться и тем меньше интенсивность потока вновь поступающих на ремонт машин. Для замкнутых СМО характерным является ограниченное число источников заявок, причем каждый источник "блокируется" на время обслуживания его заявки (т.е. он не выдает новых заявок). В подобных системах при конечном числе состояний СМО предельные вероятности будут существовать при любых значениях интенсивностей потоков заявок и обслуживании. Они могут быть вычислены, если вновь обратиться к процессу гибели и размножения.
Системы МО являются частью более широкого класса динамических систем, которые иногда называют системами потоков. Системой потоков называется система, в которой некоторые предметы перемещаются по одному или нескольким каналам с ограниченной пропускной способностью с целью перемещения из одной точки в другую. При анализе систем потоков их разбивают на два основных класса:
регулярные системы, т. е. системы, в которых потоки ведут себя предсказуемым образом (известны величина потока и время его появления в канале). В случае, когда канал один, расчет системы тривиален. Очевидно, что между интенсивностью потока λ и скоростью обслуживания с есть соотношение λ < c ;
нерегулярные системы, т. е. системы, в которых потоки ведут себя непредсказуемым образом.
Более интересным является случай регулярного потока, который распределяется по сети каналов. Очевидно, что условие λ < c сохраняется для каждого канала. При этом возникает сложная комбинаторная задача.
Имеется семь дорог:
A→B→D→E→F
A→C→B→ E→F
A→C→B→D→E→F
A→C→B→ D→F
Необходимо перевезти груз из А в F . Пропускная способность каждого канала известна. Какова пропускная способность сети и каким путем должен следовать поток? Решить эту задачу можно с помощью теоремы о максимальном потоке, которую мы рассматривали ранее (рис.6).
Ко второму классу относятся случайные вероятные потоки, в которых время поступления требования не определено, число требований непредсказуемо. Решением таких задач и занимается теория массового обслуживания.
В общем случае система массового обслуживания может быть представлена на рисунке 7.
Рис. 7.
Предметом теории массового обслуживания является установление зависимости между характером потока заявок, числом каналов, производительностью, правильностью работы и эффективностью.
В качестве характеристик эффективности могут применяться следующие величины и функции:
среднее количество заявок, которые может обслужить СМО в единицу времени;
среднее количество заявок, получающих отказ и покидающих СМО;
вероятность того, что поступившая заявка немедленно будет обслужена;
среднее время ожидания в очереди;
среднее количество заявок в очереди;
средний доход СМО в единицу времени и другие экономические показатели СМО .
Анализ СМО упрощается, если в системе протекает марковский процесс, тогда систему можно описать обыкновенными дифференциальными уравнениями, а предельные вероятности – линейными алгебраическими уравнениями.
Марковский процесс требует, чтобы все потоки были пуассоновскими (без последействий), но аппарат марковских процессов используется и тогда, когда процесс отличен от марковского. В этом случае характеристики СМО могут быть оценены приблизительно: чем сложнее СМО, тем точнее приближение.
Классификация систем массового обслуживания
СМО могут быть двух видов:
СМО с отказами;
СМО с ожиданием (т. е. с очередью).
Обслуживание в системах с очередью может иметь различный характер:
обслуживание может быть упорядоченным;
обслуживание в случайном порядке;
обслуживание с приоритетом, при этом приоритет может быть с прерыванием и без прерывания.
Системы с очередью делятся на:
системы с неограниченным ожиданием , при этом поступившая в СМО задача становится в очередь и ждет обслуживания. Рано или поздно она будет обслужена;
системы с ограниченным ожиданием , при этом на заявку в очереди накладываются ограничения, например ограниченное время пребывания в очереди, длина очереди, общее время пребывания в СМО. В зависимости от типа СМО для оценки эффективности могут быть применены разные показатели.
Для СМО с отказами используются следующие показатели эффективности:
абсолютная пропускная способность А – среднее число заявок, которое может быть обслужено в единицу времени;
относительная пропускная способность Q – относительное среднее число заявок. При этом относительную пропускную способность можно найти по формуле
Где λ – это интенсивность поступления заявок в СМО.
Для СМО с ожиданием абсолютная пропускная способность А и относительная пропускная способность Q теряют смысл, но важными становятся другие характеристики:
единица времени ожидания в очереди;
среднее число заявок в очереди;
среднее время пребывания в системе.
Для СМО с ограниченной очередью интересны обе группы характеристик.
В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.
Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:
S 0 – система свободна и находится в состоянии простоя;
S 1 – обслуживается одна заявка, канал занят, очереди нет;
S 2 – одна заявка обслуживается, одна в очереди;
S m +1 - одна заявка обслуживается,т в очереди.
Граф состояний такой системы показан на рисунке номер 5:
S 0 S 1 S 2 S m+1
μ μ μ ………. μ μ
Рисунок 5: Одноканальная СМО с ограниченной очередью.
В формуле для р 0 найдем сумму конечного числа членов геометрической прогрессии:
(52)
С учетом формулы для ρ получим выражение:
В скобках находится (m+2) элементов геометрической прогрессии с первым членом 1 и знаменателем ρ. По формуле суммы (m+2) членов прогрессии:
(54)
(55)
Формулы для вероятностей предельных состояний будут иметь вид:
Вероятность отказа в обслуживании заявки определим как вероятность того, что при поступлении заявки в систему ее канал будет занят и все места в очереди также заняты:
(57)
Отсюда вероятность обслуживания (а также и относительная пропускная способность ) равны вероятности противоположного события:
Абсолютная пропускная способность – число заявок, обслуженных системой в единицу времени:
(59)
Среднее число заявок под обслуживанием:
(60)
(61)
Среднее число заявок в системе:
(62)
Одноканальную СМО с ограниченной очередью можно рассмотреть в Mathcad.
Пример :
На стоянке обслуживается 3 машины с интенсивностью потока 0,5 и средним временем обслуживания 2,5 минуты. Определить все показатели системы.
6 Многоканальная смо с неограниченной очередью
Пусть дана система S, имеющаяп каналов обслуживания, на которые поступает простейший поток требований интенсивностью λ. Пусть поток обслуживания также простейший и имеет интенсивность μ. Очередь на обслуживание не ограничена.
По числу заявок, находящихся в системе, обозначим состояния системы: S 0 ,S 1 ,S 2 ,…,S k ,… S n , гдеS k – состояние системы, когда в ней находитсяkзаявок (максимальное число заявок под обслуживанием -n). Граф состояний такой системы изображается в виде схемы на рисунке номер 6:
λ λ λ λ λ λ λ
……. …….
S 0 S 1 S 2 S m+1 S n
μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ
Рисунок 6: Многоканальная СМО с неограниченной очередью.
Интенсивность потока обслуживаний меняется в зависимости от состояния системы: kμ при переходе из состоянияS k в состояниеS k -1 так как может освободиться любой изk каналов; после того, как все каналы заняты обслуживанием, интенсивность потока обслуживаний остается равнойпμ, при поступлении в систему следующих заявок.
Для нахождения финальных вероятностей состояний получим формулы аналогично тому, как это было сделано для одноканальной системы.
(63)
Отсюда формулы для финальных вероятностей выражаются через
Для нахождения р 0 получим уравнение:
Для слагаемых в скобках, начиная с
(n+ 2)-го, можно применить
формулу нахождения суммы бесконечно
убывающей геометрической прогрессии
с первым членом
и знаменателем ρ/n:
(66)
Окончательно получим формулу Эрланга для нахождения вероятности простоя системы:
(67)
Приведем формулы для расчета основных яоказателей эффективности работы системы.
Система будет справляться с потоком заявок, если
выполнено условие
,
(68)
которое означает, что число заявок, поступивших в систему за единицу времени, не превосходит числа заявок, обслуженных системой за это же время. При этом вероятность отказа в обслуживании равна нулю.
Отсюда вероятность обслуживания (а также иотносительная пропускная способность системы) равны вероятности противоположного события, то есть единице:
(69)
Абсолютная пропускная способность - число заявок, обслуженныхсистемой в единицу времени:
(70)
Если система справляется с потоком заявок, то в стационарном режиме интенсивность выходящего потока равна интенсивности потока поступающих в систему заявок, так как обслуживаются все заявки:
ν=λ . (71)
Так как каждый канал обслуживает μ заявок в единицу времени, то среднее число занятых каналов можно вычислить:
(72)
Среднее время обслуживания каналом одной заявки;
.
(73)
Вероятность того, что при поступлении в систему заявка окажется в очереди, равна вероятности того, что в системе находится более чем п заявок:
(74)
Число заявок, находящихся под обслуживанием, равно числу занятых каналов:
(75)
Среднее число заявок в очереди:
(76)
Тогда среднее число заявок в системе:
(77)
Среднее время пребывания заявки в системе (в очереди):
(78)
(79)
Многоканальную СМО с неограниченной очередью можно рассмотреть в системе Mathcad.
Пример 1 :
Салон-парикмахерская имеет 5 мастеров. В час пик интенсивность потока клиентов равна 6 человек. В час. Обслуживание одного клиента длится в среднем 40 минут. Определить среднюю длину очереди, считая ее неограниченной.
Фрагмент решения задачи в Mathcad.
Пример 2:
В железнодорожной кассе имеются 2 окна. Время на обслуживания одного пассажира 0,5 минут. Пассажиры подходят к кассе по 3 человека. Определить все характеристики системы.
Фрагмент решения задачи в Mathcad.
Продолжение решения задачи в Mathcad.
