2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 31
Текст из файла (страница 31)
Из (3) и (5) находим (5) а! (а!Р!2+ агйг!! +а,, 2(1 — а»Р1!) Йг[й!(ч!+ 02Р221 2 +а. (»-,Р„) х 21 1 — й»()1! х„= х + 12 1 — Йг[)2! !76 Р! (1, 1) =Й1, Р2(1, 1) =Й2. Отсюда, в частности, следует, что Р»(1,4) и.Рг(1, 1) не зависят от выбора функции переключения и(1). Далее, дифференцируя (2) а) два раза по г», б) ПОЗ»ИПОХг, в) два раза по г,, в точке х»=хг=! получаем следующие три соотношения: ( — 2+ 2агр!1 — а»2 р!2) а»+ 2 (1 — а»р!1) хн+ + аг [ — а!' ргг[ +2 ( — а»рг») х㻠— — О, (3) (агр»1 — а,а!р!2) а, + (1 — а»[)11) х„+ ( — аг[)1 !) х11+ Подставляя полученные выражения для хп и хгг в (4), имеем хи хг, агав]агВгг+агВгг] ] 1 1 В„1~,Ви 2(1,п,Вп] ] 1,Ви + ! В„3 1 — аг Используя полученные результаты, функционал 7 можно записать в виде сваг!Вгг сгагагВвв 7 = сгЯ1г + сгМ1,г = сгхггВгг + сгВггхгг+ + + агв сгагагргг сгагрвв + сгВггхгг + сгВггхгг + 2 2 сгВггагВгг а,Вгг хг, + сгВггхгг + сгВггхгг + сгВгг хгг + Ф 1 — агВгг .Ввг где еВ зависит от сь с,, аь аг, Вгг, Виь Вм, Ваь но не зависит от функции переключения.
Преобразовав выражение для 7, получаем х„+ 'Вп х„+ гр. 1 — агВгг ' 1 — ~Ввг Кроме того, хм и хгг связаны соотношением хи хп 1 — агВгг 1 — агВгг где у а,а,(агВгг+агВгг] 1 1 + 2(1 — агВгг — агВгг] ! ! — агВгг 1 — агВвг Полагая «гв хгг = Угг = Уи авВгг ! — агВгг имеем Х = с!Вг!Угг + сгВг !У~ а+ф, (6) Уса+Ум =У. (7) КРоме того, Уи>0, Уи>0. Из (7) Угг=у — Угь Следовательно, г =- (С~Вг! — сгВи)угг+ф+сгВиу, причем 0 (угг (7. Итак, У представляет собой линейную функцию по уп. Ее минимум на отрезке !О, у) достигается либо в точке угг=О, . ибо в точке ум=у (что эквивалентно у~г=О) в зависимости от того, с1Вг| — сгВи>0 пли с1Вгт — сгВп<0, т.
е. с1/Ви>сг1Вг~ илп сДп(сг/Вг! ° 177 ? В Ф Матвеев, В. Г. Ушвког Для определенности рассмотрим какой-нибудь один из эт случаев, например снф~>сг/йм. Тогда хн>0, хм>0, ха> хм=О. Вспоминая, что дР;(гд, г,) д2~ л,=! а Р;(гь гз) — совместная производяшая функция числа требо ваний первого и второго потоков в момент начала обслужива;, ния требования 1-го потока, видим, что (так как хм=О, а вщ коэффициенты разложения Р,(х, гг) по степеням г„и гз неотрицательны) Р,(аь ха) не зависит от г,; это эквивалентно тому, что требования первого потока имеют относительный приоритет, перед требованиями второго потока. В 3. Задачи. 3 а д а ч а 1.
Доказать утверждение теоремы 1 для произ. вольного г) 2. 3 ад а ч а 2. Доказать, что утверждение теоремы 1 остается справедливым, если функция переключения выбирается в зависимости от траектории процесса 1. (Г) от 1=0 до момента принятия решения включительно. Литература: 12, 4, 5, 13, 161 Глава 4. Системы обслуживания с непуассоновскими входящими потоками В предыдущих главах были изучены различные модели систем массового обслуживания, при этом предполагалось, что входящий поток требований является пуассоновским. Отказ от э1ого предположения приводит к существенному усложнению задачи.
Даже для рекуррентных входящих потоков в приоритетных системах обслуживания изучено очень мало характеристик. В данной главе будут рассмотрены два частных случая рекуррентных потоков; эрлангоэские и гиперэкспоненциальные. С одной стороны, такие потоки часто возникают в реальных системах, с другой — ими достаточно точно можно приблизить широкий класс рекуррентных потоков. В частности, во многих случаях для получения необходимой точности достаточно приблизить первые два момента интервалов между поступлениями требований.
В этих случаях при о)га можно взять гиперэкспоненциальный поток, а при о<т — эрланговский, где ти — математическое ожидание и о' — дисперсия интервалов между поступлениями требований. $ и СИСТЕМА ОБСЛУЖИВАНИЯ НМ)О,П(~ С ОТНОСИТЕЛЬНЫМ ПРИОРИТЕТОМ 1. Описание системы. Рассматривается одноканальная система обслуживания с г (г~1) приоритетными классами требований.
Длительности обслуживания — независимые в совокупности и не зависящие от входящего потока случайные величины, стохастически эквивалентные для Бго приоритетного класса сл. в. Вь р;(э) =Ме — 'и*', В;(1) =Р(В~<1). Входящий поток требований — рекуррентный, определяемый плотностью распределения интервалов между поступлениями требований вида и Я с,.а;ехр( — а;1), 1) О, а (1) = О, 1<0, и где а;эьа; при(ф)', с;)О, Яс;=1.
с'=1 Поступившее требование направляется в 1-й приоритетный класс с вероятностью р; (р = (рь ..., р„) ) независимо от остальных требований. Рекуррентный входящий поток, задаваемый плотностью распределения (1), эквивалентен следующему: интервалы времени между поступлениями требований независимы в совокупности и показательно распределены со случай- 179 ным параметром а, принимающим значения а«с вероятностямц' рь «= 1, д«, причем значение а определяется непосредственно перед началом отсчета времени до следующего поступления и не меняется между двумя поступлениями.
Событие ()(!) =!) будет означать, что в момент времени ! а=ар Сделаем некоторые замечания о характере дисциплины вы-, бора требований из очереди на обслуживание. Мы будем пред-' полагать, что эта дисциплина не допускает прерывания обслуо!«, живания. Многие результаты будут справедливы для всего,; класса систем без прерывания обслуживания. Наиболее де-о тально будет изучена система с конкретной дисциплиной без:", прерывания — дисциплиной относительного приоритета. Ней ограничивая общности (при исследовании систем с относитель-„"« ным приоритетом), будем предполагать, что приоритетные клиссы перенумерованы таким образом, что классу с меньши номером соответствует более высокий приоритет.
Предполагаем, что в начальный момент времени 1=0 сис тема свободна от требований. 2« Основные обозначения. Для характеристик длительност обслуживания требования будут использоваться следующи обозначения: В«(!) — функция распределения, Ь«(!) — плот ность распределения, р«! — !-й момент, р««=М(В«1з, и р«(з) —. преобразование Лапласа — Стилтьеса, р«(з) =Ме — 'в,, длитель, ности обслуживания требования «-го приоритетного класса.. « Введем следующие случайные процессы н величины, которые«« будут основными объектами исследования: (- (!) = (И (!), "., (-.
(!) ), Е«(!) — число требований «что класса в системе в момент (, «! П(п') — длительность периода занятости, начавшегося сцоо случайного числа требований по, т. е. случайного интервал~ времени, начинающегося с обслуживания одного из и' требова ний и кончающегося в момент первого освобождения системно «р(г) =Мг" . Пусть, далее, «(!) — номер приоритетного класса, требова ние которого обслуживается в момент времени (, и г(1) — вр мя, прошедшее с начала обслуживания этого требования до моо мента ! (если в момент ! система свободна, полагаем ((!) нй г(() равными нулю).
Кроме того, введем следующие обозначения: Р(п, !) =Р(Е(!) =п), Ро(!) =Р(0, !), р(г, з) = (де — ««Мгь«««Ш, о ро (з) = р (О, з), т!; (х) = Ь«(х) (! — В, (х) ) Рп (и, х, !) = — Р(!. (!) = п, ! (!) = ), «'(!) = «', г(!) ( х), дк 180 р„(г, х, з) = — е-о!М[г"<!>у(у(у) = у, о(у) = !', г(у) < х)[йу, д Г дх о Ро! (У) = Р (1 (У) = О, у (У) = у), ро! (.) = 5 ° Ро! (У) йУ, о р„(г, О, з) =рп(г,'+О, з), П„(по, у)йу=Р(П(по) ен(у, у+йу), у(у) =у!у(О) =т), пу,(по з) = ) е — и Пу,(по У) йУ о н ! ри =(~~!'са,— !) ~ р р„.
3. Предварительные результаты. Ниже будут введены и изучены функции уо!(г) и уо!*(з), 1=1, У!У, через которые выражаются основные характеристики рассматриваемой системы обслуживания. Функции уо!(г), ..., ухи(г) определяются следующим образом. Рассмотрим уравнение (относительно уо) и и П (р + а!) = А (г) ~ су'а; П (р + а!), о=! у=! аллу где функции А(г) удовлетворяет следующим условиям: А(г) аналитична в области ~г!~ <1 и непрерывна при (г,( <1„1'=1, г, А (1) =1, (А(г) ) <1, (г!) <1, 1=1, и (3) Так кауо (2) 181 н н П(у!+ а) — А(г)) с;а; П(р+ а) !=! у=! !оку является по у! многочленом степени у!у, то указанное уравнение имеет У!У решений для любого г. Обозначим их уо!(г), ..., 1хн(г).
Кроме того, А(г) непрерывна при )г;) <1, 1=1, г, поэтому можно считать функции уо!(г) непрерывными в той же области. Л е м м а 1. Функции 1о!(г), у=1, !т', обладают следующими свойствами: а) одна и только одна из функций р;(г) обращается в нуль в точке г=1; б) для любой функции А(г), удовлетворяющей условиям 13), и для любых гь таких, что ) г,) <1, 1= 1, т, Ке(р!(г)) <О, у=1, У!У; в) функции р!(г) и р;(г) при !~) могут совпадать лишь на конечном числе множеств вида А(х) =с. Д о к а з а т ел ь с т в о. Докажем сначала свойство а) .
Уравнение (2) при г=1 преобразуется к виду р[рн — ! 1 ~ а(„н-гц ~ а.а.рн — з+ !=! !<а<и<% + ~,' ац... а,~ч ! — Я с;а; [рн — '+ Я АР-з+ !<!,<„,«и !<и /=1 Фф/ + ~ а!,а!,р"-4+ ... + Я ац... а!, г1[ = О. !<!,<!ь<у !<!~< "<!и — 2<в «,+Ь !,чь!' !!!Фь !=!, л — ! Отсюда получаем, что решениями уравнения (2) при х=1 являются 1!=0 и решения уравнения и ри-! ~- ~; а!рн-'+ ... + '~' ац. он != — ! !<ц«...!н !<н ~ сга. [)ьн — ! + ~~~ црн — 3 ц- ...
+ + Я а!,...а!„~] = О. !<ц«...!Ф вЂ” 2<У !!!Ф!', !=!!. и — 2 Однако последнее уравнение число нуль своим корнем не имеет. Итак, утверждение а) леммы доказано. Вместо б) докажем несколько более общее утверждение, а именно; докажем, что б) выполняется без требования А(1) =1 и при единственном ограничении на си Я, с, = 1. Восполь! зуемся методом математической индукции.
При У=1 уравнение (2) имеет вид р+а!=А(х)а! и его решение р(х)= — а!(1 — А(г)) имеет неположительную действительную часть при (г;(<:1, 1=1, г, в силу того что а!>О и (А(х) (<1 для указанных г. Предположим, что утверждение выполняется при !!!=й — 1, т. е. для любых а!, ...,аь !, а!>О, й=1, Ф вЂ” 1, и сь ...,сд !, ь — ! Я с! = 1, для любой функции А(г), удовлетворяющей усло! 182 вию (А(г) ~~1 при !х,! (1, 1=1, г, и для любых гь !г!~~1, действительные части решения уравнения » — 1 » — 1 П ()о + а!) = А'(х)') с(а! П ()о + а!) о=! !=! оФ! неположительны. Докажем это утверждение для оо'=а.
Будем доказывать методом от противного. Предположим, что существуют ао, ..., а»; а!)О, о=1, Й, сь ...,с», ~." с! =1, функция А(х) и точка хо, о=! такие, что существует решение а(хо) уравнения П ()о + а!) = А (ао) ~ с)а! П ()о + а!), о=! о=! ооо! Отсюда » ! » †! П (р (г ) + а!) = А (ао) Я с(а! П ()о (хо) + а,) + о-! )=! ' ооо! » — ! + "'"' ' П(р(*)+ ) й(*о) + а» или )А (яо) ((о(оо) + а») (! — с») Х )! (ео) + ໠— А (оо) с»а» П (р(.)+ а!)— Х, "-.„ Отсюда вытекает, что )о(хо) а(Д ()о(хо) + а).
! оо! является решением уравнения » 1 (х,)) с;а; П()»+а!), о=! ооо! П ()о + ао) = А о=! где с! = с;(1 — сД имеющее положительную, действительную часть. Так как » Я со=1, то по крайней мере одно из чисел со, о=1, й, полоо=! жительно. Предположим для определенности, что с»)0, Имеем » 1» П ()о (го) + а!) = А (го) ()» (го) + а») Я с;а; П (р (го) + а!). о=! (=1 оФ! А(х) = ! (~)+ «( «) А (г). )< (гю) + л« вЂ” А (М) с«е« Заметим, что если Ке()«(г«)))0, то (А(х) ) <1 при (г<( <1, 1= =1, г. Отсюда в силу предположения индукции должно быть йе(р(х«)) (О. Противоречие. Утверждение б) доказано.
Докажем теперь свойство в). Заметим, что если х, и ха таковы, что А(х,)~А(х«), то )<<(г<)чь<«<(г,) для любых 1 и 1. Пусть рл(г«) =(«<(х,) =)<(г«) при !Ф!' в некоторой точке хм Тогда, во первых, )«<(г) =)«<(х) для всех х, таких, что А(х) = =А(г«), и, во-вторых, («(г«) является решением уравнения 1~' П (р + а!) — А (х,) ~ ' с; а; ~ П ()«+ а<) = О. <=« Ф! <=< <<«! <э«! чм< Следовательно, )<(г«) одновременно удовлетворяет двум соотношениям и и П (р(г,) + а!) = А (г,) Я с;а< П ()<(х ) + а;), <=< <=« ««! П(р(х,) + а!) =А(х,) ~' с)а; Я П ()«(г,) + а,.).