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

ВВЕДЕНИЕ.

ГЛАВА I. СИСТЕМ M|s|l СО СЛУЧАЙНЫМ ВЫБОРОМ НА

ОБСЛУЖИВАНИЕ.

§ I. Описание системы и постановка задачи . . №

§ 2. Определение совместного стационарного распределения характеристик системы . •

§ 3, Некоторые числовые характеристики системы . . ЗЦ

§ 4. Сравнительный анализ дисциплины случайного выбора с дисциплинами FIFO и LIF

ГЛАВА 2. СИСТЕМА СО СЛУЧАЙНЫМ ВЫБОРОМ НА ОБСЛУЖИВАНИЕ

ВНУТРИ ПАКЕТА.№

§ I. Описание системы и постановка задачи . . ЦО

§ 2. Определение совместного стационарного распределения характеристик системы . . №

§ 3. Некоторые числовые характеристики системы.

§ 4. Сравнительный анализ дисциплины случайного выбора с дисциплинами FIFO и

ГЛАВА 3. СИСТЕМА СО СЛУЧАЙНЫМ ВЫБОРОМ НА ОБСЛУЖИВАНИЕ

ВНУТРИ ПАКЕТА ОГРАНИЧЕННОЙ ДЛИНЫ . 6Z

§ I. Описание системы и постановка задачи

§ 2. Определение совместного стационарного распределения характеристик системы . . £

§ 3. Некоторые числовые характеристики системы.$

§ 4. Анализ характеристик системы.S

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

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

Изучению систем массового обслуживания посвящено много работ. Особенно продвинуто изучение систем класса М|(т|1 с различными дисциплинами обслуживания £"4, 5, 23 7. Настоящая работа продолжает эти исследования для дисциплины случайного выбора.

Вопросы изучения отдельных характеристик СМО со случайным выбором рассматривались ранее /~14,22, 25-28/. Морз Ф. исследовал и 1рафически проиллюстрировал зависимость распределения времени ожидания заявки в системе И|М | П> от дисциплины обслуживания.

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

F (wb)(B (v*))

UHS ^ y ( FIFO J ~~ ЕТ0Р0И момент времени ожидания заяЕки в системе со случайным Еыбором (прямым порядком выбора) на обслуживание зая-еок из очереди,^ - загрузка системы.

Кингман /~257 рассмотрел дисциплину случайного Еыбора для произвольного распределения длительности обслуживания и получил интегральное уравнение для преобразования Лапласа-Стилтьеса функции распределения Бремени ожидания заявки в системе. Он доказал теорему, позволяющую получать оценки снизу для моментов Бремени ожидания.

Кингман /~267 также изучал Елияние дисциплины обслуживания на дисперсию Бремени ожидания и привел оценки, показывающие, что дисперсия Бремени ожидания при случайном выборе на обслуживание заявок из очереди больше, чем при прямом порядке обслуживания.

Коэн Z~227 указал способ получения моментоЕ виртуального времени ожидания заявки б системе И J Q- 1 со случайным Еыбором на обслуживание заявок из очереди и привел явные выражения для первого и второго моментов.

Спирн </"~29j7 рассматривал случайный выбор на обслуживание в узле марковской- сети массового обслуживания. Даниелян /"237,

Саакян (/"17-7исследовали распределение виртуального Бремени ожидания б приоритетной системе M^|Q-x|l 00 в предположении, что заяЕки каждого приоритетного класса обслуживаются в соотвеоствии с дисциплиной случайного Еыбора.

В настоящей работе исследуется совместное стационарное распре9 деление характеристик некоторых однолинейных СГО со случайным Еыбором и произвольной функцией распределения Бремени обслуживания заявки5и определяются стационарные характеристики этих систем до

Еторого момента, Еключая и смешанные моменты второго порядка.

При исследовании СИО обычно применяются метода: теории цепей Маркова 12, 30J7, цроцессов восстановления, регенерирующих и полурегенерирущих цроцессов Z""9>12,13,21J и т.д. В указанных работах по исследованию СМО со случайным выбором применяются методы дифференциально-разностных уравнений /"25,27,287, исследования цроцесса на периоде занятости Z"237, методы статистического среднего C&J и локального баланса Z"~297. в данной работе важное значение для анализа систем имеет предельная теорема для полурегенерирущих процессов Z~97, которая о процессе в установившемся режиме позволяет судить по его поведению на цикле регенерации. Благодаря используемым методам удается получить явные выражения и алгоритмы для определения совместных расцределений исследуемых характеристик в виде цроизводящих функций и преобразований Лапласа-Стилтьеса. Для числовых характеристик приводятся явные формулы.

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

В главе I рассматривается фундаментальная система М (J 'I со случайным выбором на обслуживание заявок из очереди. Это означает, что если в очереди tb заявок, то любая принимается на обслуживание первой с вероятностью \/хъ . Для этой системы получена совместная производящая функция и преобразование Лапласа-Стил-тьеса стационарного распределения длины очереди и функции распределения (ф.р.) виртуального времени цребывания заявки в системе, а также первые два момента этих случайных величин и их кова-риация.

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

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

Система с ограниченным размером пакета и групповым обслуживанием рассматривалась японскими математиками Т.Осоной и Т.Фуд-зиявой. В работе £~3 О J определена длина очереди для этой системы. В главе 3 рассмотрена аналогичная система с пакетным обслуживанием: на один прибор поступает пуассоновский поток заявок; заявки обслуживаются пакетами, размер которых не может превышать 171; внутри пакета заявки на обслуживание выбираются случайным образом. Получены совместное распределение и моменты второго порядка для следующих характеристик системы: длины очереди; длины очереди перед началом обслуживания пакета; размера пакета; виртуального времени пребывания заявки в системе. На основе полученных характеристик исследованных систем и систем, аналогичных им с прямым и инверсионным порядком обслуживания, составлен и отлажен комплекс подпрограмм на ФОРтРАНе. Тексты программ прилагаются. Были выполнены расчеты при различных значениях параметров в зависимости от загрузок систем,и был проведен сравнительный анализ систем при порядках обслуживания случайного выбора (R$ ) , прямого (FX F(D) и обратного (L/IF0).

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

Предельная теорема для полурегенерирующих процессов.

Определение. Циклом длительности Ъ называется упорядоченная пара 1)> где ^ -неотрицательное действительное (случайное) число, а £ - случайная функция, определенная на [0,ъ) и принимающая значения в измеримом пространстве ( X, В ) ♦

Рассмотрим последовательность циклов и образуем новый процесс

Рассмотрим еще последовательность 4 , г случайных величин, принимающих значения из дискретного множества £ , и сбудем считать, что последовательность | Ъ^, связана следующим цредположением : 04t<Zn,, n-Z-oJ П1. Последовательность {связайа однородной марковской зависимостью вида

В этом случае цроцесс £ £ ^ взывается полумарковским.

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

Р(ъ*-н , (f) 6 6 = L0, Щ+.-.+ Япгх)'' P(*n,+4 U+iffiSl^l) не зависит от П . В случае выполнения этого условия процесс j £ , }■. называется полурегенерирущим.

Нас интересуют условия существования цредела

Jim, Р , t&^Z} и способ его нахождения. Положим yij^ (у) (у, В) = Р (ZftH >jf, ZnTfl

Определим набор функций F =|F ij, J :

Fty fx) = P ( % n>+1 = f,

Кроме того, предположим, что

П2. Вложенная цепь п., Oj с матрицей переходных вероятностей Р= | ру, • L}js € В]г неприводима и возвратна. ПЗ. Существует пара состояний to и J,0 из Н , таких что

Р i.,/0 > 0. Л и ,/>о) < ' - где л ^ fy (x)/F$ (+ -).

П4. Оуществует пара состояний 9 ^ такая, что рц ^ >0 и распределение Лц^ нерешётчатое.

Мы регулярно будем пользоваться следующим утверждением: Теорема Если выполнены предположения

П1 - П4 и функция Jij (■-b 9 Е>) по ~t интегрируема по Риману на каждом конечном промежутке и О < ufj ( си у есть среднее время пребывания системы в состоянии ^ до перехода в следующее состояние), тогда

В случае, если у вложенной цепи ^ 5ft ? Я- ^0 j существует стационарное расцределение, где [щ] , Z 1 , - стационарное расцределение вложенной ^цепи ^ ? ti-^Oj •

Нумерация теорем и лемм в настоящей работе едана.

При анализе всех систем для функции распределения (ф.р.) времени обслуживания одной заявки В ft) :

3(1) = S~е~ ** cf& ft) , £e 5 >0 ; pi = ,

1. Беляев К.П. Пакетная обработка заявок в системе типас относительным приоритетом и разделением процессора. Вестн. Моск. ун-та. Сер. Вычислительная математика и кибернетика, 1981, № 2, с. 29-33.

2. Боровков А.А. Вероятностные цроцеесыв теории массового обслуживания. М., Наука, 1972, 367 с.

3. Боровков А.А. Теория вероятностей. -М., Наука, 1976, 352 с.

4. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. М., М1У, 1973, 447 с.

5. Джейсуол Н.К. Очереди с приоритетами. М., Мир, 1973, 279 с.

6. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. М., Высшая школа, 1982, 256 с.

7. Ивченко Г.И., Каштанов В.А. Теория массового обслуживания.- Московский институт электронного машиностроения,1975,244 с.

8. Клейнрок Л. Вычислительные системы с очередями. М., Мир, 1979, 600 с.

9. Климов Г.П. Теория вероятностей и математическая статистика. -М., Мир, 1983, 328 с.

10. Климов Г.П. Стохастические системы обслуживания. M.f Наука, 1966, 243 с.

11. Климов Г.П., Мишкой Г.К. Приоритетные системы обслуживания с ориентацией. М., МГУ, 1979, 222 с.

12. Климов Г.П., Ляху А.К., Матвеев В.Ф. Математические модели систем с разделением времени. Кишинев, Штиница, 1983, НО с.

13. Кокс Д.Р., Смит В.Л. Теория восстановления: Пер. с англ. (под ред. Беляева Ю.К. М., Сов.радио, 1967, 299 е.).Конвей Р.В., Максвелл В.П., Миллер Л .В. Теория расписаний.- М., Наука, 1975, 359 с.

14. Матвеев В.Ф., ХаритонцеЕа И.Г. Исследование стационарных характеристик в системе со случайным выбором на обслуживание внутри пакета. Вестн. Моск. ун-та, Сер. Вычислительная математика и кибернетика, 1982, Ш% с. 51-55.

15. Прудников А.П., Брычков Ю.А., Маричев О .И. Интегралы и ряды.- М., Наука, 1983, 800 с.

16. Саакян В.Г. Предельные теоремы в приоритетных моделях при дисцйпли-. не случайного .выбора.-Молодой научный-работник.Ерев.ун-т,1982,о14-2

17. ХаритонцеЕа И.Г. Дисциплина случайного Еыбора в системе MjO-jl.- Вестн. Моск. ун-та. Сер. Вычислительная математика и кибер-. нетика, 1984,.М, с.60-63.

18. ХаритонцеЕа И.Г. Дисциплина случайного выбора в некоторых системах массового обслуживания. Тезисы докладов 1У Всесоюзной конференции "Применение вероятностно-статистических методоЕ вбурении и нефтедобыче". Баку, 1984, с.5-7.

19. Харитонцева И.Г. Исследование стационарных характеристик в системе со случайным выбором на обслуживание. Методы решения за-, дач математической физики и их программное обеспечение, М., MU,1984, е.55-57. .

20. Феллер В.Введение в теорию вероятностей и ее приложения. Т.2.- М., Мир, 1967, 752 с.

21. Cohen J.W. The Single Server Queue. Hew York, Wiley, 1969,427-451.

22. Danielian E.A. On ES discipline in some H^ 0*г ^ 00 Priority Queues.- Proc. of the System Research. Vienna, Austria, 1980, p. 405-411.

23. Klimov G.P., Nagapet^an R., Smirnov S.N. Regenerative processes with Markov's dependent cycles. Math. Operation-forsch. Statist. Ser. Optimization, 1982, 12, N2, p.287-297.

24. Kingman J.P.O. On queues in which custumers are served in random order.- Proceeding Cambridge Philosofical Society, 58(86), 1962, p.79-91.

25. Kingman J.F.G. The effect of queue discipline 011 waiting time variance.- Proceeding Cambridge Philisofical Society, 58(86), 1962, p.165-164.

26. Morse P.Li. Queues, inventories and maintenanse.- New York, John Wiley, 1958, p.II6-I2I.

27. Riordan J. Stochastic Service System.- New York, John Wiley, 1962 ( M., Сб*5Ь, с. 159-148 ).

28. Spirn J.R. Qeueing Networks with Random Selection for Service. Transactions on Software engeneering, 1979» vol. SE-5, N5,p. 287-289.

29. Tadashi Osone, Takehisa Fudjuawa. On the Queueing Systemf^j Q-1" ^ i with Maximum Batch size M.- Rep. Univ. Electro-Comm., 50-2, 1980, p.225-251.