Изучим работу n-канальной (n > 1) СМО с ожиданием, на вход которой поступает простейший поток заявок П вх с интенсивностью. Поток обслуживании каждым каналом также предполагается простейшим с интенсивностью µ. На длину очереди никаких ограничений не налагается, но время ожидания каждой заявки в очереди ограничено случайным сроком Т ож со средним значением, после которого заявка покидает систему необслуженной. Временной интервал Т ож является непрерывной случайной величиной, которая может принимать любое положительное значение и математическое ожидание которой.
Если этот поток пуассоновский, то процесс, протекающий в СМО, будет Марковским.
Такие системы часто встречаются на практике. Их иногда называют системами с «нетерпеливыми» заявками.
Занумеруем состояния СМО по числу заявок, находящихся в системе, как под обслуживанием, так и стоящих в очереди: S k (k = 0,1,…n) - k заявок под обслуживанием (k каналов заняты, очереди нет), S n+r (r = 1,2,…) - п заявок под обслуживанием (все п каналов заняты) и r заявок в очереди.
Таким образом, СМО может пребывать в одном из бесконечного множества состояний.
Размеченный граф состояний указан на рис. 1.
Рис. 1.
Из состояния в состояние слева направо СМО переходит под воздействием одного и того же входящего потока заявок П вх с интенсивностью. Следовательно, плотности вероятностей этих переходов
k-1,k = , k = 1,2,… (1)
Переход СМО из состояния без очереди S k , k = 1,…,n , в соседнее слева состояние S k-1 , (k = 1,…,n) (в котором также не будет очереди) происходит под действием суммарного потока, слагающегося из к потоков обслуживания занятых каналов, интенсивность которого, представляющая собой сумму интенсивностей слагаемых потоков обслуживании, равна kµ . Поэтому под стрелками налево от состояния s n до состояния s 0 проставлены плотности вероятностей переходов
k,k-1 =kµ, k = 1,…,n (2)
На систему в состоянии с очередью S n+r , r = 1,2,… , действует суммарный поток - результат наложения n потоков обслуживании и r потоков уходов. Поэтому интенсивность суммарного потока равна сумме интенсивностей слагаемых потоков nµ+rщ . Этот суммарный поток порождает переход СМО справа налево из состояния S n+r ,(r = 1,2,…) в среднее S n+r-1 ,(r = 1,2,…) и, таким образом,
k,k-1 =nµ+(k-n)щ, k =n+1,n+2,… (3)
Итак, плотности вероятностей переходов системы справа налево, учитывая (2) и (3), можно записать в объединённой форме
Структура графа говорит о том, что процесс, протекающий в СМО, является процессом гибели и размножения.
Подставим (1) и (4) для k=1,…,n+m в формулу
Введем в рассмотрение величину, которую можно назвать приведенной интенсивностью потока уходов, и которая показывает среднее число уходов из очереди не обслуженных заявок за среднее время обслуживания одной заявки. Подставляя в (5) и получим:
Так как в рассматриваемой СМО нет ограничений на длину очереди, то заявка, поступившая во входящем потоке, будет принят; в систему, т.е. отказ со стороны системы заявка не получает. Поэтому для СМО с «нетерпеливыми» заявками вероятность принятия в систему p сист =1, а вероятность отказа принятия в систему p отк =0 . Понятие «отказа принятия в систему» не следует смешивать с понятием «отказа в обслуживании», поскольку, в силу «нетерпеливости», не каждая поступившая (принятая) в систему заявка, будет обслужена. Таким образом, имеет смысл говорить о вероятности ухода заявки из очереди p ху и вероятности того, что заявка будет обслужена, p об . При этом, вероятность p об представляет собой относительную пропускную способность Q и p ху =1- p об .
Подсчитаем среднее число заявок в очереди. Для этого рассмотрим дискретную случайную величину N оч представляющую собой число заявок в очереди. Случайная величина N оч может принять любое целое неотрицательное значение, а ее закон распределения имеет вид
N оч |
||||||
p n+1 |
p n+2 |
p n+r |
где p= p 0 + p 1 +…+ p n . Следовательно,
или подставляя сюда (7), получим
На каждую заявку в очереди действует поток «уходов» Пух с интенсивностью щ. На среднюю очередь, состоящую из заявок, будет действовать суммарный поток, складывающийся из потоков «уходов», и имеющий интенсивность. Значит, из среднего числа заявок в очереди в среднем будет уходить, не дождавшись обслуживания, заявок в единицу времени, а оставшиеся заявки будут обслужены. Следовательно, среднее число заявок, обслуженных за единицу времени, т.е. абсолютная пропускная способность СМО
Тогда по определению относительной пропускной способности,
Q = A/ = (-)/ = 1 - (щ/),
где щ/ = показывает среднее число уходов из очереди не обслуженных заявок за среднее время между поступлениями двух соседних заявок во входящем потоке П вх .
Среднее число занятых каналов (среднее число заявок, находящихся под обслуживанием) можно получить как отношение абсолютной пропускной способности А к производительности одного канала µ. Воспользовавшись равенством (11), будем иметь:
Среднее число занятых каналов можно подсчитать и независимо от среднего числа заявок в очереди, а именно как математическое ожидание дискретной случайной величины К, представляющей собой число занятых каналов, закон распределения которой имеет вид
p 0 |
p 1 |
p 2 |
p n-1 |
где p = p n + p n+1 +…+ p n+1 + …. Но так как событие, состоящее в том, что все n каналов заняты, противоположно событию, состоящему в том, что не все n каналов заняты, а вероятность последнего события равна
p 0 + p 1 + p 2 +…+ p n-1 , то p = 1 - (p 0 + p 1 + p 2 +…+ p n-1) .
Но тогда из (11) получим:
Используя формулы (11) и (13), получим формулу для среднего числа заявок, находящихся в системе:
Выведем формулу для среднего времени ожидания заявки в очереди. Оно будет зависеть от данного среднего времени ограничивающего продолжительность пребывания заявки в очереди, для которого либо
либо найдется натуральное число i > 2 такое, что
Умножая неравенства (14) и (15) на, получим соответственно неравенства
Рассмотрим случай (14) и несовместные гипотезы состоящие в том, что система находится в состоянии. Вероятности этих гипотез
Если заявка поступит в СМО при гипотезет.е. когда система пребывает в одном из состояний в каждом из которых не все каналы заняты, то заявке не придется ожидать в очереди -она сейчас же попадет под обслуживание свободного канала. Поэтому условное математическое ожиданиеслучайной величинывремени ожидания заявки в очереди при гипотезе, представляющее собой среднее время ожидания заявки в очереди при гипотезеравно нулю:
Если заявка поступит в систему при гипотезет.е. когда СМО находится в одном из состоянийв котором все п к-п заявок (при к = п в очереди заявок нет), то среднее время освобождения одного из п занятых каналов равно, а среднее время обслуживания к-п заявок, стоящих в очереди перед поступившей в систему заявкой, равно Поэтому среднее время, необходимое для того, чтобы подошла очередь на обслуживание поступившей заявки, равно.Так как, то в силу правого неравенства (14),
Таким образом, среднее время, необходимое для того, чтобы поступившая в систему заявка была принята к обслуживанию, больше времени, ограничивающего пребывание заявки в очереди. Поэтому поступившая заявка задержится в очереди на среднее времяи покинет систему не обслуженной. Следовательно, условное математическое ожидание величиныпри гипотезе
Теперь рассмотрим те же гипотезыв случае (15). В этом случае также справедливы равенства (16).
Если заявка поступит в систему при одной из гипотез т.е., когда СМО находится в одном из состояний в котором все п каналов заняты и в очереди перед поступившей заявкой уже стоят к-п заявок (при к - n в очереди заявок нет), то так же, как и в случае (14), среднее время, необходимое для того, чтобы подошла очередь этой заявки на обслуживание, равно ограничивающим пребывание заявки. Так както, в силу левого неравенства (15),
Таким образом, среднее время, необходимое для того, чтобы пришедшая в систему заявка была принята к обслуживанию, не больше среднего времени, ограничивающего пребывание заявки в очереди. Поэтому поступившая заявка не уйдет из очереди и дождется приема на обслуживание, потратив на ожидание в очереди среднее время Следовательно, условное математическое ожидание случайной величины Т оч при гипотезе
Пусть теперь заявка поступила в систему при одной из гипотез Н ю к = n+i- т.е., когда СМО находилась в одном из состояний..., в котором все п каналов заняты и в очереди уже стоят к-п заявок. Так как то из неравенства (15):
а потому пришедшая заявка задержится в очереди на среднее время Следовательно, условное математическое ожидание случайной величины Т оч при гипотезе
По формуле полного математического ожидания получим:
В случае (15) поступившая заявка будет принята к обслуживанию, если только в момент её поступления СМО находится в одном из состояний тогда вероятность того, что заявка будет обслужена
При / = 1 формула (25) превращается в (24), поэтому для вероятности обслуживания можно записать одну формулу:
Зная вероятность обслуживания, можно вычислить вероятность ухода заявки из очереди не обслуженной:
Среднее время пребывания заявки в системе можно вычислить по формуле
где- среднее время обслуживания одной заявки, относящееся ко всем заявкам, как обслуженным, так и ушедшим из очереди, которое можно подсчитать па формуле
6. Построение и анализ модели систем массового обслуживания
Рассмотрим практическую задачу на использование СМО без ограничения на длину очереди, но с ограничением на время ожидания в очереди.
С целью увеличения дальности беспосадочного полета производится дозаправка самолетов горючим в воздухе. В районе дозаправки постоянно дежурят два самолета-дозаправщика. Дозаправка одного самолета длится в среднем около 10 минут. Если оба самолета-дозаправщика заняты, то самолет, нуждающийся в дозаправке, некоторое время может «ожидать» (совершать полет по кругу в районе дозаправки). Среднее время ожидания - 20 минут. Самолет, не дождавшийся дозаправки, вынужден садиться на запасной аэропорт. Интенсивность полетов такова, что в среднем за 1 час в район дозаправки прибывает 12 самолетов. Определить:
Вероятность того, что самолет будет дозаправлен.
Среднее число занятых дозаправщиков.
Среднее число самолетов в очереди.
Среднее число самолетов под обслуживанием.
Необходимо вычислить основные характеристики эффективности данной СМО, при условии, что заданы следующие входные параметры:
- · количество каналов обслуживания;
- · интенсивность входящего потока заявок;
- · интенсивность потока обслуживания;
- · среднее время, ограничивающее пребывание заявок в очереди.
Рассматриваемая СМО является многоканальной системой массового обслуживания без ограничения на длину очереди, но с ограничением на время ожидания. Количество каналов, интенсивность входящего потока заявок, интенсивность потока обслуживания и количество мест в очереди заданы.
В данной СМО каждый канал обслуживает в каждый момент времени одну заявку. Если в момент поступления новой заявки свободен хотя бы один канал, то пришедшая заявка поступает на обслуживание, если же заявки отсутствуют, то система простаивает.
Определим, что происходит, когда к моменту поступления заявки все каналы заняты - она становится в очередь и ожидает освобождения одного из каналов. Если в момент поступления заявки все места в очереди заняты, то эта заявка покидает систему.
Критерии эффективности функционирования СМО:
- · Вероятность простоя системы;
- · Вероятность отказа системы;
- · Относительная пропускная способность.
- · Среднее время пребывания заявки в очереди.
Данная система моделируется многоканальной СМО с «нетерпеливыми» заявками.
Параметры системы:
число каналов обслуживания n = 2 ;
интенсивность входящего поток заявок = 12 (самолетов в час);
интенсивность потока обслуживания µ = 6 (самолетов в час);
среднее время, ограничивающее пребывание заявки в очереди, следовательно, интенсивность потока уходов щ = 1/= 3 (самолета) в час.
Расчеты произведены с помощью разработанной в Turbo Pascal программе. Язык Turbo-Pascal - один из самых распространенных языков программирования компьютеров. К важным достоинствам языка Turbo-Pascal относится небольшой размер компилятора, высокая скорость трансляции программ, компиляции и их компоновки. Кроме того, удобство и высокое качество дизайна диалоговой оболочки, делают написание и отладку программ наиболее удобным в сравнении с альтернативными языками нового поколения.
Для анализа работы СМО необходимо исследовать поведение данной системы при различных входных параметрах.
В первом варианте л=12, µ=6, щ=3, число каналов n=2.
Во втором варианте л=12, µ=6, щ=3, число каналов n=3.
В третьем варианте л=12, µ=6, щ=4, число каналов n=2.
Все результаты расчетов приведены в Приложение 2.
В результате анализа полученных данных (Приложение 2), были сделаны следующие выводы.
С увеличением числа каналов увеличивается вероятность простоя системы и вероятность дозаправки на 50%.
При изменение же только времени пребывания заявки в очереди, не увеличивая кол-во каналов, изменилась интенсивность потока уходов, в результате уменьшилось число обслуживаемых самолетов и число самолетов в очереди.
По-моему мнению, необходимо набрать и обучить дополнительный обслуживающий персонал, чтобы увеличить интенсивность потока уходов, тогда будет меньше затрачиваться времени на простой дозаправщиков и не возникнет необходимости в дополнительном канале.
Хотя, выбирая наиболее оптимальные параметры, при которых работа СМО будет наиболее эффективной, нужно еще учитывать технический и экономический фактор, так как приобретение дополнительного канала обслуживания или изменение интенсивности потока уходов, требует определенных материальных затрат и затрат на подготовку кадров.
Перед выходом на передачу любой, исходящий из процессора ЭВМ, блок должен некоторое время ожидать в очереди. В общем случае при использовании относительных приоритетов обработка сообщений организуется по схеме рис. 11
Сообщениям типа Z 1 ,…,Z n присвоены относительные приоритеты 1,…,n соответственно. Сообщение Z p , поступившее в систему, и ожидающее передачи, заносится в очередь О р, в которой хранятся сообщения приоритета Р. В очереди О р сообщения упорядочены по времени их поступления. Когда процессор Пр заканчивает передачу ранее обслуживаемого сообщения, то управление передается программе "ДИСПЕТЧЕР”. Программа выбирает для очередной передачи сообщение с наивысшим приоритетом - сообщение Z i , если очереди более старших приоритетов О 1 ,..,О i-1 не содержат сообщений (т.е. оказываются пустыми). Выбранное для передачи сообщение захватывает исходящий канал на все время передачи. Если в систему поступает n простейших потоков сообщений с интенсивностями, а длительность передачи сообщений каждого типа имеют средние значения и вторые начальные моменты, соответственно, то среднее время ожидания сообщений, имеющих приоритет k, определится соотношением
Используя понятие коэффициента вариации
где - среднеквадратическое отклонение времен передачи сообщений i-го типа, получим соотношение:
В рассматриваемом нами конкретном случае анализа сети имеются всего два типа передаваемых блоков сообщений: исходящие интерактивные блоки, имеющие более высокий приоритет, и исходящие почтовые блоки, имеющие более низкий относительный приоритет.
Следовательно,
Для сообщений первого приоритета
Для сообщений второго приоритета
Следовательно, для интерактивных блоков:
Для почтовых блоков:
Для вычисления значений коэффициентов вариации длин блоков необходимо учесть следующее:
При каждом успешном опросе, ЦДП передает абоненту случайное число N исходящих блоков. Будем считать, что случайная величина N распределена по экспоненциальному закону.
Это означает, что коэффициент вариации (34)
Поскольку почтовые сообщения имеют постоянную длину, (35)
Расчет показывает, что при малой загрузке, время ожидания в очереди блоков почтовых сообщений незначительно превышает время ожидания блоков интерактивных сообщении (сообщений мало и они не мешают друг другу при передаче). С увеличением нагрузок ранним возрастает за счет того, что интерактивные блоки сообщений "выясняют" почтовые.
Время ожидания в очередях в узлах коммутации
Блоки сообщений, попадающие в центры коммутации, анализируются и направляются в соответствии с указанным в них адресом получателя через другие центры коммутации к абоненту или к ЭВМ. Прежде, чем центр коммутации (ЦК) прочтет адрес для направления блока, необходимо, чтобы вся управляющая часть блока (в у = 19 байт), содержащая адресную информацию, была полностью принята УК. Затрачиваемое на это время
Затем, спустя некоторое время реакции УК (рцк =1 мс), если очередь сообщений в УК отсутствует, рассматриваемый блок направится дальше к следующему центру коммутации.
Одновременно с приемом блоков УК ведет передачу выходящих из него блоков.
(37)
является полным временем, необходимым дня обслуживания передачи блока сообщений в УК.
Интерактивные и почтовые блоки сообщений поступают в УК вперемешку. При этом в него попадают как исходящие от ЭВМ ЦДП, так и предназначенные для нее блоки. Поэтому при рассмотрении времени ожидания очереди на передачу сообщения УК- необходимо учитывать полную загрузку сети
Учитывая, что является величиной постоянной (= 0), для определения значения времени tцк следует воспользоваться соотношением
Ввиду малой нагрузки эта величина получилась весьма незначительной, однако, при возрастании суммарной загрузки в 2 раза значение увеличивается, а при дальнейшем повышении нагрузки центры коммутации могут оказаться «узким местом» сети.
Значение эквивалентного времени ожидания в очередях центров коммутации определяется соотношением
аналогично тому, как это делалось при определении эквивалентной задержки в центре коммутации. Если принять, например, что для рассматриваемой сети каждый блок проходит один раз через 3,5 узла коммутации, то
Указанная задержка и должна учитываться при определении времени ответа для интерактивных и почтовых сообщений.
В этом разделе рассмотрим СМО типа М/М/n/m< , но, в отличие от предыдущих, наложим ограничение на время ожидания в очереди.
Это ограничение носит принципиальный характер, т.к. при вычислении вероятностей состояний СМО необходимо знание не только текущего состояния (числа требований в системе), но и того, как давно пришли требования, ожидающие обслуживания. Таким образом, процесс К(t) перестает быть марковским.
Время ожидания в очереди может быть ограничено как детерминированной, так и случайной величиной. В обеих случаях процесс К(t), как уже было сказано, характеризуется наличием последействия. Однако, способы формирования на его основе марковской модели СМО существенно различаются.
7.3.1. Время ожидания ограничено случайной величиной τ
В этом случае все зависит от закона распределения ограничения , т.к. именно ограничение вносит в систему последействие. Поэтому вернуть процессу К(t) марковость крайне просто. Достаточно принять для описания случайной величины экспоненциальное распределение. Однако при этом нельзя забывать, что такая операция возможна лишь в том случае, когда реальное распределение или действительно экспоненциальное, или близко к нему. Если это не так, то сформированная математическая модель будет неадекватна реальной СМО.
При экспоненциально распределенном ограничении на время ожидания в очереди, процесс изменения числа требований в СМО по-прежнему будет процессом размножения и гибели с той лишь разницей, что интенсивность гибели увеличится за счет, покидающих очередь требований, у которых время ожидания превысило допустимую величину.
Примем, что распределение времени ожидания имеет вид:
F(t) = 1 - e - функция распределения,
f(t) = e - плотность распределения,
где - интенсивность выхода из очереди за счет превышения допустимого времени ожидания.
Тогда параметры процесса К(t) будут равны:
K , при к N + (k - n) , при к>n . Читателю предлагается самостоятельно, руководствуясь материалом раздела 7.2.1,
написать модель рассматриваемой СМО, и формулы для вычисления основных характеристик СМО в стационарном режиме. 7.3.2. Время ожидания ограничено неслучайной величиной τ
В этом случае для описания СМО с помощью марковской модели целесообразно использовать второй из приведенных в 7.1. способов, а именно, расширение понятия состояния. Для того, чтобы прогнозировать распределения состояний в будущем, необходимо знать как давно пришли в систему требования, которые в настоящее время находятся в очереди. Это можно сделать, включив в число обобщенных координат, описывающих состояние СМО, давность прихода каждого ожидающего требования, или, что то же самое, время, которое осталось у него до окончания срока ожидания. В рамках процесса К(t), которым мы пользовались во всех предыдущих задачах, это сделать нельзя, и в рассматриваемом случае модель функционирования СМО строится на основании векторного случайного процесса X ,
характеризующего состояние системы через состояния каждого из n ее каналов: X
= { X (t), X (t),…. X (t)} = {
X (t)} X (t) – это время, которое осталось до освобождения j-ого канала. Таким образом, для каждого момента времени t, мы можем прогнозировать будущие состояния каналов: j-ый канал освободится через х j (t), если за это время не поступят требования из внешнего потока. А так как входящий поток простейший, это значит, что в процессе X
последействие отсутствует, т.е. процесс марковский. Найдем распределение этого процесса. ( 7.3)
Это функция и плотность n-мерного распределения вектора X (t) в случае, когда все каналы заняты. Занятые (и только они) каналы персонифицированы, т.е. перенумерованы. То же, что и выше, но в случае, когда занято лишь «к» каналов, а остальные свободны. ( 7.4)
В дальнейшем, для простоты, будем трактовать плотность f (t; x …x ) как вероятность того, в СМО занято к каналов, которым присвоены номера от 1 до к., опуская при этом формальное умножение на . Знание этих распределений позволит вычислять вероятности состояний рассматриваемой системы. Для вывода необходимых уравнений используем марковское свойство процесса X(t), а именно: будем выражать вероятность состояния процесса в момент t+ t (будущее) через его состояние в момент t (настоящее). Предварительно заметим, что - вероятность того, что в системе нет требований. Для нулевого состояния СМО (в системе нет требований) можем, как и прежде, записать ( 7.5)
Второе слагаемое означает, что в момент t в одном из каналов системы было требование, обслуживание которого заканчивалось на интервале t , и этим каналом мог быть любой из n. Преобразуя и переходя к пределу при t 0, получим: ( 7.6)
Рассмотрим случай, когда 0 ( 7.6)
При составлении этого уравнения учитывалось следующее: · за время t занятости всех каналов уменьшаются на , и если за это время не подойдет ни одного требования входящего потока, то к моменту t система окажется в нужном состоянии (первое слагаемое правой части); · второе слагаемое правой части: в момент t был занят к-1 канал, а канал с номером i (из числа персонифицированных) был пустым, и что бы СМО пришла в нужное состояние необходимо: чтобы пришло требование, чтобы время его обслуживания было равно x , и чтобы из (n-к) свободных каналов оно выбрало именно i-ый, причем этим каналом может быть любой из каналов с номерами от 1 до к. · последнее слагаемое означает, что в момент t был занят (к + 1) канал, но в одном из них (а именно в (к+1)–ом) на интервале обслуживание заканчивалось. Причем таким каналом может быть любой из (n – к). Теперь рассмотрим случай, когда : ( 7.7)
Поясним, как и выше, содержание правой части: · Первое слагаемое отличается от случая к · Второе слагаемое в содержательном плане ничем не отличается от случая к · Третье слагаемое правой части отвечает ситуации, когда все каналы заняты, как это нужно, но один из них «недозанят», например, X (t) = Z < x ; для того, чтобы в момент t+ СМО оказалась в требуемом состоянии надо, чтобы на интервале пришло требование со временем обслуживания (x - z), и стало бы в очередь к i-му каналу, а для этого его занятость z должна быть меньше занятости любого другого канала (z < min x ) т.к. когда все каналы заняты, требование автоматически становится в очередь к тому который раньше освободится; при этом недозанятым может быть любой из n каналов. Вспоминая определение смешанной частной производной: ,( 7.8)
производя группировку членов уравнений, как это делалось выше, и переходя к пределу при , окончательно получим: ( 7.9)
( 7.10)
Эти уравнения относятся к стационарному режиму, что получило свое выражение в том, что производные плотностей распределения по t приняты равными нулю, а сами плотности записаны в финальной форме, как функции не зависящие от времени. Кроме того, для простоты последующих выкладок, приняты следующие обозначения: f = f и f = f . Решение этой системы, т.е. отыскание функций f и f , произведем следующим образом. Вначале, исходя из общих соображений содержательного характера, найдем вид этих функций, после чего подставим их в систему уравнений с целью установить, удовлетворяют они им или нет. Если ответ будет положительным, то решение системы уравнений найдено. Сперва рассмотрим случай 0 . Как говорилось выше, функция f имеет смысл вероятности того, что в СМО занято «к» персонофицированных (перенумерованных) каналов, причем первый освободится через x единиц времени, второй через x , … , к-ый через x . Каналы функционируют независимо, и время обслуживания в каждом распределено экспоненциально. Тогда вероятность рассматриваемого события равна: ( 7.11)
Вероятность того, что занято k перенумерованных каналов P - вероятность того, что в СМО занято k каналов Система массового обслуживания
называется системой с ожиданием, если заявка, заставшая все каналы
занятыми, становится в очередь и ждет, пока не освободится какой-нибудь канал. Если время ожидания заявки в
очереди ничем не ограничено, то система называется «чистой системой с
ожиданием». Если оно ограничено какими-то условиями, то система называется
«системой смешанного типа». Это промежуточный случай между чистой системой с
отказами и чистой системой с ожиданием. Для практики наибольший интерес
представляют именно системы смешанного типа. Ограничения, наложенные на
ожидание, могут быть различного типа. Часто бывает, что ограничение
накладывается на время ожидания заявки в очереди; считается, что оно ограничено
сверху каким-то сроком , который может быть как строго
определенным, так и случайным. При этом ограничивается только срок ожидания в
очереди, а начатое обслуживание доводится до конца, независимо от того, сколько
времени продолжалось ожидание (например, клиент в парикмахерской, сев в кресло,
обычно уже не уходит до конца обслуживания). В других задачах естественнее
наложить ограничение не на время ожидания в очереди, а на общее время
пребывания заявки в системе (например, воздушная цель может пробыть в зоне
стрельбы лишь ограниченное время и покидает ее независимо от того, кончился
обстрел или нет). Наконец, можно рассмотреть и такую смешанную систему (она
ближе всего к типу торговых предприятий, торгующих предметами не первой
необходимости), когда заявка становится в очередь только в том случае, если
длина очереди не слишком велика. Здесь ограничение накладывается на число
заявок в очереди. В системах с ожиданием
существенную роль играет так называемая «дисциплина очереди». Ожидающие заявки
могут вызываться на обслуживание как в порядке очереди (раньше прибывший раньше
и обслуживается), так и в случайном, неорганизованном порядке. Существуют
системы массового обслуживания «с преимуществами», где некоторые заявки
обслуживаются предпочтительно перед другими («генералы и полковники вне
очереди»). Каждый тип системы с ожиданием
имеет свои особенности и свою математическую теорию. Многие из них описаны,
например, в книге В. В. Гнеденко «Лекции по теории массового обслуживания». Здесь мы остановимся только на
простейшем случае смешанной системы, являющемся естественным обобщением задачи
Эрланга для системы с отказами. Для этого случая мы выведем дифференциальные
уравнения, аналогичные уравнениям Эрланга, и формулы для вероятностей состояний
в установившемся режиме, аналогичные формулам Эрланга. Рассмотрим смешанную систему
массового обслуживания с каналами при следующих условиях. На вход
системы поступает простейший поток заявок с плотностью . Время обслуживания одной заявки
-
показательное, с параметром . Заявка, заставшая все каналы занятыми,
становится в очередь и ожидает обслуживания; время ожидания ограничено некоторым
сроком ;
если до истечения этого срока заявка не будет принята к обслуживанию, то она
покидает очередь и остается необслуженной. Срок ожидания будем считать
случайным и распределенным по показательному закону где
параметр -
величина, обратная среднему сроку ожидания: ; . Параметр полностью аналогичен
параметрам и
потока
заявок и «потока освобождений». Его можно интерпретировать, как плотность
«потока уходов» заявки, стоящей в очереди. Действительно, представим себе
заявку, которая только и делает, что становится в очередь и ждет в ней, пока не
кончится срок ожидания , после чего уходит и сразу же снова
становится в очередь. Тогда «поток уходов» такой заявки из очереди будет иметь
плотность . Очевидно, при система смешанного типа
превращается в чистую систему с отказами; при она превращается в чистую систему с
ожиданием. Заметим, что при показательном
законе распределения срока ожидания пропускная способность системы не зависит
от того, обслуживаются ли заявки в порядке очереди или в случайном порядке: для
каждой заявки закон распределения оставшегося времени ожидания не зависит от
того, сколько времени заявка уже стояла в очереди. Благодаря допущению о
пуассоновском характере всех потоков событий, приводящих к изменениям состояний
системы, процесс, протекающий в ней, будет марковским. Напишем уравнения для
вероятностей состояний системы. Для этого, прежде всего, перечислим эти
состояния. Будем их нумеровать не по числу занятых каналов, а по числу
связанных с системой заявок. Заявку будем называть «связанной с системой», если
она либо находится в состоянии обслуживания, либо ожидает очереди. Возможные
состояния системы будут: Ни один канал не занят (очереди нет), Занят ровно один канал (очереди нет), Занято ровно каналов
(очереди нет), Заняты все каналов
(очереди нет), Заняты все каналов,
одна заявка стоит в очереди, Заняты все каналов,
заявок
стоят в очереди, Число заявок , стоящих в очереди, в наших
условиях может быть сколь угодно большим. Таким образом, система имеет бесконечное
(хотя и счетное) множество состояний. Соответственно, число описывающих ее
дифференциальных уравнений тоже будет бесконечным. Очевидно, первые дифференциальных
уравнений ничем не будут отличаться от соответствующих уравнений Эрланга: Отличие новых уравнений от
уравнений Эрланга начнется при . Действительно, в состояние система с отказами
может перейти только из состояния ; что касается системы с ожиданием, то
она может перейти в состояние не только из , но и из (все каналы заняты, одна
заявка стоит в очереди). Составим дифференциальное
уравнение для .
Зафиксируем момент и
найдем -
вероятность того, что система в момент будет в состоянии . Это может осуществиться тремя
способами: 1)
в момент система
уже была в состоянии , а за время не вышла из него (не пришла ни
одна заявка и ни один из каналов не освободился); 2)
в момент система
была в состоянии ,
а за время перешла
в состояние (пришла
одна заявка); 3)
в момент система
была в состоянии (все
каналы заняты, одна заявка стоит в очереди), а за время перешла в (либо освободился один канал и
стоящая в очереди заявка заняла его, либо стоящая в очереди заявка ушла в связи
с окончанием срока). Вычислим теперь при любом - вероятность того,
что в момент все
каналов
будут заняты и ровно заявок будут стоять в очереди. Это
событие снова может осуществиться тремя способами: 1)
в момент система
уже была в состоянии , а за время это состояние не изменилось
(значит, ни одна заявка не пришла, ни один капал не освободился и ни одна из стоящих в очереди
заявок не ушла); 2)
в момент система
была в состоянии ,
а за время перешла
в состояние (т.
е. пришла одна заявка); 3)
в момент система
была в состоянии ,
а за время перешла
в состояние (для
этого либо один из каналов должен освободиться, и тогда одна из стоящих в очереди
заявок займет его, либо одна из стоящих в очереди заявок должна уйти в связи с
окончанием срока). Следовательно: Таким образом, мы получили для
вероятностей состояний систему бесконечного числа дифференциальных уравнений: (19.10.1) Уравнения (19.10.1) являются
естественным обобщением уравнений Эрланга на случай системы смешанного типа с
ограниченным временем ожидания. Параметры в этих уравнениях могут быть как
постоянными, так и переменными. При интегрировании системы (19.10.1) нужно
учитывать, что хотя теоретически число возможных состояний системы бесконечно,
но на практике вероятности при возрастании становятся пренебрежимо
малыми, и соответствующие уравнения могут быть отброшены. Выведем формулы, аналогичные
формулам Эрланга, для вероятностей состояний системы при установившемся режиме
обслуживания (при ).
Из уравнений (19.10.1), полагая все постоянными, а все производные - равными
нулю, получим систему алгебраических уравнений: (19.10.2) К
ним нужно присоединить условие: Найдем
решение системы (19.10.2). Для этого применим тот же прием,
которым мы пользовались в случае системы с отказами: разрешим первое уравнение
относительно подставим
во второе, и т. д. Для любого , как и в случае системы с отказами,
получим: Перейдем
к уравнениям для . Тем же способом
получим: , , и
вообще при любом . (19.10.5) В обе формулы (19.10.4) и
(19.10.5) в качестве сомножителя входит вероятность . Определим ее из условия
(19.10.3). Подставляя в него выражения (19.10.4) и (19.10.5) для и , получим: , . (19.10.6) Преобразуем
выражения (19.10.4), (19.10.5) и (19.10.6), вводя в них вместо плотностей и «приведенные» плотности: (19.10.7) Параметры и выражают соответственно среднее число
заявок и среднее число уходов заявки, стоящей в очереди, приходящиеся на
среднее время обслуживания одной заявки. В новых обозначениях формулы
(19.10.4), (19.10.5) и (19.10.6) примут вид: ; (19.10.9) . (19.10.10) Подставляя (19.10.10) в (19.10.8)
и (19.10.9), получим окончательные выражения для вероятностей состояний
системы: ; (19.10.11) . (19.10.12) Зная вероятности всех состояний
системы, можно легко определить другие интересующие нас характеристики, в
частности, вероятность того, что заявка покинет систему
необслуженной. Определим ее из следующих соображений: при установившемся режиме
вероятность того,
что заявка покинет систему необслуженной, есть не что иное, как отношение
среднего числа заявок, уходящих из очереди в единицу времени, к среднему числу
заявок, поступающих в единицу времени. Найдем среднее число заявок уходящих
из очереди в единицу времени. Для этого сначала вычислим математическое
ожидание числа
заявок, находящихся в очереди: . (19.10.13) Чтобы получить , нужно умножить на среднюю
«плотность уходов» одной заявки и разделить на среднюю плотность заявок , т. е. умножить на
коэффициент 1.
Одноканальная СМО с ожиданием и
ограничением на длину очереди.
На
практике довольно часто встречаются
одноканальные СМО с очередью (врач,
обслуживающий пациентов; кассир, выдающий
зарплату). В теории массового обслуживания
одноканальные СМО с очередью также
занимают особое место: именно к таким
СМО относится большинство полученных
до сих пор аналитических формул для
немарковских систем. Рассмотрим
одноканальную СМО, на вход которой
поступает простейший поток заявок с
интенсивностью λ
.
Предположим, что поток обслуживаний
также простейший с интенсивностью μ
.
Это означает, что непрерывно занятый
канал обслуживает в среднем μ
заявок
в единицу времени. Заявка, поступившая
в СМО в момент, когда канал занят, в
отличие от СМО с отказами, не покидает
систему, а становится в очередь и ожидает
обслуживания. Далее
предполагаем, что в данной системе
имеется ограничение на длину очереди,
под которой понимается максимальное
число мест в очереди, а именно, предполагаем,
что в очереди могут находиться максимум
m
≥1
заявок. Поэтому заявка, пришедшая на
вход СМО, в момент, когда в очереди уже
стоят m
заявок,
получает отказ и покидает систему
необслуженной. Таким
образом, рассматриваемая СМО относится
к системам смешанного
типа с ограничением на длину очереди. Пронумеруем
состояния СМО по числу заявок, находящихся
в системе, т.е. под обслуживанием и в
очереди: S
0
–
канал свободен (следовательно, очереди
нет); S
1
–
канал занят и очереди нет, т.е. в СМО
находится (под обслуживанием) одна
заявка; S
2
–
канал занят и в очереди стоит одна
заявка; …………………………………………………….. S
m
+1
–
канал занят и в очереди m
заявок. Граф
состояний данной СМО представлен на
рис. 6 и совпадает с графом, описывающим
процесс гибели и размножения, с тем
отличием, что при наличии только одного
канала обслуживания все интенсивности
потоков обслуживаний равны μ
. Рис.
6. Схема состояний
в одноканальной системе с очередью Для
описания предельного режима работы СМО
можно воспользоваться изложенными
правилами и формулами. Запишем сразу
выражения, определяющие предельные
вероятности состояний: где
ρ = λ/μ
–
интенсивность нагрузки канала. Если
λ = μ
,
то получаем
. Пусть
теперь
. Заметим,
что при m
= 0
мы переходим к уже рассмотренной
одноканальной СМО с отказами. В этом
случае
. Определим
основные характеристики одноканальной
СМО с ожиданием: относительную и
абсолютную пропускные способности,
вероятность отказа, а также среднюю
длину очереди и среднее время ожидания
заявки в очереди. Поступившая
на вход СМО заявка получает отказ тогда
и только тогда, когда канал занят и в
очереди ожидают m
заявок,
т.е. когда система находится в состоянии
S
m
+1
.
Поэтому вероятность отказа определяется
вероятностью появления состояния S
m
+1
: Относительная
пропускная способность, или доля
обслуживаемых заявок, поступающих в
единицу времени, определяется выражением: Заметим,
что относительная пропускная способность
Q
совпадает
со средней долей принятых (т.е. не
получивших отказ) в систему заявок среди
всех поступивших, поскольку заявка,
попавшая в очередь, непременно будет
обслужена. Абсолютная
пропускная способность системы . Среднее
число заявок L
оч
,
стоящих в очереди на обслуживание,
определяется как математическое ожидание
дискретной случайной величины k
–
числа заявок, стоящих в очереди: . Случайная
величина k
принимает
значения 0, 1, 2, … , m
,
вероятности которых определяются
вероятностями состояний системы p
k
.
Таким образом, закон распределения
дискретной случайной величины k
имеет
следующий вид: Поэтому
по определению математического ожидания
дискретной случайной величины (с учетом
формул для вероятностей состояний)
получаем: (16) Предположим,
что ρ ≠
1
.
Очевидно, имеем: Но
сумма
представляет
собой сумму первых m
членов
геометрической прогрессии
.
(17) Подставив
выражение (17) в (16), найдем: или,
используя равенство
Если
же ρ =
1
,
то из равенства (16)
Тогда
среднее число заявок в очереди (18) Важной
характеристикой СМО с ожиданием является
среднее время ожидания заявки в очереди
. Для
вычисления математического ожидания
воспользуемся формулой полного
математического ожидания: если об
условиях опыта можно сделать n
(попарно)
несовместных гипотез где
M
(X
|
H
k
)
– условное математическое ожидание
величины X
при
гипотезе H
k
.
Рассмотрим
m
+
2
несовместных гипотез H
k
,
k
=
0,1,...,
m
+
1
,
состоящих в том, что СМО находится
соответственно в состояниях S
k
,
k
=
0,1,...,
m
+
1
.
Вероятности этих гипотез p
(H
k
)
=
p
k
,
k
=
0,1,...,
m
+1
. Если
заявка поступает в СМО при гипотезе H
0
S
0
,
в котором канал свободен, то заявке не
придется стоять в очереди и, следовательно,
условное математическое ожидание M
( Для
заявки, поступившей в СМО при гипотезе
H
1
,
т.е. когда СМО находится в состоянии S
1
,
в котором канал занят, но очереди нет,
условное математическое ожидание M
( Условное
математическое ожидание M
( Если
заявка поступит в систему при гипотезе
H
m
,
т.е. когда канал занят и в очереди ждут
m
−
1
заявок, то M
( Наконец,
заявка, пришедшая в СМО при гипотезе
H
m
+1
,
т.е. когда канал занят, m
заявок
стоят в очереди, и свободных мест в
очереди больше нет, получает отказ и
покидает систему. Поэтому в этом случае
M
( Следовательно,
по формуле полного математического
ожидания среднее время ожидания заявки
в очереди Подставляя
сюда выражения для вероятностей
p
k
(k
=1,2,...,m
),
получаем: Если
интенсивность нагрузки канала ρ
≠
1
,
то из равенства (19) с учетом формул (17),
(18), а также выражения для p
0
находим: Если
же ρ =
1
,
то, подставляя в равенство (19) выражение
p
0
= 1/(m
+2),
значение суммы
Итак,
для любого ρ
получаем
формулу для среднего времени пребывания
заявки в очереди, которая называется
формулой Литтла:
Пример.
На автозаправочной станции (АЗС) имеется
одна колонка. Площадка при станции, на
которой машины ожидают заправку, может
вместить не более трех машин одновременно,
если она занята, то очередная машина,
прибывшая к станции, в очередь не
становится, а проезжает на соседнюю
АЗС. В среднем машины прибывают на
станцию каждые 2 мин. Процесс заправки
одной машины продолжается в среднем
2,5 мин. Определить основные характеристики
системы. Решение.
Математической
моделью данной АЗС является одноканальная
СМО с ожиданием и ограничением на длину
очереди (m
=
3).
Предполагается, что поток машин,
подъезжающих к АЗС для заправки, и поток
обслуживаний – простейшие. Поскольку
машины прибывают в среднем через каждые
2 мин, то интенсивность входящего потока
равна λ
=1/2 =
0,5
(машин в минуту). Среднее время обслуживания
одной машины
Определяем
интенсивность нагрузки канала: ρ
= λ/μ
= 0,5/0,4 =
1,25. Вычисляем
вероятность отказа Среднее
число машин, ожидающих в очереди на
заправку Среднее
время ожидания машины в очереди находим
по формуле Литтла Таким
образом, из анализа работы СМО следует,
что из каждых 100 подъезжающих машин 30
получают отказ
(P
отк
≈ 29,7%),
т.е. обслуживаются 2/3 заявок. Поэтому
необходимо либо сократить время
обслуживания одной машины (увеличить
интенсивность потока обслуживаний),
либо увеличить число колонок, либо
увеличить площадку для ожидания.
.
Выражение дляp
0
можно
в данном случае записать проще, пользуясь
тем, что в знаменателе стоит сумма m
+ 2
членов геометрической прогрессии со
знаменателем ρ
:
(полученное
приρ ≠
1
),
имеем
а учитывая, что в этом случае
и
(суммаm
членов
арифметической прогрессии), окончательно
получаем
.
.
Пусть T
оч
–
непрерывная случайная величина,
представляющая собой время ожидания
заявки в очереди. Среднее время ожидания
заявки в очереди вычислим как математическое
ожидание этой случайной величины:
то полное математическое ожидание
случайной величиныX
может
быть вычислено по формуле
|
H
0
)
случайной величины
при
гипотезе H
0
,совпадающее
со средним временем ожидания заявки в
очереди при гипотезе H
0
,
равно нулю.
| H
1
)
случайной
величины
при
гипотезе H
1
,
совпадающее со средним временем ожидания
заявки в очереди при гипотезе H
1
,
будет равно среднему времени обслуживания
одной заявки
.
| H
2
)
случайной
величины
при
гипотезе H
2
,
т.е. при условии, что заявка поступила
в СМО, находящуюся в состоянии S
2
,
в котором канал занят и в очереди уже
ждет одна заявка, равно 2/
μ
(удвоенному
среднему времени обслуживания, поскольку
нужно обслужить две заявки: ту, которая
находится в канале обслуживания, и ту,
которая ждет в очереди). И так далее.
| H
m
).
| H
m
+1
)
= 0.
(19)
,
используя формулу (18) приρ
=
1
и
учитывая, что в данном случае μ
= λ
,
будем иметь
т.е.
среднее
время ожидания заявки в очереди
равно
среднему числу заявок в очереди
L
оч
,
деленному на интенсивность
λ
входящего
потока заявок.
= 2,5
мин, следовательно, интенсивность потока
обслуживаний μ
=1/2,5
= 0,4
(машины в минуту).
откуда относительная пропускная
способность
и
абсолютная пропускная способность A
= λ
Q
≈ 0,5⋅0,703
≈ 0,352.
= L
оч
/λ
≈1,559/0,5
= 3,118.