Материал. Лекции теория массового обслуживания для студентов экономических специальностей очной, заочной и дистанционной форм обучения Шахты 2006
 Скачать 0.66 Mb.
|
|
СМО с отказами В качестве показателей эффективности СМО с отказами будем рассматривать A 6 – абсолютную пропускную способность СМО, те. среднее число заявок, обслуживаемых в единицу времени Q 7 – относительную пропускную способность, те. среднюю долю пришедших заявок, обслуживаемых системой (или вероятность того, что пришедшая заявка будет обслужена отк P – вероятность отказа – вероятность того, что заявка покинет СМО необслуженной; k – среднее число занятых каналов (для многоканальной системы. 1.Одноканальная система с отказами Рассмотрим следующую задачу. Имеется один канал, на который поступает поток заявок с интенсивностью λ . Поток обслуживаний имеет интенсивность μ . Найти предельные вероятности состояний системы и показатели ее эффективности. Здесь ив дальнейшем будем предполагать, что все потоки событий, переводящие СМО из состояния в состояние, – простейшие. К ним относится и поток обслуживаний – поток заявок, обслуживаемых одним непрерывно занятым каналом. Поскольку среднее время между двумя произвольными соседними событиями простейшего потока обратно по величине интенсивности потока, а для потока обслуживаний это время есть время обслуживания одной заявки, то среднее время обслуживания μ 1 = об T Рисунок 8. 6 A – первая буква английского absolute – абсолютный. 7 Q – первая буква английского quota – доля, часть, квота. 0 S 1 S λ μ Система S (СМО) имеет два состояния 0 S – канал свободен, 1 S – канал занят. Размеченный граф состояний представлен на рисунке 8. В предельном стационарном режиме система алгебраических уравнений (6) для вероятностей состояний имеет вид (см. правило составления таких уравнений ⎩ ⎨ ⎧ = = , , 0 1 1 те. система вырождается водно уравнение. Учитывая нормировочное условие 1 1 0 = + p p , найдем из полученной предельные вероятности состояний μ λ λ μ λ μ + = + = 1 Предельные вероятности состояний 0 p и 1 p можно выразить через средние времена простоя канала при обслуживания одной заявки об. Для этого в формулы для вероятностей следует подставить об и пр. В результате получим пр об пр T T T p + = 0 , пр об об T T T p + = 1 Предельные вероятности выражают среднее относительное время пребывания системы в состоянии 0 S (когда канал свободен) и 1 S (когда канал занят, те. определяют соответственно относительную пропускную способность Q системы и вероятность отказа отк P : , μ λ μ + = Q μ λ λ + = отк P Пояснение. Почему 0 p Q = ? В самом деле, 0 p есть вероятность того, что заявка будет принята к обслуживанию (система находится в состоянии 0 S , те. канал свободен. Всего в единицу времени приходит в среднем λ заявок и из них обслуживается 0 p λ заявок. Тогда доля обслуживаемых заявок по отношению ко всему потоку заявок определяется величиной 0 Абсолютную пропускную способность (или, иначе, среднее число заявок, поступающих в СМО в единицу времени) найдем, умножив относительную пропускную способность Q на интенсивность потока заявок μ λ λμ λ + = = Пример. В фирму поступает простейший поток заявок на телефонные переговоры с интенсивностью 90 = λ вызовов в часа средняя продолжительность разговора по телефону 2 = об T мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера. Решение. Интенсивность потока обслуживаний = = = = ) 1 ( 5 , 0 2 1 1 мин T об μ ) 1 ( 30 ч . Относительная пропускная способность СМО 25 , 0 ) 30 90 ( 30 = + = Q , те. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа составит 75 , 0 25 , 0 1 = − = отк P . Абсолютная пропускная способность СМО 5 , 22 25 , 0 90 = ⋅ = A , те. в среднем в час будут обслужены 22,5 заявки на переговоры. Очевидно, что при наличии только одного телефонного номера СМО будет плохо справляться с потоком заявок. Многоканальная система с отказами задача Эрланга). Здесь мы рассмотрим одну из первых повремени, классических задач теории массового обслуживания эта задача возникла из практических нужд телефонии и была решена в 1909 г. датским инженером- математиком А.К. Эрлангом. Задача ставится так имеется n каналов (линий связи, на которые поступает поток заявок с интенсивностью λ . Поток обслуживаний каждого канала имеет интенсивность μ . Найти предельные вероятности состояний системы и показатели ее эффективности. Система S (СМО) имеет следующие состояния (нумеруем их по числу заявок, находящихся в системе 0 S , 1 S ,…, n S , где k S – состояние системы, когда в ней находится заявок, те. занято k каналов. Граф состояний СМО соответствует процессу гибели и размножения (рис. 9): Рисунок 9. Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ . Интенсивность же потока обслужива- ний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии 2 S (два канала заняты, то она может перейти в состояние 1 S (один канал занят, когда закончит обслуживание либо первый, либо второй канал, те. суммарная интенсивность их потоков об- служиваний будет μ 2 . Аналогично суммарный поток обслуживаний, переводящий СМО из состояния 3 S (три канала заняты) в 2 S , будет иметь интенсивность μ 3 , те. может освободиться любой из трех каналов, и т.д. В формуле (14) для схемы гибели и размножения получим для предельной вероятности состояния 1 2 2 0 ! ! ! 2 1 − ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + + + + + + = n n k k n k p μ λ μ λ μ λ μ λ , (15) где члены разложения μ λ , 2 2 ! 2 μ λ ,…, n n n μ λ ! – коэффициенты при 0 p в выражениях для предельных вероятностей n p p p ,..., , 2 Заметим, что в формулу (15) интенсивности λ и μ входят не по отдельности, а только в виде отношения μ λ . Обозначим и будем называть величину ρ приведенной интенсивностью потока заявок или интенсивностью нагрузки канала. Она выражает среднее число заявок, приходящих за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулу (15) в виде λ μ λ μ 2 λ μ 3 λ μ k λ μ ) 1 ( + k λ μ n ... ... ... ... 0 S 1 S 2 S k S n S 19 1 2 0 ! ! 2 1 − ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + + + + = n p n ρ ρ ρ . (16) При этом 0 1 p p ρ = , 0 2 2 ! 2 p p ρ = , … , 0 ! p n p n n ρ = . (17) Формулы (16) и (17) для предельных вероятностей получили названия формул Эрлан- га в честь основателя теории массового обслуживания. Вероятность отказа СМО есть предельная вероятность того, что все n каналов системы будут заняты, те. 0 ! p n p P n n отк ρ = = Отсюда находим относительную пропускную способность – вероятность того, что заявка будет обслужена 0 ! 1 1 p n P Q n n отк ρ − = − = Абсолютную пропускную способность получим, умножая интенсивность потока заявок на Q : ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − = = 0 ! 1 p n Q A n ρ λ λ . (18) Осталось только найти среднее число занятых каналов k . Эту величину можно было бы найти впрямую, как математическое ожидание дискретной случайной величины с возможными значениями n ,..., 1 , 0 и вероятностями этих значений n p p p ,..., , 1 0 : ∑ = = ⋅ + + ⋅ + ⋅ + ⋅ = n k k n kp p n p p p k 0 2 1 0 2 Подставляя сюда выражения (17) для k p и выполняя соответствующие преобразования, мы, в конце концов, получили бы формулу для k . Однако среднее число занятых каналов можно найти проще, если учесть, что абсолютная пропускная способность A системы есть нечто иное, как интенсивность потока обслуженных системой заявок (в единицу времени. Так как каждый занятый канал обслуживает в среднем μ заявок (в единицу времени, то среднее число занятых каналов или, учитывая (18): Пример. В условиях предыдущего примера определить оптимальное число телефонных номеров в фирме, если условием оптимальности считать удовлетворение из каждых 100 заявок на переговоры в среднем не менее 90 заявок. Решение. Интенсивность нагрузки канала 3 30 / 90 = = ρ , теза время среднего (по продолжительности) телефонного разговора мин T об 2 = поступает в среднем 3 заявки на переговоры. Будем постепенно увеличивать число каналов (телефонных номеров) ,... 4 , 3 , 2 = n и определим для получаемой канальной СМО характеристики обслуживания. Значения характеристик СМО сведем в таблицу. Число каналов (телефонных номеров) Показатели эффективности Обозначение 1 2 3 4 5 6 Относительная пропускная способность Q 0,25 0,47 0,65 0,79 0,90 0,95 Абсолютная пропускная способность A 22,5 42,3 58,8 71,5 80,1 85,3 По условию оптимальности 9 , 0 ≥ Q , следовательно, в фирме необходимо установить 5 телефонных номеров (в этом случае 90 , 0 = Q ). При этом в час будут обслуживаться в среднем 80 заявок ( 1 , 80 = A ), а среднее число занятых телефонных номеров (каналов) = k 67 , 2 30 Тут уже проглядывает некоторый намек на оптимизацию. В самом деле, содержание каждого канала в единицу времени обходится в какую-то сумму. Вместе стем, каждая обслуженная заявка приносит какой-то доход (если речь идет о СМО, для которых этот доход можно оценить. Умножая этот доход на среднее число заявок A , обслуживаемых в единицу времени, мы получим средний доход от СМО в единицу времени. Естественно, при увеличении числа каналов этот доход растет, но растут и расходы, связанные с содержанием каналов. Что перевесит – увеличение доходов или расходов Это зависит от условий операции, те. отплаты за обслуживание заявки и от стоимости содержания канала. Зная эти величины, можно найти оптимальное число каналов, наиболее экономически эффективное. СМО с ожиданием (с очередью) 1. Одноканальная СМО с ожиданием и ограничением на длину очереди На практике довольно часто встречаются одноканальные СМО с очередью (врач, обслуживающий пациентов кассир, выдающий зарплату телефон-автомат на улице и т.д.). В теории массового обслуживания одноканальные СМО с очередью также занимают особое место именно к таким СМО относится большинство полученных до сих пор аналитических формул для не- марковских систем. Рассмотрим одноканальную СМО, на вход которой поступает простейший поток заявок с интенсивностью λ . Предположим, что поток обслуживаний также простейший с интенсивностью. Это означает, что непрерывно занятый канал обслуживает в среднем заявок в единицу времени. Заявка, поступившая в СМО в момент, когда канал занят, в отличие от СМО с отказами, не покидает систему, а становится в очередь и ожидает обслуживания. Далее предполагаем, что в данной системе имеется ограничение на длину очереди, под которой понимается максимальное число мест в очереди, а именно, предполагаем, что в очереди могут находиться максимум 1 ≥ m заявок. Поэтому заявка, пришедшая на вход СМО, в момент, когда в очереди уже стоят m заявок, получает отказ и покидает систему не- обслуженной. Таким образом, рассматриваемая СМО относится к системам смешанного типа с ограничением на длину очереди. Пронумеруем состояния СМО по числу заявок, находящихся в системе, те. под обслуживанием ив очереди 0 S – канал свободен (следовательно, очереди нет 21 1 S – канал занят и очереди нет, те. в СМО находится (под обслуживанием) одна заявка 2 S – канал занят ив очереди стоит одна заявка …………………………………………………….. 1 + m S – канал занят ив очереди m заявок. Граф состояний данной СМО представлен на рис. 10 и совпадает с графом , описывающим процесс гибели и размножения, стем отличием, что при наличии только одного канала обслуживания все интенсивности потоков обслуживаний равны Рисунок 10. Для описания предельного режима работы СМО можно воспользоваться изложенными ранее правилами и формулами. Запишем сразу выражения, определяющие предельные вероятности состояний ( ) ⎪⎩ ⎪ ⎨ ⎧ + + + + = + = ⋅ = − + , 1 , 1 ,..., 2 , 1 , 1 1 2 где μ λ ρ = – интенсивность нагрузки канала. Если μ λ = , то получаем ) 2 ( 1 1 1 Пусть теперь μ λ ≠ ( 1 ≠ ρ ). Выражение для 0 p можно в данном случае записать проще, пользуясь тем, что в знаменателе стоит сумма 2 + m членов геометрической прогрессии со знаменателем ρ : 2 0 1 Заметим, что примы переходим к уже рассмотренной одноканальной СМО с отказами. В этом случае ) ( ) 1 ( ) 1 ( 2 0 μ λ μ ρ ρ + = − − = p (как и было получено ранее. Определим основные характеристики одноканальной СМО с ожиданием относительную и абсолютную пропускную способность, вероятность отказа, а также среднюю длину очереди и среднее время ожидания заявки в очереди. Поступившая на вход СМО заявка получает отказ тогда и только тогда, когда канал занят ив очереди ожидают m заявок, те. когда система находится в состоянии 1 + m S . Поэтому вероятность отказа определяется вероятностью появления состояния 1 + m S : ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ = + ≠ − − = = + + + 1 , 2 1 ; 1 , 1 ) 1 ( 2 1 1 ρ ρ ρ ρ ρ если m если p P m m m отк Относительная пропускная способность, или доля обслуживаемых заявок, поступающих в единицу времени, определяется выражением ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ = + + ≠ − − = − = + + 1 , 2 1 ; 1 , 1 1 1 2 1 ρ ρ ρ ρ если m m если P Q m m отк ... ... 0 S 1 S 2 S 1 + m S λ λ λ λ μ μ μ μ Заметим, что относительная пропускная способность Q совпадает со средней долей принятых (те. не получивших отказ) в систему заявок среди всех поступивших, поскольку заявка попавшая в очередь непременно будет обслужена. Абсолютная пропускная способность системы Среднее число заявок оч L , стоящих в очереди на обслуживание определяется как математическое ожидание дискретной случайной величины k – числа заявок, стоящих в очереди ) ( k M L оч = Случайная величина k принимает значения 0, 1, 2, … , m, вероятности которых определяются вероятностями состояний системы k p . Таким образом, закон распределения дискретной случайной величины k имеет следующий вид k 0 1 2 … m p 1 0 p p + 2 p 3 p … Поэтому по определению математического ожидания дискретной случайной величины (с учетом формул для вероятностей состояний) получаем = ⋅ + + ⋅ + ⋅ + + ⋅ = +1 3 2 1 0 2 1 ) ( 0 ) ( m p m p p p p k M ∑ ∑ ∑ = − = + = + = = = m j j m j j m j j j p p j jp 1 1 0 2 1 0 1 1 1 ρ ρ ρ . (19) Предположим, что 1 ≠ ρ . Очевидно имеем ∑ ∑ ∑ = = = − = = m j j j m j m j j d d d d j 1 1 1 Но сумма ∑ = m j j 1 ρ представляет собой сумму первых m членов геометрической прогрессии m ρ ρ ρ ρ ,..., , , 3 2 : ρ ρ ρ ρ ρ ρ ρ − − = − − = + = ∑ 1 1 ) 1 ( 1 1 m m m j j , 1 ≠ ρ . Тогда ) 1 ( ) 1 ( ) 1 ( 1 1 2 1 1 1 1 ≠ − − + − = ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ − − = = + = = − ∑ ∑ ρ ρ ρ ρ ρ ρ ρ ρ ρ ρ ρ m m d d d d j m m m j j m j j . (20) Подставив выражение (20) в (19), найдем 2 0 2 ) 1 ( ) 1 ( 1 ) ( ρ ρ ρ ρ − − + − = m m p k M m , или, используя равенство 2 0 1 1 + − − = m p ρ ρ (полученное при 1 ≠ ρ ), имеем ( ) ) 1 )( 1 ( ) 1 ( 1 ) ( 2 Если же 1 = ρ , то из равенства (19) ∑ = = m j j p k M 1 0 ) ( , а учитывая, что в этом случае ) 2 ( 1 0 + = m p и 2 ) 1 ( 1 + = ∑ = m m j m j (сумма членов арифметической прогрессии, окончательно получаем Итак, среднее число заявок в очереди ( ) ⎪ ⎪ ⎩ ⎪⎪ ⎨ ⎧ = + + ≠ − − − + − = + 1 , ) 2 ( 2 ) 1 ( ; 1 , ) 1 )( 1 ( ) 1 ( 1 2 2 ρ ρ ρ ρ ρ ρ ρ если m m m если m m L m m оч (21) Важной характеристикой СМО с ожиданием является среднее время ожидания заявки в очереди оч T . Пусть оч T – непрерывная случайная величина, представляющая собой время ожидания заявки в очереди. Среднее время ожидания заявки в очереди вычислим как математическое ожидание этой случайной величины ) ( оч оч T M T = Для вычисления математического ожидания воспользуемся формулой полного математического ожидания если об условиях опыта можно сделать n (попарно) несовместных гипотез n H H H ,..., , 2 1 , то полное математическое ожидание случайной величины X может быть вычислено по формуле ) | ( ) ( ) ( 1 k n k k H X M H P X M ∑ = = , где ) | ( k H X M – условное математическое ожидание величины X при гипотезе k H [Вентцель, Овчаров Прикладные задачи теории вероятностей. – М Радио и связь, 1983, с. Рассмотрим 2 + m несовместных гипотез k H , 1 ,..., 1 , 0 + = m k , состоящих в том, что СМО находится соответственно в состояниях k S , 1 ,..., 1 , 0 + = m k . Вероятности этих гипотез, Если заявка поступает в СМО при гипотезе 0 H , те. когда СМО находится в состоянии, в котором канал свободен, то заявке не придется стоять в очереди и, следовательно, условное математическое ожидание ) | ( 0 H T M оч случайной величины оч T при гипотезе 0 H , совпадающее со средним временем ожидания заявки в очереди при гипотезе 0 H , равно нулю. Для заявки, поступившей в СМО при гипотезе 1 H , те. когда СМО находится в состоянии, в котором канал занятно очереди нет, условное математическое ожидание ) | ( 1 H T M оч случайной величины оч T при гипотезе 1 H , совпадающее со средним временем ожидания заявки в очереди при гипотезе 1 H , будет равно среднему времени обслуживания одной заявки μ 1 = об T Условное математическое ожидание ) | ( 2 H T M оч случайной величины оч T при гипотезе, те. при условии, что заявка поступила в СМО, находящуюся в состоянии 2 S , в котором канал занят ив очереди уже ждет одна заявка, равно μ 2 (удвоенному среднему времени обслуживания, поскольку нужно обслужить две заявки ту, которая находится в канале обслуживания, и ту, которая ждет в очереди. Итак далее. Если заявка поступит в систему при гипотезе m H , те. когда канал занят ив очереди ждут 1 − m заявок, то μ m H T M m оч = ) | ( Наконец, заявка, пришедшая в СМО при гипотезе 1 + m H , те. когда канал занят, заявок стоят в очереди, и свободных мест в очереди больше нет, получает отказ и покидает систему. Поэтому в этом случае 0 ) | ( 1 = + m оч H T M Следовательно, по формуле полного математического ожидания, среднее время ожидания заявки в очереди ∑ ∑ ∑ + = = = = ⋅ = ⋅ = = 1 0 1 1 1 ) | ( ) ( ) ( m k m k m k k k k оч k оч оч kp k p H T M H p T M T μ μ Подставляя сюда выражения для вероятностей k p ( m k ,..., 2 , 1 = ), получаем ∑ ∑ = − = = = m k k m k k оч k p p k T 1 1 1 0 0 1 ρ μ ρ ρ μ . (22) Если интенсивность нагрузки канала 1 ≠ ρ , то из равенства (22) с учетом формула также выражения для 0 p находим = − − + − ⋅ − − ⋅ = + 2 2 ) 1 ( ) 1 ( 1 1 1 ρ ρ ρ ρ ρ μ ρ m m T m m оч λ ρ ρ μρ ρ ρ ρ оч m m L m m = − − − + − = + ) 1 )( 1 ( ) 1 ( 1 ( 2 Если же 1 = ρ , то, подставляя в равенство (22) выражение ) 2 ( 1 0 + = m p , значение суммы 2 ) 1 ( 1 + = ∑ = m m k m k , используя формулу (21) при 1 = ρ и учитывая, что в данном случае λ μ = , будем иметь λ λ оч оч L m m m T = + + = ) 2 ( 2 ) 1 ( Итак, для любого ρ получаем формулу для среднего времени пребывания заявки в очереди, которая называется формулой Литтла: λ оч оч L T = , те. среднее время ожидания заявки в очереди оч T равно среднему числу заявок в очереди оч L , деленному на интенсивность λ входящего потока заявок Пример. На автозаправочной станции (АЗС) имеется одна колонка. Площадка при станции, на которой машины ожидают заправку, может вместить не более трех машин одновременно, и если она занята, то очередная машина, прибывшая к станции, в очередь не становится, а проезжает на соседнюю АЗС. В среднем машины прибывают на станцию каждые 2 мин. Процесс заправки одной машины продолжается в среднем 2,5 мин. Определить основные характеристики системы. Решение. Математической моделью данной АЗС является одноканальная СМО с ожиданием и ограничением на длину очереди ( 3 = m ). Предполагается, что поток машин, подъезжающих к АЗС для заправки, и поток обслуживаний – простейшие. Поскольку машины прибывают в среднем через каждые 2 мин, то интенсивность входящего потока равна 5 , 0 2 1 = = λ (машин в минуту. Среднее время обслуживания одной машины 5 , 2 = об T мин, следовательно, интенсивность потока обслуживаний 4 , 0 5 , 2 1 = = μ (машины в минуту. Определяем интенсивность нагрузки канала 25 , 1 4 , 0 Вычисляем вероятность отказа 297 , 0 1 ) 1 ( 5 4 ≈ − − = ρ ρ ρ отк P , откуда относительная пропускная способность 703 , 0 297 , 0 1 1 = − ≈ − = отк P Q и абсолютная пропускная способность Среднее число машин, ожидающих в очереди на заправку ( ) 559 , 1 ) 1 )( 1 ( ) 3 4 ( 1 5 3 2 ≈ − − − − = ρ ρ ρ ρ ρ оч L Среднее время ожидания машины в очереди находим по формуле Литтла 118 , 3 5 , 0 559 , 1 = ≈ = λ оч оч L T Таким образом, из анализа работы СМО следует, что из каждых 100 подъезжающих машин 30 получают отказ ( % 7 , 29 ≈ отк P ), те. обслуживаются 2/3 заявок. Поэтому необходимо либо сократить время обслуживания одной машины (увеличить интенсивность потока обслуживаний), либо увеличить число колонок, либо увеличить площадку для ожидания. Оптимальное решение принимается с учетом затрат, связанных соответственно с увеличением штата обслуживающего персонала (увеличение производительности канала, с расширением площадки для ожидания или приобретением дополнительной колонки, и потерь, связанных с потерей заявок на обслуживание. |