автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Исследование приоритетных систем массового обслуживания конечной емкости с марковскими потоками

На правах рукописи

Нгуен Хунг Фонг

ИССЛЕДОВАНИЕ ПРИОРИТЕТНЫХ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ КОНЕЧНОЙ ЕМКОСТИ С МАРКОВСКИМИ ПОТОКАМИ

(06.13.17 - теоретические основы информатики)

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1007

Работа выполнена на кафедре теории вероятностей и математической ' статистики факультета физико-математических и естественных наук Российского университета дружбы народов

Научный руководитель -доктор технических наук, профессор П.П.Бочаров

Официальные оппоненты: доктор технических наук, профессор С.Н.Степанов кандидат физико-математических наук, доцент Е.В.Чепурин

Бедующая организация: Институт проблем управления Российской Академии наук

Защита диссертации состоится /7» ¿HcTjïSj ъ1 1997г. > 15 час. 00 мин. на заседании диссертационного совета К 053.22.28 i Российском университете дружбы народов.

Адрес: 117923, Москва, ул. Орджоникидзе, 3

о

С диссертацией можно ознакомиться в Научной библиотек Российского университета дружбы народов по адрессу: 117198, Москва, yj Миклухо-Маклая, д.б

Автореферат разослан U. » CçsuJTgïi] Л 1997 г.

Ученый секретарь

диссертационного совета .

кандидат фйэихо-математнческих наук, доцент /ВЛ.Кокотушк«

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Анализ производительности стреми-гельно развивающихся б последние годы цифровых сетей с интеграцией служб, способных одновременно передавать данные, речь I видеосигналы, цифровых сетей связи и др. считается в настоящее )ремя одной из самых актуальных задач информатики. При этом од-шм из основных инструментов аналитического моделирования сетей I их компонентов является теория массового обслуживания.

Процессы очередей, наблюдаемые в узлах цифровых сетей, обла-1ают целым рядом особенностей. Часто потоки сообщений, форми-»ующне эти очереди, не являются пуассоновскими. Более того, в >яде случаев между ними могут существовать определенные завн-имости. При обслуживании очереден возможны случаи, когда тот [ли иной тип сообщений пользуется приоритетом, который может ¡ыть без прерывания обработки текущего сообщения или же с его [рерыванием. Длительности обработки сообщений в общем случае ¡осят случайный характер. Также нужно учитывать еще один важ-:ый фактор—это реальные ограничения на объем буферной памяти узлах сетей, что приводит к изучение моделей ограниченных оче-едей. При этом параметры входящих потоков могут зависеть от остояния очередей, что позволяет решать задачу управления пото-ами.

Наиболее общие из известных к настоящему времени моделей чередей с относительным или абсолютным приоритетами предста- -ляют собой СМО с накопителями конечной емкости и распределе-иями фазового типа. Исследование приоритетных систем конечной мкости с марковскими потоками, обобщающими потоки фазового ипа и позволяющими учитывать зависимость интервалов между по-гуплеииями заявок, для случая произвольного распределения вре-ени обслуживания ранее в литературе не проводилось. Поэтому вма диссертационной работы является актуальной.

Целью диссертационной работы является

1. Развитие методов анализа и разработка алгоритмов расчета гационарных показателей производительности однолинейных при-* эитетных СМО конечной е.\...ости с марковскими потоками заявок произвольным обслуживанием.

2. Создание на базе результатов теоретических исследовали комплекса программ для анализа стационарных показателен прон: водительности исследуемых СМО.

Результаты, выносимые, на защиту, определяются поставлм нон целью и состоят в следующем:

1. Для анализа однолинейных СМО конечной емкости с марки скнми потоками и произвольным обслуживанием с относительны или абсолютным приоритетами получены рекуррентные матрнчны алгоритмы для расчета стационарного совместного распределен!] длин очередей для произвольного момента времени, а также для м< ментов поступления заявок или окончания их обслуживания и выв( дены выражения для ряда показателей производительности систем

2. В развитие методов анализа стационарных харнктернсти однолинейной СМО конечной емкости с марковскими потоками, з< висящими от состояния очереден, и произвольным обслуживанием относительным приоритетом получен матричный рекуррентный а~ горптм для расчета стационарного совместного распределения оч< редей в произвольные моменты времени, а также в моменты посту] лення заявок или выхода их из системы.

3. На основе результатов теоретических исследовании разраб* тан комплекс программ на языке Турбо Паскаль для расчета стащ онарных показателей производительности однолинейных СМО огр; ниченной емкости с марковскими потоками и обслуживанием с о' ноентольным или абсолютным приоритетатми.

Методы исследования. В днссертационой работе применяют« в основном методы.теорнн вероятностей, теории случайных проце сов, теории массового обслуживания, матричной алгебры и числе: ные методы.

Обоснованность научных положений. Полученные в диссерт цин результаты полностью обоснованы корректными математич скнми доказательствами и проведенными численными исследован ямн.

Научная новизна работы состоит в развитии методов и разр ботко расчетных алгоритмов для анализа однолинейных СМО к ночной емкости с марковскими потоками и произвольным обслуж ванном с относительным или абсолютным приоритетами. В ди сортгщионной работе впервые при исследовании стационарных х рак горпотик однолинейных СМО конечной емкости с проиэвольнь обслуживанием и приоритетами учитывается, что входящие пото]

логут быть марковскими, при этом в случае относительного прио-жтета параметры потоков могут зависеть от состояния очереден; \ля основных показателей производительности этих систем полу-1ены аналитические выражения и вычислительные алгоритмы.

Все результаты диссертационной работы являются новыми.

Практическая ценность работы. Результаты, полученные в диссертации, могут применяться при аналитическом моделировании (нфропых сетей с интеграцией служб, цифровых сетей связи и дру-'их сетевых систем. Результаты диссертации позволяют более точно юделировать процессы очереден для широкого класса реально суще-твуюгцнх сетевых систем. В число результатов диссертации входят рограммы, составленные для большинства приведенных в ней выделительных алгоритмов и включенные в програмный комплекс для асчета систем и сетей массового обслуживания, разрабатываемый Российском университете дружбы народов (РУДН), которые мо-ут использоваться в учебном процессе для студентов направления Прикладная математика и информатика" при проведении спецла-ораторий rio курсу "Стохастическое моделирование", а также при ыполненпи курсовых и выпускных работ и магистерских днссерта-ий.

Реализация реэулътапюв работь. Исследование приоритетных истем массового обслуживания конечной емкости с двумерным мар-овским потоком и произвольным обслуживанием проводилось в рамах НИР "Разработка математических методов и алгоритмов ана-иэа мультипроцессорных вычислительных систем, локальных и ин-егральных информационно-вычислительных сетей" (государствен-ын регистрационный номер 01.9.10 033110), которая выполнялась в ютветствии с координационными планами РАН.

Апробация работы. Материалы диссертации докладывались на I, XII и XIII Белорусских зимних школах-семинарах по теории мас->вого обслуживания (Минск, 1995,1997 гг.; Гродно, 1996 г.); XXXI, XXII и XXXIII научных конференциях факультета фнзнко-мате-атнческнх и естественных наук РУДН (Москва, 1995-1997 гг.), а 1кже на научном семинаре кафедры теории вероятностен и мате-а/гической статистики РУДН (1994-1997 гг.)

Публикации. По материалам диссертации опубликовано 5 работ, i них две з центральной печати.

Структура и объем, работы. Диссертация состоит из введе-ш, трс:-: глав, заключения, списка литературы из 78 наименовании

н приложения. Диссертация содержит 121 страницу текста и 14 ри сун ков.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации приводится обзор опубликованных по данной теме работ, кратко из лагаются основные результаты диссертации и содержание по главам "В первой главе исследуется СМО МAP^/G^/l/r/fi, подробно описание которой дано в § 1. На вход системы поступают два неза висимых марковских потока заявок, определяемые матрицами As = ((Ae)ij)iii=iX'11 N» = ((A«)ü)<j=7X' s=1'2- Эж'ш'нт ач матрицы j при i ф j представляет собой интенсивность перехода, с фалы генера цш! i на фазу генерации j, причем такой переход не сопровождаете поступлением новой заявки, а злемент Nij матрицы N есть такж интенсивность перехода с фазы генерации i на фазу j, но уже сопрс "вождающегося поступлением новой заявки. Положим А* = А,+ N, Предполагается, что матрицы Л*, «=1,2, неразложимы, а матриц! JV„, s = l,2, отличны от нулевой. Тогда матрицы Л,, s = 1,2, явл* ются невырожденными.

Длительности обслуживания »-заявок имеют общую произвол! ную функцию распределения (ФР) B,(t), для которой предполагг

оо

ется, что Bs{0) = 0 и, кроме того, f tdBf(t) = l//ig < оо, я = 1,¡

о

Дополнительно к этому предположим, что Для всех собственных зш чений {а*} матрицы Л, выполняется условие Р,{—о') ф 0, где (it{y)~ преобразование Лапласа^Стилтьеса (ПЛС) ФР B,(t), s = 1,2.

Заявки обоих типов формируют общую очередь в накопителе кости г (1 < г < оо). Заявка любого типа, закончившая свою генер! цню и заставшая систему полностью занятой, теряется и вновь в ci стему не возвращается. При выборе на обслуживание 1-заявки пол] зуются относительным приоритетом по сравнению с 2-заявками. 3i явки одного приоритетного класса обслуживаются в соответствии фиксированной дисциплиной из множества дисциплин обслуживаш {FIFO, UFO, RANDOM}.

В § 2 строится математическая модель для процессов очередей данной СМО. Функционирование СМО можно описать линейчаты майкопским процессом {t(t), t > 0} над множеством состояний

.v = {(.\j\o), ¿ = !X j = 1Л;

(s,i,j,n,m,x), s = 1,2, i = l,ii, j = 1 ,¡2, 0 < n + m < r, x > 0}. (1)

Состояния процесса {7(<), i > 0} интерпретируются следующим образом: 7(t) = (t,/, 0), если система пуста и генерируемые на входе СМО заявки 1-го и 2-го типов проходят фазы i и j соответственно; K(t) = (з, t, j, n, m, x), если генерируемые на входе СМО заявки проходят фазы i и j соответственно и в накопителе находятся п 1-заявок I! т 2-заявок, при этом время, прошедшее с начала обслуживания »-заявки, находящейся на приборе, равно х.

В сделанных предположениях процесс {7(f), t > 0} является фгодическим и существует единственное стационарное распределе-те данного процесса, при этом стационарные плотности вероят-юстен p,,ij,n,m{x) состояний (я, i,j, n, т, х) представляются в виде y,,i,j,n,m(x) = [1 - где q.,i,j,n,m{x) <С <00.

Для величин qe,i,j,n,m{z) и стационарных вероятностей Pij,o со-:тояний (»,j,0) выведены система дифференциальных уравнений СДУ) и граничные условия. Пусть p,,i,j<n,m—стационарная вероятность состояния (s,i,j,n,m,x), когда не учитывается прошедшее ipem обслуживания, и pQT = (pi.i.o,• • • ,pi,i,,o,P2,i,o. • • • .P/i,i,,o),

~ (P«,l,l,n,m» • • • iPt,i,l],n,m> • • • iP*,l\ ,lj ,n,m),

<fsjn,m(x) ~ (<7»,l,l.n,m(X)' • • •» .. . , 9.,l„l,,n,m(*)) •

В § 3 найдено решение СДУ. Для его записи вводятся матричные )ункции

FQ,o(x) = eA*, Fl0(x) = сл*ж,

X

Fn,ra(x) = u(n) JFn_1>m(y)(M ® I)eA<'-*dy+ 0

x

+u(m) J Fntm-1(y)(I®N2)eA^-v)dyy n > 0, m > 0, n + m > 0,

0

*

F*ra(*) = «(n) J Fn-Um(y№®ne/i'(x-v)dy+

0

x

Hi{m) I F„,m^(y){I & Л-2)e<VU-y)dy, n > 0, m > 0, n + m > 0. 0

и матрицы

сю ОС

о о

' Здесь А ® В—кронекерово произведение матриц А и В, А® В—их кронекерова сумма, Л = Л! ф Л2) Л* = Л^ © и и(х)—функция Хевисанда.

Теорема 1. Решение СДУ для имеет вид

п гп

Я.1.М = Е Е Сп-к.т-М*), о < П + т < Г - 1,

А:=0 1=0

г—т т

Я.Тг-т,т{*) = Е Е^-т-Ь.т-Л'Л*). т = ^ к=0 1=0

при этом векторы дв1„,т = 9«,п,т(0) определяются соотношениями Ч.Тп,т=РаТЯ'.п.т, а = 1,2, п=0,«(2-«)(г-1), ш = 0,г-1-п, (2)

т—1

<32,0,т = (^т - Е <5210,;¥'т,;)у>т!т. Ш = 0,Г- 1, Л-О ,

т

• = + Оп.т, 0<П + т<Г-1,

Л'0,() = -Дг.О.О^Г.О.О» <70,0 = -ЛВ^о 0.

т —1 п —1 т

\я,т = (\п-1,т - Е Хп,т-1-»В1,о,|+1 - Е Е Хп-1-*.т-<Д1,*+1,'~

/=о ь=о ;=о

,-1

--В2,п,т)В1"о,о> т = 0, г - 2, п = 1,г-1-т,

т —1 п—1 т •

^м.т = [<*п-1.т ~ Е СГп.т-1-<-В1,0,|+1 ~ Е Е ап-1-к,т-1В1<к+1,1~ 1=0 к=0 1=0

-м(2 - п - т)(Лг, ©/)]ВГл.о, т = 0,г-2, п = 1,г-1-т,

т—1

Хо.т = ("(2 ~ т)1 - В2,0,Ш - Хо,1Вио%т-1)В^ 0,

ыо

тп-1

Сто,т = -[51 °'о,т-1-(-В1,о,|+1+и(2-т)(/®А'г2)]В1^10, т = 1,г - 1, 1=0

т г—1—т (=.)' к=0

т I

«Ст /) V Хг .т./_л-В1*0>т_,-В21Г_га1т__,.) т = 0,г- 1, > = 67т,

I'}

т г—1—т /=0 к=0

т-1

+ 5> <Тг-т.'^1,0,т-1 - ™ = О, Г - 1,

(=0

а вектор ро находится с точностью до константы из системы линел-ных алгебраических уравнений

РоГЛ* = Д' Я, где С? = Л* - £ £ "е"1 Я.,н,п (I ~ В', о, о).

з=1 /с=0 п=0

В § 4 даются методы вычисления матриц и В* к1, представляющих собой матричные экспоненциальные моменты ФР В, (х). _ Вычисление матриц Вв>к,1 можно осуществлять на основе ряда

¿=М,п&,п. » = 1,2, 0<& + /<г — 1,

п=к+1

где /?,.„ =

о

п-1

= (^1 ® Л«"1, = (/ ®

Р = I + а_1Л, а = тах|Л,,|.

Матрицы В* к , вычисляются подобным образом. В случае, когда Ва(х) имеет дробно-рациональное ПЛС, т.е. ФР В.(х) представляется в виде Ва(х) = 1 - Д,те-(7*ХГ, х > 0, где собственные числа матрицы Св имеют положительные вещественные части, а 1—вектор-столбец из единиц, матрицы и В*ак1 можно найти рекуррент-

ным образом. Для матриц верны следующие соотношения:

* в.м= {I ® 0.т)Ф.,кЛ1 ® Р.), « = 1,2, 0 < к + I < г — 1,

оо _

где фя,к,г= /{Рк,1(х) ® ем'*)(1х, М, = -С., /1, = -М. 1, при этом о

матрицы фв>к,1 определяются равенствами

Ф*,о,о = "(ЛфМ,)"1,

Ф,,к,1 = [и(к)фя>к-1,1(^1 ® / О /)+

+ 1)}Ф,,о,о, « = 1,2, 0</г + /<г — 1. ■

В § 5 выведены выражения для расчета стационарных вероятностей состояний СМО для произвольных моментов времени:

п т

Р^п.т = Л 0<П + Ш<Г-1,

' к—0 1=0 г—т т

Ре!1—т,т = У^.Ч'Тг-т-к.т-Р'а.к.Ь т ~ ^Т»"» к=0 ¿=0

где .

оо

= I - В.(х))ах, 0 < * + / < г - 1,

о

оо

• = I,(*)[1 - В.(х)}<1х, 0< к + 1 < г.

о

Вычисление матриц Г«.^,/ " Г*^ , осуществляется на основе подхода, используемого для вычисления матриц В,¿л и В* к[. В частности, когда ФР В, (л ) имеет дробно-рационально? ПЛС, имеем, что

Г,.*,, = (/ 8 ® 1), 0< к + 1 < г-1,

г;,,., = (/ 8 И.Т)Ф:,кА1 о 1). 0 < к + 1 < г. 8

Векторы ра>п,т вычисляются с точностью до константы, которая затем определяется из условия нормировкн.

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

В § 7 найдены стационарные вероятности состояний цепей Маркова, вложенных в процесс {7(<), £ > 0} по моментам поступления заявок или завершения их обслуживания.

В § 8 изучено время ожидания приоритетных заявок и доказана Теорема 2. Для СМО МАР2/С7/1/г/^ ПЛСи^у) стационарной ФР времени ожидания 1-заявок, принятых в систему и обсуживаемых по дисциплине РСРБ, имеет вид

где Ад = А(1'(1 - тгх), 7Г1—вероятность потерн 1 -заявки, А(1) — интенсивность потока 1 -заявок, а

В § 9 приводятся результаты численного анализа рассматриваемой СМО с помошыо программы на языке Турбо Паскаль, реализующей полученные в главе 1 расчетные алгоритмы.

В главе 2 проводится исследование СМО МАР-^/Съ^/г]которая отличается от исследуемой в главе 1 системы лишь тем, что при выборе на обслуживание 1-заявки теперь пользуются абсолютным приоритетом при этом вытесненная из прибора 2-заявка обслуживается заново.

В тех же предположениях, что и в главе 1, данная СМО опи-1о1вается линейчатым марковским процессом, состояния которого :овпадают с состояниями множества (1) с тон разницей, что состояния (2,г,],п,т,х) определены лишь для п=0, и этот процесс является

п т

• = 1,1 0<г>4-т = <1—1

1в,к,1 = (В»Х1 - и(1 -к- 1)1 - и(к)1,,к-1ЛN1 ® /)+ +и(0/,>>|_1 (I ® ЛГ2)) (У1 + Л)"1.

эргодичсскнм. Мы сохраним здесь обозначения главы 1 для стационарных плотностей и вероятностей состояний данного процесса, а также ряда других вспомогательных обозначений главы 1.

В § 2 выводятся СДУ и граничные условия для дв,^,п,т{х) и стационарных вероятностей р^.о-. В § 3 получено решение СДУ для Теорема 3. Решение СДУ для г/в,¡¿,п,т имеет вид

п т

Чип,т(х) = ^СЕ^-Мг-^МО*). 0<п + т<г — 1,

к=0 1=0 г—т т

Й^г-т.тС*) = Ш = «Гг.

к=0 1=0

гг>

й5,т(®) = т = О,Г — 1,

г 1=0

где зекторы 5=1,2, п = 0, «(2 — з)(г — 1), т — 0, г — 1— п,

определяются соотношениями (2), а для 91,о,г справедливо равенстве

.г-1

91 А.г = 2® О. ¡=о

приэтомматрицы^(х), Вв)к,1, В*ак1, у'пи ,т

я определяются так же, как в главе 1, а для матриц Хп,т 11

цмеют место следующие соотношения:

Хо,о = —^2,0,0-Э^0,0>

т—1 п—1 т

Хп,т = (Хп-1 ,т - 53 Хп,т-1-/-В1)о,(+1 - У] УЗ Хп-1-Ь,т-<Д1,*+!,< — (=0 *г=0 1=0

- и(2 - п)и(т)Га,о1т-1(Л''1 0 /))ВГ^,0, п = 1,г- 1,т = 0,г - 1 - п

т-1

Хо,т= (у(2 - т)7 - В2,о,т- 53 Хо,гг.-1-«В1,о,»+1)В^10, т = 1, г — 1.

(=0

г—т т к=О I=}

-и(т~г + 2)и(т-у)Г2,о,т-1^(^1<ЭТ), т = 0, г - 1, 3 = 0~т;

вектор ро с точностью до константы"находится из системы линейных алгебраических уравнений

р0тЛ/ = бг, ' где 0—вектор-столбец из нулей, а

2 г-1 г—1

» = 1 /=0 «=0

В § 4 выведены формулы для стационарных вероятностей состояний СМО в произвольные моменты времени:

п тп

Phn.Tr> = Ц 53<г1^_)с,т-|Г1,»!,Ь 0<П + П»<Г-1,

/с=0 1=0 г—т т

Риг-т,т = ™ = О» Г,

(:=0 (=0

т

<=0 - .

при этом векторы ря,п,т вычисляются с точностью до константы,, которая затем определяется из условия нормировки.

В § 5 приведены выражения для основных показателей производительности СМО в стационарном режиме.

В § б получены стационарные распределения вероятностей состояний для цепей " Гаркова, вложенных в рассматриваемый линейчатый марковский процесс по моментам поступления заявок или завершения их обслуживания.

В § 7 найдено выражение для ПЛС стационарной ФР времени зжндания приоритетных заявок, принятых в систему и обслуживаемых согласно дисциплине FCF5.

Численные результаты для данной СМО представлены в § 8. Вычисления производились с помощью программы, составленной по полученным б главе 2 расчетным алгоритмам на языке Турбо Паскаль.

В третьей главе разливается излагаемый в главе 1 метод иссле-допанпя однолинейной СМО с конечным накопителем и относительным приоритетом, когда параметры входящих марковских потоков зависят от числа заявок, находящихся в накопителе, и представляются в виде Л^,,, и N^rn, « = 1,2. Аналогично вводятся Л„,т =

© Лп.т, = Л*>т + ЛГ* т, Я = 1,2 II Л* т — Л*т +

Здесь п и т суть числа заявок 1-го и 2-го типов соответственно находящихся в накопителе.

Предполагается, что матрицы Л* т неразложимы, а матрицы отличны от нулевых. Тогда матрицы и Л„,т являются невырожденными матрицами для каждого п и т.

Длительности обслуживания в-заявок имеют общую произволь ную ФР для которой сохраняются все предположения из главь

I, Кроме того, предполагается, что для всех собственных знамени* матрицы Л*,т выполняется условие /3,(-«,т)(.) ф 0, гд< ва{у) по-прежнему есть ПЛС ФР 2?„(£), $ = 1,2.

Все остальные предположения и обозначения главы 1 остаюта в силе и для данной главы.

В § 2 получена СДУ для (¡а,п,т(х) и граничные условия, а в § ( дается ее решение. Для его записи используются матричные функ цни

Л.мЛ®) = О <*; + /< г - 1,

X

0

п>0т>0, п + т > О, 0 < п + к + т + / < г - 1,

*М,о,|(*) = елг.««, О <к + 1< г,

X

О

" > 0, т > 0, п + >73 > О, 0 < п + к + т + / < г.

Тоорема 4. Решение СДУ для <?в,п,т(я) представляется в виде

п т

Ч,Тп,т(Х) = Е т-|Л,п-М,т-|(*)> 0<П+Ш<Г — 1,

* = 0/=0 г—т т

Ч.Тг-т,т(Х) = Е ГП = 0~Г.

к—0 1=0

Значения векторов (¡,¿,1 " Ро находятся с помощью метода, раз-штого в главе 1. Однако некоторые матрицы теперь определяются ю-другому, а именно:

оо оо

Вв<пХт,, = I В;1пХт1, = I Ъм{х)йВ.{х),

о о

^'0,0 = -^2,0,0,0,0-0^0,0,0' т-1

Сп,т = [Хп-1,т ~ Е Хп,"1-1-/^1,0,п,1+1,т-1-< — 1=0

п — 1 т к=0 /=0

- Вг.п.о.т.о]^^ п 0 т, т = о, г - 2, п = 1, г - 1 - т,

т-1

;о,т= [«(2 - т)/-В2,о,0,т,0- Е

• ¡=0

т = 1,г - 1,

Со,О = -Ло,о-01~о,о,о,о'

— [<7п-1,т — Е <Тп,т-1-ГВ1,0,п,1+1)т-1-| — /=0

п—1 т

- У^. Е ^п-Л-к.т-!п-1-1-.|,т-|-

- и(2 - п - т)(Лг1 ^ 1)]В^п<0>т, т = 0~Г^2, п = 1,г-1-т,

т-1

1+

/=0

+■ и(2 — т)(/ ® ^о,о)]-^Го,о,о,т> т=17ГГТ,

?—1—т т

<Рт,] = \'г-1-т,т-; ~ 53 53 Хк,1-}Щ,г-т-к,к,т-к,1~ к—0 (=]

т-1

— и(т — ]) 53 Хг-т,1-}Щ,0,г-т,т-1,1 ~ Щ,г-т,0,т-^,}» 1-]

т — 0, г — 1, = О, т,

г—1—т т т —1

'¿'т — 53 "»./-ВГ.о.г-т.т-«,/-

к=0 (=0 1=0

— СГг-1-т,7п. т = О, Г — 1,

2 г

л/ = (с?2,о,г-1

« = 1 1=0

В § 4 развивается метод вычисления матричных экспоненциальных моментов для рассматриваемой СМО.

В § 5—§ 8 отражены результаты, аналогичные рузультатам, полученным в соответствующих параграфах главы 1.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

Проведенные исследования позволили получить ряд новых результатов, которые заключаются в следующем:

1. Для обоих типов приоритетного обслуживания, включая систему с относительным приоритетом, когда параметры марковских потоков зависят от состояния очередей, выведены матричные алгоритмы расчета стационарного двумерного распределения длин очередей в произвольные моменты времени и формулы для вычисления основных показателей производительности этих систем.

2. Для всех исследуемых СМО найдены стационарные распределения вероятностей состояний цепей Маркова, вложенных по моментам поступления заявок или моментам завершения их обслуживания.

3. Для всех рассматриваемых систем получено преобразование Лапласа-Стилтьеса для стационарной функции распределения времени ожидания приоритетных заявок, принятых в систему и обслуживаемых по дисциплине

4. На основе полученных вычислительных алгоритмов для обоих типов приоритетного обслуживания без учета зависимости параметров потоков от размеров очередей разработан комплекс программ на языке Турбо Паскаль для расчета стационарных распределений длин очередей и ряда других показателен производительности этпх систем и на его основе проведен численный анализ некоторых характеристик исследуемых систем.

Основные результаты диссертации отражены в следующих опубликованных работах:

1. Бочаров П.П., Фонг Н.Х. Анализ системы обслуживания МАР^/Сг/^/г с относительным приоритетом// XII Белорусская зимняя школа-семинар по теории массового обслуживания "Исследование систем и сетей массового обслуживания": Тезисы докладов.—Минск: Изд-во БГУ, 1996.—С. 16-17.

2. Бочаров П.П., Фонг Н.Х. Анализ системы массового обслуживания МЛРг/Сг2/1/'' с относительным приоритетом// Вестник Российского университета дружбы народов. Серия "Прикладная математика и информатика". 1990.—N 2.—С. 67-84.

3. Бочаров П.П., Фонг Н.Х. Анализ системы обслуживания МАР-2/С?/1/г с абсолютным приоритетом// XIII Белорусская зимняя школа-семинар по теории массового обслуживания " Массовое обслуживание. Потоки, система, сети": Тезисы докладов—Минск: Изд-во БГУ, 1990— С. 21-23.

4. Бочаров П.П., Фонг Х.Н. Анализ системы массового обслуживания МЛРг/Сг/!/'' с абсолютным приоритетом// Автоматика и телемеханика.— 1997.—N 9.—С. 66-85.

5. Фонг Н.Х. Анализ системы МАР^/Сг/Х/г с относительным при-оритётом и с потоками, зависящими от состояния очередей// XXXIII научная конференция факультета физико-математических и естественных наук РУДН: Тезисы докладов—М.: Изд-по РУДН, 1997.—( 99.

Nguyen Hung Phong (Vietnam)

Investigation of the priority queueing systems of finite capacity with Markov arrival processes

Single-server queueing systems of finite capacity having Markov arrival processes, arbitrary service times and non-preemptive or preemptive priorities are considered. The case of non-preemptive priority under consideration that Markov flows parameters depend on queues lengths is considered too. Such queueing systems can serve good models for performance evaluation of integrated service digital networks, communication networks and so on. For stationary two-dimensional distributions of Markov processes describing behaviour of corresponding systems the matrix-recurrent algorithms are derived. Stationary distributions of Markov chains embedded on customers arrival instants or their departure moments are obtained too. The Laplas-Stiltjes transforms for the stationary wating time of priority customers as well as some other systems performance characteristics are given. Numerical results are presented.

Нгуен Хунг Фонг (Вьетнам)

Исследование приоритетных систем массового обслуживания конечной емкости с марковскими потоками

Исследуются однолинейные системы массового обслуживания ко нечной емкости с марковскими входящими потоками, произвольным обслуживанием и приоритетами двух типов—относительным и абсолютным. При этом для относительного приоритета рассматривается случай, когда параметры марковских потоков зависят от состо янил очередей. Такие модели могут быть использованы для анализе производительности цифровых сетей с интеграции служб и другш сетевых систем. Для линейчатых марковских процессов, описываю щих функционирование соответствующих систем, получены матрич ные алгоритмы для стационарных /вумерных распределении длш очередей. Также выведены выражения для стационарных распре делений цепей Маркова, вложенных по моментам поступления за явок или моментам окончания их обслуживания. Получены выра жения для основных стационарных показателей производительност! систем: вероятностей потерь для заявок каждого типа, интенсивно стей выхода заявок различных типов и др. Для всех исследуемы: систем получено преобразование Лапласа-Стилтьеса времени ожи дания приоритетных заявок. Представлены численные результаты.