1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 53
Текст из файла (страница 53)
5. ПРИМЕНЕНИЕ БОЛЕЕ ОБЩНХ 3(ЕТОДОВ 2. Построение моментов обновления. В системах обслу)кивания, где происходит периодическая очистка системы, моменты очистки, т. е. освобон(дения системы от требованпй, характеризуются тем, что для дальнейшего течения процесса несущественна вся предыстории — нужно лишь знать моменты поступления требований в будущем и длительности их обслуживания. Такии образом, если эти величины независимы от предыстории, то следующпй за моментом очистки момент поступления требований будет моментом обновления.
Следовательно, моментами обновления обладают все системы с простейшим входящим потоком. Система СУ)6)т при т~ 2 также обладает моментами очистки при достаточно малом р, но, скажем, при детерминированном потоке с интервалом Л между требованиями и длительностями обслуживания, равномер)ю распределенными в интервале ((т — ()Л, тЛ), в системе постоянно присутствуют требования. Тем не менее при р(т удается построить моменты обновления: если длительности интервалов между требованиями больше, а длительности обслуживания меньше определенных чисел, то через конечное число шагов очередь исчезнет, и тогда все последующее течение процесса не зависит от предыдущего. Этот прием использован нами в доказательстве теоремы Пифера — Вольфовица для системы 61)6)т (э 5.2).
Пусть вообще имеется система обслуживания с несколькими типами требования и операций обслуживания. Функционирование системы определяется последовательностью )з«, «)ь" ), где з»Ю— интервалы между поступлением требований, «(Г» — длительности обслуживания, 1« — номер, г — тип требования (обслуживания). Допустим, что существует «номинальный» режим функционирования системы, характеризующийся «допусками» тй) „) О) (г) » (а(", ц» ~ ~Ь, нарушение же этих неравенств рассматривается как его воамущение. Любая разумно построенная система способна «отрабатывать» воамущения: если, начиная с некоторого момента времени элементы «управляющей» последовательности ) зз, Ч, ) находятся в пределах допусков, то через ко- О) (г) нечное число шагов процесс выйдет на номинальный режим. Коли последний характеризуется стационарностью распределения основного марковского процесса, то момент вь(хода на этот режим и будет моментом обновления.
Важно лишь удостовериться в том, что веронтность выполнения «допусковых» неравенств положительна. В качестве примера рассмотрим многофазовую систему обслуживания с бяокировкой 61)6)т,)г, — )С)т,)г, )... — )6)т,)г„ состонщую из многолинейных подсистем с ограниченным числом мест для ожидания. Требования, образующие поток восстанов- $5,5.
эРГОдические теОРемы 281 лепин, образуют очередь перед первой подсистемой, если в ней уже наводится т, + г, требований. Если в Е11 подсистеме (2-=1(5 а) находится т1+г1 требований, то при окончании обеду;кпзаш1я требования в (( — 1)-й подсистеме зто требование продолжает занимать прибор (вблокирует» его), пока закрыт доступ в 1-ю подсистему. Обозначим через з, интервалы между поступлением требовании, ц»О — длетельности обслуживания требований в 1-й подсистеме. Пусть также ((1) — суммарная работа, которую нужно зь1полннть после момента 1 для завершения обслуживания требований, имеющиеся в системе в момент й До тех пор, пока системе присутствует хотя бы одно требование, ('(1) ( — 1; и) значит, еслп достаточно большое число раз подряд Рм + ...
+ + 1~»о(А»+1 — е, е >О, то наступит момент очистки системы (прп любом заданном текущем значении ((1)). Рассмотрим прием, предложенный И. Н. Коваленко и Н. 10, Кузнецовым )1) и использующий существование абсолютно непрерывной компоненты распределений случайных величин, определяющих процесс обслуживания. Ограничимся лишь той обп1ностью изложения, которая достаточна для понимания основной идеи. Пусть поведение системы описывается однородным марковским процессом ь(1) =(ь1(1), ..., ь„(1) ), где ь1(1) — числовые О 1 О »1 переменные, причем для некоторой точки х' = (х„..., х 1 с вероятностью 1 процесс бесконечно много раз возвра1цается в любую окрестность этой точки У,(х ) = ((х„..., х„): ~х1— — т,'; ~(е, 1(1(и).
Предполагается, что до момента скачка процесс следует детерминированной траектореп, причем расстояппе между возможными траекториями не увеличивается: если ~(5) и ь'(1) — траектории процесса, соответствующие начальным состояниям х и х' в момент 1„то ез х ж У,(х') следует ~(1) П К'(г)). г>1' Момент скачка для первой траектории т, для второй т', где ~т — т'! ~ с,е. (Если в интервалах между скачками процесс следу1т дифференциальному уравнению Ь'(1)+ а(Ь(1) ) = О, и(х) = =(55 (х),, а (х)), а1(х)>а > О, а скачки происходят в момопт достижения какой-либо компонентой процесса фиксированного уровня, то, как легко видеть, с~ 1/а'.) Обозначим Н(х)у) распределение Ь (1+ О), где 1 — момент скачка, при условии (1 — 0)=у.
Пусть для некоторого и»-мерного множества У(у») положительной меры !У( ОИ(х)у)> р5(х1... 5(х, ~) >О, при любыл у ~ п,(у') и х 1и»'. тогда после каждого попадания ь(1) У.(х') с вероятностью р(Р( наступает момент обновления, в который значение Ь(1) равномерно распределено в множестве Р(р'). (Заметим, что моменты обновления, соответствующие 282 Гл, 5, пРименение Более ОБщих методов различным траекториям, сдвинуты по времени один относитель- но другого.) Часто встречается ситуация, когда при скачке «обновляется» лишь одна компонента ь(1), получающая при этом скачке не- нулевое приращение.
В таком случае нуя«но ожидать момента, когда «обновятся» все компоненты. Пример; Пусть имеется в» независимых процессов восста- новления с распределением В(х) времени между восстановле- ниями и ~~(1) — время до очередного восстановления 1-го из этих процессов.
Предположим, что иВ(1)~ риг в интервале (а, а+ А), где а>0, Л)0. Фиксируем е, 0<э<А, е<а, и пусть такой момент, что некоторое ~~(г — 0) = О и все остальные ~,(~ — 0)< е. Тогда аа время е произойдет восстановление всех процессов. Если ь(~ — 0)=у, дра(к[у) = йР(5(Г+ Л) <х[~(1 — О) = у), то йг «(х [у) э рйх,... Ых, а < х1 <а + Л вЂ” е, 1 < 1 < и. Следовательпо, обновление наступит в момент ~+А с вероятнестью 3(Л вЂ” е)"; в этот момент распределение состояния процесса равномерно в гиперкубе а < х, < а + Ь вЂ” е, 1 -= 1 < т.
3. Устойчивость систем массового обслуживания. Пусть функционирование системы определяется рекуррентным соотношением з(и+1)=1(з(п), $(п)), н~О, (13) где и = (з (0), $ (О), $ (1), ...) — так называемая управляющая последовательность, з(н) — состояние системы на н-м шаге. Наряду с (13) рассмотрим последовательность (з*(н)), определяемую тем же соотношением, но с управляющей последовательностью я*=(з*(О), Ээ(0), $«(1), ...).
Теоремы устойчивости (непрерывности) устанавливают близость последовательностей (з(л) ), (зе(н)) при достаточно малых отклонениях ае от а. Понятие близости последовательностей задается той или иной метрикой, например, расстоянием р (а, а*) = шах([з (О) — з*(О) [[, эпр [[э (и) — Яе (н) [ф, ело где 1х1 — норма элемента х (длина вектора, если з(н), 5(л)— векторы евклидова пространства).
Можно рассиатривать аналог (14) при замене «..Л на М~[...[[", г>1. Теория устойчивости систем, описываемых уравнением (13) при независимых одинаково распределенных 3(н), развита В. В. Калашниковьгм [1), разработавшим метод пробных функций, который обобщает прямой метод А. М. Ляпунова.
Цепь Маркова (з(н), п>О) со значениями из метрического пространства Я называется устойчивой е среднем по времени, г 5.5. системы с БОльшОЙ злггузкоп 283 если для любого е ) 0 найдется постоянная 6 ) 0 такая, что при Мр,(г(0),ге(0))<6, МргД(п),гч(п))<6, л~)О, где р„рл — расстояние в соответствующих пространствах, выполняется неравенство л — 1 — „ХР(р*( (п), *(я))ЭБ)< . л=-о (15) Пусть.
И, — расстояние между распределениями г(0), г*(0), 55,— расстояние между распределениями $(1) и $*(1), я((), ~в)— расстояние Леви — Прохорова между распределениями в Е, т. е. минимальное значение е) О, для которого прп любом измеримом ВсЕ Д(В) < л,*(В,)+ е, ()*(В) < ~(В)+ е, АИ'(х) = М (Иг (г(1)) ( х(0) = г), (16) где Иг(х) — неотрицательная функция, Прн некоторых условиях на АИг(х) прп соответствующей функции И~(х) цепь Маркова (г(и)) устойчива в среднем по времени. Важнейшее из зткх условий — неравенство АИ'(х)< — в <0 прн р(г, гв)) 6.
й 5.6. Системы с большой загрузкой 1. Предельная теорема для распределения времени ожидания в системе 61(6(1. Нам понадобится некоторая общая предельная теорема теории вероятностей; ее доказал А. Я. Хинчин (5) в связи с исследованием второй проблемы диффузии. Пусть имеется последовательность случайных величин г„г„ го ..., г„, ..., образующая цепь Маркова с распределением вероятностей перехода за один шаг г" (ха р) = Р(гв< р~гч г = х) где В.
— е-окрестность В. Предполагается, что при любых допустимых распределениях г(О), $(0) существует предельное распределениее ч (В) случайной величины г (и) (и — ) . Цепь Маркова (г(п)) слабо устойчива в пределе, если л(9, 9")< е при 55, < 6(е), р, <6(е). Как доказал В. В. Калашников, из (15) следует слабая устойчивость (г (и)) по времени. Для установления устойчивости В. В. Калашников рассматривает последовательность х(п)=(г(п), г~(и)) и ее производящий оператор 284 гл, к пгнмкнкник волне ОБщих методов и некоторым начальным состоянием з„а ~в, ~ Ь.
Пусть, далее, имеются два барьера на уровнях а и Ь. Спрашивается: чему равна вероятность Р(х) того, что при ус- ловии з, =х иэ этих барьеров первым будет достигнут верхний (х = Ь)? Теорема. Пусть Р(х, у) зависит от некоторого параметра е, причем при е — О имеют место предельные соотношения (усло- вие Линдеберга) М (г„— з„, [ зь т = х) = еа (х) + о (е), М ((з„— з„,)' [ з„, = х) = ер (х)+ о (е), (1) М ((з„ вЂ” з„ ,)' [Е (з„ вЂ” з„ , — т) + Е (т — з„ + з„ ,)[[ з„ = х) = о (е) [1, х)О, при любом т) О, где Е(х) = ~ а(х) и р(х) — непре- [О, х<О, рывные функции, причем о(е) равномерно по х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
