Приоритетные модели с гиперэкспоненциальными потоками тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Ушаков, Андрей Владимирович

• Ушаков, Андрей Владимирович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Ушаков, Андрей Владимирович

Содержание

Введение

1 Описание модели

1.1. Гиперэкспоненциальный поток

1.2. Дисциплины обслуживания

1.3. Вероятностно-временные характеристики

2 Длина очереди в системе с абсолютным приоритетом

2.1. Описание системы

2.2. Основные обозначения и определения

2.3. Предварительные результаты

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

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

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

3.1. Описание системы

3.2. Основные обозначения и определения

3.3. Вспомогательные результаты

3.4. Основные результаты

Я

4 Предельное распределение виртуального времени ожида-

ния в условиях критической загрузки

4.1. Описание системы

4.2. Основные обозначения и предположения

4.3. Предварительные результаты

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

4.5. Предельная теорема при условии существования моментов длительностей обслуживания порядка 1<7<2

Список литературы

Введение диссертации (часть автореферата) на тему «Приоритетные модели с гиперэкспоненциальными потоками»

Введение

Актуальность темы. Математическая теория массового обслуживания нашла широкое применение при моделировании работы многих реальных систем: ннфотелекоммуникационных, вычислительных, систем транспорта и т.п. Усложнение структуры анализируемых систем, повышение требований к адекватности их описания и точности моделирования приводит к необходимости учета в модели массового обслуживания многих дополнительных факторов. Одним из таких факторов является неравноправие поступающих в систему требований. По разным причинам требования могут иметь разную степень важности, для реализации которой необходимо организовать работу системы таким образом, чтобы улучшить показатели обслуживания одних требований за счет ухудшения показателей других. Этого можно достичь введением различных систем приоритетов.

Первые работы, в которых был проведен содержательный математический анализ характеристик систем массового обслуживания с приоритетами, появились в конце 50-х, начале 60-х годов XX века ([42, 50, 51, 52, 57, 58, 59, 61, 63, 70]). В них рассматривались либо одноканаль-ные системы с пуассоновскими входящими потоками, либо марковские системы с относительным и абсолютным приоритетом с дообслуживани-

см прерванного требования. В дальнейших исследованиях наибольшее внимание было уделено именно однолинейным приоритетным системам с пуассоновскими входящими потоками. К концу 60-х, началу 70-х годов была создана стройная теория таких систем и появились две монографии ([7, 16]), в которых были систематизированы и обобщены исследования в этом направлении. Методы, используемые в этих монографиях, содержат общие идеи: введение вспомогательных дополнительных компонент к исследуемому случайному процессу так, чтобы расширенный процесс стал марковским и использование регенерирующих свойств полученного процесса. Второе свойство позволяет свести изучение процесса на всей временной оси к его изучению на системе вложенных промежутках занятости различных типов, во время которых обслуживаются только требования определенных приоритетов. В результате исследование процесса (например длины очереди) сводится к изучению аналогичного процесса в системе с меньшим числом приоритетных классов и, в конце концов, к системе без приоритетов. Основное отличие методов в этих монографиях состоит в том, что в [16] выводятся системы дифференциальных уравнений в частных производных для распределения исследуемого процесса, которые затем решаются с помощью различных интегральных преобразований (производящих функций, преобразований Лапласа и Лапласа-Стилтьеса). В |7] используется вероятностная трактовка указанных интегральных преобразований и преобразования искомых распределений находятся из вероятностных соображений без составления промежуточных дифференциальных уравнений. В дальнейшем этот метод был усовершенствован и применен к анализу широкого класса однолинейных

систем с пуассоновскимн входящими потоками и различными приоритетными дисциплинами. При всех достоинствах указанного метода ему присущи и существенные недостатки:

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

2) этот метод не применим для ряда важных приоритетных дисциплин, для которых нарушается регенерирующая структура процессов обслуживания. В частности, к таким дисциплинам относятся дисциплина приоритета более длинной очереди (см. [45]), дисциплина случайного выбора очереди и др;

3) и, главное, возникают серьезные затруднения с распространением этого метода на системы с неиуассоновскими входящими потоками (см., например, [60, 64, 65, 66, 21, 22]).

В конце 70-х годов появились работы ]9, 20, 34, 35, 36], в которых метод дополнительных компонент был модифицирован для анализа приоритетных систем с эрланговскими и гнперэкспоненциальными потоками. В 90-х годах этот метод был еще более усовершенствован и применен при исследовании систем с рекуррентными потоками ([39, 40, 73]). Однако этим методом удавалось исследовать только распределение длины очереди (и частично периода занятости) в двух разновидностях приоритетных дисциплин без прерывания обслуживания: относительный приоритет и

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

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

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

1) первый метод состоит в использовании общих предельных теорем для функцноналов от сумм случайных величин (см. [4, 25, 49, 55, 56]). Чтобы использовать этот метод необходимо представить изучаемый случайный процесс как функционал от суммы случайных величин с достаточно хорошими свойствами. Для рассматриваемых

в диссертации систем обслуживания для длины очереди и виртуального времени ожидания такого представления пока получить не удалось;

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

3) третий метод (который и использован в данной работе) заключается в использовании информации о допредельном распределении изучаемой характеристики. Для рассматриваемых в диссертации систем обслуживания допредельное распределение виртуального времени ожидания задается через преобразования Лапласа и Лапласа-Стилтьеса, поэтому для нахождения предельного распределения используется модификация метода характеристических функций. Его применение сводится к изучению асимптотики решений систем функциональных и интегральных уравнений. Ранее для различных классов однолинейных приоритетных систем такой метод использовался в работах [1, 2, 10, 11, 12, 14, 15, 18, 19, 26, 27]).

Объект исследования. Объектом исследования являются однока-нальные системы массового обслуживания с неограниченным числом

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

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

Задачи диссертационной работы Для достижения поставленной цели необходимо решение следующих задач:

1) разработка методов анализа систем массового обслуживания с гиперэкспоненциальным входящим потоком и различными разновидностями абсолютного приоритета;

2) изучение основных характеристик приоритетных систем массового обслуживания: вектора длин очередей из требований каждого приоритета, виртуальных времен ожидания начала обслуживания, различных промежутков занятости системы;

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

4) разработка алгоритмов и программ численного расчета характеристик анализируемой системы при конкретных числовых значениях ее параметров.

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

1) различные методы теории вероятностей и теории случайных процессов: методы теории марковских процессов, метод дополнительных компонент при исследовании немарковских процессов, метод характеристических функций;

2) методы теории функций комплексного переменного и функционального анализа;

3) методы линейной алгебры;

4) методы теории дифференциальных и интегральных уравнений, в том числе асимптотического анализа решений этих уравнений.

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

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

2) найдены преобразования Лапласа-Стилтьеса длительностей различных промежутков занятости системы с относительным приоритетом;

3) найдено преобразование Лапласа виртуального времени ожидания начала обслуживания в нестационарном режиме в системе с относительным приоритетом и двумя дисциплинами обслуживания тре-

бованпй одного приоритета: FIFO (прямой порядок обслуживания) и LIFO (инверсионный порядок обслуживания);

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

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

Апробация работы. Результаты работы докладывались и обсуждались на научно-исследовательских семинарах "Теория риска и смежные вопросы "(факультет ВМК МГУ им. М.В. Ломоносова), "Аналитические методы в теории массового обслуживания11 (факультет ВМК МГУ им. М.В. Ломоносова), XXIX и XXX (2011, 2012 гг.) международных семинарах по проблемам устойчивости стохастических моделей, на V и VI (2011, 2012 гг.) международных рабочих семинарах "Прикладные задачи теории вероятностей и математической статистики, связанные с моделированием информационных систем11.

Публикации. Результаты диссертации опубликованы в семи работах [29]—[33], [71], [72], из них первые пять - в журналах, входящих в список

ВАК "Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени доктора и кандидата наук".

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

Список литературы диссертационного исследования кандидат физико-математических наук Ушаков, Андрей Владимирович, 2013 год

Список литературы

[1] Азларов Т.А., Хусаинов Я.М. Предельные теоремы для систем обслуживания с абсолютным приоритетом в условиях большой загрузки. Известия АН Узб. ССР, сер. физ.-мат. наук, 1974, № 6, с. 53-55.

[2] Акбулатов H.A., Ушаков В.Г. Одна предельная теорема для длины очереди системы с чередованием приоритетов при критической загрузке. В сб. Случайный анализ, М., МГУ, 1987, с. 3-7.

[3] Белокуров Д.В., Ушаков В.Г. О виртуальном времени ожидания в системах обслуживания с абсолютным приоритетом. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 1986, № 1, с. 67-70.

[4] Боровков A.A. Вероятностные процессы в теории массового обслуживания. М., Наука, 1972, 367 с.

[5] Боровков A.A. Асимптотические методы в теории массового обслуживания. М., Наука, 1979, 357 с.

[6] Бочаров П.П., Печинкин A.B. Теория массового обслуживания. М., Изд-во РУДН, 1995, 529 с.

[7] Гнеденко Б.В. и др. Приоритетные системы обслуживания. М., изд-во Моск. ун-та, 1973, 448 с.

[8] Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М., Наука, 1987, 336 с.

[9] Даниелян Э.А.,Ушаков В.Г. О длине очереди системы ^|G|l|oo. Доклады АН Арм. ССР, 1977, т. LXV, № 4, с. 193-198.

[10] Даниелян Э.А. Предельные теоремы для времен ожидания одно-канальных приоритетных систем. Доклады АН Арм. ССР, 1980, т. LXXI, № 3, с. 129-135.

[11] Даниелян Э.А. Описание одного класса предельных распределений в одноканальных приоритетных системах. Теория массового обслуживания. М., ВНИИСИ, 1981, с. 48-52.

[12] Даниелян Э.А. К асимптотике периода занятости и времени ожидания приоритетных систем Mr\G г\1\оо при критической загрузке. Изв. АН Арм. ССР, Математика, 1975, т. X, № 3, с. 272-287.

[13] Даниелян Э.А. Дисциплины FIFO, LIFO, RS в системах AIr I Gr 111 oo с относительными и абсолютными приоритетами. Изв. АН Узб. ССР, сер. физ.-мат. наук, 1981, № 5, с. 9-14.

[14] Даниелян Э.А., Земляной Н.С. К асимптотике длины очереди систем Mr\G г\1\оо в условиях критической загрузки. Доклады АН Арм. ССР, 1978, т. LXVI, № 4, с. 193-196.

[15] Даниелян Э.А. Одна многомерная предельная теорема для приоритетных систем G/r|Gr|l|oo. В сб. Теория вероятностей и математическая статистика, Ереван, 1981, с. 105-118.

[16] Джейсуол Н.К. Очереди с приоритетами. М., Мир, 1973, 280 с.

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

[18] Кожевин Д.А., Ушаков В.Г. О предельном распределении длины очереди в СМО с относительным приоритетом при критической загрузке. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 1988, № 2, с. 43-47.

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

[20] Матвеев В.Ф., Ушаков В.Г. Системы массового обслуживания. М., изд-во Моск. ун-та, 1984, 240 с.

[21] Погосян И.А. Двухприоритетная система массового обслуживания .Еп|(?|1| с ожиданием. Кибернетика, 1973, № 5, с. 64-66.

[22] Погосян И.А., Клименко А.И. Однолинейная система Ek\G\l\ с относительным приоритетом и ограничением на время ожидания. Кибернетика, 1974, № 5, с. 76-79.

[23] Попов В.А., Литвинов М.Л., Литвинов А.Л. Исследование системы массового обслуживания с гиперэкспоненциальным входным потоком и эрланговским распределением времени обслуживания. Ав-томатизир. системы управл. и приборы автоматиз. Респ. межвед. темат. сб., 1975Б в. 34, с. 165-168.

[24] Попов В.А., Литвинов M.JL, Литвинов А.Л. Анализ системы обслуживания при входном потоке требований с гиперэкспоненциальным распределением. Проблемы передачи информации, 1977, № 1, с. 97™ 102.

[25] Прохоров Ю.В. Переходные явления в процессах массового обслуживания. Литовский математический сборник, 1963, т. 3, № 1, с. 199-206.

[26] Савенков Т.Ю. Предельные распределения вектора длин очередей при критической загрузке для СМО с чередованием приоритетов. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 2002, № 3, с. 46-49.

[27] Савенков Т.Ю. Предельные теоремы для характеристик систем массового обслуживания с пакетной обработкой требований. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 2003, № 3, с. 42-45.

[28] Симонян А.Р. Новое представление многомерных предельных законов в модели M|G|l|oo. В сб. Вероятность и оптимизация, Ереван, 1991, с. 77-94.

[29] Ушаков A.B. О виртуальном времени ожидания в системе с относительным приоритетом и гиперэкспоненциальным входящим потоком. Информатика и ее применения, 2012, т. 6, вып.1, с. 2-6.

[30] Ушаков A.B. Анализ системы обслуживания с гиперэкспоненциальным входящим потоком в условиях критической загрузки. Информатика и ее применения, 2012, т. 6, вып.З, с. 117-121.

[31] Ушаков A.B. О длине очереди в системе HM\G\\\oo с абсолютным приоритетом и потерей прерванного требования. Вестник Тв-ГУ. Прикл. мат., 2012, вып. 32 , с. 7-15.

[32] Ушаков A.B., Ушаков В.Г. О длине очереди в системе с абсолютным приоритетом и гнперэкспоненциальным входящим потоком. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 2012, К® 1, с. 27-34.

[33] Ушаков A.B., Ушаков В.Г. Предельное распределение времени ожидания при критической загрузке в системе с относительным приоритетом. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 2012, № 4, с. 11-16.

[34] Ушаков В.Г. Приоритетная система обслуживания с неординарным эрланговским входящим потоком и обратной связью. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 1977, № 2, с. 82-88.

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

[36] Ушаков В.Г. Однолинейная система обслуживания с относительным приоритетом. Известия АН СССР. Техн. кибер. 1978, № 1, с. 76-80.

[37] Ушаков В.Г., Харитонцев Е.Г. Оценки скорости сходимости в некоторых предельных теоремах для приоритетных СМО. В сб. Случайный анализ, М., МГУ, 1987, с. 121-129.

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

[39] Ушаков В.Г. Аналитические методы анализа системы массового обслуживания G/|G>|ljoo с относительным приоритетом. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 1993, № 4, с. 57-69.

[40] Ушаков В.Г. О длине очереди в однолинейной системе массового обслуживания с чередованием приоритетов. Вестник Моск. ун-та. Сер. 15, Вычисл. матем. и киберн., 1994, № 2, с. 29-36.

[41] Abate J., Whitt W. Asymptotics for M|G|1 low-priority waiting-time tail probabilities. Queueing Systems, 1997, v. 25, p. 173-233.

[42] Cobham A. Priority assigment in waiting line problems. Operat. Res., 1954, v. 2, p. 70-76.

[43] Cohen J.W. The single server queue. North Holland, Amsterdam, 1982.

[44] Cohen J.W. On the M\G\2 queuing model. Stoch. Process. Appl., 1982, v. 12, p. 231-248.

[45] Cohen J.W. A two-queue, one-server model with priority for the longer queue. Queueing Systems, 1987, v. 2, p. 261-283.

[46] Cox D.R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables. Proc. Cambridge Phil. Soc., 1955, v. 51, p. 433-441.

[47] Cox D.R. A use of complex probabilities in the theory of stochastic processes. Proc. Cambridge Phil. Soc., 1955, v. 51, p. 313-319.

[48] Iravani F., Balcioglu B. On priority queues with impatient customers. Queueing Systems, 2008, v. 58, p. 239-260.

|49] Harrison J.M. The heavy traffic approximation for single server queues in series. J. Appl. Prob., 1973, v. 10, № 3, p. 613-629.

[50] Heathcote C.R. The time-depended problem for a queue with preemptive priorities. Operat. Res., 1959, v. 7, p. 670-680.

[51] Heathcote C.R. A single queue with several preemptive priority classes. Operat. Res., 1960, v. 8, p. 630-638.

[52] Heathcote C.R. Preemptive priority queuing. Biometrika, 1961, v. 48, p. 57-63.

[53] Hokstad P. A supplementary variable technique applied to the M\G\1 queue. Scfnd. J. Statist, 1975, № 2, p. 95-98.

[54] Hooke J.A. A priority queue with low-priority arrivals general. Operat. Res., 1972, v. 20, p. 373-380.

[55] Hooke J.A. Some heavy-traffic limit theorems for a priority queue with general arrivals. Operat. Res., 1972, v. 20, p. 381-388.

[56] Hooke J.A., Prabhu N.U. Priority queues in heavy traffic. Opsearch, 1971, v. 8, p. 1-9.

[57] Jackson J.R. Queues with dynamic priority discipline. Manag. Sci, 1961, v. 8, p. 18-34.

[58] Jaiswal N.K. Preemptive resume priority queue. Operat. Res., 1961, v. 9, p. 732-742.

[59] Jaiswal N.K. Time-dependent solution of the head-of-the-line priority queue. J. Roy. Stat. Soc.,Series B, 1962, v. 24, p. 91-101.

[60] Jaiswal N.K., Thiruvengadam K. Preemptive resume priority queue with Erlangian inputs. Indian. J. Math., 1962, v. 4, p. 53-70.

[61] Kesten H., Runnenberg J. Priority in waiting-line problems I and II. Nederl. Akad. Wetensch. Proc., Series A, 1957, v. 60, p. 312-336.

[62] Maertens T., Walraevens J., Bruneel H. Priority queueing systems: from probability generating functions to tail probabilities. Queueing Systems, 2007, v. 55, p. 27-39.

[63] Miller R. G. Priority queues. Ann. Math. Statist,., 1960, v. 31, p. 86103.

[64] Schassberger R. On the work load process in a general preemptive resume priority queue. J. Appl. Prob., 1972, v. 9, p. 588-603.

[65] Schassberger R. Basic analysis of a head-of-the-line priority queue with renewal type input. J. Appl. Prob., 1975, v. 12, p. 346-352.

[66] Schassberger R. A broad analysis of single server priority queues with two independent input streams, one of them Poisson. Adv. Appl. Prob., 1974, v. 6, p. 666-688.

[67] Schassberger R. On the waiting time in the queueing system G|G|1. Ann. Math.Statist. v. 41, p. 182-187.

[68] Stanford D.A., Drekic S. Interdeparture time distributions in EiMi/Gi/1 priority queues. Queueing Systems, 2000, v. 36, p. 1-21.

[69] Subramanian V., Srikant R. Tail probabilities of low-priority waiting times and queue lengths in MAP\GI\l queues. Queueing Systems, 2000, v. 34, p. 215-236.

[70] Takacs L. Priority queues. Operat. Res., 1964, v. 12, p. 63-74.

[71] Ushakov A.V. The heavy traffic limiting distribution of the waiting time in a priority queue with hyperexponential input stream. XXX International seminar on stability problems for stochastic models, Book of abstracts, Moscow, Institute of Informatics Problems, 2012, p. 93-94.

[72] Ushakov A.V.,Ushakov V.G. On a queue length in queueing system with preemptive loss priority. XXIX International seminar on stability problems for stochastic models, Book of abstracts, Moscow, Institute of Informatics Problems, 2011, p. 88-89.

[73] Ushakov V.G. Some results for the queuing system GIr\GIr\l\oo with relative priority. J. of math, sciences, 1995, v. 76, p. 2202-2207.