1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987).djvu), страница 13

$ 1.6. Общие принципы построения марковских моделей систем 1. Однородный марковский процесс. Пусть Х вЂ” конечное или счетное множество, З(е) — однородный марковский процесс с множеством состояний Х и инфинитезимальной матрицей Л= е),о1, элементы которой определяются соотношениями Р ($ (е + Л) — У 1 $ (г) = 1) = Учу Л + о (Л), (1) Р($(1+ Л) =1) $(Т) = 1) 1 — )1Л+ о(Л) = 1+ уиЛ+ о(Л), (2) д,= — Ли= ХЛН. (5) уж~ Велнчина у ее при у' тое называется интенсивностью перехода из состояния 1 в состояние у, величина ).е — интенсивностью выхода ИЗ состояния 1.

Как правило, в реальных случаях можно постулировать свойство регулярности марковского процесса: с вероятностью 1 траектория процесса $(г) — ступенчатая функция с конечным числом скачков в любом конечном интервале и для всех г одновременно $(1) совпадает с $(1 — О) или $(1+0), т.

е. пределом слева или справа. чаще всего при этом можно задать процесс $(г) так, чтобы почти все его траектории были, например, непрерывны справа, т. е. $(е) = $(1+ О). Пусть з(е) — регулярный непрерывный справа марковский процесс с характеристиками (1) — (3). Определим ((1) как число скачков процесса в интервале (О, 1) и обозначим 1() (~(),(()) Тогда, очевидно, р,(1) = Р(З(г) у) Х р( ~(1) ее=с где ,1 1(г) Р(с(е) у, ~(1) гп), Процесс ь(1) никогда не возвращается в исходное состояние и в этом подобен процессу чистого размножения. о"равнения для его переходных вероятностей имеют внд рекуррентных формул —,', р1ее(г) + Х,р1РО(1) =,')'„Х„р',1-П(1), т-=1, (5) 1Ф3 + р(ю(г) + л;р~ю (1) = О (6) з в.

в В. Гоезенио, И. Н, Коееаеоно 66 Гл. !. 3АдАчи твовии мАссОВОГО Овслуживания и удовлетворяют начальным условиям р!! '(О) = О, во~~1, р,о!(О) = р!(О)=Р(~(О) =)). Уравнения (5) и (6) легко решаются: с р!~~ (!) ~~.", ЛН~ р! '~ (à — х) е ~го!)х, т)~(, (7) о (о]( ) (О) -А! (8) Пусть ! — Момент т-го скачка процесса при ! ) О, $ $(! + О), т. е. $ — состояние процесса непосредственно после ло-го скачка. Уравнения (7), (8) выражают собой следующие важные свойства: !. При известном состоянии ! = З(О) величина !о разная времени пребывания процесса в состоянии о, распределена по показательному закону с параметром ) .

2. Если известны значения $ 6 ! = г, то ! +, = г+ 7, где 7 — независимая от поведения процесса до момента Г„показательная случайная величина с параметром ) б $ +, независимо от аначениЯ 7 Равно 7' с веРоЯтностью А!!/) о! т'= !. 2. Характеристики функционалов. При использовании марковских моделей систем обслуживания интересуются как характеристиками мгновенных значений процесса Рб(!)=О=рз(!). Р($(!) А)= Х р!(!) з-А МИ (!)) - Х 1 (И р! Я. так и характеристиками функционалов траектории. Приведем наиболее употребительные из них.

Пусть т!(Т) — время пребывания процесса в состоянии ! в течение интервала (О, Т). Тогда Мт;(Т) = ) р!(!) о)г, о Пусть имеется поток Пуассона с параметром А, причем появле нне события в интервале (3, !+ Л) не зависит от з(г), хотя после этого события состояние $(!) Может измениться. ОбозначиМ Ц(Т) число событий потока, аастазших процесс 3(г) в состоянии ). Тогда МЛ~з(Т)=7.) р,(г)аг. (9) о Действительно, !Уг(Т) = Ыг (Т) + )(!; (Т), где )о!.

(Т) — чио" ло событий потока в интервале (О, Т), для которых в любом з ео, пРинципы постРОения мАРкОВских мОделей бт интервале ((й — 1)Л, еЛ), где Л = Туп, до момента события потока скачков процесса не было; Ир,(Т) = Лс; (Т) — Мс„(Т). Имеем в-ьь Р,. ((й — 1) Л) (1 — е ьа) ( = М Р;. (йЛ) — Л';. ((й — 1) Л)) ~ р, ((й — 1) Л) ),Л. (1О) Просуммировав по й, легко получим, что т Нш МХ„; (г) = Х) р, (г) с)г.

(11) п о Нзяв п = 2', найдем, что Л;„(Т) 1 О с вероятностью 1; посколь- 'Ф ку же Мдс; (Т)~АТ, то из этого следует, что МЛ;„(Т)-» О. Этим формула (9) обоснована полностью. Следствие. Среднее число потерянных в интервале (О, Т) требований в системе с сп приборами и г местами для ожидания равно т ,~ р.+,(») Й. о Если рос+»(») -~ Р,»+„то среднее этой величины по ннтервас лу (О, Т) стремится к «с +„при Т вЂ”; зто оправдывает отождествление данной величины с вероятностью потери требования в установившемся режиме. Пусть, наконец, с«сс(Т, Л) — число интервалов пребывания процесса в состоянии ~', включающихся в интервал (О, Т), по длительности ббльших Л.

Тогда т-А МЛс (Т, Л) = в ~с~ ~)«сс ~ р«(с) дс. (12) о 3. Общая схема построения марковской модели системы обслуживания. 1. Выбор фавовово пространства Х. Это пространство выбирается с тем условием, чтобы по значению» «и Х можно было определить, какие операции производятся в данном состоянии. Обозначим через ~с~ («ранг» с) общее число операций в состокиии 1 и назовем их Ос„..., Оее. НаРЯдУ с Реальными опеРациями в зто число включаются фиктивные — ожидание того или иного события, Так, можно считать, что событие простейшего потока появляется в момент окончания «операции» ожидания этого обытия; длительность такой операции распределена по показательному закону.

Н Определение параметров операции Обозначим через д с парамегР вьшолнениЯ опеРации Осг Таким обРазом, если в момент г состояние системы равно с, то за время Л может закончиться !'-я операция с вероятностью 1«ссЛ + о(Л). е» 68 ГЛ. 1. ЗАДАЧИ ТЕОРИИ Ь1АССОВОГО ОБСЛУЖИВАНИЯ 111. Определение возможных переходов при окончании операции. Обозначим через р)А вероятность того, что при окончании ()) операции Оц система переходит в состояние й. (Если переходыдетерминированы, то р!май=11 рп, О при йФвч, где и — то состо- 0) О) яние, в которое процесс переходит при окончании операции Оо.) Марковская модель поведения системы построена.

Именно, определен однородный марковский процесс с множеством состоянии Х и интенсивностями перехода н! ~а = Д )Ао'Р)ОА. 118) Разумеется, модель будет адекватной лишь в том случае, когда вероятность окончания любой операции за время Л не зависит от поведения системы до момента й Все рассмотренные выше примеры 'систем укладываются в описанную схему. В следующих двух параграфах будут рассмотрены системы с ограничениями, служащие примерами систем с простейшим потоком и показательным законом обслуживания, в которых тем не менее нельзя обойтись дискретной марковской модолью: требуется рассмотрение марковского процесса с континуальным множеством состояний.

4, Гиперэрланговская аппроксимация. Построение марковской модели можно применять и в том случае, если определяющие случайные величины распределены не по показательному, а по эрланговскому закону с плотностью !)л)' ' рг!х;)) =) — )е-ь*, х О, для г=1, 2...„) О. (г — )! Пусть, например, такому закону следует деятельность обслуживания )).

Воспользуемся методом фиктивных фаз, восходящим к Эрлангу: представим г) в виде суммы г) =))~+...+ ))„где т);— независимые случайные величины, имеющие показательное распределение с параметром ). Тагшм образом, т) разбивается на г фаз обслуживания. Обозначив через 1(!) число фаз, которые должны осуществиться для окончания обслуживания, начиная с момента 1, найдем, что 1(!) — марковский процесс с состояниями О, '1, ..., г, начинающийся с состояния г и последовательно переходящий в состояния г — 1, ..., 1, О: последнее означает окопчанйе обслуживания данного требования.

Интенсивность перехода из й в й — 1 равна )1. Если распределение — гиперэрланговское, т. е.имеет плотность вида в в=1 то можно применить тот же прием, выбирая г случайным обра- з ьх системА с ОТРАниченным ВРеменем Ожидхния бп зом в соответствии с вероятностями р,. Если реальные распределения отличны от гипзрэрланговских, то их можно аппроксимировать последними. Различные аспекты гиперэрланговской аппроксимации см. Маршалл, Харрис Щ Н. П. Бусленко, В.

В. Калашников и И. Н. Коваленко Щ Ньютс $2$ З Б7. Система с ограниченным временем ожидания Б Постановка задачи. Предположим, что в системе обслуживания имеются т приборов, эквивалентных между собой. На эти приборы поступает простейший поток требований, параметр которого равен 7.

Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей П(х)=1 — е '". Каждое требование, поступившее в систему обслуживания, остается в ней и либо начинает обслуживаться сразу, если имеется хотя бы один свободный от обслуживания прибор, либо остается ожидать своей очереди на обслуживание. Но при этом ожидание ограничено определенным временем т. Если требование за время т со времени его поступления не начало обслуживаться, то оно теряется.

С постановкой задачи в таком плане приходится иметь дело достаточно часто. Например, лица, пришедшие на телефонную станцию, имеют лишь ограниченное время для ожидания соединения с интересующим их абонентом. Еще пример: скоропортящиеся продукты, поступившие в магазин, пригодны для продажи лишь определенный срок т. Если за зто время они не проданы, то становятся непригодными к употреблению.