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

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

КОРОТЫШЕВА Анна Владимировна

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Вологда - 2014

13 НАР 2014

005545871

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

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

Зейфман Александр Израилевич, зав. кафедрой прикладной математики Вологодского государственного педагогического университета

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

Морозов Евсей Викторович,

ведущий научный сотрудник лаборатории математической кибернетики Института прикладных математических исследований Карельского научного центра Российской академии наук

кандидат физико-математических паук Горшенин Андрей Константинович, старший научный сотрудник Института

проблем информатики Российской академии наук (ИЛИ РАН)

Ведущая организация: Московский государственный университет им. М.В.Ломоносова, факультет ВМК

Защита диссертации состоится 25 апреля 2014 г. в 15 час. 30 мпн. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: Москва, ул. Орджоникидзе, дом 3, ауд. 110.

С диссертацией можно ознакомиться в научной библиотеке РУДН по адресу: 117198 Москва, ул. Миклухо-Маклая, дом 6 (отзывы па автореферат просьба направлять по указанному адресу) и на официальном сайте диссоветов РУДН но адресу: www.dissovet.rudn.ru. Автореферат разослан < > марта 2014 года.

Ученый секретарь диссертационного совета

М.Б. Фомин

Общая характеристика работы

Актуальность темы. В исследовании современных телекоммуникационных систем огромную роль играют методы н модели теории массового обслуживания.

Первые работы, относящиеся к такого рода тематике, были проведены А. К. Эрлангом в начале прошлого века. Примерно в 50-е годы двадцатого века выяснилось, что задачи, связанные с обслуживанием больших массивов однородных требований, возникают во многих областях естествознания и техники, и была создана так называемая теория массового обслуживания (англоязычный термин - теория очередей), являющаяся с тех пор активно развивающимся разделом прикладной теории вероятностей.

Существенный вклад в развитие этой области внесли российские и зарубежные ученые В. В. Анисимов, Л. Г. Афанасьева, Г. П. Башарии, А. А. Боровков, П. П. Бочаров, Р. Л. Добрушин, Б. В. Гнеденко, А.Н. Дудин, А. И. Зейфман, В. В. Калашников, Н. В. Карташов, Е. В. Морозов, А. В. Печинкин, В. В. Рыков, И. А. Соколов, С. Г. Фосс, Е. Van Doom, М. Neuts, R.L. Tweedie, W. Whitt и многие другие.

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

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

Анисимов В.В. Оценки отклонений переходных характеристик неоднородных марковских процессов // Укр.матж.ж.. - 1988. - 40. - с. 699-706

достаточно затруднительно. Для процессов со счетным числом состояний аналогичные результаты в терминах инфинитезнмальных характеристик были получены А.И. Зейфманом2.

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

В работах А. И. Зейфмана начато систематическое исследование свойств типа эргодичности и устойчивости для неоднородных марковских цепей с непрерывным временем и приложение этих результатов к моделям массового обслуживания, описываемым процессами рождения и гибели4.

В последние годы, с одной стороны, А. 10. Митрофановым5 были улучшены оценки устойчивости для равномерно эргодичных однородных марковских цепей, а с другой, удалось расширить класс исследуемых марковских моделей6, в связи с чем на настоящем этапе весьма актуальной стала задача построения оценок устойчивости для новых классов моделей и применение этих оценок для построения предельных характеристик конкретных систем массового обслуживания, в том числе с катастрофами и с групповым поступлением и обслуживанием требований.

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

zZeifman A. I. Stability for contionuous-time nonhomogeneous Markov chains // Lect. Notes Math.. - 1155. -1985. - p. 401-414

3Kartashov N. V. Strong stable Markov chains. Kiev: Utrecht, VSP, TBiMC, 1996

4Zeiiinan A. I. Upper and lower bounds on the rate of convergence for nonhomogeneous birth and death processes // Stoch. Proc. Appl.. - 1995. - 59. - p. 157-173; Зейфман А. И., Бенинг В. E., Соколов И. A. Марковские цепи и модели с непрерывным временем. М.: Элекс-КМ, 2008

5Mitrophanov, A.Yu. Stability and exponential convergence of continuous-time Markov chains // J. Appl. Prob. - 2003. - 40. - p. 970-979

6Сатин Я.А., Зейфман А.И., Коротышева A.B., Шоргип С.Я. Об одном классе марковских систем обслуживания // Информатика и ее применения. - 2011. - 5. - N4. - с. 6-12

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

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

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

- получены условия слабой эргодичности и оценки устойчивости для системы А^/А'/[/£' с катастрофами;

- получены оценки устойчивости и улучшены оценки скорости сходимости для систем обслуживания М4/М(/Лг/М и А^/Л^/ЛГ/ЛГ + Д;

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

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

Методы исследований. Для решения поставленных задач используется эволюционный оператор (оператор Коши) и генеральный показатель дифференциального уравнения в банаховом пространстве, и методы их оценки. Проблемы вычисления искомых параметров сводятся к изучению дифференциальных уравнений на множестве стохастических векторов. В этом случае возникают проблемы, связанные с получением явных оценок генерального показателя. Для получения этих оценок используется логарифмическая норма оператора, понятие которой введено у Лозинского, а для операторов в банаховом пространстве изучено Далецким и Крейном. Научная новизна.

- в случае равномерной эргодичности (напр., см. теоремы 8, 9, 10) получена оценка устойчивости, в которой множитель ЛГ, имеющий порядок размерности системы, заменен на 1п Ж;

- на основании полученных оценок исследованы системы обслуживания с катастрофами типа М(/М(/ЛГ//\Г и А^/Мь/М/М + Я, для близких к которым сложных систем найдены предельные характеристики ;

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

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

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

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

Результаты, выносимые на защиту.

1. Получены общие оценки устойчивости нестационарных марковских систем обслуживания с катастрофами.

2. На основании общего подхода получены оценки устойчивости систем обслу-

жнвания Mi/Mi/S с катастрофами.

3. Получены оценки устойчивости для систем обслуживания Mt/Mt/N/N и Mt/Mt/N/N +R.

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

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

Апробация работы. Результаты работы докладывались на: семинарах кафедры прикладной математики ВГПУ "Стохастические модели сложных систем" (2009-2013), IV ежегодных смотрах-сессиях аспирантов и молодых ученых по отраслям наук (Вологда, 2010), международной летней конференции по вероятности и статистике (Болгария, Созополь, 2010), International Conference on Ultra Modern Telecommunications (Москва, 2010), 5th International ICST Conference on Performance Evaluation Methodologies and Tools (South of Paris, France, May 16-20, 2011), международной конференции, посвященной 110-той годовщине И.Г. Петровского (Москва, 2011), международной научной конференции "Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей"(Queues: Flows, Systems, Networks, Минск, Беларусь, 2011), международной конференции "Теория вероятностей и ее приложения"(Москва, 2012), международной конференции "Современная стохастика: теория и применения III" (Modern Stochastics: Theory and Applications III, Киев, Украина, 2012), XXIX международном семинаре по проблемам устойчивости стохастических моделей (Светлогорск, 2012), международной научной конференции "Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных ceTei1"(Queues: Flows, Systems, Networks, Минск, Беларусь, 2013).

Публикации автора. Основные результаты опубликованы в [1]-[17], в том числе работы [1]-[8] - в журналах, рекомендуемых ВАК. В работах, опубликованных в соавторстве, соискателю принадлежат следующие результаты: формулировки и доказательства результатов, относящихся к устойчивости; исследование конкретных систем и построение их предельных характеристик; разработка алгоритмов и программных средств для проведения численных расчетов; численные расчеты и интерпретация полученных результатов.

Структура и объем работы. Диссертация состоит из введения, пяти глав, разбитых на параграфы, заключения, приложения, библиографического списка литературы, включающего 76 наименований, включая работы автора. Работа изложена на 146 листах машинописного текста.

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

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

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

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

Рассмотрим «возмущенный» ПРГ с катастрофами X = £ > 0, обозначая через Ап(£), Рп(0 11 <?(£) его интенсивности рождения, гибели и катастрофы

соответственно. Для простоты записи оценок будем предполагать, что возмущения «равномерно малы», то есть при всех п и почти всех /. > 0 выполняются неравенства

|ап(<)| < £1, !А„(£)1 < £2, \т\ < £3. (0.1)

Теорема 1. При совпадении начальных условий для исходного и возмущенного ПРГ с катастрофами для всех í > 0 справедлива следующая оценка

Г1 ~!((т)(1Т

1|р(0-р(«)11<2(£1+е2+ез) / е " ¿въ (0.2)

Jo

Для получения более простых оценок будем предполагать, что найдутся р 6 (0; 1) и натуральное к такие, что для всех п, í выполнено условие <

(1-рЖ*)-

Теорема 2. При совпадении начальных условий для исходного и возмущенного ПРГ с катастрофами для всех £ > 0 справедлива оценка устойчивости среднего

((&! +&2 + 4) (||р(0)||и + + кез) ^е-йКЬ+ъ-ъ—^Лг. (0.3)

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

Теорема 3. Пусть ау(4) и £¡(4) 1-периодичны. Пусть £¡(4) > £(£) при всех г >

0 и почти всех £ е [0,1] и существует положительное число в <

Тогда для любых начальных условий р(в) и р(з) процессов Х(€) и соот-

ветственно справедливо неравенство

lim||p(í)-p(i)||<^-^. (0.4)

t—*00 (7

Теорема 4. Пусть выполнены условия теоремы 3 и пусть существует возрастающая последовательность положительных чисел {c?¡} такая, что a)mfk>i(dj/k) = из > 0; b) supk(dk+i/dk) = т < оо; с)Ь — (mN - 1 )К > 0. Тогда при любых начальных условиях р(0) и р(0) справедлива следующая оценка устойчивости среднего:

-тi < u{b_ (m„ _ ^tfi* _ 1)к_т„еУ

где £(t) < К < оо.

В §3 главы 2 изучается модель системы обслуживания M(t)/M(t)/S с катастрофами в случае, когда интенсивности катастроф зависят от числа требований в системе обслуживания. Получена аппроксимация, вычислены и смоделированы предельные характеристики возмущенных процессов. Рассмотрено практическое применение результатов.

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

- интенсивности катастроф существенны при любой длине очереди;

- интенсивность обслуживания требований достаточно велика;

- достаточно велика интенсивность поступления требований, а интенсивности катастроф существенны для ситуаций, когда длина очереди (количество требований в системе) пропорционально некоторому натуральному числу.

Исследован вопрос устойчивости таких процессов в трех случаях. Случай больших катастроф.

A. Пусть существуют Q > 0 и /3 > О такие, что

e-jUWu < Qe-№-S)5 (0.6)

для любых s, i, 0 < s < t.

Теорема 5. Пусть выполнено условие A. Toada

IIP(Í) " P(í)!l < M + l-Qe^e + Qe-^||P(0) - p(0)|| (0.7)

для любых начальных условий р(0), р(0) и всех t > Случай больших интенсивностей гибели.

B. Пусть существуют 5 G (1, функция 0(1) и положительные числа R и V такие, что

Sfi(t) - 6X(t) > e(t)- е-Л'^-^'Ж«)^ < Re-"(«-»)f для любых s, t, 0 < s < t.

Теорема 6. Пусть выполнено условие В и A(¿) < М. Тогда для любых начальных условий р(0) и р(0)

(08)

C. Пусть существуют S € (1, Д], функция i>(t) и положительные числа L и и) такие, что

№ + (1 - Í-'XSMO - ÍA(Í)) > < Le-**-*,

для любых a, t, 0 < s < í. Пусть W = inffc>i y > 0.

Теорема 7. Пусть выполняется условие С. Тогда для любых начальных условий р(0) и р(0)

В главе 3 получены оценки сходимости и более простые оценки устойчивости нестационарной системы Ме/Л^/Д^/ЛГ. Вычислены и смоделированы предельные характеристики возмущенных процессов.

Теорема 8. Пусть существует последовательность положительных чисел (4,} и 0 > 0 такое, что «,(£) > (3, г = 1,2,..., IV, t > 0. Тогда справедливы следующие оценки для любых начальных условий р(0) и р(0) процессов Х{£) и Х(1) соответственно:

Цт||р(0 - р(4)|| < К Й а), (О.Ю)

¿-•оо /3

и

1157| ЕРЦ) - ЁР(Ь)\ < ^ *>, (0.11)

£-+00 Р

где б = ^ = гшп;

Также получены оценки в случае 1-периодичных интенсивностей. В главе 4 рассмотрена модель обслуживания Л^/А^/ЛУN + Я. Получены общие оценки сходимости и устойчивости и оценки устойчивости для конкретных случаев. Получена аппроксимация, вычислены и смоделированы предельные характеристики возмущенных процессов.

1). Пусть при некотором I > 1 и для любого I > 0 выполняется условие

Np.it) - /А(0 > ш > 0. (0.12)

Пусть ¿1 = 1, ^ = 1, к < N - 2, и ^ = I, к > N - 1.

10

Теорема 9. Пусть существует последовательность положительных чисе.л такая, что а,(1) >()>{), г = 1,2,..., Ы+И, Ь > 0. Тогда справедливы следующие оценки:

(->оо (1 —

(0Л4)

где С — А1 — 1 + I', для любых начальных условий р(0) и р(0) процессов

и Х(£) соответственно.

2). Пусть при некотором I < 1 выполняется условие

гА(£) - Иц{Ь) > о; > 0 (0.15)

Положим = I. к > 1.

Ль > —

Теорема 10. Пусть существует последовательность положительных чисел такая, что а*(£) > 9 > 0, г = 1,2, + Я, 4 > 0. Тогда справедливы следующие оценки:

£(1 + 1п^1)

Ит|[р(£) -р(4)|| < 4 ..-(0.16)

г—»оо — 1 )Си

шп|ад-А.(01<-тг—я-(°-17)

оо г —

для любых начальных условий р(0) и р(0) процессов Х({) и Х(Ь) соответственно.

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

Рассмотрим матрицу интенсивностей

Л(0 =

(аоо(0 ¡Ф)

Ах(г) ац(«) /ц(4) М*)

А2(*) А1(0 аи(4) 1иЦ)

А3(г) А2(4) А^) азз(0

V

(0.18)

причем ай(4) = -£^=1^(0 ~ ЕГ=1Л1Й-

Пусть количество состояний системы конечно и равно г. Пусть (1 = тшккг4 С = ^ = а* = /о <*(№, М = ем°+и', где

М0 = тах|{^,|<1 а(и)<1и.

Теорема 11. Пусть Ап(£) и 1-периодичны. Для любых начальных условий р(б') к р(в) процессов Х(£) и Х(1) соответственно справедливы неравенства

Шп||р(о-р(ОН<

I—»00

е(1 + 1п^)

а*

(0.19)

Ит|ВД - Вр(()| <

ге(1 + Ь^)

а*

(0.20)

В §2 главы 5 рассмотрена система массового обслуживания, число требований в которой описывается нестационарной марковской цепью с непрерывным временем и бесконечным пространством состояний, причем требования

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

Рассмотрим "возмущенный"процесс X — { > 0, с матрицей интен-

сивностей А(Ь). Будем предполагать, что возмущения малы, то есть |]А(£) —

Мт<е.

Введем последовательность {/¿¡}. Пусть

й = Ы(1и = (0.21)

«>1 ¿>1 г

6" = зирх<;;<г и К, Ь такие, что

<1Мг) + (А + ё2)\2{1) + ... + (¿¡)ХТ{1) < к,

1<г<г

^1(Аг(<) - Аг(0) + № + <Ь)(А2(0 - А2(«)) + •■• + ( ]С - *,-)(*)) < Ье-

1<;<г

Теорема 12. Пусть существует положительная последовательность {с^} и положительные числа М, а, г такие, что й > 0, IV > 0, и

ОО ОО

с-ЦаЫ)Ли < Ме-а0-)9 = ]Г А,(0 = 0,

¿=Г+1 ¡=Г+1

для всех к и почти всех Ь > 0, Ад^) < оо. Тогда справедливы следующие оценки устойчивости:

-—/ч , ч, еМ<Ьа + 23КМ) .„

Ьш|Р(*)-Р(*)1< 1а(а_2£5) (0-22)

и

т—. . ^ я , еМ(Ьа + 2БКМ) ,„ооЧ

Ьш\ЕР{1)-Ет\< ;¥а{а_2£8) (0-23)

для любых начальных условий р(я) и р(й) для Х(£) и Х{Ь) соответственно.

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

Приложение содержит описание программы, с помощью которой проводились вычисления и построения предельных характеристик.

Основные выводы и результаты. Таким образом в работе получены следующие результаты:

1) для моделей массового обслуживания с нестационарным марковским поступлением и обслуживанием требований с N серверами и R местами ожидания (Mt/Mt/N/N + R, R > 0) в случае равномерной эргодичности (напр., см. теоремы 8, 9, 10) получена оценка устойчивости, в которой множитель N, имеющий порядок размерности системы, заменен на lniV;

2) для тех же моделей с возможностью катастроф найдены предельные характеристики ;

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

Публикации автора по теме диссертации в изданиях, рекомендованных ВАК

1 Зейфман, А.И., Коротышева, A.B., Терешина, H.A., Сатин, Я.А. О предельных характеристиках системы обслуживания M(t)/M{t)/S с катастрофами / А.И. Зейфман, A.B. Коротышева, H.A. Терешина, Я.А. Сатин // Информатика и ее применения. - 2009. - 3.- N3. - с. 16-22.

2 Зейфман, А.И., Коротышева, A.B., Сатин, Я.А., Шоргин, С.Я. Об устойчивости нестационарных систем обслуживания с катастрофами / А.И. Зейфман, A.B. Коротышева, Я.А. Сатин, С.Я. Шоргин // Информатика и ее применения. - 2010. - 4. - N3. - с. 9-15.

3 Зейфман, А.И., Коротышева, А.В., Панфилова, Т.Л., Шоргин, С.Я. Оценки устойчивости для некоторых систем обслуживания с катастрофами / А.И. Зейфман, А.В. Коротышева, Т.Л. Панфилова, С.Я. Шоргин // Информатика и ее применения. - 2011. - 5. - N3. - с. 27-33.

4 Сатин, Я.А., Зейфман, А.И., Коротышева, А.В., Шоргин, С.Я. Об одном классе марковских систем обслуживания / Я. А. Сатин, А.И. Зейфман, А.В. Коротышева, С.Я. Шоргин // Информатика и ее применения. - 2011. - 5. - N4. - с. 6-12.

5 Сатин, Я.А., Зейфман, А.И., Коротышева, А.В. О скорости сходимости и усечениях для одного класса марковских систем обслуживания / Я.А. Сатин, А.И. Зейфман, А.В. Коротышева // Теория вероятностей и ее применения. - 2012. - т. 57. - 3. - с. 611-621.

6 Zeifman, A., Korotysheva, A., Shorgin, S., Bening, V. Stability bounds for Mt/Mt/N/N + R queue / A. Zeifman, A. Korotysheva, S. Shorgin, V. Bening // Proceedings of the 5th International Conference on Performance Evaluation Methodologies and Tools 2011. - Cachan. - Paris, Prance. - May 16 - 20. - 2011.

7 Zeifman, A., Korotysheva, A. Perturbation Bounds for Mt/Mt/N Queue with Catastrophes / A. Zeifman, A.Korotysheva // Stochastic Models. - 28:1. - p. 49-62.

8 Zeifman, A., Korotysheva, A., Panfilova, Т., Satin, Ya., Shilova, G. On a Queueing Model with Group Services / A. Zeifman, A. Korotysheva, T. Panfilova, Ya. Satin, G. Shilova // Lecture Notes in Communications in Computer and Information Science. - Springer. - 2013. - p. 198-205.

Прочие публикации автора по теме диссертации

9 Коротышева, А.В. Оценки устойчивости для конкретных моделей процессов рождения и гибели с катастрофами / А.В. Коротышева // Вестник НСО ВГПУ. Выпуск VIII. - Вологда: издательство ВГПУ. - 2010. - с. 16-28.

10 Зейфман, А.И., Коротышева, А.В., Панфилова, Т.Л. Оценки устойчивости для некоторых линейных систем / А.И. Зейфман, А.В. Коротышева, Т.Л. Панфилова // Международная конференция, посвященная 110-той годовщине И.Г. Петровского. Тезисы докладов. - М.: Изд-во МГУ и ООО "ИНТУИТ.РУ". - 2011, с. 216.

11 Коротышева, А.В. Оценки устойчивости для модели Mt/Mt/N с катастрофами / А.В. Коротышева // Статистические методы оценивания и проверки гипотез: межвуз. сб. науч. тр. / Пермь: Перм. гос. нац. иссл. ун-т. -2013. - Вып. 25. - с. 132- 143.

12 Zeifman, A., Korotysheva, A., Tereshina, N. On M(t)/M(t)/S queue with catastrophes / A. Zeifman, A. Korotysheva, N. Tereshina // Proceeding of the 6-th St. Petersburg Workshop on Simulation. - 2009. - p. 79-82.

13 Zeifman, A., Korotysheva, A., Tereshina, N. On the properties of differential equations for a queueing model with catastrophes / A. Zeifman, A. Korotysheva, N. Tereshina // International Conference "Geometry in Odessa - 2009". Abstracts. - Odessa. - 2009. - p. 99.

14 Zeifman, A., Korotysheva, A., Satin, Ya. On stability for M(t)/M(t)/N/N queue / A. Zeifman, A. Korotysheva, Ya. Satin // ICUMT 2010. International Conference on Ultra Modern Telecommunications. - Moscow. - 2010. - p. 1-5.

15 Zeifman, A., Korotysheva, A., Shilova, G., Satin, Ya. Stability bounds for some queueing models / A. Zeifman, A. Korotysheva, G. Shilova, Ya. Satin //Modern Stochastics: Theory and Applications III. International conference. Abstract. -Kyiv. - 2012. - p. 69.

16 Zeifman, A., Korotysheva, A., Satin, Ya., Shilova, G., Shorgin, S. Approximations for a Class of Markovian Queueing Models / A. Zeifman, A. Korotysheva, Ya Satin, G. Shilova, S. Shorgin //VI International Workshop Applied Problems in Theory of Probabilities and Mathematical Statistics Related to Modeling of Information Systems, (Autumn Session, 2012). Abstracts. - Moscow. - IPI RAS. - 2012. - p. 82-90.

17 Zeifman, A., Korotysheva, A., Panfilova, Т., Satin, Ya., Shilova, G. On stability foi nonstationary M/M/N/N 4- R queue / A. Zeifman, A. Korotysheva, T. Panfilova, Ya. Satin, G. Shilova // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции. - Минск. - 2011. -с. 271-276.

Коротышева Анна Владимировна (Россия)

Оценки устойчивости для нестационарных марковских моделей с непрерывным временем

В диссертации рассматриваются оценки устойчивости для нестационарных марковских моделей с непрерывным временем. Приводится метод получения оценок устойчивости для векторов состояний и средних. Исследуются нестационарные модели с катастрофами. Улучшены общие оценки устойчивости для систем обслуживания М(/А-/,/Л7Аг и + Я: константа, связанная

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

Stability bounds for nonstationary Markov models in queuing systems

Stability bounds for non-stationary continuous time Markov models are obtained. Using a new approach we improve known perturbation bounds for the probability characteristics of queue-length proccss for Mt/Mt/N/N and Mt/Mt/N/N + R queues with possible catastrophes. We also consider a class of nonstationary Markovian queues with batch arrivals and group services, study conditions for weak ergodicity of the correspondent queue-length process and obtain bounds on the rate of convergence and stability for this model. The theoretical results are applied for modeling of the limiting characteristics for some concrete examples, the respective software package is developed, and approximations of each model are obtained.

Korotysheva Anna Vladimirovna (Russia)

Подписано в печать: 21.02.2014

Заказ № 9335 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Вологодский государственный педагогический университет

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

04201457207

КОРОТЫШЕВА Анна Владимировна

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

ДИССЕРТАЦИЯ

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

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

Вологда - 2013

Оглавление

Введение 5

1 Основные понятия 12

1.1 Пространство 1\........................................................12

1.2 Дифференциальные уравнения в пространстве 1\.........14

1.3 Логарифмическая норма оператора................15

1.4 Марковкие цепи ...........................16

1.4.1 Основные понятия......................16

1.4.2 Процессы рождения и гибели с катастрофами ......19

1.4.3 Возмущенные процессы...................20

2 Нестационарные системы обслуживания с катастрофами 23

2.1 Системы обслуживания с независимыми от числа требований в системе интенсивностями катастроф................23

2.1.1 Введение............................24

2.1.2 Устойчивость вектора состояний..............25

2.1.3 Оценка для среднего.....................27

2.1.4 Примеры ...........................30

2.2 Системы обслуживания с зависимыми от числа требований в системе интенсивностями катастроф................39

2.2.1 Введение............................39

2.2.2 Устойчивость для вектора состояний............40

2.2.3 Оценки для среднего.....................42

2.2.4 Аппроксимация........................45

2.2.5 Пример............................48

2.3 Система обслуживания с катастрофами........50

2.3.1 Введение............................50

2.3.2 Слабая эргодичность.....................51

2.3.3 Примеры ...........................57

2.3.4 Устойчивость.........................64

2.3.5 Оценки для среднего.....................70

2.3.6 Примеры ...........................70

3 Система обслуживания М/М/]Ч/ЧЧ 74

3.1 Введение................................74

3.2 Оценки скорости сходимости....................75

3.3 Оценки устойчивости ........................79

3.4 Примеры ...............................81

4 Система обслуживания М/М/ТЧЛЧ+И 85

4.1 Введение................................85

4.2 Общие оценки устойчивости.....................85

4.3 Оценки скорости сходимости....................91

4.4 Оценки устойчивости для системы М^/М^/АТ/ЛГ + Я.......94

4.5 Примеры ...............................97

5 СМО с групповым поступлением и обслуживанием требований 102

5.1 Введение................................102

5.2 Конечные системы..........................103

5.2.1 Скорость сходимости.....................104

5.2.2 Устойчивость.........................107

5.2.3 Примеры ...........................110

5.2.4 Аппроксимация........................113

5.3 Счетные системы...........................116

5.3.1 Оценки скорости сходимости................116

5.3.2 Аппроксимация........................122

5.3.3 Пример............................126

5.3.4 Устойчивость.........................127

5.3.5 Примеры ...........................132

Заключение 135

Приложение 136

Описание программы 136

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

Введение

Актуальность темы. В исследовании современных телекоммуникационных систем огромную роль играют методы и модели теории массового обслуживания.

Первые работы, относящиеся к такого рода тематике, были проведены А. К. Эрлангом в начале прошлого века. Примерно в 50-е годы двадцатого века выяснилось, что задачи, связанные с обслуживанием больших массивов однородных требований, возникают во многих областях естествознания и техники, и была создана так называемая теория массового обслуживания (англоязычный термин - теория очередей), являющаяся с тех пор активно развивающимся разделом прикладной теории вероятностей.

Существенный вклад в развитие этой области внесли российские и зарубежные ученые В. В. Анисимов, JI. Г. Афанасьева, Г. П. Башарин, А. А. Боровков, П. П. Бочаров, P. J1. Добрушин, Б. В. Гнеденко, А.Н. Дудин, А. И. Зейфман, В. В. Калашников, Н. В. Карташов, Е. В. Морозов, А. В. Пе-чинкин, В. В. Рыков, И. А. Соколов, С. Г. Фосс, Е. Van Doom, М. Neuts, R.L. Tweedie, W. Whitt и многие другие.

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

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

ния следующего типа: из равномерной экспоненциальной квази-эргодичности процесса Х(£) следует его равномерная устойчивость; получены соответствующие оценки. Результаты В.В. Анисимова сформулированы в терминах оператора перехода, а не интенсивностей, поэтому применение их к цепям с непрерывным временем достаточно затруднительно. Для процессов со счетным числом состояний аналогичные результаты в терминах инфинитезималь-ных характеристик были получены А.И. Зейфманом (см. [54]).

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

В работах А. И. Зейфмана начато систематическое исследование свойств типа эргодичности и устойчивости для неоднородных марковских цепей с непрерывным временем и приложение этих результатов к моделям массового обслуживания, описываемым процессами рождения и гибели (см. [59], [11]).

В последние годы, с одной стороны, А. Ю. Митрофановым (см. [43]) были улучшены оценки устойчивости для равномерно эргодичных однородных марковских цепей, а с другой, удалось расширить класс исследуемых марковских моделей (см. [63]), в связи с чем на настоящем этапе весьма актуальной стала задача построения оценок устойчивости для новых классов моделей и применение этих оценок для построения предельных характеристик конкретных систем массового обслуживания, в том числе с катастрофами и с групповым поступлением и обслуживанием требований.

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

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

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

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

- получены условия слабой эргодичности и оценки устойчивости для системы М1/М1/Б с катастрофами;

- получены оценки устойчивости и улучшены оценки скорости сходимости для систем обслуживания и М^/М^/ЛГ/ЛГ + Щ

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

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

Методы исследования. Для решения поставленных задач используется эволюционный оператор (оператор Коши) и генеральный показатель дифференциального уравнения в банаховом пространстве, и методы их оценки. Проблемы вычисления искомых параметров сводятся к изучению дифференциальных уравнений на множестве стохастических векторов. В этом случае возникают проблемы, связанные с получением явных оценок генерального показателя. Для получения этих оценок используется логарифмическая норма оператора, понятие которой введено у Лозинского, а для операторов в банаховом пространстве изучено Далецким и Крейном. Научная новизна.

- для моделей массового обслуживания с нестационарным марковским поступлением и обслуживанием требований с N серверами и Я местами ожидания (Мг/Л/г/АГ/ТУ 4- Я, Я > 0) в случае равномерной эргодичности (напр., см. теоремы 28, 36) получена оценка устойчивости, в которой множитель А/",

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

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

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

1. Получены общие оценки устойчивости нестационарных марковских систем обслуживания с катастрофами.

2. На основании общего подхода получены оценки устойчивости систем обслуживания М^М^Б с катастрофами.

3. Получены оценки устойчивости для систем обслуживания М^/М*/М/М и М*/М*/ЛГ/N + Я .

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

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

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

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

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

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

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

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

В главе 3 получены новые оценки сходимости и более простые оценки устойчивости нестационарной системы Мг/Мг/Л^/ЛГ. Рассмотрены примеры.

В главе 4 рассмотрена модель обслуживания М^/М^/ТУ/А7" + Я. Получены общие оценки сходимости и устойчивости и оценки устойчивости для конкретных случаев. Рассмотрены примеры.

В §1 главы 5 рассмотрена система массового обслуживания, число требований в которой описывается нестационарной марковской цепью с непре-

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

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

В приложении приведено описание программы для построения характеристик марковского процесса.

Апробация результатов. Результаты работы докладывались на: семинарах кафедры прикладной математики ВГПУ "Стохастические модели сложных систем"(2009-2013),

IV ежегодных смотрах-сессиях аспирантов и молодых ученых по отраслям наук (Вологда, 2010),

международной летней конференции по вероятности и статистике (Болгария, Созополь, 2010),

International Conference on Ultra Modern Telecommunications (Москва, 2010),

5th International ICST Conference on Performance Evaluation Methodologies and Tools (South of Paris, France, May 16-20, 2011),

международной конференции, посвященной 110-той годовщине И.Г. Петровского (Москва, 2011),

международной научной конференции "Современные вероятностные методы анализа, проектирования и оптимизации информационно-телекоммуникационных сетей"(Queues: Flows, Systems, Networks, Минск, Беларусь, 2011),

международной конференции "Теория вероятностей и ее приложения" (Москва, 2012),

международной конференции "Современная стохастика: теория и применения III"(Modern Stochastics: Theory and Applications III, Киев, Украина, 2012),

XXIX международном семинаре по проблемам устойчивости стохастических моделей (Светлогорск, 2012),

международной научной конференции "Современные вероятностные методы анализа, проектирования и оптимизации информа-ционно-телекоммуникационных сетей"(Queues: Flows, Systems, Networks, Минск, Беларусь, 2013).

Основные результаты опубликованы в [60]-[76].

Глава 1

Основные понятия

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

1.1 Пространство /1

Рассмотрим пространство - множество всех последовательностей х = {х1,Х2, ■ ■ •}, Х{ е Я, для которых \хг\ < оо. Нормой вектора х в данном пространстве называется величина и обозначается ||х|| (^-норма). ¿1

- линейное пространство, полное относительно метрики р(х, у) = ||х — у|| (.банахово пространство).

Единичные векторы (орты) 1\ обозначаются через е* (е* - вектор, у которого ьй член соответствующей последовательности 1, а остальные - нули). Тогда каждый вектор х € 1\ можно представить в виде х = щ • ег, причем \щ\ < оо.

Рассмотрим отображение А из 1\ в себя. Тогда этот оператор однозначно определяется матрицой 1. Норма оператора вычисляется по следую-

щей формуле:

1И11 = sup |Их||/||х||= sup |Hx||=supEkil-

Цх||<1 ||х||=1 3 i

Будут рассматриваться только ограниченные операторы, то есть такие операторы, для которых выполняется условие

||А|| = sup £ lay I < оо.

3 i

Пусть каждому t > О ставится в соответствие вектор х € 1\. Тогда говорят, что задана вектор-функция x(t). Вектор-функция называется непрерывной (в точке to), если при t —»to

||x(i)-x(i0)||->0.

Понятие дифферснцируемости в точке и понятие интеграла от вектор-функции вводится соответственно через предел отношения и интегральные суммы. Аналогично вводятся понятия оператор-функции, ее непрерывности, дифференцируемое™ и интегрируемости.

Рассмотрим понятие показательной функции вида etF. Оно вводится следующим образом

ос (+Р)п

е = / + (tF) + (tF)2/2! + (£F)3/3! + ... = Е ^f-.

i=о n-

Ряд, стоящий в правой части, сходится при любом i, что следует из сходимости ряда из норм

оо (tF)71 00 tnH т?Нп

¡7

Е ll^f-ll < Е = em.

i=О П\ ¿=0 П\

Мы получили, что

\\е№\\ < е«.

Можно доказать, что при любых действительных в справедливо равенство

еа+з)Р = е1Р.

Из последнего равенства при s = —t вытекает, что оператор etF обратим при любом t.

1.2 Дифференциальные уравнения в пространстве 1\

Рассмотрим дифференциальное уравнение в пространстве последовательностей 1\

jt[ = A(t)y(t) + f(t) (1.2.1)

и соответствующее ему однородное

I =

где x(t),y(t), f(t) - вектор функции из R+ в l\, a A{t) - оператор 1\ в 1\. Назовем U(t,r) - оператором Коши дифференциальных уравнений, где

U(t, т) = I + J* AMdsi + J* A(si) J*1 A{s2)ds2dsi + ...,

при этом ряд в правой части сходится равномерно на любом конечном отрезке и

U(t,s) = U(t, r)U(r, s).

Теорема 1. Пусть A(t), f(t) - непрерывны, т > 0 и у* 6 1\. Тогда существует, причем единственная y{t), определенная на [г, оо) и такая, что: V У(т) = у*;

2) y(t) непрерывна и дифференцируема при всех t > т. Теорема 2.

Пусть A(t), f(t) - непрерывны, т > 0 и х*, у* 6 1\. Тогда существуют единственные x(t),y(t), определенные на [г, оо) и такие, что:

х(т) = х*,у(т) = у*,

х(г) = и(г,т)х(т), у(£) = т)у(т) + £ 1/(г, з)/(з)(18. (1.2.2)

1.3 Логарифмическая норма оператора

Понятие логарифмической нормы для конечных матриц введено и изучено Лозинским; на случай оператор-функций оно обобщено в [9]. Ниже приводятся само это понятие и важные оценки связанные с ним.

Определение 1.

Число

к у " /г—>+о /г

называется логарифмической нормой оператора А.

Теорема 3. При всех t > 0 существует 7(А{£)), причем

1(т) = Цт У^лт-г

Следствие 1.

К(А(Ь)) = вир + Е \а>лШ] ■ о V ¥з )

Теорема 4.

Для любых t,s (£ > в > 0) выполняется неравенство: е-Гт(~А(т))ат < (([/(¿)5)Л < еХл{А{т))йт^

Теорема 5.

Свойство неотрицательности: С/(£, в) > 0 при всех £ > з > 0 - равносильно тому, что > 0 при всех г,] таких, что г ^ j, и любом и > 0.

Рассмотрим случай подпространства в Пусть матриица И образована элементами последовательности {¿¿} и с? = > 0.

Пусть 1\£, - пространство последовательностей г = (Р0,Р\,Р2, • • •) таких, что ||г||1д = \\Dz\h < 00.

Теорема 6.

Пусть В \ 1\ —> 1\- линейный оператор. Пусть из 1ю, тогда

\\в\\110 = \\пво-%,

1.4 Марковкие цепи

1.4.1 Основные понятия

Рассмотрим систему 51, которая может находится в момент £ в одном из состояний с номерами 0,1,... Множество Е = {0,1,...} называется пространством состояний системы <5\ Пусть X(¿) - состояние системы в момент Предположим, что если Х(Ь) = г, то при к > 0 Х(Ь-\-к) = з с вероятность�