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