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

Г. МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

1 ' Факультет вычислительной математики и кибернетики

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

УШАКОВ Владимир Георгиевич

УДК 519.21

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

01.01.05 — теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

Москва — 1994

Работа выполнена на кафедре математической статистики факультета вычислительной математики и кибернетики Московского государственного университета им. М. В. Ломоносова.

Официальные оппоненты:

доктор физико-математических наук, профессор А.Д.Соловьев;

доктор физико-математических наук, профессор В. В. Калашников;

доктор физико-математических наук, профессор А. В. Печинкин.

Ведущая организация:

Нижегородский государственный университет им. Н. И. Лобачевского.

Защита состоится „ 6 " 199.Tr. в 11 часов

на заседании специализированного совета Д 053.05.38 при МГУ им. М. В. Ломоносова (119899, ГСП-3, Москва, Воробьевы горы, МГУ, факультет ВМиК, ауд. 685).

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан , 2-3 - слм^Щ^_199*/г.

Ученый секретарь специализированного совета, профессор

Н. П. Трифонов.

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

Актуальность теш. Математические модели, описываемые системами массового обслуживания с приоритетами, широко применяются при проектировании и анализе функционирования информационно-вычислительных систем, систем связи и транспорта, автоматизированных систем управления и др. Это стимулировало сотни публикаций и в итоге привело к созданию ноеого направления в теории массового обслуживания - теории приоритетных систем. Систематизация результатов по математической теории одЕокаяальных приоритетных систем обслуживания приведена в монографиях Б.В.Гнеденко и др. (Приоритетные системы обслуживания,- М.: изд-во Моск. ун-та, 1973), Н.Джейсуола (Очереди с приоритетами.- Ы.: Мир, 1973), В.Ф.Матвеева и В.Г.УшакоЕа (Системы массового обслуживания,- М.: изд-во Моск. ун-та, 1984) и ряде докторских диссертаций.

Одним из предположений, которое в значительной мере определило метода, используемые в теории приоритетных систем обслуживания, является предположение о том, что входящие потоки требований являются пуассоновекими. Однако, при изучении реальных систем оказалось, что входящие потоки не всегда могут быть приближены пуассоновскимй, и, что замена реального потока пуассоновским может привести -к значительному искажению результатов. Кроме того, в последнее время большое значение приобрело направление в теории массового обслуживания, связанное с анализом сетей. Вводящие потоки в узлы сети редко бывали? пуас-соковскнж. Для них характерны как зависимость интервалов между поступлениями требований, так и отличие распределения этих интервалов от показательного. Изучение систем обслуживания с рекуррентными потоками позволяет учесть Еторую особенность потоков в сетях.

Задача исследования приоритетных систем с непуассоновски-ми входящими потоками оказалась очень сложной. В этом направлении имеется совсем мало работ, причем в большинстве из них рассматриваются не произвольные рекуррентные потоки, а некоторые их подклассы (гиперэкспоненциальные потоки, смеси потоков Эряанга). Если для численного нахождения характеристик системы можно использовать и имитационное моделирование, то для решения задач оптимизации, исследования асимптотического поведения в условиях малой и критической загрузки, ранения обратных задач необходимы аналитические зависимости характеристик от параметров системы. Таким образом, разработка аналитических методов анализа приоритетных систем при общих предположениях о входящих потоках и распределениях времен обслуживания является весьма важной для теории массового обслуживания и ее приложений.

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

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

обслуживания по ев характеристикам.

Научная новизна •работы определяется следующими основными результатами, полученными впервые:

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

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

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

4. Получен класс предельных распределений длины очереди при критической загрузке в системах с относительным приоритетом и чередованием приоритетов.

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

6. Указан алгоритм восстановления параметров широкого класса однолинейных систем обслуживания по выходящему потоку и згремени пребывания требования в системе.

Апробация работы. Результаты диссертации докладывались на 1У Всесоюзной школе-совещании по теории массового обслуживания (Баку, 1978 г.), Всесоюзной конференции по теории массового обслуживания и стохастической геометрии (Цахкадзор, 1983 г.), III Международном семинаре по теории телетраффнка (Москва, 1984 г.). Всесоюзной конференции "Современные методы анализа

информационно-вычислительных сетей" (Петрозаводск, 1986 г.), на Всесоюзных совещаниях по математическому моделированию систем связи (Минск, 1989 г., Ташкент, 1990 г.), на семинарах по теории вероятностей в Белорусском ГУ ( 1988 г.),.в институте математики АН УССР ( 1986, 1989 гг.), а также неоднократно на научных семинарах кафедры математической статистики факультета ШиК М1У (рук. Ю.В.Прохоров) и на семинарах по избранным вопросам теории вероятностей, математической статистики и теории массового обслуживания в МГУ (рук. В.М. Золотарев, В.В. Калашников, В.М. Круглов).

Публикации. По теме диссертации опубликовано 19 научных статей. Основные результаты содержатся в [ I] - £14] .

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 105 наименований. Объем диссертации - 259 страниц.

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

Во введении обсуждаются существующие методы анализа приоритетных систем обслуживания, трудности, возникающие при по»

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

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

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

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

ностью 81 (х) для требований из ¿-го класса.

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

1) не допускается прерывание обслуживания;

2) приоритетная дисциплина не зависит от реализаций времен обслуживания и интервалов между поступлениями, и не влияет на них. .

Положим

где ¿¡¿ (±) - число требований с -го класса в системе в момент времени £ , ¿(¿) - номер класса, требование которого обслуживается в момент времени Ь , ~x.Lt) - время, прошедшее с начала его обслуживания до момента £ ( если ¿.а)* О , полагаем С (Ь) = зе = О ), #(-6) -время, прошедшее с момента последнего поступления требования до момента -Ь,

1 Ъхду

— 00 п.

п=о

о

оо ов ^

* 'Л

о "

^ -иг 1С

р. (е —-

У

■иг и.

л ИГ«-

Л С*'"'*)* \ е --—--РЛЬ^!'

О

Теорема I. Справедливы с л едущие соотношения:

г -I ... — .

2) П£>гг /££^^/>¿.(2, 6 = *

1

= I-С? + иг)р,(£,ъг,?);

о

ЛО

С « С

со

а'"0«»,*)п>/1,

о

о

Теорема 2. При дисциплине относительного приоритета функции определяются из следующих соотно-

шений:

оо

+ X С/5» 2)*" / а**( у

1-А(р-ъ)

■ 0£ = О.,

а функции Д. определяются последовательно

для = 1 из соотношений

оо оо

+ Г j" /cf fr,*, i, I) <P¿ (*'",T,s)</rJ,

= < о

K¿\r, yts, z)= K¿ í.T^s г),

чч-О г i

o

rn4l[¡¿, Tj

K¿(T,hs,z)= J -ave-к) e * •

o

¿-Í г •

- Z Л- Ä- íy-* y(s,t,}) Г p¿ zy.,

ОО t

У,^ ЕÍh C*(J)> и+Ъ S>U~

L j-LH О .

frzO "-0

7 e^a-i^QoCu+^s)^,

+ p. г,- - у

^ ' ^ о .....

r¿) ,, cv

г a-ty)

-

В теореме 3 параграфа I получено другое представление для д. у, 2) , а именно, через решения ряда краевых задач

Римана для аналитических функций.

Если сС(5) представляет собой дробно-рациональную функцию, распределение случайного процесса ¿Ш)

монно получить в более удобном виде.

Пусть

ы - ; Л.

и

Щ (3) ... ^н ■> М - п< + ... + п^ - решения

уравнения

¿=г

, .. • , ЪгЦУСъСС\ Я) - уравнения

I

* / ар \пе г

и Д (г),..., (г) - уравнения

" ^ / \пе

г-/ V ^ /

Теорема 4. Если входящий поток имеет дробно-рациональное

преобразование Лапласа-Стилтьеса, то

СО

Г е ---.¿^

о

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

L r еЦ-«7 -i 1-Щ) . *

+ СР, ТЕ) Л (ае-ъг) (ъг,2,Ж,5) = /)t. (н, sj, t--t

Ai

7ех/>{- (f+frfr))*}*

v-t

ЪГ

р.1г,*,ъг,!).[1-В^х>]е l j e ———^ ,

M * f-V <0 «и"®* '

i .(^V'iiJ, ^ i) to- - .

._ n _-_——

h(br,ZU>,S)=Pt h[ ZT /> ^fris+ъгуз

Ъ -l 2 -/-'Aiy; ^

'1- о 4-А1?) ' еч 7

■ / а, ,•> Г-** №<{>>°**>*) ,

о

. р>а\ к)4 Ос (Ъ Л = £ (Ъ

н П(*е'КЮ) ы-ггуС*)

у / л- — л +

-П1

' ем

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

. В параграфах 3 и 4 исследуются системы с чередованием приоритетов. В § 3 результаты теоремы I § I использованы при нахождении распределения вектора длин очередей в системе с двумя классами требований. Случаю дробно-рационального преобразования Ладласа-Стилтьеса входящего потока и произвольного числа приоритетных классов посвящен § 4.

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

загрузки.

В § I рассматривается та же система обслуживания, что и в параграфе I главы I. ,

Пусть

-í ¿ i -Г*V* , ¿

f.-i-i^n'rp^Jio), j>.f ¿ ; ^

Prí = - Ы'м)1 f-*?>■ ■■

Теорема I.

fio

ff* u,jt

= a £f-AW

oi

t'

к Г ■

+ e J e -/J. ,

Л ! [ . ¿-t ■,

= a[i~

Здесь

Ргг

>*-т+~r ~а

В параграфе 2 аналогичная предельная теорема получена для длины очереди Е системе с 2. независимыми рекуррентными потоками и относительным приоритетом.

В § 3 рассматривается система с двумя пуассоновскими потоками и чередованием приоритетов. Положим

со о

Q< fin* frx •

Теорема I.

ton. P(f ?\с*/Р*')<х>)*

x* г Pn^bi^l I J, , «

У j (fa pu J ' ]

I 2

Г h fo oo f*1 ?

« u4 ri* Г- -¿i^hi^l

° f' i 9f e*Pt t-Ь [ Я«, 1 J

<-z

>

l- b^^AifjM-h^

и*-

+

Здесь л

ег

$с(*.) = ~=г Г е 4 А ф .к-

~ *Г, 1 / А* }

-3) ( ~ т -—I

Ргг о о

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

В качестве примера приведем некоторые результаты для системы с относительным приоритетом. Пусть в однолинейную систему поступают два пуассоновских потока требований с ин-тенсивностями и Ад, соответственно. Длительности • обслуживания - независимые случайные величины с функциями распределения В1Ы) и В^Сх.) ,

со ОО ■ .

о О

Ь С5)

- преобразование Лаяласа-Стилтьеса

выходящего потока требований с -го типа.

Теорема 4. При дисциплине относительного приоритета функции и £¿(-2) определяются по формулам

£ (5) - р! I--— Л +-—-г*

Л --:--)),

1518 »1 - + <¿4 с-лад,

А*^, С^)) г -т—----'

А , (

а - является решением уравнения

4(5) =

■ - - ■■ - •

% Д - ^щса^))

Во втором параграфе главы 3 решаются задачи врсстановления параметров однолинейных неприоритетных систем обслуживания по одномерным распределениям выходящего потока и времени пребывания в стационарном режиме. В § 3 аналогичные задачи решаются для приоритетных систем.

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

1. В.Г.. Ушаков. Приоритетная система обслуживания с неординарным эрланговским входящим потоком и обратной связью.-Вестник Моск. ун-та, сер. 15 вычисл. штем. и киберн.,

1977, ü 2, с. 82 - 88.

2. В.Г. Ушаков. Система обслуживания с эрланговским входя- . щим потоком и: относительным приоритетом.- Теория вероятн. и ее примен., 1977, т. 22, Л 4, с. 860 -.866.

3. В.Г. Ушаков. Однолинейная система обслуживания с относительным приоритетом.- Известия АН СССР, техн. киберн.,

1978, » I, с. 76 - 80.

4„ V. С. Uskakov. On some, fyueaeihj. Systems -uriih.

XeBatiTre priority.. — F und(K,men.'bQ.ßs of 1еРе-£га.-£. Theory: Prac. of ihe. 3-Ж Tntern.. ^аЫпаЪ ол. Тяег-traf. Theory-. H. 19*4, p.

5. В.Г. Ушаков, Е.Г. Харитонцев. Оценка скорости сходимости

в некоторых предельных теоремах для приоритетных С Ж).- в »

сб. "Случайный анализ", М.: изд-во Моск. ун-та, 1987, с. 121 - 129.

H.A. Акбулатов, В.Г. Ушаков. Об одной предельной теореме для системы с чередованием приоритетов при критической

загрузке.- в сб. "Случайный анализ", М.: изд-во Моск.-ун-та, 1987, с. 3 - 7.

7. В.Г. Ушаков, Е.Г. Харитонцев. Об оценках близости распределений по их преобразованиям Лапласа-Стилтьеса,- в сб. "Вероятностное моделирование систем и сетей обслуживания", Петрозаводск, Петрозаводский ГУ, 1988, с. 79 - 84.

8. Д.А. Кожевин, В.Г. Ушаков. О поведении длины очереди в СЮ с относительным приоритетом в условиях критической загрузки.- в сб. "Вероятностное моделирование систем и сетей обслуживания", Петрозаводск, Петрозаводский 1У, 1988, с. 20 - 24.

9. Д.А. Кожевин, В.Г. Ушаков. О предельном распределении длины очереди в CMD с относительным приоритетом при критической загрузке.- Вестник Моск. ун-та, сер. 15 вычисл. матеъа,- и киберй., IS88, .4 2, с. 43 - 47.

10. В.Г. Ушаков. Аналитические методы анализа системы

О I I Сгг 11 / «*> с относительным приоритетом.-Вестник Moca, ун-^га, сер. 15 вычисл. матем, и киберн.,

1993, й 4, с. 57 - 69.

11. В.Г. Ушаков. О длине очереди з однолинейной системе кассового обслуживания с чередованием приоритетов.-Вестник Мося. ун-та, сер, 15 вычисл. татем. и киберн.,

1994, й 2, с. 29 - 36.

12. З.Г. Ушаков, 0 решении некоторых обратных задач в теории кассового обслуживания,- М.: МГУ, деп. в ВИНИТИ РАН, 1994, 25 с.

13. В.Г. Ушаков, 0 предельном распределении длины очереди

при критической загрузке в системах обслуживания с различными приоритетными дисциплинами без прерывания обслуживания. - М,: М1У, деп. в ШКИТИ РАН, 1994, 20 с.

14. V. G. Vshakoir. Sone. resue^s for Ые.

fueaeinj spsten QIt / G ( f I

letabtlr-e. prior-i tj.. - T. of "lik.

Sciences , V.C9, {934, Cf>.