Idea Transcript
МИНИСТЕРСТВО
ВЫСШЕГО
И
СРЕДНЕГО
СПЕЦИАЛЬНОГО
ОБРАЗОВАНИЯ
СССР
•
МОСКОВСКИй ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ш-IСТИТУТ
НЕФТЕХИМИЧЕСКОй
И
Г АЗОВОИ
ПРОМЫШЛЕННОСТИ им. И. М. ГУБКИНА
Кафедра прикладной математики
Д. ·КЕНИГ,
В.
РЫКОВ,
Д. Ш110ЯН УТВЕРЖДЕНО Советом института
в
качестве
у'lебного
пособия
ТЕОРИЯ
МАССОВОГО
ОБСЛУЖИВАНИЯ
(Основной курс: марковекие модели, методы марковизаuии) Учебное пособие по математике для студентов специальности 0647- прикладноя математика
МОСКВА-1979
©Московский иисти1ут нефтехимической и газовой промышлеиности.
1979 r.
ПРЕДИСЛОВИЕ Предла·гаемое учебное nособие .предназначено для матема тиков-шрик.lадников
и
составлено
по
материалам
основного
курса, читаемого ·студента•м специальности 0647 прик.лад ная математика МИНХиГП им. И. М. Губ~ина и студентам математикам Ф,райбе,р.гской горной академии (ФГА, ГДР). ·Уч.ебtно.с пособие может быть IИопользовано также для студен
тов других специальностей, таких, например, как
0634 -
ав
томатизация производст,венных nроцесоов, 0646 автомати зированные системы УJПравления и др. От ЧJИтателя предnола гается знакомство с курсами теории вероятностей и теории слу чайных процессов в объеме, даваемом студентам вуза с по вышенной математической под;гоwвкой. В пособие rВiключены как 11радrиционные воnросы, так и не КО'ГО,рые специальные (сети СМО), вше,р.вые включенные в учебную литературу, однако представляющие, по нашему убеждению, значительный nрактический интерес. В авязи с этим при подготовке курса и составлении пособия использова ЛИIСЬ ка к книги [1, 2], та·к и менее доступные издания [3] и
Ж:УIРНальные статьи. Ссылки на литературные и.сточники раз делены на основную
и специальную литературу и
приводятся
лишь в ·тех случаях, когда они .могут помочь более глубокому изучению rпредмета.
Пособие написано в соответствии с планом совместных ра бот кафедры прикладной математики МИНХиГП и секции ма rематики ФГ А 1В ра·м·ках договора о ·науqном ссmрудниче.стве МИНХиГП им. Губкина и ФГА; гл. 1, 11 наnи-саны В. В. Ры ковым; гл. 111 Д. Кенигом 'И Д. Штояном. В пособии принята сплошная нуtмерация rпара.графов, каж дый из которых разбит на пункты. Формулы имеют самостоя телыную нумерацию внутри параг,рафа.
Так как в
каждом
пу:нкте соде.ржится в осно!Вном одна теорема, то теоремы
не
нумеруются, а при ссылке указывается пункт, содержащий не
обходимую теорему. Ссылки на формулы внутри параiЛрафа состоят из одной цифры, а из другого-из двух. первая из ко торых указывает номер пара.rрафа.
3
ГЛАВАI
ВВЕДЕНИЕ
§ 1.
ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ
1l.l.
Предмет ТМО. nримеры
Теория массового обслуживаНJИя (ТМО) является .разде лом исс..rtедования операций и изучает функционирование сис тем в условиях массового постушлеНiия 11ребоiваний и наличия
случайных факторо,в. При этом в ТМО из;учаrются явления загруженности
систем,
проя,вляющиеся
в
виде
обра.зования
оче,редей, простоя оборудова1ния, задержек или отказов в об слуЖiИвании и т. п., вне зависимости от конкретного вида тре бований и обслуживающих оредств, а также конкретного содержания
процесса
0
зволяет с единой матема
D
·несколыю 1пр:имеров.
их обслуживания. Это по тической
точки
рассматривать клаrсс ·СИСТе!М.
l~
Рнс.
4
\.
МодеJiь АЗС
Приведем
Пример 1. АЗС. смотрим
Рас
автозаправоч
ную станцию
JD
зрения широкий
(АЗС)
бензоколонками, жащими k типов
·
с
n;
IС'Одер бензи
нов, и оrра·ниченным (rпл-о
щадкой перед
ста1wцией)
Числ'Ом мест т для ожи дания (рис. 1). К. АЗС в случайные моменты ;вре мени 'Подъезжают авmма шины и при нал;ичиИ сво
бодной
бензоколонки
с
нужной маркой бензина
начинают заправляться. В против-
ном случае автомашины становятся в очередь, если есть места,
или покидают АЗС. Так как автомашины разных марок обла дают бензобаками различной емкости и подъезжающие авто машины имеют различный запас бензина, длительность за
правки является,
вообще говоря, случайной величиной.
Не
регулярность поступления автомашин и случайность длитель
ности их обслуЖивания приводит к нерегулярности
рабсты
АЗС: в отдельные периоды времени бензоколонки простаи вают, в другие периоды образуются очереди, вызывающие большие задержки транспортных средств. Возникают задачи изучения и количественной и качественной оценки этих явле ний, а также расчета необходимого количества бензоколонок
и мест прое1ктир01вания АЗС.
Лаоненты J---1
~
-----Рис.
2.
Модель АТС
Пример 2. АТС. Ра•сомотри.м у1прощен,НI}'Ю м01дель аtвтомати ческой телефонной станции (АТС), оодержащей n линий связи (рис. 2). В ·случайные моменты времени ·на АТС посrупают от абонентов вызовы на связь. При наличии свободной ли.нии с помощью нимается
коммутатора
К устанавливается
на случайное время
~
-
связь и линия
за
длительность разговора,
в течение к:от01рого эта линия не может быть nредоеrавле.на другим абонентам. Если в момент поступления вызова все .тш нии окажутся занятыми, абонент получает отказ ('вызов теря
ется). Возникает задача исследования во в,ремени поведения системы, кото,р01е в силу СЛ)'IЧайности моментов постуmл.ения вызовов и длительностен разtГоворов описывается нек'Оwрым
случайным процеосом, расчета ее характеристик, в частности,
вероятности потери .вы.:зо.ва и оцен~и неабrодим·ого по задан наму крит.ерию числа линий, наприме;р такоrо числа линий, чтобы вераятиость потери не превЬl\Шала заданную величину.
Пример 3. ВС. Ра'Ссмотр;и;м 'ВЫЧИIСЛИ'Гельную систе·му (ВС) или отдельную ЭВМ, работающую в режиме автоматизи,ро ванного управл1ения некоторЬIIМ объектом (п·редJПриятием), скаж-ем, в ра1мках .д:.СУ (1рис. 3). Такая СИ'стема сна•бжена КО'М-
5
плексом
программ, соот
ветствующих
задачам,
решаемым АСУ, и на нее в некоторые (среди кото
рых могут быть как строго
регламентированные,
та'к и случайные) моменты времени
JBM
1111111111
просы
на
поступают
решения
личных задач. Работой осей системы управляет
Jaoattu IIC!I
программа-диспетчер,
tt
t
информация
Рис.
за
раз
3.
решения задач, при нали чии
нескольких
запросов
одновременно.
Среди
многочисленных
Модель ВС
ко
торая определяет порядок
организации
проблем
работы ВС
важное значение имеют вопросы оценки качества программы
диспетчера, оценки загруженности различных устройств ВС и задержек в решении тех или иных задач АСУ. Пример 4. Надежность. Пусть некоторое сложное техниче ское устройство, например ЭВМ, подвержено отказам, возни кающим в случайные моменты в'реме1IИ, на выsrвлениrе и уе11ра-
ремонт
npoqшлaкmUJ(O
fJIJOoma
х
в
t Рис. 4. Профилактика
нение которых тратится такж-е случайное время. Разработка методов предуnредительной профи.лактики }'IСТройсr.ва, вооро сы оценки его эффекти.вноСТ1И и др. цриоодят к необходИ!М'ОСТИ исслед'Ования процессов функцнонирова;ния таких . устройств (рис. 4).
Пример
5.
Гастроном. Покупатели гастронома
(рис. S)·по
стуmают в .случайные моменты времени, "I'ребуют обслужива н:ия случайной длителЬ'Ности и образуют очереди к продаtЩам
6
различных различным висимости
·секций
и
кассам от
к
1
в за
1!
номенкла
туры nриобретаемого то вара. Таким образом, ·обслуживание покупате .лей осуществляется в не
сколько
фаз
-
каждый
покупатель должен
опла
·тить товар в кассе (пер вая фаза) и получить то-вар у продавца (вторая фаза). Здесь возникает задача
оценки
редей и ния а
у
длин
оче
времени ожида-
касс
и
продавцов,
при проектировании
со
-ответствующих предпри
ятий задачи расчета наи .лучшей (возможно наи-
·
-
6олее экономичной) орга ни-зации обслуживаfшя покупателей (количество касс,
Рис.
5.
Модель гастронома
продавцов,
закрепление
касс
.за секциями и т. п.).
1.2.
'
Понятие СМО. Элементы СМО.
Несмот,ря на физические различия перечисленных в при
МеJрах си-стем, зада·чи ·их исследования имеют обшJtе сущест веннЫiе черты, и так как эти за•дачи отнО'сятся к из·учению яв-
~'lений загруженности системы
(образования оЧередей, задер
жек, простоев оборудо.вания, потерь требо:ва·ний), их решени-е не за-висит от конкретного соде,ржа.ния систем % процесоов об служи-вания, а ли.шь от н·екот01рых формальных характе,ристик этих·процессов и систем. Это зам,еча·ние позволяет рассматри вать столь различные си•стемы (как ш~речисленные в п.римерах, так и многие дру.гие) с единой математической точ,К'и зре ния. Чтобы сформулировать понятие абстрактной системы массовото обслужива•ния (СМО), выделим те общи~ черты, кото рьrм•и обладают все перечwсл.енные ,в п,римерах сисrемы.
1.
Всякая СМО сосrоит из обслуживающих средств, кото
рые будем называть приборами; вспомогательных средсm
-
мест для ожидания, за,крепленных некоторой структурой си,с темы. В примере 1 это n, rвозмож·но, различных цри'боров (бен зоколонок) и т мест для ожидания; ~ примере 2 n одинаковых nрwборов (линий) без мест ожидания; в при!мере 3 один при
бор (ЭВМ), о·бслуживающий .несколько 'потоков требований, 1В при~ере 4 устройство, являющееся источником отказов, кото рые уст,раrняются бригадой ра'бочих, выполняющих в данном
7
·
случае роль обслуживающих приборо.в; •в примере 5 обслу•жи· вающими приборами являюТ!ся касси·ры и пр.а:давцы, а систе м а имеет двухфазную структуру обктором nри.зна.ков in. Та·ким образом, по ток требований можно описать случайным продессом an =r(tn, iп) (гд-е tn- тачечный процес·с, а in- св.язанный с ним векторный процесс призна.ков) марк.ирован.н.ы,и. точечным
=
процессом.
Определение. Требования называются статистически одно родными, если 'вектор признаков in стати'Стически оДtнороден, т.
е.
его
распр·еделение не
за,висит от :времени :И номера
однороdными, есл.и признаки требований
in
n,
и
тождественно сов
падают. В нослед·нем оелучае вектор признаков можно не рас сматривать. В дальнейшем мы будем расам'а'J1риrвать rпотоки событий, характеризующихся только •количеством Vn поСТJ'IПа ющих в момент tn требований; ·В этом ·случа~ in= Vn.
Определение. Поток т,ребований называется
ординарным.,
=
если V пР! Vn = 1 ) 1, т. е. с каждым событием потока с вяза но поступление с ве-роятностью 1 лишь одного 11ре'бования.
С •каждым IМаркирава,нным точечным :процессом о:п={tп, v~} можно св,язать еще три про.цесса:
Jоtаркированный процесс интервалов
{Хп, vп},
г де
= tn- ln-I; счетчиrс числа поступивших в интервале
N (t)= ~
{0, t]
Xn =
требований
vh;
( k :tk < l}
случайную функцию интервала поток.: число шоступивших в
- N (s) - О назыв-а
ется парамет;ром потока.
Д о н. аз а т е ль с т в о.
Так как согласно определению от
·су;ст,вия последейст.вия СВ a(L\i) независИJмы для нооерес-ека ющих·ся интервалов, а распределение а(д;) в силу стационар ности не зависят от положения интерmала
l.ll;,
а лишь от его
длины, 'ГО ::~:остаточно доказать фо,рмулу
(at)ll
Pk (t) :=.::=: Р {~ (0, t)=k}- P{N (t)=k}= - · e-at kl
(3)
для интервала А= (О, t) ;длины t с левым -коНцом в .наtЧале ко ординат. Покажем снО). Далее, Ро( ~ )=[Ро (~) ]k =е -aktn. t
Наконец, Для произвольнаго
подберем такие
k и n, Чтобы (4)
Тогда •в С'илу ·монотонности функции Po(t) имее;м
е
·
-а~
=
-а k~ 1
( k) ( k+1 ) Ро -;;
р
О} =
1-р
k=O
Безусловная с-редняя длина оч~реди равна
(6)
~
_Р_
1-р
Аналогично вычисляrют·ся дисперсии.
Время ожидания
5.3.
Для нахождени.я х•арактерИ'стик длительнQстей пребывания и ожидания тов (ПФМ), v
v
w (s)
вычислим их nроизводящие функции !момен = Me-•v, w (s) = Me-sw в стационарном режи
ме, для чего зам~тим, что поступающее в стационарном режи
ме работы системы требование застает'> ее в состоянrии k с вероятностью Pk= ( 1-p)ph. При эrом его вр~мн ОЖrИдания начала обслуживания
w
ра·вно k-1
w = ~'
+ i=O ~ ~~.
где ~' остаточное Вrремя обслуживания тре О
j'
х
V(x)
=
(1- р) о( и)+
а(1 - р) е-(Ь-а) и du =
о
_ l -
-ре
-(Ь-а)_..
.
(9)
Аналогично z
W(x)
=
S
(b'-a)e-(o-a)udu = 1- e-l/1-aJx.
о
54
(10)
Упражнения. Показать, ~то имеют •мес-rо фар!мулы р
Mv = _.:___ ь (1-р)
Mw= _ } _
+ _!_ =
=
а М~. 1
(11) = aM"f},
(12)
и дать их физическое ТОЛ!КО'ВЭIНИе. Эти формулы
,дОIП)'!Сiкают
ь (1-~)
ь
ь (1-р)
·О'бобщения ·на немар.конские ;модели. ' Вычiwслwrь щ. испероии 'Времени ожида•ния бы'Вания v.
§
6.
6. 1.
w
ЗАДАЧА ОБ ОБСЛУЖИВАНИИ СТАНКОВ.
и вре1меаи пре
Описание системы. Вычисление инфинитезимальной матрицы
Рассмот.рим замкнутую .си-стему
(1ри~.
20),
~остоящую из
n
П\)'иборов (станков), которые могут выходить .из строя игре бовать внимания обслуживаю-
щего персонала. Для обслужи-
вания .ста.нков имееi'СЯ m(m 1.
( 1)
1
Пока же м, что начальные услов'ия для 1реше.ния системы
( 1)
имеют·вид
где
стационарные вероятности, вычисленные в п. Pk = lim Р \ '1j
Pk -
обще говоря, ста.Цiионарные вероятности
5.2. (t)
t-O
Во
=k J
не о·бязаны сов,падать с вероятностями состояний системы ,в некоторые случайные моменты ·времен.и (в ча.стности, в ·момоо ты окончания обслуживания) при стационарном ре:жиме ра боты. Однако в дан·ном случае такое совпадение имеет место. Для до.казатЕЩьства это·го факта за·метим, ·что .с01гласно эргод'и чоокой теореме, Fk(O) 111ред.ставляет !Собой долю переходов ти
nа
k+.l ~k,
стоян·ии
k.
а
Pk
-долю ·време.н.и, пров·еденноrо сис1емой ·в со
Однако ч.исло переходов
k+ 1---?k
на любом интер
·вале времени .не может отличаться от числа переходов ->-
k +1
ности
более чем на
,J;..,
1,
а доля переходов k~ k
+1
k
---+
равна вероят-
которая совпадает с Pk (см. сноску на стр. 53), :rюэ
том,у Fk (О) =р 1,. Далее, простой проверкой легк·о убедиться, что единственное решение системы ( 1) с начальным условием (2) имеет в.•ид
Fk(t ) =p~r.e -а/ .
(3)
Сум·ми1 руя выражения .(3) '"о k, убеждаемся, ·что инт·ервалы между моментам.и :окончания обс-луtЖиван.ия имеют щжазатель ное распред~лен.ие, что за·вершает доказательство.
Следствие. Длина интервала 'Между тр~оованиями выходя щего лотока и число тр~бований в ·системе ·в конце зто·rо интер вала - независимые •случайные величины.
Доказательство :выт,екает ив форtмулы ции
Fk (t),
(3)
для функ
если заметить, что она .раопадается в 1Пiроизведение
соответству.ющих вероятностей.
61
7.2.
Многофазная система с неоrраниченными
очередями
M\Mjn, ~
Доказа.нная в 1предьrдущем разделе тоор~ема 1поЗволяет рас пространить ряд ,результатов § 5 на мнО\Гофазные .системы об служивания. Действительно, так как выходящий лоток nер вой фазы рассматриваемой систе.мы в ·стацоонарном режим-е ее раакте.ристики •СИ стемы. АлiГQритм вычисления 'Н·О:рlмирующего мнюжителя и рас чета харахтермс.тик за.м.кнуrых се•rей реаЛ\изован .на ЭВМ Р-1020 в СВЗ МИНХиГП им. И. М. Губкина.
ГJIABAIII
МЕТОДЫ МАРКОВИЗАЦИИ В данной .главе рассматриваются системы 1Массовоrо об служивания, содержащие наряду с лаказательными также и не
пока,зательные ,р асш ределен.ия
длительl'!остей
обслу~Ж~ивания
или длителоностей ·между ,моментам•и IПОС'Г)'IПлени•я требований.
Поэтом1у ,излож·еНiные 1в главе
II
меrо:ды исмедова.ния 'ма.рков
скиiХ \fоде:лей ·не пр1И1М€1НИIМЫ. В § 9 мы перейдем от показательного раопреJДеления к эр ланговск·ому и IПокажем,
как для него можно ;путем ·в'Веден,ия
подходящих состояний применять также методы однородных
марковских процессов гл. II. Затем 6удет доказана теорем·а аппроксимации распределения неотрицательной СВ смесью распределений Эрланга, которая является основой приб.rJИжен ного метода исследования систем обслуж,ивания с любыми функциями распределения путем замены их системами с со ответствующими эрланговскими распределениями.
В § 10 изла•гае'I'ся ИЗiВ•еiСтный метод теори1и массо"Воп:-о об служива,н·ия метод BIJIOЖe·НIIIЬIX целей Маркова. Он 1Пр,И1ме няется для систем обслуживания, допускающих ·не более одной не показательно распределенной величины. При этом случай ные
процессы,
ха.рак'Т·е,ризующие
ни, :не являются
xapaкfl'epиcruк .неVIьзя
ложен·ные в гла:ве ты
времени,
так
заТJ')'IЗ'КУ 'СИСтемы 1во
маркавс•ким.и, 'Так
II.
'IfTO
для
време
ОIП.р·едел·ения
п•р'И!Менить .непоQред'ствен-но
их
методы, ·из
Однако, ·еоли удается найт.и та.К!ие м·Gмен
называемые
вложенные
моменты,
в
которые
прОIЦесс 1ведет с·е.бя по-ма.рК'ОВIС'КИ, то можно бущет ИIС!Пользо вать методы маiВЫ II. В §§ 11 и 12 из111атаютС'я
меl'оды ,и 1приводятся
примеры
расчета ти1п.ич·ны:х харакrrеристик си.стем ·обслуживан·ия, содер жащих более че~м одну !Не показательно раiалреде.п·енную ве
лич•ину. Для этого осноВiной .случаЙ'ный процесс, являющийiСя вначале не марковским, путем введения в описание состояний дополнительных переменных превращается в м.арковский про цесс, т. е. он «марковизуется».
72
Тогда в нашем
распоряже-
ни·и будут .необходИ'мые анаLЛит.иочески·е вапомоrателыные сред-· ства для .ра 1ачета мскомых харак'f1ер.~С1'ИК иссл·едуемой .си.сте
мы абслу:жиша:ния. В §§
11 IИ 12 Л'ри,водJ111Ся ,различные •ва:ри
анты эrото мето~а.
С точки з•реiшя введения д01п·ол.нительных пере1мен·ных ме
тод фаз Эрланrа и 1метод вложенных марковских цепей пред став.ляют собой ·час'Гные СЛ}"чаи 1ма.рко,В'изации.
§ 9.
9.1.
МЕТОД ФАЗ ЭРЛАНГА
Распределение Эрланrа
Еще А. к:. э,рланг iПpИ'MeH'ЯIJI в ОВIОИХ матемаr.ИЧОС'КiИХ ис следОIВЗIНИЯ.Х систем обслуiЖ,ИIВа:ния :наряду
с покавательным
раопределением та•кже функцию распределения, которой !ПОзд нее •п.р·иtво,или его .имя.
Эта функция распределения зависит от пара.метров f.t>O/ и k=
1, 2, 3, ... ,м
имеет ви.д
Е", 11-(t)
=
1
10
tО,
J=l
N
г де а 1 >О, ~
al = 1, которая называется гиперэрланговским
i=l
распределением. С помощью соответствующих гиперэрлангов сюих 1расцреде:лен.ий 1мож.ню харошо аюпроксимировать бQль
шинство встречающихся функций распределения. Для систем Оlбслуживания с пуассоновским tпотоком тре бований и гиперэрланrовским распределением длительностей
обсдуживан.ия та:кже можtно пр.им.енять метод фаз Эрла:н'Га. Модель щ:ш э1'ом бу.дет медующая. В ша·чале обслуживаiНия требования с вероятностями а.,
кому •ffЗ
N
... , aN
разыгрывается,
по I{а
э,рланtг.овских ,ра.с~пределеннй
Ek., . .. , EkN ано будет tвыпол,няе-тся ,в ki фаз, как описано
осущеС11В'ляrrься. Затем ано .в разделе 9.2 (см. рис. 27). При введении соответствующих
к
.
---------~~~--------'W:.--.... ~ ___....,..
-
* --- ....""'"'
:;w.'":.::::_iE'~::.::;.-"" Kt.
Kn.
--------------~~~-------------~ * ___.,. tt .... _ _....,.""'..
~ "'r-----..or'lf. Р~с.
27.
---~
Модель обслуживания при rипсрэрланrовском распределс нии
дополнительных
дискретных
переменных
в
описание
состоя
ний для систем с гиперэрланговским распределением длитет.) ностей обслуживания случайный процесс, описывающий по ведение системы во времени, становится
марковским, молель
обслуживания- марковской. При этом можно пользоваться рассуждениями, аналогичными приведеиным в п. п.
9.2
и
9.3.
77
Следует, однако, учесть, что нз всех
k1 +k2 +... +kN
фаз одно
временно на каждом приборе может выполняться лишь одна
из них.
Например,
состояние
j-ro обслуживающего Прибора
можно описать следующим образом:
iO
если j-й обслуживающий прибор свободен,
J(1:
i),
если
j-й
обслуживающий
обслуживание
распределению Е" !L
l
прибор
занят
и
выполняется по эрланговскому 1
rоздкн:-.I, ·не :i-IarлядiHЫ'>I системам У'рав·нений, .кото рые част'о бывает трудн·о решить в явнам .виде. Для отдель ных конкретных задач были разрабQтаны специальные рекур ршП!ные а.пгооритмы решения анетем тшейных у1 раJв•нен.ий для·
стаrщонарных вероятностей состояний в системах обслужи 'вания со 1~1ногпми фа,зами Эрланга (Н ..Мальцева ( 1972)). Бе зу.словсiо, это обстоятельство сужает применимюсть метода· фаз Эрланга для 1Р·еШе1ния конкретных задач.
Далее следует обратить внима,ние 1На то, Ч1'О ша п.рак11ике: пр.еж:.::r.е
в•сего
исходным
приходится
данным,
определять лараме11ры 'системы
в частности
по
по эмпирической функции
распределения, например, времен!/ обслужив:шия,
подбирать
соответствующие эрлаrнговское или 1ГИ1Перэрла·нговское .распре
деление. По,это'>IУ для юпределения юараметров, вег,речающих·
ся rв оrе-сях, шеобх,оди,мы эффеюшrвшые ·методы. Кокс
(1955)
рассмотрел случай, когда каждая функция распределения с раuмональ·ным 1Преобразо.ва·нием Лапласа определяется спе циа.'lьной пр10\Iент t находилась или в состоянии О (тог~а оста точное вре:v1я жизни J.Олжно находиться в интервале (1t, х+ +~t)) и.1н в состоянии 1, nричем ремонт заканчивается (с ве роятностью b.~t) за время 2-е уравнение. СИ"сте:viа в :VIО :чент находится в состоянии 1 с остаточным tвреJМеНе"-'1 жизни О) нахо::tнтся i
требований (i= О, 1, ... , n). Для ~простоты расс:wотрю1 то,1ько случай n=2 фор:vrулы 1для произвольнаго случая 'Содержатся в § 4.2. Воспользуемся методом интегродифференциальных уравнений.
1-й щаг: построение проuос·са, определение функuий расnределений и плотностей.
необходюiЬiх
Допо.1нительньr:vtи пере::.1енны::.rи яв.1яются здесь «возраст» обс.1уживания, т. е. вре\ш, затраченное на обслуживание тре·
бований, находящихся в системе, бований в систе:v1е в МО'>1ент
v (/)
равно I..:о:нr! бы часть распределений, характеризующих поведение э.н~мен тов, была .поr.I 'СЛедующие предПОЛОЖе !!ИЯ:
1)
имеется точно одно макросастояние
стояние) с означает
lvl =0.
количество
менных, т.
е.
lvl
При этом величина соответствующих
имеющихся
в состоянии
v=O
(нулевое со
для каждого
дополнительных
v
'1
Е
N
пере
непоказатльrю
рас
нреде.'lенньrх случайных величин;
2) каждо~rу v отвечает вектор (cr.", ... , CJvlv) с de 1(t)
dt т. е. в состоянии
v
=
-Сjн
.--0 """"'Cj."
<
оо,
допотштельные ,переменные убывают
со
скоростью с;. >О (ci." =О означает, что наступают временные перерывы до тех ~пор, пока система остается в состоянии
v,
на
пример перерывы в обслуживании); 3) если j-я дополнительная пере'.iенная становитсп равной нулю, .процесс из первоначального макросастояния (v=FO) пе
реходит в макросастояние v' с вероятностью р (v, j, v'), при чем 'при необходимости изменяется нумерацая дополнитель
ных переменньrх:
lv'l = lvl-1
если процесс в момент с вероятностью а." •. Ы+o(L1t)
4)
(скачок вниз);
t
находится в состоянии переходит за время [t,
состоянии v' с 1v' 1 > 1 v 1 (скачок вверх) .
v,
то он в
t+.11]
Положни
s
При этом к имеющимся остаточным длrпельностя\f 1 (t), ... , добавляются новые остаточные длительности ТJt (t), ... , '1Jiv'l-l•l (t), которые стохастически не зависят от предысто
Er,, 1 (t)
рии процесса, в частности от si(t), i=1~Tvl, н вводятся дующим
образом.
Они
имеют
совместную
сле
lv'l-lvl-мep
нyю функцию раопределения Н.,.,.:
которая зависит тот,ко от
v' и относительно которой пред полагается существование ПЛОТНОСПI. Через Н.".·(Х 1 , . • • Xlv'l-1•\
v
и
обозначается вероятность
105
При этих условиях ~(t) является однородным
марковским
прсщессом, для .полно:го описания которото, конечно, необходи мо еще начальное раапределение в момент С 1помощью
t=O.
КЛМП можно описывать очень многие модели теории м·ассо вого обслуживания и надежности.
Пример: система
12.3.
MjGijn, =
Рассмотрим модель
Ml Gll n, .оо
с функ:цией распределения
времени обслуживания В (х) и интенсивностью потока требо
ваний а. Предположим, что
v (t)
обозна·чает количество тре,бо
t
вшний, находящих·ся в момент в системе, ~j(t) остаточное вре'Чя обслуживания того требования, которое пост)'!пило в систему j-ым из имеющихся
в системе
в данный
момент,
jv(t) 1 =v(t). Нулевое состоя,ние: пустая ,система, v(t) =0, ско рости убывания.
с.
= {
}v
1,
О
'
I< j ~ min{Y, n}, nU M"l'/i
для всех ~Е N, v =1= (),
< оо
для всех
и имеются действительные числа v>O и
Jv'I-JvJ ~
...::...;
i=l
для всех
j k>O
М·л·(x), ~
pJx) =
=F О,
:l=l где 00
F~(x) = р0 а 0 ,
e-a"t
\
Ноо ( Х 1 + с 1 " t, . . . х 1 " 1 + с. 1 • 1 t)
dt,
о
· · · ' xl•'l
1•1+1
L
р(·/,
j; 'J) Cjv'
i=l д
Хди
х.J- 1 для
+с
} -1. v
t,
хi
r
е
-а
1 v
+
Х
.J
о
[-(п-1)(
Fv•
+ с1
... v
Х1
+ Clv f '
.
'
t; . .
n=2, 3 ...
Подобные итерационные формулы можно без особ~rо тру
да привести для расчета нестационарных вероятностен состо
яний. Они облегчают аналитическое решение нестационарных задач даже в тех случаях, иогда не все элементы имеют
108
no-
казателыюе распределение; ОJ.нако практический опыт приме·· пения этого
метода
показал,
что вычисления
являются
до
вольно гро:иоздюнш и .приходится много раз ,пользоваться итс
ра.ционными фор\!}'.1Ю!И, ес.1п нужно получить J.оrтаточно тач ные результаты.
Посредство:н итеращюнных фор:\!:ул стационарное решение может быть определено и :методо>vi последовательных прибли жений. При методе пос.1едовательных приближений итера ции заканчиваются пос.1е конечного числа шагов. Применять
этот метод !Целесообразно особенно тогда, -когда нагрузка си стемы небольшая, т. е. когда а...
мало по сравнению с вели
чиной, обратной математпческим ожиданиям велачин t'}i (но вых дополнительных лере'viенных).
Простейший ,путь заключается в том, чтобы заранее задать определенное чис.1о .циклов, до которого с.1едует рассчитывать.
Несколько сложнее яв;lяется следующий более точный метод: ДОПУСТИМ, ЧТО avv' ИМеет ТаКОЙ ВИД: avv' =kv•·E ГДе Е МаЛО, k;:) имеет порядок M'f)1). Пусть требуемая точность допускает исключение всех членов порядка е 111 , е"+ 1 • Тогда определяются только члены, содержащпе степени е, меньшие чем Е 111 •
12.6.
Примеры применения метода
последовательных приближений
Рассчотриы снсте'lу Па.1ь\1а сn станкюш ремонтной еднн1щей (см.§
6,
п.
10.4).
(n=2)
и одной
Пусть время жизни стан
ков до выхода их из строя нмеет пахазательное распре,.1.еление
с лараметрои а, а вре\IЯ ремонта имеет функцию распределе
IIия В (х), станки
релюнтируются в порядке выхода
их из
строя. Эту модель \южно описать J(ЛМП: через
v (t) обозна чим количество выбывших из строя статюв, lv (t) 1=v (t), че рез ~j(t) -остаточное вре:v1я ре~юнта j-ro выбывшего из строя станка.
Нулевое состояние: все станки работают (исправны). Ско рости убывания
c·-{1,j=]v=;t=.O; Jv-
О в остальных случаях.
Вероятности перехода
p(v; j, v') =
] ,· v' { (), в
=
v-
1-, v
..L
т
О,
остальных случаях
]09
У!нтенсивностиперехода
av, v+l = (n- '1)
а, а= в,
(х)= В(х).
Hv,v+l
Следует принимать во внимание только члены порядка до (г)2, т. е. М=З. Поэтому можно рассматривать только функ ции
Итераrционные формулы принимаютвид
""r> f
(l)(
1
х1
=p0 rtE J\
)
с
-(n-1)~1 -В(
Х1
t+ ) dt=
о
(1)
)
= ЕРо tfJ1 (х. ,
F~ 1(x1, Х2) = (n- 1) Е 2
,.
e-("-21 "t rp\ 11 (x 1 +t)B(x~)dt = :
о
=е
) f (З)( 1 Х1 =-Е 2
2
PofP2(2)( Xt,
"" \
.
--(n-1) tl
е
-д ~- \Р:.!(2)
ди-
) Х2,
(
U,
Х1
+ t)] и= О df
=
о
t
=е Ро
• ) fPI(3)( Х1 ·
Согласно этому, предельные вероятности состояний
Pt =11m Р/'1(1) = i}, i =О, n t-cv
приближенно равны
Pl = F\ 11(0) + F\31(0) = ер0 {р\ 11 (0) + е 1р 0 {р\
31
~
Р2
=
р, =
(2)
F 2 (0, о(е 1)
О)
=
(0),
(2)
е 2р0 q>2 (0, 0),
(i = 3, 4), .
. ).
Приближенное значение р 0 , которое может быть использова но также для расчета Pi по вышеуказанной формуле, дается в виде
:110
.Для случая постоянного времени ремонта (математическое ожидание = 1) в нижеследующей таблице при n=4 сравнива-
ются точные Pi и приближенные р'"( значения. Для малых зна чений е можно обнаружить достаточную точность. Таблкца
1-
i о
1 2 3
4
€=а=0,1 Р;
p-i
1
0,52 0,26
0,62 0,35
0,05 0,07
о о о
o.os
.,
в=а=0,01
-1
Pi
0,09 0,03 0,00
O,UO
0,00
Pi
0,96 0,04 о о о
Упражнения
l) Можно ли описать систему GIIM/n,m с ,помощью КЛМП? 2) В каком случае система с .потерями Энгсета может быть описана в помощью КЛМП?
3)
Вычислите с помощью е-метода приближенные значения
вероятностей для системы
MIGIII,
оо
(m=l, 2, 3).
ЛИТЕРАТУРА
Основная
1. Г н е д е н к о Б. В., К о в а л е н а{ о И. Н. Введение в теорию массового обслужиnання. Наука, М., 1966.
ц ~' ~
_
И~
1-
2. Konlg D., Stoyan D., Nlethoden der Bedinung~theorie (Wessenschaftliche Taschenbu.chcr, Band 143, .'v\athematlk-Physik) AkadcrnteVer1ag. Ber11n, 1976.
3. К л и ·м о в а Е. 3. Теория систем массового обслужИ!Вания (ч. 1, II)
МИНХиГП,
1972-73.
4.
Б у с л е НIК о
Н. П., К а л а ш н и .к о ,в В. В .. J( о в а л е н •к о И. Н, Лекдни :no теории сложных систем. Советакое радио, М., '1973.
5.
Чжу н
К ай-Лай. Однородные цепи Маtркова, Мир, М., 1964. Специальная
Brockmeyer Е., Halstrom Н. !.. , Jensen А. The Life апd wo•·ks of Erlang. Acta Polytcchnica Scaпdinavla, 1960. Bux W., Herzog \f. Approximat!on von Verteiltlllgsiвnktionen, cin wlchtiger Schrltt bet der Model!Ыlduвg Rechcnsysteme. Workshop u·ber Modelle fur Rechensystemc, Bonn, 31 ..1-1.4. 1~77. InformatikSachЬerichte 9, Sprlnger-Verlag. Berlln (Helde!Ьerg) New-York, 1977. Bux W., Herzog V. The Phase Concept: Approxlmation of measured Data and Performaпce Analys1s, iп: Computer Performance К. М. Chandy and М. Relser (Eas), North Holland PuЫishing Company, 1977, А. К.
fur
s. 23-37. Buzen 1. Р. Computational algorithm for closed queueing networks with exponential servess. Commun of the АСМ, 16, N~ 9. 1973. G!ller! Н. Ein Beitrag zur Theorie der stueckweise linearen Prozesse. Math. Nachr. 70, 99-110, 1975. Gordon W. 1., Newel G. F. Closed qнeнein systerns with exponentlal serwcrs. Oper. Rcs, 15, н~ 2. 1967. К а л а ш н и к о в В. В. Некоторые свойства IКусочно-лниейных марко в· ских nроцессов. Теория вероятности и ее nрил.
3, с. 511--683, 1976. Kc!nig D., Matthes К. Verallgemeinerungen der Er1angschen Formeln. Math Nachr. 26, 45-56, 1963. Konlg D. Veralll!emt-lnerungen der Engsetschen Formeln. Math. Nachr. 28, 145-1-15, 1965.
112
К:бntg D., Mathes К. Nawrotzki К.. Verallgemelnerungen der Erlangschen und Engsetschen Formeln ( etne Methode ln der Bedienнngstheorie). Akademleverlag. Berlin, 1967. К:onlg D., Jansen U., К:otzurek "\1 .. Rabe М. Ergebn!sse von Invar!anuntersuchungen fi.ir ausgewahlte Bedienungs-und Zuverlasslgheltssysteme. Math. Operationsforsch and statistlk, 7, .N'~ 4, 523-555, 1976. l(ё н и г Д. Метод проверки свойств пнвариантности и вычисление ста ционарных вероятностей для систем массового обслуживания с nрерыва нием, функциона.%нымн и стохастичеакими зависимостяiМи. Теория массо
вого обслуж:иваНii'Я. Тр. III Всесоюзной шко.1ы совещания изд. М.ГУ, 1976, с. 93-·114.
no
ТМО, т.
1,
К:on!g D., Ro1sky Т., Schmidt \'., Stoyan D., Stochastic Processes wtth lmledded Markov Point Processes (РМР) апd tltelr Appllcation Math. Operattonsforsh. Stat!st. ser. Optirnization, 9, 125-141, 1978. К о за л е н :к о И. Н. Некоторые анали11ичесн:ие методы в теории массового обслуживания. Сб. К:пбернетику на службу коммунизму, Энергия, М.-Л .. 1964. Кle!nrock L. Queнcing Systems. Vo\. 1: Theory. John Wiley and Sons.
New-York (London/Sydney) Toronto, 1!115. Сох D. R. А Use of cornplex probaЫ\itks in tlte theory оЬ stochastic prosesses. Proc. СашЬ. Phil. Soc. 51, рр. 313-319, 1955. Сох D. R. The analysls of non 1\\arkovlaп stochastlc processes Ьу lhe lnc1usion of supplementary variaЬ!es. Proc. Caшbridge Philos. Soc., 51, 433-441, 1955. Kosten L., Over Ьlockerlngs-en \Vac11tttjd proЬlemen. Doct. Diss. Delbl (Holland), 1942. Р ы ·К о в
В.
В.
Тр. ЦНИИК:А, вып.
Некоторые
8, .! 1964,
с.
-математические
модели
резервирования.
157--'1!93.
С е в а с т ь я н о 11 Б. А. Преде.1ьная теорема для марковск11х процес сов и ее nрил