авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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

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

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

Долгов Виталий Игоревич ДИНАМИЧЕСКОЕ УПРАВЛЕНИЕ ИНТЕНСИВНОСТЯМИ ОБСЛУЖИВАНИЯ В СЕТЯХ МАССОВОГО ОБСЛУЖИВАНИЯ 01.01.09 – Дискретная математика и математическая кибернетика

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

Саратов – 2010

Работа выполнена на кафедре системного анализа и автоматического управления Саратовского государственного университета им. Н. Г. Чернышевского

Научный консультант: доктор технических наук, профессор Митрофанов Юрий Иванович

Официальные оппоненты: доктор физико-математических наук, профессор Розен Виктор Владимирович кандидат физико-математических наук, доцент Шульга Татьяна Эриковна

Ведущая организация: Институт проблем точной механики и управления РАН

Защита состоится « 28 » октября 2010 г. в 17 часов 00 мин на заседа нии диссертационного совета ДМ 212.243.15 в Саратовском государствен ном университете им. Н. Г. Чернышевского по адресу: 410012, г. Саратов, ул. Астраханская, 83, механико-математический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Саратов ского государственного университета им. Н. Г. Чернышевского.

Автореферат разослан « » сентября 2010 г.

Ученый секретарь диссертационного совета к.ф.-м.н., доцент В. В. Корнев

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

Актуальность темы. Эффективное использование сетей массового обслуживания в качестве математических моделей дискретных систем с се тевой структурой и стохастическим характером функционирования, приме рами которых являются информационно-вычислительные сети, сети переда чи данных, транспортные и гибкие производственные системы, обусловило продолжающееся более полувека интенсивное развитие теории сетей массо вого обслуживания, методов анализа, синтеза и оптимизации сетей массово го обслуживания различных классов [1–9]. Как модели дискретных систем сети массового обслуживания используются для вычисления временных ха рактеристик, коэффициентов использования устройств, надежности, произ водительности и других функциональных характеристик дискретных систем при достаточно общих предположениях об их структуре и процессах функ ционирования. Широкому практическому применению сетей массового об служивания способствует простота и естественность, с которыми они ото бражают структуру моделируемых систем и процессы обработки в системах объектов различных типов. Большой вклад в развитие теории, методов ана лиза, оптимизации и синтеза сетей массового обслуживания внесли Г. П. Башарин, А. А. Боровков, П. П. Бочаров, В. М. Вишневский, В. А. Жожикашвили, В. А. Ивницкий, Ю. И. Митрофанов, В. В. Рыков. Сре ди зарубежных специалистов необходимо отметить значительный вклад в развитие этого научного направления таких ученых, как Дж. Джексон, Л. Клейнрок, Ф. Келли, К. Чэнди, Д. Тауслей, М. Райзер, Дж. Уолрэнд.

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

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

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

В основу диссертации положены результаты научных исследований, выполненных при участии автора в Саратовском государственном универ ситете по темам, включенным в план НИР СГУ: «Динамическое управление сетями массового обслуживания» (шифр «Темп», гос. рег. № 01200201953), «Анализ сетей массового обслуживания с динамическим управлением» (шифр «Тракт», гос. рег. № 01200602692), «Разработка и применение фун даментальных методов исследования задач математического анализа, диф ференциальных уравнений, дискретной математики, теории упругости и га зодинамики» (шифр «Интеграл», гос. рег. № 01200002986).

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

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



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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты докладывались и обсуждались на на учных семинарах кафедры системного анализа и автоматического управле ния Саратовского государственного университета, Международных научных конференциях «Компьютерные науки и информационные технологии» (1– июля 2007 года, 1–4 июля 2009 года, г. Саратов), Десятом Всероссийском симпозиуме по прикладной и промышленной математике (19–24 мая 2009 года, г. Санкт-Петербург), Ежегодных межвузовских научных конфе ренциях «Компьютерные науки и информационные технологии» (27 апреля 2005 года, 19 мая 2006 года, г. Саратов), представлены и обсуждались на Шестом Всероссийском симпозиуме по прикладной и промышленной мате матике (1–7 октября 2005 года, г. Сочи–Дагомыс).

Публикации. По результатам диссертации опубликовано 9 работ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и заключения. Объем диссертации 109 страниц. Диссертация содержит 11 таблиц. Список литературы включает 82 наименования.





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

Введение содержит общую характеристику работы.

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

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

Рассматривается замкнутая экспоненциальная сеть массового обслу живания N, образованная L системами массового обслуживания Si, i = 1, K, L, типа M / M / 1 с интенсивностями обслуживания µi и содержа щая Q требований одного класса. Переходы требований между системами обслуживания в процессе функционирования сети определяются неприво димой маршрутной матрицей = ( ij ), i, j = 1, K, L. Вектор s ( n ) = ( si( n ) ), i = 1, K, L, где si(n) – число требований, находящихся в системе Si, опреде ляет состояние сети с номером n. Множество X состояний сети имеет мощность c X = X. Обозначим через I = {1, K, L} и B = {1,K, c X } соответст венно множества номеров систем массового обслуживания и номеров со стояний сети. Предполагается, что для каждого состояния s ( n ) X опреде лено неотрицательное вещественное число V (n ), называемое потенциалом этого состояния. Значение потенциала состояния отражает уровень значимо сти пребывания сети в этом состоянии с точки зрения обеспечения заданных характеристик качества ее функционирования. Нумерация состояний произ водится по убыванию потенциалов. Базовое состояние s o = ( sio ), i = 1, K, L, имеет номер 1 и наибольший потенциал. Выбор некоторого состояния сети в качестве базового обуславливается необходимостью достижения требуемых значений заданной стационарной характеристики сети, например, пропуск ной способности сети, общих задержек обслуживания или коэффициентов использования ресурсов сети массового обслуживания.

Множество X делится на подмножества Y и Z доминантных и орди нарных состояний, cY = Y и cZ = Z. Множество номеров доминантных состояний сети обозначим через D. К доминантным относятся состояния, пребывание в которых обеспечивает значение основной характеристики ка чества функционирования сети более близкое к экстремальному значению, чем пребывание в ординарных состояниях. Потенциалы доминантных со стояний превосходят по величине потенциалы ординарных состояний. При определении потенциалов состояний, способа нумерации состояний в мно жестве X и формировании множеств Y и Z используются векторы d ( n ) = (d i( n) ), di( n ) = si( n ) sio, и вектор b = (bi ), bi 0, i = 1, K, L, граничных значений числа требований в системах обслуживания. Состояния s ( n ) X, для которых справедливы неравенства d i( n) bi, i = 1, K, L, относятся к множеству Y, остальные состояния – к множеству Z.

Пусть N c – сеть массового обслуживания, структура, параметры и ал горитмы функционирования которой такие же, как у сети N, и которая от личается от N только тем, что в N c реализовано динамическое управление интенсивностями обслуживания. Управление осуществляется посредством управляющих воздействий, формируемых в процессе функционирования се ти N c системой управления. Основной целью управления является дости жение максимального значения стационарной вероятности (Y ) пребыва ния сети в подмножестве Y доминантных состояний при ограничении R на интенсивность управления R, определяемую как число управляющих воз действий, формируемых в единицу времени.

Различаются два режима функционирования сети N c – нормальный и коррективный. Периоды функционирования сети в этих режимах называ ются соответственно нормальным и коррективным тактами. Такт будем обо значать через x (k ), где k {1, 2, K} – номер такта в общей последовательно сти тактов, а момент окончания такта x (k ) – через (k ). Все такты имеют фиксированную длительность. Режимы функционирования отличаются используемыми в сети векторами интенсивностей обслуживания требова ний – в нормальном такте используется вектор µ = ( µi ), i = 1, K, L, в коррективном такте – коррективный вектор, зависящий от состояния сети в момент окончания предшествующего такта.

Вектор интенсивностей обслуживания, используемый в течение такта x, обозначим через µ ( k ) = ( µi( k ) ), i = 1, K, L, k {1, 2, K}. Значения ком (k ) понент вектора интенсивностей обслуживания µ ( k +1), используемого в тече ние такта x ( k +1), определяются в зависимости от состояния сети s (,k ) в момент (k ) и значения вектора b.

В момент (k ) выполняются следующие действия: 1) идентификация состояния s (, k ) ;

2) формирование вектора d (, k ) = ( d i(, k ) ), i = 1, K, L, где d i(,k ) = si(,k ) sio ;

3) проверка выполнения неравенств d i(, k ) bi. Если дан ные неравенства не выполняются для всех систем, то следующий такт явля ется нормальным, и в течение такта x ( k +1) используется вектор µ (k +1) = µ.

Если хотя бы для одной системы неравенство выполнилось, то следующий такт является коррективным, формируется вектор µ ( k +1) = µ ( k +1), значения ~ компонент которого направляются системам обслуживания и используются в течение такта ~ ( k +1). После окончания такта x ( k +1) в момент ( k +1) произ x водится очередное выполнение действий 1) – 3) и т. д.

Предлагается следующий метод формирования коррективного век тора интенсивностей обслуживания µ ( k +1) = ( µ i( k +1) ), i = 1, K, L. Обозна ~ ~ чим через ijk +1), i, j I, интенсивность потока требований из S i в S j в те ( чение коррективного такта ~ ( k +1), а через ( k +1) и ( k +1) – интенсивности x i i потоков требований, выходящего из S i и входящего в S i в течение этого такта. Алгоритм формирования µ ( k +1) содержит вспомогательный шаг и ос ~ новные шаги, число которых зависит от требуемой точности определения вектора µ ( k +1). При выполнении вспомогательного шага предполагается, ~ что i( k +1) = µi, i = 1, K, L, и определяются величины ( si(, k ) + µ i sio ) при si(, k ) + µ i sio, = ( ( k +1) µi 0 при si(, k ) + µ i sio.

На первом основном шаге полагается, что i( k +1) = µ i( k +1), i = 1,K, L, ( и определяются ijk +1) = i( k +1) ij, i, j = 1,K, L, (jk +1) = iL=1 ijk +1), j = 1,K, L, ( ( ~ ( k +1) = ( si + i (, k ) ( k +1) sio ) при si(, k ) + i( k +1) sio, µi 0 при si(, k ) + i( k +1) sio.

При выполнении следующих основных шагов производится подстановка вместо i( k +1) величин µi( k +1), i = 1, K, L, определенных на предыдущем ос ~ новном шаге.

Теорема 2.9. Оптимальная длительность такта, при которой дости гается max (Y ) при R R, 0 = 1 R.

Замечание 2.2. При µ ( k +1) µ и µ ( k +1) µ, i = 1, K, L.

~ ( i i i i Далее коррективный вектор интенсивностей обслуживания будем обо значать через µ J, J {1,K, cZ }, если коррективный такт начинается в со ~ стоянии s ( cY + J ) Z.

Эволюция сети обслуживания N c описывается случайным процессом с множеством состояний X, который является последовательностью фрагментов, соответствующих нормальным и коррективным тактам. Цепь Маркова, описывающую эволюцию сети N c в течение нормальных тактов, обозначим через C, а цепи Маркова, описывающие эволюцию сети N c в те чение коррективных тактов, – через C J, J {1,..., cZ }. Длительности реали ~ заций цепей C и C J равны. Множеством начальных состояний цепи C ~ является множество {s (1),K, s (cY ) }, а цепи C J – {s (cY + J ) }. Длительности ~ пребывания цепей C и C J в состоянии s ( n) X являются случайными ве ~ личинами с экспоненциальными функциями распределения с параметрами n и n соответственно. Для цепей C и C J соответственно обозначим ~ ~J P = ( p mn ) и P J = ( ~mn ), m, n = 1,..., c X, – матрицы вероятностей перехода;

~ pJ P (t ) = ( pmn ) и P (t ), J = ( ~mn J ) – матрицы вероятностей перехода за время t.

~ (t ) p (t ), Теорема 2.10. Существует единственное стационарное распределе ние процесса = ( n ), n = 1,..., c X, зависящее от и являющееся решени ем системы линейных уравнений cY + J ~c( ), JJ, n, n = 1,K, c X, cZ l pl(n ) n = + p+ Y n = 1.

l D J = с условием нормировки nB Обозначим через ql (t ) вероятность того, что процесс в момент t (0, ] находится в состоянии s (l ) X, cY + J ~c(Y),+JJ, l.

cZ m p ml) (t pt ql (t ) = + mD J = Теорема 2.11. Стационарные вероятности p n перехода процесса в состояние s ( n) X, зависящие от длительности такта, определяются выражениями pn = 1 n (t ) dt, n B, 0 (t ) где ql (t )( l pln m + lJ cY + J ~lJn ), cZ ~ n (t ) = p l B mD J = ql (t )( l m + lJ cY + J ).

cZ ~ (t ) = l B mD J = Обозначим: si – математическое ожидание числа требований в Si ;

i – интенсивность входящего в систему Si потока требований;

ui – математиче ское ожидание длительности пребывания требований в Si ;

i – коэффици ент использования обслуживающего прибора в Si.

Теорема 2.12. Сеть N c имеет следующие стационарные характери стики, i = 1,K, L :

kP{si = k}, где ( n n ;

Q si = P{si = k} = ) (n) k =1 X & si =k s µiJ cY + J ;

сZ i = µ i (1 P{si = 0}), где µ i = µ i ~ m + m D J = ui = si / i ;

i = i / µ i = 1 P{si = 0}.

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

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

Рассматривается замкнутая экспоненциальная сеть массового обслу живания N с Q требованиями одного класса. Отличие от сети, рассмотрен ной в главе 2, состоит в том, что в состав сети N помимо L систем обслу живания Si, i = 1, K, L, типа M / M / 1 с интенсивностями обслуживания µ i входит система обслуживания S 0 типа M / M / Q с интенсивностью µ 0 об служивания требований одним прибором. Системы Si, i = 1, K, L, называют ся базисными, а S 0 – терминальной. Переходы требований между система ми в процессе функционирования сети N определяются неприводимой мар шрутной матрицей = ( ij ), i, j = 0,1,K, L. Обозначим через I = {0,1, K, L} – множество номеров систем в сети, H – базисную подсеть, J = {1,K, L} – множество номеров систем в подсети H.

Обозначим: µ = ( µ i ), i = 1,K, L ;

(µ ) математическое ожидание длительности реакции сети обслуживания для системы S 0 ;

ci ( µ i ) стои мость системы S i при использовании в ней интенсивности обслужива ния µ i ;

C (µ ) суммарная стоимость сети N (не включая стоимости систе мы S 0 ), C ( µ ) = iL=1 ci ( µ i ) ;

i интенсивность входящего потока требова ний в систему S i ;

i – относительная интенсивность входящего потока тре бований в систему Si, = ( i ), i = 0,1,K, L, – решение уравнения = i = 0 i = 1.

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

A1. Минимизация функции стоимости C (µ ) сети при ограничении (µ ) U ( U 0 ).

A2. Минимизация математического ожидания (µ ) длительности ре акции сети при ограничении C (µ ) ( 0).

Рассмотрим задачу A1 при 0 µ i и линейных функциях ci ( µ i ) = a i µ i, ai 0, i = 1,K, L. Следующая теорема определяет решение µ = ( µ i ), i = 1,K, L, этой задачи оптимизации.

Теорема 3.1. При заданном ограничении (µ ) = U функция C ( µ ) = iL=1 ai µ i, где ai 0, принимает минимальное значение, если i L µ i = i + a j j, i = 1,K, L, 0U ai j = где Qi i =, i = 0,1,K, L.

0 (U + 1 µ 0 ) Пусть N c – сеть массового обслуживания, структура, параметры и ал горитмы функционирования которой такие же, как у сети N, и которая от личается от N только тем, что в N c реализовано динамическое управление интенсивностями обслуживания в базисных системах. Для параметров и ха рактеристик сети N c используются введенные для соответствующих пара метров и характеристик сети N обозначения с индексом « c ». В частности, число требований в подсети H сетей N и N c обозначается соответственно через QH и QH. Целью управления интенсивностями обслуживания в N с c является уменьшение математического ожидания длительности реакции c сети N с для системы S0 и вероятности c пребывания этой сети в состоя ниях, в которых QH больше математического ожидания QH числа требова c ний в подсети H сети N.

Рассмотрим метод динамического управления интенсивностями об служивания в сети N c. Так же, как и в главе 2, предполагается, что в сети обслуживания реализована централизованная система управления. Различа ются нормальные и коррективные такты функционирования сети. Обозна чим через µ ( k ) = ( µi( k ) ), i = 1, K, L, – вектор интенсивностей обслуживания, используемых в Si в течение такта x (k ), а через Q H ) – число требований (k в подсети H в момент (k ) окончания такта x (k ).

В момент (k ) выполняются следующие действия: 1) определение Q H ) ;

2) проверка выполнения неравенства QHk ) QH. Если неравенство вы ( (k полняется, то такт x ( k +1) считается нормальным и в течение этого такта ис пользуется вектор µ (k +1) = µ, в противном случае этот такт – коррективный, формируется зависящий от Q H ) вектор µ ( k +1) = µ ( k +1), значения компонент ~ (k которого направляются базисным системам и используются в течение ~ ( k +1). После окончания такта x ( k +1) в момент ( k +1) производится очеред x ное выполнение действий 1) и 2) и т. д.

Предлагается следующий метод формирования коррективного век тора µ ( k +1) = ( µ i( k +1) ), i = 1,K, L. Значения µ i( k +1) находятся с использова ~ ~ ~ нием теоремы 3.1, как решение соответствующей задачи оптимизации, ~ a j (jk +1), i J, i( k +1) L ~ ~ ~ ( k +1) = ( k +1) + µi ~( k +1) i H 0 U ai j = где Hk0 1) – интенсивность потока требований из H в S0, ~( + ~( + Hk0 1) = µ 0 ( s0 s0k ) e µ 0 ) /(1 e µ 0 ), ( а i( k +1) – интенсивность потока требований в S i, ~ ~ ~( + i( k +1) = Hk0 1)i 0.

Здесь s0 – математическое ожидание числа требований в S 0 сети N, s0k ) – ( число требований в S0 сети N c в момент (k ).

Округлим с избытком Q H до целого числа q. Для каждого из D = Q q + 1 значений Q Hk ) Q H формируется используемый в течение кор ( рективного такта вектор µ (r ), r {1,K, D}. Определим разбиение множества X состояний сети N c на подмножества X ( 0), X (1), …, X (D ) такие, что X (0) = {s ( n ) X | 0 QH q 1}, X ( j ) = {s ( n ) X | QH = j + q 1}, j = 1,K, D.

c c Множество X ( j ), j {0,1,K, D}, назовем агрегированным состоянием с но мером j сети N c. Обозначим через B ( j ) множество номеров состояний се ти N c из множества X ( j ).

Предлагаются два метода анализа сети N c с типовой структурой и ди намическим управлением интенсивностями обслуживания. В основе первого метода анализа лежит предположение о достижении сетью к моменту окон чания такта стационарного режима.

Пусть сети N и N (r ), r {1,K, D}, с векторами интенсивностей об служивания соответственно µ и µ (r ) отличаются от N c только отсутствием в них управления. Стационарные вероятности P(s ) и P ( r ) ( s ), s X, состоя ний сетей N и N (r ) определяются по формулам:

1 L i 1 L i, ;

s s i i G s0 ! i = 0 µ i s0 ! i = 0 µ i P( s ) = G= s X i i 1 L i P ( s) = (r ) (r ), G =.

s s i L µ s0 ! i = 0 µ i( r ) (r ) (r ) G s0 ! i = 0 i s X Стационарные распределения = ( j ) и = ( j ), j = 0,1,K, D, (r) (r) вероятностей агрегированных состояний сетей N и N (r ) определяются вы ражениями:

j = P ( s ), (jr ) = P ( r ) ( s).

s X ( j ) s X ( j ) Теорема 3.5. Стационарное распределение = ( j ), j = 0,1,K, D, ве роятностей агрегированных состояний сети N c является решением урав нения =, где 0 1 L D (1) ( 0 1(1) L D) = L L L, (D) 1( D ) L D ) L 0 (D j = 0 j = 1.

D с условием нормировки Следствие 3.1. Если известны стационарные характеристики g i и g i(r ), r =1,K, D, сетей N и N (r ), то соответствующая стационарная характеристика сети N c D g i( r ) r.

g ic = g i 0 + r = Поскольку в основе данного метода анализа сети N c лежит предполо жение о достижении сетью к моменту окончания такта стационарного ре жима, то при использовании этого метода необходимо задать величину ошибки приближения эволюции сети N c к стационарному режиму.

Теорема 3.6. При t e = ln(Q ) µ 0 режим эволюции сети N c явля ется стационарным с известной ошибкой.

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

В основе второго предлагаемого метода анализа лежит описание эво люции сети N c случайным процессом с непрерывным временем и конеч ным множеством состояний B, который представляет собой последователь ность фрагментов, соответствующих нормальным и коррективным тактам функционирования сети (аналогично описанию в главе 2). Фрагментами реа лизаций процесса являются реализации цепей Маркова C и C ( r ), ~ r {1,K, D}, с множеством состояний B и непрерывным временем. Эволю ция сети N c в течение нормальных тактов описывается цепью C с множе ством начальных состояний B ( 0), а в течение коррективных тактов – цепями C ( r ) с множествами начальных состояний B (r ) соответственно. Длительно ~ сти реализаций цепей C и C ( r ) равны. Обозначим через P (t ) = ( pm )n ), ~ (t P (t ),( r ) = ( ~mt ),( r ) ), m, n = 1,K, c X, матрицы вероятностей перехода за время t ~ p( n цепей Маркова C и C ( r ) соответственно.

~ Теорема 3.7. При заданном значении стационарное распределение = ( n ), n = 1,K, c X, сети N c существует, является единственным и удовлетворяет уравнению = P, где P = ( p m n ), m, n = 1,K, c X, pm n, m B ( 0), ( ) = ~m n, m B, r {1,K, D}.

pm n p ( ), ( r ) (r ) Очевидно, c = D n.

r =1 s ( n ) X ( r ) Стационарные характеристики сети N c вычисляются по формулам, приведенным в теореме 2.12, с использованием математических ожиданий интенсивностей обслуживания в базисных системах D n + µi( r ) n, i = 1,K, L.

µ ic = µi (n) ( 0) (n) X (r ) r = X s s Математическое ожидание длительности реакции сети N c для S L c= sic.

c µ 0 s0 i = Как показывают результаты численного и имитационного моделиро вания, предложенные методы анализа обеспечивают возможность определе ния с удовлетворительной точностью стационарных характеристик замкну тых экспоненциальных сетей массового обслуживания с типовой структурой и динамическим управлением интенсивностями обслуживания при различ ных длительностях тактов. Длительность такта в сетях этого типа, являясь одним из основных параметров метода управления, в существенной степени определяет качество функционирования сетей.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ 1. Разработаны методы динамического управления интенсивностями обслуживания в замкнутых экспоненциальных сетях массового обслужива ния с произвольной и типовой структурами.

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

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

СПИСОК ЛИТЕРАТУРЫ 1. Башарин, Г.П. Анализ очередей в вычислительных сетях. Теория и методы расчета / Г.П. Башарин, П.П Бочаров., Я.А. Коган. – М.: Наука.

ГРФМЛ, 1989. – 336 с.

2. Боровков, А.А. Асимптотические методы в теории массового об служивания / А.А. Боровков. – М.: Наука, 1980. – 384 с.

3. Жожикашвили, В.А. Сети массового обслуживания. Теория и при менение в сетях ЭВМ / В.А. Жожикашвили, В.М. Вишневский. – М.: Радио и связь, 1988. – 192 с.

4. Клейнрок, Л. Теория массового обслуживания / Л. Клейнрок. – М.:

Машиностроение, 1979. – 432 с.

5. Митрофанов, Ю.И. Анализ сетей массового обслуживания / Ю.И. Митрофанов. – Саратов: Научная книга, 2005. – 177 с.

6. Уолренд, Дж. Введение в теорию сетей массового обслуживания / Дж. Уолренд. – М.: Мир, 1993. – 336 с.

7. Jackson, J.R. Networks of waiting lines / J.R. Jackson // Oper. Res. – 1957. – V. 5, № 4. – P. 518-521.

8. Kelly, F.P. Reversibility and stochastic networks / F.P. Kelly. – London, Wiley, 1979. – 230 p.

9. Reiser, M. Mean-value analysis of closed multichain queueing net works / M. Reiser, S.S. Lavenberg // J. ACM. – 1980, V. 27, №. 2. – P. 313-322.

СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ 10. Долгов, В.И. Метод анализа сетей массового обслуживания с ди намическим управлением интенсивностями обслуживания / В.И. Долгов, Ю.И. Митрофанов, Е.С. Рогачко // Известия Сарат. ун-та. Нов. серия. Серия Математика. Механика. Информатика. – 2009. – Т. 9, вып. 3. – С. 22-27.

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

11. Долгов, В.И. Модели и методы анализа сетей массового обслужи вания с динамическим управлением интенсивностями обслуживания / В.И.

Долгов, Ю.И. Митрофанов, Е.С. Рогачко // Обозрение прикладной и про мышленной математики: Тез. докл. X Всерос. симпоз. по прикл. и пром. ма тем., Санкт-Петербург, 19–24 мая 2009 г. – М.: Науч. изд-во «ОПиПМ», 2009. – Т. 16, вып. 2. – С. 323-324.

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

12. Долгов, В.И. Исследование сетей массового обслуживания с управ лением интенсивностями обслуживания / В.И. Долгов // Обозрение при кладной и промышленной математики: Тез. докл. VI Всерос. симпоз. по прикл. и пром. матем., Сочи–Дагомыс, 1–7 окт. 2005 г. – М.: Науч. изд-во «ОПиПМ», 2005. – Т. 12, вып. 4. – С. 949-950.

13. Долгов, В.И. Динамическое управление интенсивностями обслу живания в сетях массового обслуживания / Ю.И. Митрофанов, В.И. Долгов // Автоматика и вычислительная техника. – 2008. – № 6. – С. 44-56.

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

14. Долгов, В.И. Сети массового обслуживания с управлением интен сивностями обслуживания: синтез, метод управления, исследование / Ю.И. Митрофанов, В.И. Долгов;

Сарат. гос. ун-т. – Саратов, 2005. – 26 с. – Деп. в ВИНИТИ 13.05.05, № 688-В2005.

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

15. Долгов, В.И. Исследование зависимости характеристик сетей мас сового обслуживания с управлением интенсивностями обслуживания от то пологии сетей / В.И. Долгов;

Сарат. гос. ун-т. – Саратов, 2005. – 23 с. – Деп.

в ВИНИТИ 25.05.05, № 744-В2005.

16. Долгов, В.И. Исследование зависимости качества функционирова ния сети массового обслуживания с управлением интенсивностями обслу живания от реакции системы управления сетью / В.И. Долгов // Теоретиче ские проблемы информатики и ее приложений: Сб. науч. тр. – Саратов: Изд во Сарат. ун-та, 2006. – Вып. 7. – С. 47-51.

17. Долгов, В.И. Имитационная модель сети массового обслуживания с динамическим управлением интенсивностями обслуживания / В.И. Долгов // Компьютерные науки и информационные технологии: Матер. Междунар.

науч. конф., Саратов, 1–4 июля 2009 г. – Саратов: Изд-во Сарат. ун-та, 2009. – С. 80-83.

18. Долгов, В.И. Моделирование сети массового обслуживания с управлением интенсивностями обслуживания / Ю.И. Митрофанов, В.И. Долгов, Е.П. Станкевич // Компьютерные науки и информационные технологии: Тез. докл. Междунар. науч. конф., посвящ. памяти проф.

А.М. Богомолова, Саратов, 1–4 июля 2007 г. – Саратов: Изд-во Сарат. ун-та, 2007. – С. 83-85.

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

Работы [10–12] опубликованы в журналах, включенных в перечень ВАК ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертации на соискание ученой степени кандидата наук.

Подписано в печать 17.09.2010 Формат 60х84 1/16. Бумага офсетная.

Гарнитура Times. Печать RISO. Объем 1,0 печ.л. Тираж 100 экз.

Отпечатано с готового оригинал-макета Центр полиграфических и копировальных услуг Предприниматель Серман Ю. Б. Свидетельство № 410000, г. Саратов, ул. Московская, 152, офис

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

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