2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 13
Текст из файла (страница 13)
1 — е '". Перед каждым прибором допускается неограниченная очередь. Входящий поток требований — пуассоновский с интенсивностью а. Пусть Г,(1) — число требований перед 1-м прибором (включая 66 и то, которое находится на обслуживании) в момент 1, 1.(!) = = (Е1(!), ..., Еь(1)). Показать, что при гпах — ( 1 ы.<ь Ь! ! пп Р (1. (!) =- и) = П ~ 1 — — );— ~=! где п= (пь ..., пь). $3 МЕТОД ЭТАПОВ ЭРЛАНГА 1. Введение. В этом параграфе мы изучим системы обслуживания, в которых либо интервалы времени между поступлениями требований, либо времена обслуживания распределены по эрланговскому закону. Процесс Е(!) (число требований в системе в момент 1) в этих случаях не является марковским.
Поэтому, исходя из определения, данного в начале главы, такие системы не являются марковскими. Тем не менее в силу большого сходства применяемых здесь методов с методами анализа марковских систем и близостью рассматриваемых моделей к системам с групповым поступлением .или групповым обслуживанием данный параграф помещен в главе, посвященной марковским СМО. Идея применяемого в данном параграфе метода основывается на следующем свойстве распределения Эрланга.
Пусть ~— случайная величина, имеющая распределение Эрланга порядка й. Тогда где ~ь ...,=ь независимы и одинаково распределены по показательному закону. 2. Система обслуживания М!Еь!1!со. Пусть а — интенсивность входящего потока, В (х) = ьм ьФ-1 е — "йи- —,'к о. времени обслуживания. Как мы уже (Ь !Р о отмечали, в случае й~ь! процесс ' (1) не является марковским. Однако, используя своиство (1) эрланговского распределения, можно свесги изучение процесса Е(!) к изучению марковского процесса т (!), к описанию которого мы сейчас перейдем. Из представления (1) вытекает, что время обслуживания каждого требования можно представить в виде суммы «этапов обслу>киванияэк которые независимы и показательно распределены Каждое требование начинает обслуживание с 1-го этапа и покидает систему, как только завершится й-й этап.
Такая интерпретация процесса обслуживания позволяет ввести следующий марковский процесс т(1) (который полностью определяет Е(!)); будем считать, что в систему через показательно распределенные с параметром а интервалы времени поступают 67 некоторые фиктивные требования — «этапы». Их поступление производится группами объема й. Длительности обслуживания этапов — показательно распределенные с параметром ((Ь случайные величины. Этапы обслуживаются по одному. Процесс т(!) определяется как число этапов обслуживания в системе в момент й Из определения процесса т(!) вытекает справедливость следующих соотношений, связывающих распределения сл.в.
т(!) и г.(!): Р(й(!) =О) = Р(т(!) =О), м Р (). (!) = !) = Е Р (ч (!) = )), ! =- 1 2 (=.(( — пь+1 п«=1((п Р(Е(!) =О) =!!гп Р(т(!) =О) =ро, (2) и,. =-1пп Р(Ь (!) = !) = ! ° м м — 1(ппР(т())=))= ~а р;, (=1,2, .... (3) (= (~ — и г-(- ! ю /=(( — пг+1 Для нахождения р; воспользуемся результатами $2, в котором была изучена система с групповыми поступлениями требований. Пусть Р (г) =- ~ г'рь (еа тогда при а(Ь<1 (так как распределение т(() совпадает с распределением числа требований в системе М [М [1[ос с групповым поступлением фиксированного объема й): Р (г) = ЬЬ (1 — Ь) (1 — г) АЬ+ агг+' — (а+ Ьь) г Для нахождения р; представим знаменатель в выражении для Р(г) в виде И+аг'-' — (а+И)г= (! — г) [И вЂ” а(г+гг+...+г")].
Обозначим через гь ..., гх корни многочлена И вЂ” а ( г+ гг+ ... + г') . Тогда Р(г) = (( — г)гб ... (1 — г(г,) Отсюда Из последнего соотношения находим ро= 1 — а/Ь, р; = (1 — а/Ь) ~)~ ~г —,. 1 П, /,'= 1, 2, 1 — 71/7л л=-1 л«1 Используя (2) и (3), получаем по=1 — а/Ь, л 7 1 — 71 я,.
=- (1 — а/Ь) ~ г,— '" ) — 71 П 1 1 — 7117л л=! лМ 3. Система обслуживания. Ео(М)1) оо. В этом случае ф. р. интервалов между поступлениями требований имеет вид л»« и" ' А (Х)' = ~ Š— «7(и, (Ь вЂ” 1)! ф. р. времени обслуживания В(х) =1 — е — "". Процесс поступления требований в рассматриваемую систему обслуживания можно интерпретировать следующим образом: каждое требование при своем поступлении проходит /т «этапов поступления». Время пребывания требования на каждом этапе является случайной величиной с показательным распределением 1 †е †"'*. Поступление каждого требования начинается с первого этапа, н, как только истечет время пребывания на этапе Ь, требование поступает в систему.
Такая интерпретация процесса поступления позволяет следующим образом интерпретировать процесс обслуживания. Будем считать, что каждое требование содержит в себе столько этапов, сколько «этапов поступления» оно прошло. В частности, требование, уже находящееся в системе, содержит й этапов. Пусть ))(()— общее число этапов в системе в момент времени й Из определения процесса ))(/) вытекают следующие соотношения: 7)1-)-1) — ! Р(/.(/) =1) = Е Р(Р(/) =/) )=и Л(1-)- !) — 1 Л!1+!) — 1 11,.
=!ппР(Е(/) =-1) = ~ 1$)п Р(Р(/) =/) = ~ р;. )'=ь ) —" л 69 Кроме того, процесс ))(/) можно рассматривать как число требований в момент / в следующей системе обслуживания: входящий поток — пуассоиовский с интенсивностью Ьа; требования обслуживаются группами объема Ь; длительность обслу- о-! (! .
оФ) ~ъ у!р. Р(г) = ооо~+' — (! —, оа) о" -о ! (4 где р=а,'Ь. Знаменатель в правой части (4) представляет сабо многочлен по г степени /о+1, поэтому он имеет /о+! корень Один из нпх равен 1. Используя теорему Руше, можно показать что в области 1г~ < 1 находится ровно й корней, а в облает (г)<1 — Ь вЂ” 1 корень (обозначим их г;, ..., го ~). Таким абра зом, один пз корней многочлена (обозначим его го) удовлетво ряет условию )го~ >1. Так как функция Р(г) ограничена пр (г~ <1, числитель в (4) должен обращаться в нуль в точка 70 живания группы требований — случайная величина с показа тельным распределением 1 — е-'"; если в системе находится 1 1<1, требований, то их обслуживание не производится до те пор, пока число требований в системе не станет больше ил равным А. Легко видеть, что процесс р(!) является однородной мар- ковской цепью с непрерывным временем и обладает следующи-~ ми свойствами.
1. Множеством его состояний является множество целых не- отрицательных чисел. 2. Время пребывания процесса р(/) в состоянии !, 0<(<з </о — 1, является случайной величиной с показательным распре-, делением 1 — е — о'", после чего он переходит в состояние 1+1., Время пребывания процесса р(!) в состоянии !, (~й, — сл.в. с показательным распределением 1 — е-мо+ь>*, после чего про- цесс переходит в состоянии 1+1 и ! — Ь с вероятностями Аа/(/оа+Ь) и Ь/(/оа+Ь). Положим Р,(/) =Р(р(/) =!). Исходя из свойств 1, 2 процес- са р(/) выводится система дифференциальных уравнений Ро'(/) = — 'йаРоЯ +Ьри(/), Р,'(/) = — йаР, (/) + йаР,, (/) + ЬР;,о (/), 1 <( < й — 1, Р;(/) = — (/оа+Ь)Р;(/)+йаР, ~(1)+ЬР~о,(!), /)й.
Если а/Ь<1, то существует !пиР,(/) =р„н р; удовлетворяют системе линейных уравнений /гаро= Ьрм дар,=йар,, +Ьр,„о, 1 <1</о — 1, (иа+ Ь) р, =йар,, + Ьр,~,, () й, р, =-1. ~=-о ! Положим Р(г) == Ъ г'р,. Тогда у=о гь ..., го, и 1. Так как все корни многочлена г' — 1 равны по модулю единице, го, ..., го, должны быть корнями многочлена о †! г!Р;. !=о Таким образом, (4) можно переписать в виде (! — го) ро ,(" — г,) ... (г — го ,) Р (г) = Ар (г — 1)(г — го) (г — го) ... (г — го г) (! — го) !го !гр (! — г)(! — ггго) го Гак как Р (!) =. 1, то ' ' = 1 или Лр (1 — г,— ') го дарго о(! — го !) Следовательно, (! — г )(! — го ) о ! о ' (Ыго) ' Р(г) = =(1 — г') ~— гг(! — г)(! — г/го) 1 ! — г ! — г!го ,Разлагая Р(г) по степеням г, находим ) г '(1 — г,— ! — '), 0 ~<1~(й — '1, Р1 =- р(г,— 1)г„'-1-', 1) л. Напомним, что цвыл †! я,.
= 1пп Р(1.(!) =- !) = ~) р1. оо 1=м Отсюда (1 — р, !'=О, [ р(г," — 1) га и 1= 1 2 4. Заключение. Заметим, что метод этапов Эрланга, использованный при анализе систем обслуживания М(Ео(1(со н Ео(М(1(со, фактически является частным случаем метода дополнигельных компонент, который систематически будет использоваться в последую!цих главах. Поясним это на примере системы М(Е„(1!оо. Введем случайный процесс !(1) следую!цнм образом; если в момент ! система занята и требование, находян!ееся на приборе, проходит 1-й этап обслуживания, полагаем /(!) =)г — 1+1 Если в момент ! система свободна, полагаем )(!) =О. Из свойства отсутствия последействия у показагельного распределения следует, что процесс (Е(!), 1(!)) яв!яется однородной марковской цепью с непрерывным временем, чножсством состояний которой является множество пар неотрицательных целых чисел (г, /), где г=О, 1, 2, ...,1=0, 1, ..., й.
Пе- 71 ренумеровав состояния процесса следуюшим образом: (0,0) О, (Е,у) /гК+1', Х>0, 1>1, получаем процесс т(1). Аналогичный метод применим к анализу и других систем ,' обслуживания (см. задачу 2). 5. Задачи. 3 а д а ч а 1. Найти 1!гп Мь(Г) в системах М1Ез)11оо и с Ез1М~!1оо. Сравнить с аналогичной характеристикой системы М (М11 ! оо. 3 а д а ч а 2. Найти стационарное распределение процесса Е(Г) в системах а) Е~)Е,(1)оо; б) Ед|НМ,111оо; в) НМ~(Е,(1(оо; г) НМ» ~ НМ,111оо. Литература 13, 6, 121 Глава 2. Системы обслуживания йь (6~1 В предыдущей главе мы изучили системы обслуживания, в которых интервалы времени между поступлениями требований н длительности обслуживания имели показательные распределения. Одно из основных свойств показательного распределения — отсутствие последействия — обеспечивает сравнительную простоту изучения таких систем, Если отказаться хотя бы от одного из этих предположений (о показательном распредеиии интервалов между поступлениями или показательном распределении длительности обслуживания), анализ становится существенно более сложным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
