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

005013047

Кондрашова Елизавета Владимировна

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

Специальность 01.01.05 — теория вероятностей и математическая

статистика

АВТОРЕФЕРАТ

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

2 9 мдр ¿012

Москва-2012

005013047

Работа выполнена на кафедре «Исследование операций» Московского государственного института электроники и математики.

Научный руководитель:

доктор физико-математических наук, профессор, заведующий кафедрой исследования операций Московского государственного института электроники и математики (технического университета) Каштанов Виктор Алексеевич

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

доктор физико-математических наук, профессор, главный научный сотрудник Федерального государственного бюджетного учреждения науки Института проблем информатики Российской академии наук (ИЛИ РАН) Печинкин Александр Владимирович

кандидат физико-математических наук, доцент, доцент кафедры теории вероятностей механико-математического факультета Московского государственного университета им. М.В. Ломоносова. Манита Анатолий Дмитриевич

Ведущая организация: Обнинский институт атомной энергетики -филиал федерального государственного автономного образовательного учреждения высшего профессионального образования «Национальный исследовательский ядерный университет «МИФИ»

Защита состоится «17» апреля в 15.00 на заседании диссертационного совета Д 212.133.07 при Московском государственном институте электроники и математики (техническом университете) по адресу: 109028, г. Москва, Б. Трехсвятительский пер., д. 3

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики (технического университета) по адресу: 109028, г. Москва, Б. Трехсвятительский пер.

Автореферат разослан «15 » марта 2012 г.

Ученый секретарь

диссертационного совета Д 212.133.07

к. ф.-м. н., доцент "иГ.ИАидркьб.

Шнурков П.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы.

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

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

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

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

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

Большой вклад в развитие теории, методов анализа и оптимального управления систем внесли Р. Ховард1, X. Майн, С. Осаки2, В. Джевелл, Ивченко Г.И., Каштанов В.А., Коваленко И.Н., Рыков В.В. и другие.

1 Ховард Р. А. Динамическое программирование и марковские процессы. М: Советское радио (перевод с английского), 1964.

2 Майн X., Осаки С. Марковские процессы принятия решений. М: Главная редакция физико-математической литературы издательства «Наука», 1977.

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

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

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

Предметом исследования являются управляемый входной поток, (CBSMAP-поток), управляемые системы массового обслуживания.

Управляемый поток является обобщением ранее введённого Д. Лукантони ВМАР-потока3 (Batch Markov Arrival Process - марковский групповой входной поток). ВМ4Р-потоки хорошо описывают входящие потоки данных в телекомунникационных сетях, когда требования в систему поступают группами различного размера.

Остановимся подробнее на управляемом групповом входном потоке CBSMAP. Введённое обозначение расшифровывается следующим образом: Controlled Batch Semi-Markov Arrival Process, что означает -управляемый полумарковский групповой входной поток. Поступление заявок может происходить только в моменты изменения состояний некоторого полумарковского процесса с непрерывным временем и конечным множеством состояний.

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

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

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

3 Lucantoni D. M. New results on the single server queue with a batch Markovian arrival process// Communications in Statistics, Stochastic Models. 1991. V. 7(1). C. 1-46.

Научная новизна и основные результаты диссертации. Научная новизна диссертационной работы состоит в разработке, описании и применении управляемого входного потока. Проведено исследование системы массового обслуживания с СВБМАР-ъотоком, рассмотрены элементы управления входным потоком. Рассмотрено три варианта управления: управление типом требований, управление типом требований и моментами поступления группы и управление типом требований, моментами поступления и количеством заявок в группе. Новый подход связан с управлением несколькими параметрами систем, структурой системы в полумарковской и марковской моделях массового обслуживания.

Получены следующие новые научные результаты:

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

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

3. Проведено исследование полумарковских систем массового обслуживания с СВБМАР-потоком. Данные системы рассматриваются как управляемые системы массового обслуживания, в которых проводится управление входным потоком требований. Найдены основные характеристики управляемых систем с СВБМАР-потоком: управляемое полумарковское ядро, стратегии управления, функционал доходов.

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

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

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

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

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

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

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

- Международная научная конференция ALT 2010, Accelerated Life testing, Reliability-based Analysis and Design, University Blaise Pascal, France, Clermont-Ferrand, 2010;

- Пятая Международная научная конференция IMAACA 2011 International Conference on Integrated Modeling and Analysis in Applied Control and Automation, Italy, Rome, September, 12-14,2011;

- Научно-техническая конференция студентов, аспирантов и молодых специалистов Московского государственного института электроники и математики 2009,2010,2011 годов;

- Семинар кафедры «Исследование операций» Московского государственного института электроники и математики, 2012.

Публикации. Основные результаты диссертации опубликованы в 8 работах соискателя. Из них работы [4-8] являются тезисами и расширенными тезисами докладов на международных и российских конференциях, [1,2,3] - статьи в ведущих рецензируемых научных журналах и изданиях, определенных Высшей аттестационной комиссией. При этом работы [1,2,3] представляют собой развёрнутые научные статьи, включающие подробное изложение и обоснование полученных результатов. В указанных публикациях содержатся основные результаты диссертации.

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

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

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

Глава 1 «Анализ характеристик входного потока, управляемого цепью Маркова» посвящена исследованию входного потока управляемого цепью Маркова.

В параграфе 1.1 приводятся вводные замечания и обозначения для однородного процесса марковского восстановления.

В параграфе 1.2 описывается управляемый процесс марковского восстановления (управляемый полумарковский процесс), а также дается определение входного потока управляемого цепью Маркова

Управляемый полумарковский процесс Х{г) = {£(/), и(/)} определяется однородной трехмерной марковской цепью или однородным управляемым процессом марковского восстановления4

(<Г„,0л,гО, п>0, ^ еЕ, вп е =[0,оо), и„еи, (1) которая определяется переходными вероятностями специального вида Щм =т,ип=и} =

1,те1Г, иеЦ, ВеА

и начальным распределением

р=Р{£0=Щ<сс,и0&и}. (2)

В дальнейшем будем использовать следующие обозначения

П$п+1 = ьК+1 < {>ип+1 еВ/{п=Ъ = ёу((,В). (3)

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

Это значит для каждого 1еЕ задано множество управлений £/, и о-алгебра А1 подмножеств этого пространства [/¡.

При г^>сои В=1/1 получаем переходную вероятность

р»=ал*,ю==ж„=о (4>

для вложенной цепи Маркова, характеризующей эволюцию первой компоненты введенной выше трехмерной цепи Маркова.

Из определения (3) следует

£,(С0 ,В) = Нтп^МЛиВ) = = 7>„+, *ВЦЛ= /}. (5)

Следовательно, семейство функций Qv(t,B) порождает на

измеримом пространстве (UbAi) семейство вероятностных мер при ieE, ВеА,

= =г}. (6)

jeE

Тогда существуют функции £>(*,«), для которых имеет место равенство

Q^B^lQ^G^du). (7)

в

Функции Qij{t,u) есть условные вероятности

0,(i,M) = P{C, =м+; <t!Zn =/,Чи7 = «}■ (8)

Таким образом, однородный управляемый процесс марковского восстановления может быть задан семейством матриц Щ,(А и)},

множеством вероятностных мер Gt(B) и начальным распределением вероятностей состояний/^ i,j еЕ, teR+, ueUb BeAj.

Семейство матриц {Qff(t,u)} назовем полумарковским ядром управляемого полумарковского процесса, а семейство вероятностных мер G — {G1(B),G2(B),...,Gn(B)} назовем семейством управляющих мер. Считающий процесс v(i), определим равенством v(0 = sup{«:2><i}, в0=0.

Чп

Управляемый полумарковский процесс X(t)5 (УПМП) определяется как пара

x(t)=m, m, (9)

где u(t) = Mv((Hr

Процесс <f (f) совпадает со стандартным полумарковским процессом. Вторая компонента управляемого полумарковского процесса u(t) определяет траекторию принимаемых решений.

Возможно определить ещё один способ задания управляемого полумарковского процесса:

• задается марковская однородная стратегия управления G = {Gi(B),G2(B),...,Gn(B)}

• задаются характеристики управляемой марковской цепи -начальное распределение р, = P{Ç0 = /} >0, ieE, р, = 1 и матрица

ieE

переходных вероятностей рр (и) = P{Çn+1 -]Цп= i, ип+, = и} ;

• задаются условные распределения интервалов и) = />{#„,, <//£„+у =./,<?„ = '>"„+;="}> на которых первая и вторая

компоненты управляемого полумарковского процесса ЛЭД = {£(?), принимают постоянное значение.

Заметим, что первые два положения определяют управляемую цепь Маркова. Третье положение определяет эволюцию состояний этой цепи во времени.

Считающий процесс назовем входным потоком заявок,

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

При построении модели массового обслуживания возможны следующие варианты поступления требований в систему:

- однородные заявки, неординарный поток;

- однородные заявки, ординарный поток;

- неоднородные заявки, неординарный поток;

- неоднородные заявки, ординарный поток.

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

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

Исследование этих характеристик базируется на изучении процессов восстановления, вложенных в полумарковский процесс. Пусть полумарковский процесс стартует из состояния г е Тогда интервалы между соседними моментами попадания УПМП в состояние ]еЕ образуют процесс восстановления с запаздыванием при и образуют простой процесс восстановления при }=1 и Н^ (г) - функция восстановления этого процесса восстановления.

Обратное время возвращения г), (время недоскока) определяется как время от момента последнего поступления требования (или группы требований), произошедшего на интервале [0,1), до момента

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

Р{Л,<х} =

1, x>t,

м{т],)=^mt)+(i i)

ieE jeE о

где Fi{t) = P{9n <//£„_, =/} = 2&(/), Щ = 1-Fft).

jeE

Прямое время возвращения £ (время перескока) определим как время от момента f до ближайшего изменения состояния УПМП (управляемого полумарковского процесса), произошедшего после í. Заметим, что при любом х>0 событие {^¡>х} означает, что на интервале (t,t+x) УПМП не меняет состояний.

Для распределения прямого времени возвращения и математического ожидания справедливы равенства:

Р& < х} = £Р,{F,(t + x)-F.(t) + YJ\{Fj(t + x-z)-F](t-, (12)

ieE JeE,-x

00 со t

M(l) = ]>>,[J^(í + + ZjjF/r + * - z)dH¡J{z)dx\. (13)

ieE o JeE o O

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

Если существуют стационарные распределения для вложенной цепи Маркова и математические ожидания времени непрерывного пребывания процесса в состоянии конечны, то используя узловую теорему восстановления6 и лемму7, получаем предельные характеристики: lim Р{т]. <*} = lim Р{т]. < х / £ (О) = /} =

X

(14)

= lim < х) = lim < х / £(0) = /} = ^^-,

2-,ткпк

ieE

00

Z KjjyFjiy^y \\тМ(т],) = limA/(£) = —--, (15)

/->oo /-юo

L 7ljmj

jeE

где 7tj - стационарное распределение состояний вложенной цепи Маркова определяется из системы л, =

keE ieE

6 Кокс Д., Смит В. Теория восстановления. М.: Советское радио, 1967.

7 Каштанов В.Л. Элементы теории случайных процессов (с.22). М.: МИЭМ, 2010.

mj - математическое ожидание времени непрерывного пребывания УПМП

В параграфе 1.5 построен стационарный входной поток, управляемый цепью Маркова.

Определение. Стационарным потоком v(t) называется процесс, у которого распределение числа заявок (или групп заявок), поступивших в интервале (t,t + x), не зависит от расположения этого интервала (не зависит от t), то есть функция P{v{t + х) - v(<) = k) зависит от х и к.

ТЕОРЕМА 1. Пусть существует стационарное распределение для вложенной цепи Маркова ж} и математические ожидания mj времени

непрерывного пребывания процесса в фиксированном состоянии j конечны. Если начальное распределение вложенной цепи Маркова равно л ¡т.

P{Çq = i} =— первый переход полумарковского процесса

переходы определяются полумарковским ядром Qy (/), то процесс восстановления с запаздыванием vj(t), образованный соседними

моментами попадания УПМП в состояние j е Е, стационарен.

СЛЕДСТВИЕ 1. В условиях теоремы 1 считающий процесс является стационарным.

В параграфе 1.6. проведено исследование структуры предельных характеристик стационарного входного потока, управляемого цепью Маркова.

ТЕОРЕМА 2. В стационарном случае распределения и математические ожидания прямого и обратного времени ожидания являются дробно-линейными функционалами относительно мер, определяющих стратегию управления.

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

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

8 Барзилович Е.Ю., Беляев Ю.К, Каштанов В.А и др. Вопросы математической теории надежности. М.: Радио и связь. 1983г. 376с.

в фиксированном состоянии j, т} = , (z)dz < оо.

о

£ягsms

определяется вероятностями QÏ- (х) =

iFy&dz

-2-, а последующие

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

Считаем, что в момент перехода УПМП в состояние к в систему массового обслуживания поступает конечная группа требований £-го типа, число требований в группы определяется производящей функцией

м,

Ф к(2) = %гтр«\т) (16)

т-1

где М^ максимальное число заявок в группе ¿-го типа.

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

1. Требования одного типа поступают в свою систему (подсистему) массового обслуживания, каждая из которых работает независимо от других подсистем. Подсистему массового обслуживания, осуществляющую обслуживание требований к-го типа, будем обозначать СМО(к), кеЕ = {1,2,...,Ы}, (индекс к, будет присвоен всем характеристикам этой подсистемы).

2. Во временном интервале между соседними моментами изменения состояний УПМП в систему массового обслуживания заявки не поступают (ни в одну из подсистем), поэтому осуществляется только процесс обслуживания заявок, если таковые в подсистемах есть. Процесс обслуживания в к-ой подсистеме характеризуется числом заявок, находящихся в подсистеме в момент г. Предполагается, что у(*'(/) есть однородный Марковский процесс гибели с поглощающим экраном в нуле и интенсивностями перехода, зависящими от состояния.

В данных условиях ставятся следующие задачи:

• Исследовать структуру функционала накопления (удельного дохода) в зависимости от стратегии управления входящим потоком;

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

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

В параграфе 2.2 описывается алгоритм исследования системы массового обслуживания с СВ5МАР-потоком. Определяются Марковские моменты, состояния полумарковского процесса, пространство управлений и стратегии управления, полумарковское ядро, функционал доходов на траекториях УПМП.

Состояния системы массового обслуживания (состояния управляемого полумарковского процесса £(/)) определяются вектором О',/^,...,/^), где г - состояние входного потока (в Марковский момент поступает группа требований /-го типа), 1к - количество требований в подсистеме к-го типа, Мк + Ык + пк>1к>0, кфг, Mj+Nt+n¡>ll>0, где пк и Ык - соответственно количество каналов обслуживания и количество мест для ожидания в СМО(к), ¡еЕ = {1,2,. Количество требований в подсистеме конечно и зависит от дисциплины принятий требований в систему и структуры системы массового обслуживания. Поэтому 1к&Ек = {0,1,2,...,Мк +Ык +пк-1}, е Е х Е, х... хЕы :

В дальнейшем примем следующие обозначения:

• для вектора, определяющего число требований в подсистемах, введем обозначение (¡,,12,...,1Ы)=1;

• для пространства состояний дискретной компоненты введем обозначение ЕхЕ,х...хЕ„=Ё.

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

Характеристики, отмеченные в параграфе 2.1, определяются для трех вариантов построения пространства управлений:

1. В зависимости от состояния полумарковского процесса (/,/) е Е выбираем только тип требований. Тогда справедливо равенство и(.Г)=Е = {1,2,...,Щ, а вероятностная мера на дискретном пространстве Е - {1,2,...,Ы} определяется набором вероятностей

са?)с/)=рт=]/т=(,-,/)}=Л)Г).,

№

где обозначено и(/) решение, принимаемое в Марковский момент (;

2. В зависимости от состояния полумарковского процесса (¡,1)еЕ выбираем тип требований и момент поступления заявок этого типа. Тогда справедливо равенство

иоЬ=Ех[0,со) = {и,и), ]еЕ={1,2,...,Щ, иеЯ+=[0,оо)},

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

FoI)(j\u) = P{e<u/mHi,h <t) = j), j^E = {l,2,...,N), usR+, a стратегию определить равенствами

G^U, и) = P{u(t) = j,0 <и/m = (/, / )} = р(,н/(,1у(и), (1 g)

jeE = {l,2,...,N}, u&R\ 3. В зависимости от состояния полумарковского процесса (г, 1)еЕ выбираем тип требований, момент поступления заявок этого типа и число заявок в группе. Тогда справедливо равенство для пространства управлений

U(.h=Ex[0,<x>)xMk =

= {(j,u,s), j&E = {l,2,...,N}, ueF=[0,ao),s<=Mk={l,...,Mk}, то есть пространство управлений состоит из конечного числа полупрямых. Вероятностную меру на этом пространстве можно задать набором вероятностей, принять решение, что поступает группа j -го типа размера s (дискретная компонента),

Р{и( 0 = (j,s) / «/) = (/, /)} = P{iJ){M = p,j,/4s\

Рцтт-0' X PiiJuM,=l,jzE = {l,2,...,N), seMk (19)

(Jj)eExMi,

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

Fw)0'>">")=р(в < =оЛ u(t)=а,«)},

jeE = {l,2,...,N}, u&R+, neMk, a стратегию определить равенствами

G(lJ)(j,u,n) = P{u(t) = (j,n),6 <u!Ç(t) = (/,/)} =

= Piihjp{i){n)Fuh{j,u,n), (20)

jeE = {l,2,...,N}, ueR+, ие{Д...,М,.}. Математическое ожидание накопленного дохода в подсистеме к за

время t>0 при условии, что процесс стартует из состояния (/,/),

обозначим

gtv (f^

Для функционала «S*** = lim-^— справедливо равенство9

ДжевеллB.C. Управляемыеполумарковские процессы. Москва: Мир, 1967.

т

С(» _ (¡ЛеЕ_

(УГОЛ

(ум

где - математическое ожидание накопленного дохода при работе СМО(к) за время непрерывного пребывания процесса £(/) в состоянии (г,/и),

" математическое ожидание времени непрерывного пребывания процесса в фиксированном состоянии (г,те),

- стационарное распределение для вложенной цепи Маркова.

ТЕОРЕМА 3. Пусть существует стационарное распределение для вложенной цепи Маркова , математические ожидания времени непрерывного пребывания процесса £(/) в фиксированном состоянии (¡,т) и л'*]^ - математические ожидание накопленного дохода при работе СМО(к) за время непрерывного пребывания процесса £(г) в состоянии (},т) конечны. Тогда функционал удельного накопленного дохода (21) для СМО(к) является дробно-линейным функционалом относительно распределений С = (1,т)еЕ}, определяющих марковскую

однородную рандомизированную стратегию.

N

ТЕОРЕМА 4. Функционал удельного накопленного дохода 5 =

к=1

для всей СМО является дробно-линейным функционалом относительно распределений О = {С(1>й)(ы), (г,т)еЕ), определяющих марковскую однородную рандомизированную стратегию.

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

В параграфе 2.4 приводится пример исследования системы с СВЗМАР-птокои при входном потоке, принимающем два состояния, одноканальных подсистемах. Управление в системе осуществляется посредством выбора типа следующего требования. Характеристики системы, изложенные в параграфе 2.2, найдены для всех возможных стратегий управления.

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

В параграфе 3.1 описывается система М/С*/1ЛЧ* (символ * указывает характеристики СМО, которые меняются в марковские моменты, то есть этими характеристиками мы управляем) и приводится алгоритм определения оптимальной стратегии в классе

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

Для исследуемой модели марковские моменты - моменты начала обслуживания очередного требования. Состояние управляемого процесса — есть число заявок в марковский момент. Детерминированная стратегия определяется двумя параметрами: сколько поставить свободных мест для ожидания и сколько времени обслуживать очередное требование. Если наблюдается состояние »=1,2то считаем т,, у1 - назначенная длительность обслуживания и число свободных мест в очереди соответственно. Функционал доходов определяется константами:

- с, плата за единицу времени работы прибора в период обслуживания требования;

- с2 плата за единицу времени простоя прибора;

- с3 плата за единицу времени пребывания требования в очереди;

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

- с5 плата за одно потерянное требование;

- с5 плата за одно добавленное место в очереди.

Для исследуемой системы удельный доход есть функция переменных при т,, V,, ¡ = \,2,...,Ы

£ = ^-- (22)

1еЕ

ГДе = 2 Н*+ Д И 2 Д КОТ°РУЮ

необходимо исследовать на максимум.

В параграфе 3.4 приводится пример исследования модели М/в*/1/2*.

В параграфе 3.5 описывается управляемая марковская система массового обслуживания М/М/п*ЛЧ*, в которой управление осуществляется выбором числом мест для ожидания и количеством каналов обслуживания. Приводится алгоритм решения.

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

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

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

В Приложении 1 показан вид полумарковского ядра для решения задачи поиска оптимальной стратегии из Главы 2.

В Приложении 2 размещена матрица системы алгебраических уравнений для поиска стационарных распределений цепи Маркова для управляемой полумарковской системы массового обслуживания из Главы 3.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Сформулирована и доказана теорема, определяющая условия, при которых рассматриваемый входящий поток является стационарным.

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

4. Исследованы управляемый входной поток СВБМАР-поток и системы с данным потоком. Рассмотрено три варианта построения пространства управлений для системы с СВБМАР-потоком.

5. Доказана теорема о дробно-линейной структуре функционала удельного накопленного дохода для подсистемы системы с СВБМАР-входным потоком.

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

7. Приведен пример исследования системы с СВБМАР-потоком при управлении типом требований, поступающих в систему.

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

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в реферируемых изданиях, входящих в перечень ВАК:

1. Каштанов В.А., Кондрашова Е.В. «Анализ входного потока, управляемого цепью Маркова». Журнал «Надёжность», № 1, с. 52-68, 2012.

2. Кондрашова Е.В. «Алгоритмизация исследования качества работы системы массового обслуживания». Журнал «Качество. Инновации. Образование», №8, с. 40-46,2011.

3. Кондрашова Е.В. «Оптимизация функционала доходов в управляемой системе массового обслуживания». Управление большими системами. № 36. - М.: ИПУ РАН, 2012 (13 стр.)

Статьи и тезисы в сборниках научных трудов и материалах научных конференций и научные публикации:

4. Кондрашова Е.В. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Внутривузовский сборник. Тезисы докладов. «Исследование систем массового обслуживания при управлении несколькими параметрами», с. 9-10,2009.

5. Кондрашова Е.В. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Внутривузовский сборник. Тезисы докладов. «Управляемая марковская модель массового обслуживания», с. 5-6,2010.

6. Кондрашова Е.В. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Внутривузовский сборник. Тезисы докладов. «Исследование модели массового обслуживания с ВSMAP-потоком», с. 5-6,2011.

7. Kashtanov V.A., Kondrashova E.V. «Controlled semi-markov queueing model», Proceedings of the third international Conférence ALT 2010 (Accelerated Life testing, Reliability-based Analysis and Design), Université Biaise Pascal, France, p. 243-249,2010.

8. Kashtanov V.A., Kondrashova E.V. «Controlled semi-markov queueing models», IMAACA 2011 International Conférence on Integrated Modeling and Analysis in Applied Control and Automation, Italy, Rome, p. 1-8, 2011.

Подписано в печать 14.03.2012г. Усл. Печ. 1,25 Тираж 100 экз. Заказ № 525 Отпечатано в типографии «ДЦ «Каретный Двор»» 101000, Москва, Лубянский пр., д.21, слр.5-5а Тел.: (495) 621-70-09 www.aUaprint.nl

61 12-1/755

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ (ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ) Факультет прикладной математики

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

Кондрашова Елизавета Владимировна

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

Специальность 01.01.05 - теория вероятностей и математическая

статистика

ДИССЕРТАЦИЯ

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

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

Москва-2012

Содержание

Введение..............................,.....................................................................4

Глава I. Анализ характеристик входного потока, управляемого цепью

Маркова...................................................................................................17

1.1. Вводные замечания. Обозначения.............................................17

1.2.Определение входного потока, управляемого цепью Маркова..21

1.3. Исследование характеристик входного потока заявок (нестационарный случай)...................................................................28

1.4. Анализ предельных распределений (стационарный случай)... 36

1.5. Построение стационарного входного потока, управляемого цепью Маркова....................................................................................41

1.6. Исследование структуры предельных характеристик стационарного входного потока, управляемого цепью Маркова.....44

Глава П. Исследование полумарковских систем массового обслуживания при управляемом входящем потоке..............................46

2.1. Вводные замечания, обозначения и постановка задачи...........46

2.2. Алгоритм исследования системы с CBSMAP-входным потоком .................................................................................................................52

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

2.4. Пример исследования системы с CBSMAP-потоком.................70

Глава Ш. Исследование систем массового обслуживания при управлении структурой системы...........................................................85

3.1. Исследование системы M/G*/l/N*..............................................85

3.2. Исследование системы M/M/n*/N*.............................................99

Заключение...........................................................................................118

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

Приложение 1.......................................................................................127

Приложение 2.......................................................................................133

Приложение 3.......................................................................................134

Введение

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

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

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

Одной из первых работ по теории массового обслуживания считается работа А.К. Эрланга «Теория вероятностей и телефонные разговоры» («The Theory of Probabilities and Telephone Conversations») [58]. Среди учёных, уделивших внимание развитию теории массового

обслуживания, можно выделить Д. Кендалла [54], Л. Такача [66], Хинчина А.Я. [42, 43], Феллера В. [41], Гнеденко Б. В., Коваленко И.Н. [7, 8] и др.

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

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

Отметим, что с помощью теории было получено большое число аналитических результатов, характеризующих различные качества систем. К этим результатам можно отнести исследования распределений вероятности потерь, распределения длины очереди, времени ожидания, среднего времени пребывания заявки в системе и т.д. [4,5,8,11,42,43,50,54,59-62] В классической теории массового обслуживания не предполагается вмешательства в процесс работы системы, то есть можно сказать, что система рассматривается без управляющих воздействий из вне.

Однако в реальной жизни часто возникает необходимость управления системой в процессе работы. Системы, в которых какие-либо из элементов допускают управление, будем относить к управляемым системам массового обслуживания. Методы теории управляемых систем массового обслуживания применяются для оптимального управления очередью, обслуживающими приборами, длительностью обслуживания и др.[15, 39,45, 46,49, 53]

Большой вклад в развитие теории, методов анализа и оптимального управления систем внесли Р. Ховард, X. Майн, С. Осаки, В. Джевелл, Ивченко Г.И., Каштанов В.А., Коваленко И.Н., Рыков В.В. и другие [30, 31, 44, 57, 52, 53, 14, 39, 40, 41, 47-49]. Заметим, что при исследовании характеристик систем массового обслуживания успешно используется теория марковских и полумарковских процессов, а также теория цепей Маркова [4, 31, 32, 39, 40].

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

Отметим, что в последнее время в задачах массового обслуживания рассматриваются 2?М4Р-потоки заявок [37, 49, 50, 55, 56, 63]. Процесс ВМАР впервые был введён в 1991 году Лукантони

[55, 56]. Описание ВМАР-штокоъ и рассмотрение систем массового обслуживания с ВМАР-пототм было также сделано Д. Лукантони.

Данный поток - Batch Markov Arrival Process - марковский групповой входной поток характеризуется следующим образом.

Поступление заявок может происходить только в моменты изменения состояний некоторого марковского процесса с непрерывным временем и множеством состояний {0,1,...,W}. Заявки могут поступать группами различного размера. Время пребывания процесса в состоянии / имеет экспоненциальное распределение с параметром Д, где i = 0,W. Процесс переходит из состояния i в состояние j с вероятностью pk(i,j) и генерируется группа из к требований ВМАР-штош. Предполагается, что переход из состояния / в то же самое состояние при генерации требований невозможен.

Также предполагается, что вероятности удовлетворяют условию

00 w . -

нормировки X Z Pk(iJ) = 1 ПРИ любом i = 0,W.

к=О j=О

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

Обобщение МАР-потока введено в работах Печинкина А.В. [34, 35, 36]. Данный полумарковский поток характеризуется следующим образом.

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

были получены стационарные распределения основных характеристик обслуживания [34-36].

Диссертация продолжает работы в области исследования управляемых систем массового обслуживания. Такие системы являются актуальным объектом исследований и имеют практическую ценность, так как позволяют создавать аналитические модели, применимые для моделирования систем, встречающихся в различных сферах производства и обслуживания. Отметим, что предлагается ввести входной поток, который является обобщением отмеченных выше потоков, CBSMAP-шуток, Controlled Batch Semi-Markov Arrival Process, что означает - управляемый полумарковский групповой входной поток. Входящий CBSMAP-uotok, управляемый цепью Маркова, определяется управляемым полумарковским процессом с конечным множеством состояний. Поступление заявок может происходить только в моменты изменения состояний некоторого полумарковского процесса с непрерывным временем и конечным множеством состояний. Таким образом, становится возможным использовать теорию управляемых полу марковских процессов [13, 14, 31, 52, 53] для анализа характеристик систем массового обслуживания и расширения круга моделей.

Кратко остановимся на содержании диссертации.

Глава 1 посвящена исследованию входного потока управляемого цепью Маркова. Этот входной поток определяется через управляемый полумарковский процесс X{t) = {^{t\u(t)}, у которого первая компонента принимает значения из конечного множества, = {1,2,...,7V}. Вводятся обозначения, определяется объект исследования. Рассматриваются характеристики входного потока

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

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

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

В главе 2 исследуются системы массового обслуживания с управляемым входным потоком, СВЯМАР-потоком, структура которого представляет собой композицию N потоков заявок различных типов (по числу состояний управляемого полумарковского процесса).

В задачах управления с СВЗМАР-иотоком может проводиться управление следующими характеристиками:

- типом заявок, поступающих в систему;

-типом заявок, поступающих в систему, и временем, через которое поступает группа заявок;

-типом заявок, поступающих в систему, временем, через которое поступает группа заявок, и количеством заявок в группе.

В данной главе показано, что структура функционала накопления [9, 18] для систем массового обслуживания с СВЯМАР-потоком является дробно-линейной относительно распределений, определяющих марковскую однородную рандомизированную стратегию. Исследование проводится в предположении, что каждый тип заявок обрабатывается в своей подсистеме массового обслуживания СМО(к), к е Е = {1,2,...,Щ.

Состояния управляемого полумарковского процесса определяются вектором (/,/) = (/,/,,/2,...,/у) - типом последнего пришедшего требования и числом требований в каждой подсистеме.

Доказаны теоремы.

Теорема 2.1. Функционал удельного накопленного дохода Бкк) для СМО(к) является дробно-линейным функционалом относительно распределений, определяющих марковскую однородную рандомизированную стратегию.

Теорема 2.2. Функционал удельного накопленного дохода

N

8 = для СМО в целом является дробно-линейным

к=1

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

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

и

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

В главе 3 исследуются марковская и полумарковская системы массового обслуживания при управлении структурой системы.

Марковская система М/М/п*/М* задаётся следующим образом: моменты поступления требований образуют простейший поток однородных событий с параметром А, длительность обслуживания распределена экспоненциально с интенсивностью обслуживания ¡и. Число каналов обслуживания является параметром управления. Количество мест для ожидания также является параметром управления.

Полумарковская система М/С*/1/Ы* задаётся следующим образом: моменты поступления требований образуют простейший поток однородных событий с параметром X, функция распределения длительности обслуживания меняется в зависимости от состояния системы, то есть является параметром управления. Система является одноканальной. Число мест для ожидания может изменяться в зависимости от состояния процесса, является параметром управления. Число мест для ожидания ограничено.

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

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

В Приложении 1 приведены элементы полумарковского ядра для решения задачи поиска оптимальной стратегии из Главы 2.

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

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

В связи с вышеизложенным целью работы является исследование управляемых систем массового обслуживания, поведение которых может быть описано управляемым полумарковским процессом. В данных системах проводится управление входным потоком, а также структурой системы. Также проводится исследование управляемого входного потока и исследование систем с данным СВЗМА Р-потоком.

Научная новизна и основные результаты диссертации.

Научная новизна диссертационной работы состоит в разработке и исследовании свойств управляемого входного потока. Определенный выше СВ8МА Р-поток является обобщением ранее введённого ВМАР-потока. Это позволяет применять управление в системах массового обслуживания, используя теорию управляемых полумарковских процессов. Исследованы системы с управляемым

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

Получены следующие новые научные результаты:

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

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