Актуальные времена ожидания в модели МrIGrI1I00 с абсолютным и относительным приоритетами тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

ЕРЕВАНСКИЙ ГОСУДАРСТВЕННЫЙ■ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ МАТЕМАТИКИ

На правах рукописи УДК 519.21

АЛЛУШ ТАРЕК АБДУЛЖАФИ (САР)

АКТУАЛЬНЫЕ ВРЕМЕНА ОЖИДАНИЯ S МОДЕЛИ MJGJ11® С АБСОЛЮТНЫМ а ОТНОСИТЕЯЬНШ ПРИОРИТЕТАМИ

' -31.01.С5. - Теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

EFSBAK - 1995

Работа выполнена на факультете Математики Ереванского государственного университета

Научный руководитель : доктор физико-математических

наук, профессор. Э.А.Даниелян

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

наук, профессор' • Е. А'. АруТЮНЯЬ

кандидат физико-математических наук, доцент Г.С.Григорян

Ведущая организаций : Московский институт электрон-

ного машиностроения.

Защита состоится oJbbUgyw,C3,9Э5г. в 12

л Специализитюванного Совета К 055.01.12 при

12 ч. на заседании специализированного извета к. изо.ш л г при Ереванском государственном университете по адресу : 375049 Ереван, ул. Алекса Манукяна, 1, факуль.тэг математики.

С диссертацией можно ознакомиться в библиотеке ЕГУ. Автореферат разослан _" ' _ 1995г.-

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

В.К.Оганян

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

Актуальность теш. Математическая теория очередей начиналась ь СССР с работ А.Я.Хинчина.Е.В.Тнзденко.И.Н.Коваленко,Г.П.Климова.

Простейшая немарковская модель теории-модель М|С|1 !«> с параметром а;0 поступления,функцией-распределения (ФР)В(х),В(+0)=0 времен обслуживания вызовов. В момент t=(T вызовы отсутствуют и начинается задержка 0>О. .

Эта модель лежит в основе статических моделей с пуассонов-скими поступлениями, которым посвящены исследования Ю.В.Прохорова, А.А.Цоровкова, Л.Такача, Дж.М.Коэна и др.

К статическим относятся приоритетные модели Мт,|Сг|1|со

Модель (оо. в одноканальную модель очередей с ожиданием

поступают независимые пуассоновские потоки 1-вызовов... . ..,г-вы-зовов с параметрами а1>0,...,аг>0 соответственно.Длительности обслуживания независимы,не зависят от процесса поступления л для к-шзовов, к=Т7г, имеют ФР 3,К{х), В^С+0)=0. В момент4=0 в модели вызовы отсутствуют и начинается задержка 930.

Приоритетная модель это модель плюс приоритетная дисциплина.

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

Приоритетные дисциплины используются при.организации прохождения программ разных типов на ЭВМ (см. монографию Л.Клейн-рока "Вычислительный системы с очередями".-М. : Мир, 1979).

Первый этап теории зазершился выходом в свет монографий Б.В.Гнеденко я др."Приоритетные системы обслуживания".-^.:МГУ, 1972, и Н.К.Джейсуола "Очередн с приоритетами".-Ы.:Мир,1072. Эта монографии содержат теорию представлений для периодов занятости,длин очередей,впемен ожидания схем А и В модели И 1С ¡1 [...■

г1 "г1 1

з терминах производящих функций, или преобразований "Лапласа. ССрисуем ситуацию для 'времен ожидания. Обозначим: и иР.

актуальнее время ожидания в момент г и время ожидания я-го"

- 3 -

поступившего вызова в модели M|G|1|co ; w®_{t) и ,к=Т~г,-вир-туальноз время ожидания к-вкзова в момент t и время ожидания п-го поступившего k-вызова в схемах А я В модели Mr|Gr|l |оо.1'

Общеизвестно интегральное уравнение Такача для u>e(t) б модели W|G¡1|oo. Его вероятностная интерпретация принадлехгит Г.П. Климову. З.А.Даниеляк предложил метод получения уравнений типа Такача для wj^ в схемах А и В, модели Mr|Gr|1

Т.З.Хачикян получил аналог уравнения Такача для ь/j в модели M¡G|1 |оо. Вопрос изучения .ш^ в схемах А и В модели Ыг|11остается открыт™. Возникает

Задача 1. В схемах А и В модели Mr|Gi,¡1 |а> получить аналог уравнений Такача для ií^.

Основываясь на теории представлений, многие авторы (З.А.Да-ниелян,Т.А.Азларов,Дж.А.Хук,Н.У.Прабху,Г.А.Пошв,Г.С.Григорян и др.)стали доказывать предельные теоремы при различных загрузках.

Пусть p=aß1 ,где р^среднее ФР В(х),р-загрузка модели K|G|1|k; р^-загрузка модели Mr|Gr| 1 1,K-вызовов (1 -вызовов,...Д-вызо-вов) в схемах А и В. Вид pk1 приведен в работе.

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

Модель K(G|t|oo. 1. Пусть конечна дисперсия времен обслуживания. При р=1 и р>1 предельные теоремы для иг, п-»®, доказаны П.Эрдешем и М.Кацом, а позже другим методом Н.У.Прабху. Аналоги этих теорем для ю6(г) установлены Н.У.Прабху.

Предположение конечности дисперсии заманим на более общее. Именно, пусть при sj.0 имеет место представление

ß(s) = J e~sx óB(x) = 1- sß1 + asT(1+o(1)), (1)

о

где 1<7<2, а-полокительная константа.

:При р=1 и р>1 цредельные теоремы для ш®, п+», доказаны Т.З.Хвчикяном, а для vP(t). t-мо, — Э.А.Дашеляном.

1) Внутри каждого потока в рассматриваемых моделях вызовы обслуживаются в порядке поступления (дисциплина FIFO).

2) Условие (1) введено A.B.Печинкиным.

- 4 -

Схемы А и 3 в модели M„|G |11<». Пусть времена обслуживания имеют

конечные дисперсии.

Для t-wa, предельные теоремы в случаях "околокрити-

ческих" загрузок

аэр^и, б) ^,„<1. Рк1>1, в) pw=1

установлены Э.А.Даниэляном. Тэ же случаи, но при двух потоках, рассматривал Дж.А.Хук.

Предположение конечности дисперсий обобщается. Пусть для всех 1=Т7г при si.0 имеют место представления

0^3) = | e~sz dBi(x) = 1- sßi1+ a^^O+od)). (3)

^ и

где l<7£. a^-положительные константы.

Пусть Условия (3) выполнены для схем А и В1, а для схем В2 и 33 имеет место (3), но при 1=1.

Предельные теоремы для zo^(t), t-w», в-случаях (2) установлены Э.А.Даниэляном. Вопрос же об асимптотическом поведении п-к», остается открытым. Возникает

Задача 2. Пусть в схемах А и В модели Mr|Gr(1 ¡со выполнены условия (3). Изучить асимптотическое поведение п-><», при любом ic=TTr в случаях (2).

Диссертационная работа посвящена решению задач 1 и 2.

Объект исследования. 1. Величины ю® , . в модели ii|GJ1|a> с

ненадежным в свободном состоянии прибором1'.

2. Величины ¡ajj, п>-1, при любом fc=T7r в схемах А и В модели

WPк

Нель работы. 1. Получить уравнения для ш® и в модели M|G|11«. с неяадехным прибором и в схемах А и В модели ?irjGr|1 jco.

1) Если Т-момент освобождения модели от вызовов. Тогда с вероятностью Sit), S(+0)=0, прибор выходит из строя в прсмекутке [?,7+t) и восстанавливается с ФР ?(х), ?(+0)=0, Бремена "жизни' л восстановлений прибора независимы и не зависят от процессов поступления и обслуживания.

2. Изучить асимптотическое поведение ш^, гнсо, в случаях "околокритических" загрузок (2) в предположении (3).

Научная новизна. Е диссертационной работе:

1. Найден аналог формулы Такача для иР в модели М|0|1 |оо с ненадежным прибором.

2. Усилен аналог формулы Такача для ш® в модели К|С| 1 |оо .

3. Найдены аналоги формул Такача для в схемах А и В модели

4. В предположении (3) в случаях (2) для ш^, п-»оо, в схемах В модели МГ|СГ|1[со доказаны предельные теоремы при любом к=Т7г .

Метод анализа. Использованы : метод вложенных цепей Маркова, прием введения дополнительных событий, метод Н.У.Прабху нахождения ФР периодов занятости, тауберовы теоремы.

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

Апробация работы. Результаты работы докладывались на Международной конференции по теории вероятностей и математической статистике в Варне (1994г.), на ежегодных сессиях профессорско-преподавательского состава ЕГУ (1990-1994гг.), на семинарах по ТМО в МЙЗМ и ЕГУ.

Структура и объем. Диссертационная работа изложена на 90 страницах машинописного текста, состоит из вводной главы, трех глав и списка литературы, содержащего 61 наименование.

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

Во вводной главе описаны объект, цель и методы исследования, даны обзоры теории'представлений и предельных теорем для модели MylGj.l11<» .

Пусть И и Р - знаки математического ожидания и вероятности. В главе 1 изучаются функции ш®(з) = И ехр (-за;®), з>0, , ' - б -

в модели M|G|1|co.B случае ненадежного прибора введем обозначения.

00 О-Г СО

e(s) = J e"sx 0Е(х), <p<s) = J" e_Sx dF(x). s>0, о о

*<*> = еы-цт^п1

t(s) = 5|I|1 , X(s) = l-Rízíj^.fg/a), fMO.a). Теорема 1. При. любых ú seto,а) выполнены равенства

шп9(3) = jRT^"1 (з){е~Бв - MS/eV^bíp/}. (4)

где при я чя ~

Et *<в)Р,_0 = е se/X(s). (5)

к^о

6 6

pn =P(u>n+1=0) при R(z)^z и из теоремы1 вытекает результат Т.З.Ха-чикяна в модели M|G|1|a>. Из (4), (5) следуют формулы для и

_ o á й ш л

Пусть рк есть рк°, шп1 есть шп1 есть uj при 8=0 и (1-р)С1-е(а)Ф(а)) ■" _ rt1?fTW

Тогда при р< 1 и любом = [ jr ~ 1 )

В частности, при абсолютно надежном приборе

П-1

п1

= а 1- Е1 ^(^=0) - Р(еМЭ)],

где ш - стационарное время ожидания.

В (5) есть ограничение нв р. Его мокно снять.

Теорема 2. Пусть ${ъ)-хиньлалъкь& по лодулю корень уравнения р(2)=гр(а-ар(2)), |2|<1. Тогда

Е гк-Р^в = ехр {-а(1-р{2))8}/П-Н(р(2))1 . 0^1. 1ЙЮ К

В случае абсолютно надежного прибора

Е ак-Р(шЛ =0) = ехр {-а(1-р(г))'в} /И-р(2)] . (6}

Числа Рп9,'п>0, можно записать в явном вида, в частности, в случае абсолютно надежного прибора.

Пусть В^(х)есть п-кратная свертка В(х) с собоЯ,В(°5(х;=1 и ия любых.и х»0: С®(х) = ^Е + (8+х)г-~к~1.

Георема 3. При всех выполнены'равенства

Р(^=0) = e"aS- J е"8*- _С®(х> dB(n)(x).

8 частности, q (гь-1 )р1+а9 "hi = -а

и; ----S + Le"ae- ¿ Je-^ ce (J) «¡ш(к-1)(1).

а а к=1 о ^

При доказательстве результатов главы используются различные методы. Например, теорема'1 получена из уравнений длин очередей в моменты окончаний обслуживания, вероятностной интерпретацией (4) и (5) непосредственно, из фундаментального уравнения = =гах(0,щ 4-Хд)-модели G|G11 |о° и т.д.

Введем обозначения для схем А и В модели М |G 11 |оо. Пусть:1*,.,-промежуток времени, начинающийся с поступления в своею дную модель i .к-í-вызова и з?г-ергатаийся первым после этого моментом освобождения модели от ТТ^Т-вызовов;¡^-промежуток вре-V-ни, начинанзцийся с поступления в свободную модель k-шзова и з-вераапзгйся первым после этого моментом освобождения модели от

данного k-вызоза и i,к-i-вызовов.

-sx, -sh

Вид функций тсу_1 (з) =Ц е к 1 , Ь^Сз) = Ц е , зЮ.

приведен в работе. Положим о^а^.-.+а^ 1=Т7г

ц-Лз) =. (з), xk(s) = a^sJ/^-s).

В главах 2 и 3 изучаются функции

u¡j¿(3) = у ejp(-s^), sjó, k=T7r , Ш.

9 9 *

В схемах В .тл^,... образуют -цепь Маркова и могут быть

лучена из теорем' и 2.Фиксируем к и опускаем зависимость от к.

Тгут^ма i. üpi лпбыг u se[0,a,K) выполнено равенство

e, , -_п-1, f Ms) n_1 в i

' ф Ъ ^ Iе ^ - £ V(s)Pi }•

W от р. «И £ %}{s)-p ® = e * - .

Kíhc-tssth р,э зависят от к: p ^-вероятность того, что после

- В -

•Л КЛ '

завершения промежутка 1гк, связанного с п-ым к-вызовом.ТТк-вызовы в модели отсутствуют.

Положим

Пусть р(2)-минимальный по модулю корень уравнения рк(г)=2Ь1с(ак-акрк(и)), |г|<1.

Теорема 5. Е^1^6 = ехр С-а^ (1-р^ Г и} )8) /П-Г:к(рк(- )) ] .

Теоремы 4,5 содержатся во введении главы 3.

п д

В схеме А •*>)£''" о0Р33Уе,г Уепъ Маркова лишь при к=г, что подчеркивает сложность задачи в этом случае.

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

Б^-д, шЯ,3=Е+Т7г, - вероятность того, что после обслуживания т-го л-Еызова з промежуток попадет начало обслуживания

некоторого 3-вызова; Л=к+-1,г,-вероятность того, что ^'>8 и б промежуток (6,1^) попадет начало обслуживания некоторого вызовз; р .-вероятность того, что после обслуживания т-го

к-БЫзовз в промежуток (ь , ) попадет момент освобожден;!.--модели от шзовов; р ^-вероятность того, что '.,)0 и в некоторый момент промежутка О,^} модель свободна от-вызовов.

Теорема 6. При любы.г п>1 и &=ГС,ак) выполнено равенсгЗо й а... „ ( -ц,.(з)е кЛэ) п-1 . о

">> = а^з ' <«> {е ^ ~ ^ Д ^(з)р^ -

(7)

При р^С! кз (7) следует уравнение . . д г 1 - ели, (з)) , д

^ & Vе*« - —^

ее

которое недостаточно для определения ро;). и .

Пусть функции >К7г, находятся из уравнений

^ _ с _

где (2) = 0^-0^(3). Теорема Т. При заданна*

д т о -б (г)в £ Рои2 « 8ДП е ' *

Теорема в. Пусть при эаданнал к, 1<к.<г,

. = X . 3=ШТГ.

3 т^о ^

Тогда функции. (2).....Сг®(г) определяет сиспьела

г й г п . -в.(2) -3^(2)0 _

хихейнъ.т урабнехий.

Пусть = | . Из теорема б при Рк1 <' следует

Г д 4 П-1 о.

Е Е + гг'Е Рол" Г'

де -среднее время обслуживания 1-ьызова.

Глава 3 содержит три предельные теоремы для схем В модели

Пусть для схемы В1 выполнены условия (3) и обозначено 7.= = гЛп £ 7(1 ).--•.}» 1=ТТИ - В схемах В2,ВЗ выполнено (3),

ео при 1=1, и обозначено 7^=71 при всех 2=Т7Ес.

9. При р>1= 1 раВкалгрно по х«[0,«>) суфствует. предел г 'А® ,

11т р { -Щ-гг- < I 1 = (х). х>0,

Л« с, и/"к }

^ /¿-"в, р-^^е-^-и-^-Тк1)^, з^О, .

о 1к v 11 iv' о у

■к'о

- 1 о

Теорема 10. При рк_11 <1, р^>1 равнолерно по хе(-а>,н») - существует' р

, икг + П&,. « предел Птр < * I = К (х), -®<х<+со,

УЬ»оо 1 ЬЬУ <к 'к

•НО .

гве (х) = егр_(-18)? , 1=У=Т .з« (.-*>,+«)..

'к -....-

Теорема 11. При Р^.ц^ ра&нолерихз по хе[0,+<ю) существует преЗех

, а ® ,

ИтР[—Щ—< х ] = Т.. (х), хю. *и<о 1 0 Лк-1 ■> 17'к-1

+00 Л ^ у у

гве X е"зх <31.., <х) = егрГ- в к~1], бзЮ. о 'к-1 '

Константы ск,Ък,с1к и ек определены, в работе. Предельные распределения в теоремах 9-11 при конечности дисперсий ввемен обслуживания зызовов суть ФР: 2Ф(х)-1, Ф(х) и 2^1-Ф(х~1/^)} соответственно, где Ф(х)-стандартная нормальная ФР.

Автор выражает глубокую признательность своему научному руководителю Э.А.Даниёляну за большую помощь и поддержку при работе над диссертацией.

Подпгсоао к печати 19Л?.95г/'" ворюг бу».60 84 1.0 печ. Зэк.178 ТКР- 100

Типографий Арм. Селхоз. Академия ул. Теряна 74.