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

РОССШКЖИИ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

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

( 05.13.17 -теоретические основы шфэритики)

АВТОРЕФЕРАТ

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

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

ЧХИТХ ВОРННАРИТХ

УДК 119.21

Москва - 1992

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

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

Официальные оппоненты: доктор физико-математических наук.

профессор В.В. Рыков; кандидат физико-математических наук, старой* научный сотрудник Ы.И. Волковинский

Ведуцад организация - Московский государственный университет имени N.B. Ломоносова

Защита диссертации состоится 25 декабря 1992 г. в IS час. ва заседании специализированного совета К 053.22.28 в Российском университете дружбы народов по адресу: 117923, г. Москва* уд. Орджоникидзе, д. 3, факультет физико-математических ■ естественных наук. ауд.

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

Автореферат роэаслан -• M 9 1992 г.

Учений секретарь специализированного Совета кандидат фнзяко-математлескйх наук

BlA. ВДмуиии

а константа q « q(0,0,0) определяется из условия П' г i 0 .

1

JLf , Л — + —] * ¿o " Uo J

Далее условимся о<5означать символом суммирование по всей воэмоюшм значениям дискретного аргумента некоторой функции. Тогда Р. - вероятность того, что прибор занят обслуживание«

(-заявки, I = Т75. а Р0 - вероятность того, что прибор отключен.

В } 2 показано, что

pt Г , » «Н>оо,1 „

В J 3 анализируется СМО lí^lo^l 1 |r|Bg при дисциплине ?1РО. Такая система описывается однородным во времени линейчатым марковским процессом X'(t) , t > О , над пространством состояния

«*- { (О); (x,l,lf,l2.....ln). х > О,

i « ПГК, ij « 7775, J « 77ñ, п » ОТ? | .

Здесь состояние ("OJ соответствует полностью свободной системе в

некоторый момент времени, а состояние (х, í, (,.....1п) означает,

что в произвольный момент времени в очереди находятся п заявок, огидаюцих в поряддш их прибытия, с номерами потоков lf,l2,...,in

{для п > /) и происходит обслуживание (-заявки (£ » /,k) или отключение прибора (I » О), которое длится уге в течение времени х.

Ь

Обозначим через п число l-заявок в очереди, £ п = п, а такге полонил Й . ,п.) и Т_ =-(l,,t~,..,t ). Пусть ft.fl; -

I с Я п I <С П

макросостояние системы'с í-заявкой на приборе (( = 77Е) или отключенным прибором (t = О) и вектором состава очереди Я; a P(l,~tn)

a P(t,ñ) стационарные вероятности состояний и (1,Я).

Теорема 2. Стационарные вероятности состояний СМО мк|ок|1 |г|Вд при дисциплине. pipo определяются сладупцюш формулами:

Р((,tn; - Ptn р] at , ( - 075, íj - 775, J = 77ñ, n = ü^,

i (*> * ay'

Pd.n) = Ptn n/[~|- , ( = n - 07r,

где Р определяются согласно теореме I. Кроме того, в 5 3 доказана

Теорема 3. Системы M|H0J1 |г|£0 и U-JCJi |г|Е0 эквивалентны с точки зрения равенства стационарных плотностей, стационарных рагпредолений длин очередей и вероятностей состояний, оггвдделяемых множествами х и и' соответственно.

Аналогичные результаты получены для дисциплин LIPO и RANDOM. Обозначим ФР времени ожидания произвольной заявки, принятой к обслуживанию в СМО ик|ак|1 [г|Ее при дисциплине PIPO в стационарном режиме через W(t) , а ее преобразование Лапласа-Стилтьеса (ПЛС) - через и(з). Кромо тсго, обозначим через ß(a) и ßi(a) ПЛС i>P Bit) и Bl(t), I = Ö7K, соответственно. В §4 доказана следующая Тоорема 4. Для системы ufc |G> |1 |г для принятых к обслуживанию заявок при дисциплине FIFO

и(х-хг) = —I - í - в ßoofi-zj] ~ х

(7)

íi'r ргх-^глп Г ра-ХгЛг .. 1

* L [-¡—J *[-¡— Чг(г)- % ß О < г < 1.

где Qr(z) - производящая функция длины очереди, а % = Р г - вероятность потери заявки.

Пусть qf- средняя длина очереди, q2 - второй факториалышй момент длины очо.реди, a vJt bj и Ъ° - J-ые начальные моменты длительности времени ожидания, времени обслуживания заявки и времени отключения прибора соответственно. В § 4 также показано, что \ (1 - х) ш, = q. ,

г о г

X (1-*)иг * к b2 q г + 2r(p-1)qt + q2 + г \ Ъг(1-%) -

-■кг pfUr) . (В)

В 5 5 результата § 2 для од"то типа заявок обобщаются на случай, когда интенсивность поступающего потока зависит от размера очереди.

Завершает главу раздел, в котором приводится результаты численных иследораний характеристик исследуемых СМО на основе программ, составленных для разработанных в данной главе, расчетных алгоритмов.

Во второй главе для СМО, описанных ь главе I, анализируются две дисциплгч отключения прибора: ограниченная, - при которой отключение прибора происходит либо после опустошения системы, либо после окончания обслуживания фиксированного числа к заявок,

с вероятностным управлением повторными отключениями прибора ( с вероятностью отключения 1- 0) при опустошении системы (.дисциплина 1.д ), и вентильная, - когда прибор обслуживает только те заявки, которые находятся в очереди в момент отключения прибора.

В § 1.1 рассматривается СМО м|нок|1 |г|1-д . Функционмрованж» данной СМО описывается линейчатым ' марковским процессом Х1(1), X > О, над пространством состояний

*,= его;, (Х,1.п,т), х « Г0,®;, { » 07й. п = оТг. т * ОТЙ,). где И{ = и(1)(Н-1) . Параметры п, ш, {их означают число заявок в очереди, число обслуженных после предыдущего отключения заявок, состояние прибора - отключение, если { = О, или обслуживание {-заяЕки, если ( = Т7Б , и время, в течение которого гг ->должэется этот процесс, соответственно, а состояние (О) имеет прежний алел.

В § 1.1 получены выражения для стационарных плотностей состояний Гх,1,п,т). Далее пусть Р0 и Р<пщ - стационарные вероятности состояний (О) и а,п) = 1) (х,1,п,я), а = > о(0,1,п,п),

ХЪО ™ 1 = »

^пи = я(0,0,п,0) , где я(0,1,п,п) - стационарная плотность

состояния (0,1,п,п). Для величин д(0,1,п,п) доказано, что

Ч(0,1,п,я) - { - 775, п = 07г^7, и - . (9)

Далее пусть

€ = ( . п = Я^Т ; - ' Ч„Ц • п = ^ ; •

= и^Т ,

я1 7 , п - 073,

*>Г - * Ро, * 9 Р,

гоо

02

кО,г-Г

'О.г--»

где 7 - вектор из единиц, размерность которого определяется контекстом. Кроме того, введем матрицы В и В0 следующего вида:

В =

р, р0 О . . о

р2 Р, е0 о • о

"г-Г

•7я 7,

р»0 Роо

^О.г-2

7о.г-2

^00 ^00

константы

Теорема 5. Величины <^пя1

з... из соотношений им

9« = (Г-ВдВ*)"' Ь

определяются с точностью до

ш = 071 ,

{. П

В

о

a q0ä определяется из условия

¿о »0 1 * 0Ы

На основе величин q^ рассчитываются стационарные вероятности состояния дайной СК10.

Теорема 6. Стационарные вероятности PQ и ?<пж для СМО

M|HGfc|1|r|Lg имеют вид

In

Р.„_ - -т~ S 7,, q(O.i.n-l.n), I - 575, n « ÜTr, т = ÜX.

inm л J^Q » » I

1 , Г-1 г-1 (13)

Pirm гр Г S q(0.l,n,m)+ u(l-i) q(0.0,r.0)\ - £ P ,

1 rwr» n=0

l « ÖX m = uit. (14)

Далее пусть P( _ m- вероятность того, что приСор обслужил m заявок и он занят обслуживанием t-заявки, Р - вероятность того, что прибор обслужил т заявок и занят обслуживанием какой-либо заявки и Р. - вероятность того, что прибор отключен. Тогда

P«

р. ш - — о , с - т^, л . юг-т.

РЛ = - . (17)

о,.,.

В § 1.2 анализируется СЫО ый|Ок|1|г|Ь* с дисциплинами обслуживания PIPO, LIPO и RANDOM. Рассмотрим сначала дисциплину PIPO. Функционирование этой СМО описывается линейчатым марковским процессом X't(t), t > О. над пространством состояний •

*,'= {(О) , (x,l,lt,lz.....(п.т) , х * 10,«) , í » D7S ,

lj = TJR . J = T^ñ ,.n » TJTr , m - 071,}.

где x, t и m имеют тот же сшсл, что и для СМО ir|HaA|i |r|Lg , a смысл вектора ?п такой же, как и для CU0 кА|СА|1.

Пусть Р(1,1п,т) и P(i.ñ,m) - стационарные вероятности состояний СМО без учета текущего времени обслуживания или отключения' прибора, при - гом символы I, ?п, Й, л имеют прежний смысл. Доказана теорема, устанавливающая связь между этими вероятностями по типу соотношений (6).

Аналогичные результаты получены для этой СМО при дисциплинах LIPO И RANDOU.

В 5 2 анализируются рассмотренные выше СМО с вентильной дисциплиной обслуживания (дисциплина 0). Для этой дисциплины заявки. находящиеся в очереди после предыдущего отключения, назовем "старыми" заявками, а заявки, поступившие за время обслуживания "старых" заявок, будем называть "новыми". Отключение прибора повторяется, если система пуста после завершения его отключения. Рассмотрим сначала СМО M|HGk|l|г|0. Функционирование этой СМО, описывается линейчатым марковским процессом Xz(t) , Г ? О , над пространством состояний

*г - | (x,(,n,mj , х « (0,а>) , I = Ö7S , п = O.r-u(l) ,

т = 0,и(1)(г-1) } ,

где состояние (х, 1,п,т) означает, чго для некоторого момента времени t в очереди находятся п "старых" заявок и т "новых" заявок, происходит обслуживать I-заявки (при 1 =77Е) или отключетю прибора (при I = О), которое продолжается время х. Для данной СМО в § 2, также как и в 5 I. реиена система интегро-дифференциальных уравнений для стационарных плотностей и вероятностей состояний СМО и выведены выражения для ряда ее показателей производительности. В § 2.2 рассмотрена СМО M^IG^Il|г при трех типах дисциплин PIPO, LIPO и RtííDOU, для которых получены результаты аналогичные случаям исчерпывающей и ограниченной дисциплин отключения.

В § 3 даются результаты чиненного анализа и сравнения различных дисциплин отключения прибора.

В третьей главе рассматривается ОНО РН|РВ|1|r|Eg, в которой ФР А(х), Bt(x), В0(х) интервалов между поступлениями заявок и времен их обслуживания, а также длительностей отключения прибора являются фазового типа и имеют неприводимые РН-представления Ca, л;, Mf; и f(30, U0) поряков 1, п, н т0 чэотвотственно.

Функционирование рассматриваемой СМО описывается однородным марковским процессом X(t) , t 0, над-пространством состояний

* - u lí -

где _^

*о{(t'O).t = >71 }. *пя = \(i.n.],a).i = T7l J = 7~?Г].

п = Ö7F , з » GTT . Здесь для произвольного момента t состояние (1,0) соответствует случаю, когда система пуста и процесс поступления заявки находит-

i-Vi}

ся на фиктивной фазе I, а состояние (I, п, 3, а) означает, что в очереди имеется п заявок, происходит обслуживание заявки ( при 8 = 1) или отключение прибора ( при э = О) и процесс поступления заявки и обслуживания (или отключения прибора) находятся на фазах I ж J соответственно.

В сделанных предположениях существует продольное распределе-

ние

р = 11т у ( Ш) = х ) , х € * , х ±+<» I )

причем рх > О для всех х € не зависят от начального распределения процесса ХЦ) и соовпадают со стационарными вероятностями. Вводем векторы

Ро = (Рю> Рго.....Рю->'

Рпв = (р|«г»в' Р«п2в""' P|n,lлg,B'•••^Plníв•'••• Рхп,тв,в)"

В 8 2 выведена система уравнений равновесия, которой удовлетворяют векторы и

Далее положим X = - А 1 ; ца - --» -»г -

«а 1

а - 0,1;

N.

Ь, Рс

о

■*„ ( -»Г _

% ' [ Но • Р*. ) • * -

-»I , -»Т "I , -» ->

р - ( о . Р, ] ; V, = - 1 , I = 0,1 .

0 0

; н,- 0

0 V

О . Р, Кроме того, введем матрицы

n

4 - - ( а ® + л ® 1 р . с = о,* ,

N = (Л Ф И,; > \ а ® I ,

л, - - ( л ® ы,; + 1 а ® ы< . I = о,1 .

В $ 3 показана обратимость матрицы N и, кроме того, доказана следувдая

Теорема 7. Если О < в < 1 и для всех собственных значений

матрица Л Р4(7в> * О. I = 0,1, то матрицы К0 и обратимы, ""ведэм теперь матрицы

\ - - ( А • Г ) » *0 А0 к,"'. * = X, н;' ,

- 13 -

, ■» -»Г .. —» г-2 ( ~ 1 с

И, - - ( \ а . I ] N . г = Я, Я [ И. Н,- Л,) [I . .

Теорема 8. Стационарное распределение { 9П » п - } СШ РН!РН!1Iг1Ед представляется в виде

Ро я0 ' " =

-Г -»Г п->

9„= 1 Р0 V . п - "Тг^Г, -»т г-г

р0 Я, И Н. , п = г,

при этом вектор ¡30 находится с точностью до константы из системы уравнений -»г -»г

р0 г = о , а константа определяется из условия нормировки .

В § 4 установлены соотношения, связывающие стационарное

+

распределение ( Р( , и *) с распре деланиями { (х), х « «} состояний СМО рассматриваемой в моменты непосредственно перед

поступлением заявок или сразу после них и с распределениями +

{ х~ (X). х а »), определяемыми для моментов выхода заявок (перед выходом или срезу после него).

Введем векторы (к, I) и (О) , аналогичные по структуре

векторам Р и Р0 соответственно. Получен следующий результат.

Теорема 9. Стационарные распределения { 1С" (х), х « *} определяются следующими соотношениями:

(0,1) = — р£ (I в

к = ^Тг, £= Ц?Г, (20)

(О) ш — > X ат, л \ 0

<7г. и = — р£{ Г \ аг • I ), к = 77г,

где 0. - символ Кронекера.

Далее введем векторы х~ (Р.,1) , аналогичные по структуре соответствующим векторам Рк1 .

Теорема 10. Стационарные распределения { (х), х « и}, определяются выражениями

№,""Т7мГ7 1

1 . - 121)

= хгмс; ' г 1 • р<;' * " ^

где 1С -вероятность потери заявки.

Рассмотрим теперь дисциплину Пусть и^и ПЛС ФР времени ожидания заявки, принятой в систему, и ПЛС ФР В^х).

Теорема 10. ПЛС ФР времени ожидания заявки, принятой в систему, при дисциплине Р1?о определяется выражением

В { 5 приводятся результаты численного анализа рассматриваемой СМО.

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

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

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

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

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

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

4. Получены выражения для преобразования Лапласа-Стилтьеса стационарного распределения времени ожидания при дисциплине

обслуживания Fifo в CMC ? многомерным пуассоновским потеком при произвольных распределения? времен обслуживания и отключения гряборэ и в СМ'", опиенвоемой рапгре делениями фазового типа, для исч«1 •"ipomefl дисциплины отключения прибора.

!*•> теме диссертации опубликованы следующие работы:

1. Бочаров П.П., Чхитх Ворннаритх. О системе конечной емкости с отключением прибора при ограниченной дисциплине обслуживания// Сети связи и сети ЭВМ как модели массового обслуживания. -Минек: Кзд-во БГУ. - 1991. - С. 26-27. г. Бочаров П.П, Чхитх Рсршшритх. О системе обслуживания конечной емкости с вентильной дисциплиной отключения прибора// Тезисы докладов IV Всесоюзного совещания по распределенным вычислительным системам массового обслуживания. - М: Изд-во ЦПУ АН СССР. - 1991. - С. 196-198. 1. Бочаров П.П., Чхитх Ворннаритх. Об обслуживании нескольких видов заявок в системе конечной емкости с отключением прибора при опустошении системы// Методы массового обслуживания в информатике. - М.: Изд-во УДН, 199?. - С. 72-88. ■1. Бочаров П.П, Чхигх Ворннаритх. Матрично-геометрическое решение для очереди фазового типа при исчерпывающей дисциплине отключения прибора// Микросистема - 92: Материалы Всесоюзной научно-технической конференции. . - Томск: Изд-во Том. ун-тч'. -1992. - С. 31-33. Ь- Бочаров П.П. Чхитх Ворннаритх, Путина C.B. Матрично-мульти-пликатиеное распределение очереди с отключением прибора и исчерпывающей дисциплиной обслуживания// Тезисы докладов XXVII научной конференции факультете физ.-мат. и ест. наук. - М.: Изд-во РУДН. - 1992. - С. 80. ь. Чхитх Ворннаритх. Время ожидания для однолинейной системы массового обслуживания с отключением прибора// Тезисы докладов XXVIII научной конференции факультета физ-.. >т и ест. наук. - М; Изд-во УДН. - 1991. - С. 140. 7.' Чхитх Ворннэритх. Анализ очереди'с вентильной диастлтой отглтжя прибора// - М. : РЦ ШГГЕ. - Труда Четвертого Международного Семинара по теории теле трафика и компьютерному уодел!ров.'..)мю (Уг""ГКМ-4 ). - 1992. - С. 192-1Э9.