1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 35
Текст из файла (страница 35)
До момента г„включительно из системы вышло и требований, а поступило и+ т„. В то же время в любом интервале число переходов й— й+ 1 может отличаться от числа обратных переходов не более чем на единицу. Отсюда ! №~ъ„(й й+ 1) — №(й+ 1 й)! <1. Однако ! №+,„(й -~ й + 1) — № (й -+- й + 1) ~ ( т„. Следовательно, ! № (й - й + 1) — № (й + 1 — й)! ~ т„+ 1. 1 Так как — Х (й+1-~й) — ~-лы а т„!и — 0 по вероятности, то 1 — „Х (й-~й+1)-~ла по вероятности.
Последнее означает, что (10) 1пп Р (т„= й) = лд. и 3. Формула Поллачека — Хинчина. Введем случайный процесс т*(г), равный т„, где и — число требований, обслужеииых до момента 1; ч" (~)=О при и=О. Этот процесс — полумарковский; (ч ) — его вложенная цепь Маркова. На основании теере- 134 гл. 4. полумАРковские мОдели систем ОвслуживАния мы 3 з 3.1 заключаем, что ло = ПщР (У (1) = 1с) = с ~~~~я с) Р (1) 1сч (С) с(о, (11) с о откуда Подобпым же образом Ро(1) 1оо(1) =е " с Р (Г)1оо(1) = Й~е В(с— о -Мс- >1.о '(с — о1" ' 1о о откуда ~'Р,(Г))„(1)аг = 11Х, о 1о-с р Ро(1)1оо(с)с)с = ') и'-'е '"В(и) сйс, 1с)~1. Введем производящую функцию а (з) = „~', зо†" ().1)ее 'В (8) с(г = и с,с о=о о = ~Е ЫСТ ОВ(с) С(Х = (1 — Су(Х(1 — З))).
о Из (11) и последующих выражений для интегралов, входящих где с — постоянная, Р(Г)У (Г) Р((1 +1) й, - ! 1) Обозначив через ст (с) пуассоновскую случайную величину с параметром )1, найдем Рз Я 6, (1) = Р (б )1, й (с) = й — 1) = = е-» (),с)" сВ (с)с(й — 1)с, 1'~ ~1, 5 кг. системА м)о(г в правую часть этого равенства, находим, что производящая функция последовательности (пй(с) имеет внд (л(г) — по) а(г) + ло(1!) + га(г)) = = по() + (л(г) — л,(1 — г)) а(г) = (1 — р)() + + (л (г) — (1 — р) (1 — г)) а (г) Данное выражение отличается лишь постоянным множителем от п(г). Использовав условие нормировки, находим Х = =, . * о ь (г — р) (г — г) гт()г() — г)) лог = л(г) = (12) о=о М1Я(г„— О)) — ~ а„ (1З) то — ~ М/ ($ (1)) й -о а.
Т т о (14) Доказательство. Легко видеть, что достаточно рассмотреть случай ). = 1. Положии и = (Т)' и рассмотрим выражение го г„ 6„= М ~ ~($ (г)) г(г = ~~ М ) (($ (г)) с(г, о ь=г ь-г где обозначено г, = О. Так как гг — гг г распределено по показа- Формула (12) называется формулой Поллачека — Хинчина. 4.
Математический закон стационарной очереди. Только что был установлен замечательный факт: в стационарном режиме системы распределение процесса т(г) в произвольный момент времени совпадает с распределением в момент поступления требования. Этот факт А. Я. Хннчин назвал математическим законом стационарной очереди. Позднее выяснилось, что такое совпадение имеет место для весьма широкого класса систем с простейшим входящим потоком.
Отсылая читателя, интересующегося современным состоянием вопроса, к книгам Франкена, Кбнига, Арндт и Шмидта (11 и В. М. Шуренкова Щ, приведем теорему в виде, легко интерпретируемом в различных приложениях. Теорема. Пусть поведение системы массового обслуживания описывается случайным процессом $(г), ) — ограниченн я функция, входящий поток — простейший с параметром ), момент поступления и-го требования.
Предполож м, что Ц((), г ( г) не зависит от моментов поступления требований при г ) г. Тогда, если 166 Гл. 4. полузтьгковские модели систем Овслуживлния тельному аакону с параметром 1, то 1о СО и М ~ ~($(1)) оЫ = М ~ е "Ых ~~Д(г~ 1+ 1)) И1= 'О-1 о о Ф ОО М ) 1 Д (го 1 + 1)) г(г ') е ийх = М ~ е 1 М~ ($ (1» 1 + о)) 1(1. Однако М/(ь(оо — 0))=М((ь(Г„1+(Го — Гд 1) — 0))=М ( е ЧД(гь-1+ Г)) йо о что совпадает с предыдущим выражением. Итак, Ьи — — Х М/Д(го — О)) иа, и- оо. 1=1 (15) В то же время 'и ь„= М ) 1($ (г)) (г + М ') 1 (5 (г)) а, откуда ! т ܄— И ( ! 51 ~ О) О ~ (7 И ~ И вЂ” О ~, о (16) где ~ = зпр)~(х) (. Имеем оценлу М(8„— г((т — и+ М(г„— и((1+ о(г„) =1+ ~~ (о — среднеквадратическое отклонение).
Требуемое утверждение следует из атой оценки в сочетании с (15) и (16). 5. Виртуальное время ожидания. Обозначим через "((Г) случайный процесс, равный в каждый момент 1 промежутку времени, которое должно протечь от момента г до полного освобождения прибора от обслуживания требований, поступивших в систему до момента й Если в момент 1 прибор свободен, то ((1)= О. Обозначим через Гь Гь 1„... моменты прибытия требований потока (г, ( 1, (...). тогда для 1„< 1 < 1„+, процесс ((1) определяется посредством равенств О, если у(4)($ — 1„, "1(г) = у(г„) — (г — г„), ес. у (ги)= г — го.
з аз, спсткмА и! о В 187 Для г = г„ имеет место равенство 7(г„ + О)= 7(ㄠ— О) + т|„, где ,1„ обозначает длительность обслуживания требования, поступившего в момент г„. Общий вид процесса 7(~) изображен на рис. 4, Процесс скачком изменяет свою величину номенты прибытия требований У остается неизменным до прибы тпя очередного требования, когда он достиг нулевого значения,убывает с единичной скоростью в тех отрезках, где он положителен.
Процесс 7(С) в сделанных нами предположениях оказывается марковским. Действительно, сколько требований поступит от мо- д мента 1 до момента г + з, не за- Рвс. 4 висит от того, как иного требоваппй поступило до момента г. Значение 7(~ + з) определяется, во-первых, величиной 7(~), во-вторых, числом требований, которые поступили в промежуток (г, Г + з), и, в-третьих, длительностью обслуживании згих вновь поступивших требований. Все трп величины не изменяются оттого, что станут известными значения 7(т) в моменты т, предшествующие й Для полной определенности процесса положим, что 7(О)= 0; это условие можно трактовать как соглашение о начале процесса обслуживания в момент 1 = О. Процесс 7(1) введен Такачем Щ и называется виртуальным (аозможнььн) временем ожидания: если в момент С поступит требование, то ему придется ждать начала обслуживания время, равное 7(г).
Отметим одну интересную аналогию, когда то же уравнение служит адекватным описанием совершенно другого физического процесса. В водохранилище в моменты 1о Сь ..., С„, ... поступают порции воды объема т)о пм ..., и, '. соответственно (~„ — зто моменты открытия шлюза). Сток воды равномерный; в едвниду вРемени вытекает единичный объем воды. Тогда 7(~) будет равно объему воды в водохранилище в момент г. 6. Предельное распределение времени ожидания.
Обозначим через ю„время ожидания и-го требования. Будем считать, что Р ( 1. По формуле полной вероятности Р (ю„)х) = и = У, Р(т,'. = О) Р(т,+, О, ..., т„)0, ю„)х(ч; = 0). (17) 1=1 Так как второй сомножятель слагаемого суммы зависит только 188 гл, «, полтмлэковскив модвли снствм овслтживлния (10) от х и и — Й а Р(т' = О) — ь 1 — р, то существует о ъ!О Пгп Р (во(х) = Р(х). а Непосредственно очевидно, что Р(х) — неуоывающая, непрерыв- ная слева функция.
Докажем, что Р( )= 1. Цепь Маркова (та) эргодична; поэтому конечно среднее вре- мя возвращения в состояние О, которое можно представить в виде ~ Р(т;+,)О, ., т;«. ~0). и=» Следовательно, в правой части (17) сумма по 1 от 1 до и — Х при надлежаг»ем фиксированном т«меньше з, сумму же от и — Ф+ 1 до и можно сделать сколь угодно малой за счет вы- бора х. Отсюда 11шР„(х)' 1 — 2с, х)х„т. е. Р( >)=1, что а и требовалось доказать.
На основании теоремы п. 4 заключаем, что т Р (х) = 1пп — ) Р (7 (1) ( х) «(1, (18) о причем предел правой части существует. Положим в (18) х =+О (это законно. поскольку з формуле (17) вместо «~х» можно писать «онА»). Тогда из (18) с учетом то о, ч о Р (а „= О) = Р (т„= О) 1 — р, ~~~у~им и т 1пп Р (7(г) 0) 81 1 р, 1 Г ,„т3 о т.
е. средняя доля времени, для которого 7(г) = О, равна 1 — р— «недогрузке» системы. Обозначим Р (о, х) = Р (у (») (,х). Возьмем два момента времени: 3 и 1+й (Й) 0). Если в интервале (1, 1+ й) требо- вания не поступали, то события (7(1+Й)(х) и (~(1)(х+ Й) эквивалентны. Если поступило одно требование с временем об- служивания «1, то ("1 (»)+ Ч < х) с ("1 (» + й) < х) с (7 (1) +»1 < х+ й), Заметив, что два или более требований могут поступить за время Й лишь с вероятностью о(й), находим (1 — Йй) Р(1, х+ й) + И~ В(х — у) г)Р(1, у) (Р(1-1- й, х)(( о о -~-ь ((1 — Йй) Р(1, + Й) + Йй ~ В(х+ Ь вЂ” у) ЫР(г, у) + о(й). а о 2.2, системА М16~ 1 усредним по г в пределах от О до Т и устремим Т к .
На основании (18) получим (1 — Лй)Г( + й)+ Лй~ В( — у) о1Г(у)о--Г(х)»~ о х+Л ~~ (1 Лй) Г (х + й) + Лй ~ В (х -(- й — у) йГ (у) + о (й), о Отсюда х+Л ЛГ(х+ й) — Л ~ В(х+ й — у) о(Г(у) + о(1) ' о х (Г(х+ й) — Г(х))~(ЛГ(х+ й) — Л ~ В(х — у) ггГ(у). (20) о 11з (20) заключаем, что правостороннее разностное отношение для Г(х) ограничено, а следовательно, Г(х) абсолютно непрерывна при х ) О, Так как интеграл в (20) есть функция распределения, то для почти всех х ) О нижняя оценка при й -о О сходится к верхней. Итак, для почти всех х) О Г' (х) = ЛГ (х) — Л ) В (х — у) ЙГ (у), о или, что то же, Г'(х) = Л) В(х — у)ооГ(у).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
