Анализ выходных потоков управляющих процессов обслуживания тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

ПРОЙДАКОВА Екатерина Вадимовна

АНАЛИЗ ВЫХОДНЫХ ПОТОКОВ УПРАВЛЯЮЩИХ ПРОЦЕССОВ ОБСЛУЖИВАНИЯ

01.09 — Дискретная математика и математическая кибернетика

□□3169 115

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 5 МАЙ 2008

Нижний Новгород — 2008

003169115

Работа выполнена на кафедре прикладной теории вероятностей факультета вычислительной математики и кибернетики Нижегородского государственного университета им Н И. Лобачевского.

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

Федоясин Михаил Андреевич

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

Ушаков Владимир Георгиевич (г Москва)

доктор физико-математических наук, профессор 1 Жильцова Лариса Павловна (г. Н Новгород)

Ведущая организация: Российский университет дружбы народов

(г Москва)

Защита состоится г в -¿У час. ^СО мин на заседа-

нии диссертационного совета Д 212.166.06 при Нижегородском государственном университете им Н И Лобачевского по адресу: 603950, г Нижний Новгород, пр Гагарина, 23, корпус 2, конференц-зал ННГУ.

С диссертацией можно ознакомиться в фундаментальной библиотеке Нижегородского государственного университета им. Н И Лобачевского.

С текстом автореферата можно ознакомиться на официальном сайте Нижегородского государственного университета им Н И. Лобачевского http://www.unn га

Автореферат разослан « » ¿¿пфг^и^ 20081

Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент

в.и

Лукьянов

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

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

Первые результаты в области выходных потоков были получены в 60-е годы XX века такими математиками, как П Дж Берк (PJ Burk), ДжВ Коэн (JW Cohen), Е Рейч (Е. Reich) и П.Д Финч (Р D Finch) Данные результаты касались только простейших систем' рассматривалась одноканальная система обслуживания с неограниченной очередью, входной поток полагался пуассоновским, обслуживание требований осуществлялось по показательному закону В нашей стране выходными потоками в разное время занимались Б В Гнеденко, ИЛ. Коваленко, ГШ Цициашвшш, И И Ежов, Н.В Маркова, В Ф Каданков и др Данные авторы, как правило, также рассматривали одноканальные системы, но уже с некоторыми усложнениями, касающимися вида входного потока, дисциплины формирования очереди и механизма обслуживания При этом выходной поток всегда описывали аналогично входному, используя для этого один из следующих эквивалентных способов

1) задавали случайный процесс {£(/); t > 0}, где ^г) при I > 0 определяет число обслуженных системой заявок за промежуток времени [0, t)n £(/) = £(<—0), ¿(0) = 0,

2) указывали случайную последовательность {(г/, £), t Z1}, в которой через t'i и обозначены соответственно t-й момент появления требований на выходе и число требований обслуженных системой в этот момент времени

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

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

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

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

Методы исследовании. Для построения моделей выходных потоков управляющих систем обслуживания применялся кибернетический подход, методологически разработанный А А. Ляпуновым и С В Яблонским (Ляпунов А А, Яблонский С В Теоретические проблемы кибернетики// Проблемы кибернетики. - М Физматгиз, 1963 - С 5-22) и развитый МА Федоткиным в ряде работ {Федоткин М А Процессы обслуживания и управляющие системы //Математические вопросы кибернетики. - М Наука, 1996 - Вып. 6 - С 51-70, Федоткин МА Нелокальный способ задания управляемых случайных процессов // Математические вопросы кибернетики - М Наука, 1998 - Вып. 7 - С 333-344) Использовались аппарат теории случайных процессов, методы математической кибернетики и

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

Теоретическая и практическая ценность. Данная работа была выполнена в рамках следующих госбюджетных НИР, проводимых на кафедре прикладной теории вероятностей ННГУ и в лаборатории теории вероятностей и математической статистики НИИ прикладной математики и кибернетики при ННГУ. «Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации» (номер государственной регистрации 01 2 00 1 07703), «Анализ дискретных управляющих систем обслуживания и систем вычисления булевых функций» (номер государственной регистрации 01 2 00 6 02598)

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

Основные результаты, выносимые на защиту. Ниже приведены наиболее существенные результаты диссертации, выносимые на защиту

- Эффективность применения кибернетического подхода при построении математических моделей выходных потоков в циклической и приоритетной системах

- Способ проведения классификации состояний марковских последовательностей

- Метод исследования предельных свойств многомерных марковских последовательностей, которые являются математическими моделями выходных потоков

- Способ определения области квазиоотвмальных параметров управления конфликтными потоками

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

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

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

1. Международная конференция «Прикладная статистика в социально-экономических проблемах» (Нижний Новгород, 2003 г.)

2. Научно-техническая конференция «Математика и кибернетика 2003» (Нижний Новгород, 2003 г.)

3. VI Международный конгресс по математическому моделированию (Нижний Новгород, 2004 г.).

4 Десятая междисциплинарная научная конференция «Нелинейный мир» (Нижний Новгород, 2005 г.)

5. Международная научная конференция «Математические методы повышения эффективности информационно-телекоммуникационных сетей» (Гродно, 2007 г.)

По теме диссертации опубликовано 15 работ, из них 4 в изданиях, рекомендованных ВАК Российской Федерации для публикации материалов диссертации. Совместно с научным руководителем выполнено 13 из 15 работ.

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

2. КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

конфликтных потоков должно происходить в непересекающиеся промежутки временя Также допускаются промежутки переналадок, разрешающие проблему конфликтности потоков, например, проблему безопасности движения транспорта на перекрестке Под обслуживанием машин понимается их переезд через перекресток Смена состояний обслуживающего устройства (автомата-светофора) осуществляется по циклическому алгоритму Г{1) Г™ -» •• Г1** - Гт ■ В состоянии Г® " где J=\,m, разрешается групповое обслуживание требований только из потока Пу с интенсивностью /4 В состоянии I^ также пропускается группа заявок только из потока П;, но уже с интенсивностью^'¡>1^ Длительности состояний Г{[\У®,. ,Г(2я) известны и равны Т\, Т-1, , Тъп единиц времени соответственно

Для построения математической модели изучаемой системы обслуживания используется так называемый «кибернетический» подход, при котором на систему смотрят не с позиции «черного ящика», а с точки зрения общего понятия управляющей системы. Следуя методологии кибернетического подхода для управляющей системы необходимо определить дискретную временную шкалу функционирования, а затем выделить схему, информацию, координаты и функцию Для схемы, в свою очередь, определяются составляющие блоки, входные и выходные полюсы, внешняя память, внутренняя память, устройство по переработке информации внешней и внутренней памяти. Стоит отметить, что проблема определения временной шкалы является сложной, поскольку не существует методики или алгоритма выбора моментов наблюдения за системой В работе управляющая система наблюдается в дискретные моменты времени г„ I = О, I, ..., переключений состояний обслуживающего устройства (фаз светофора) или на каждом из промежутков [т„ г, + 1) Дискретная шкала функционирования системы определяется случайной последовательностью {г„ 1 = 0, 1, . } Здесь момент начала функционирования системы совпадает с моментом переключения фазы обслуживающего устройства. В нашем случае входные потоки Пь Щ, , Пм первичных требований — это первый тип входных полюсов для управляющей системы обслуживания. Потоки насыщения Щ, Щ, П'п (выходные потоки системы при ее максимальной загрузке и эффективном функционировании) — второй тип входных полюсов Накопители очередей по входным потокам — внешняя память. Устройства по организации дисциплины очередей в накопителях или стратегии обслуживания требований — блок по переработке информации внешней памяти. Обслуживающее устройство (автомат-светофор) с 2т состояниями Г(|), ГС),..., Г<2я) — внутренняя память Алгоритм смены

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

Считаем, что рассматриваемые в работе случайные объекты заданы на вероятностном пространстве (0,3, Р()), где — множество описаний всех элементарных исходов системы, 3 — <г-алгебра событий А с О, а Р(А) — вероятность исхода А е 3. Описание составляющих блоков схемы осуществляется при ] =1,т, 1 = 0,1,. с помощью следующих случайных величин и элементов, заданных на (0,3, Р()):

1) ц,, — число заявок потока Пу, обслуженных за промежуток времени [г,, т, + |), 1уу, е Х= {0,1,...}; 2) — максимальное число требований, которое может быть обслужено за промежуток [ц, т, + 1) из очереди потока Пу, ^, е {0, /у, /,}, здесь [ — максимальное число заявок потока Пу, которое может обслужиться за время работы состояния " и ^ = \р) Ту - 1З, а I] — максимальное число требований потока Пу, которое может обслужиться за время работы сигнала Г®0 и /у = Ю Ту], причем /у > I), поскольку Ту-х» Ту, 3) Л — состояние обслуживающего устройства на промежутке времени [гь г( + 0» Л с Г = {Г(", Г®,.., Г0"'}; 4) агу, / — длина очереди по потоку Пу в момент времени % где е X; 5) , — число реально обслуженных требований потока П/ за промежуток времени [г„ Г/ + , е У, = {0,1,. , /у}, 6) — число реально обслуженных заявок потока Пу за промежуток времени [0, причем е Уу При 7 = 1,т, семейства , г =0,1,.. } и , »=0,1, } случайных величин

соответственно определяют потоки насыщения и выходные потоки системы

В соответствии с методикой кибернетического подхода определялись функциональные и статистические связи между блоками схемы Требования из очереди потока Пу отбираются согласно экстремальной стратегии механизма обслуживания, для которой при I = 0, 1, .., ^ = \,т, выполняется , = гшп{жу , + ¡, ,}. Пусть функция

б

I/(Л(,)) Г —► Г принимает значение Г(1> при г = 2ти значение Г<г + 11 в остальных случаях, т е при г е {1, 2 ,2т - 1}. Тогда для Л + 1 справедливо соотношение Л + 1 = = £/(Л), 1 = 0, 1, Поскольку входные потоки предполагаются пуассоновскими, то

Р(»г,. = «у 1л = г(г>) = (Л/,)"'(и,!)-'ехр{-я/г} = ?}(«,, 7», «( 6Х,;=йг = 1> Для случайной величины ¿5, / при 7 =1,ш имеет место вырожденное условное распределение следующего вида Р(£/. / = V I Г, = Г<г)) = Д Г<г)), где

1 при у = г = 2/-1,

1 при у = /у, г = 2),

1 при у = 0, г е {1,2,. 2/п}\{2/ —1,2/};

0 в остальных случаях

Входные потоки Пь Пг, , П„ и потоки насыщения П'1( П'г, .., П'„ считаем независимыми. Состояние циклической системы по потоку Щ на промежутке времени [гь г, +1) характеризуется случайным вектором (Л> „ , _ 1) Поведение системы по потоку П, описывается векторной последовательностью {(Л, ге,, /, 1), ¡2: 0}, которая определяет динамику состояний обслуживающего устройства, флуктуацию длин очередей по потокам и флуктуацию обслуженных требований. Данная последовательность задает я нелокальное описание выходного потока по 7-му направлению, причем за выходной поток отвечает §,1-1, а компоненты Л и играют роль меток.

В силу независимости входных потоков, потоков насыщения и циклического переключения состояний светофора процесс обслуживания можно рассматривать отдельно по каждому потоку Это позволяет свести задачу анализа выходных потоков системы размерности (2т + 1) к трехмерной задаче В случае циклической системы все рассуждения проводятся для произвольного 7-го потока. Предполагается, что в начальный момент ц> задано распределение вектора (Го, о, §, -0. то есть известны вероятности Р(Го = Г(1), г,, о =х, Щ и = у), Г(1> е Г, х е X, у е У/ Условное распределение каждой из случайных величин гуг„ $.1-1 зависит от выбора вектора Ь = {Т\, Тъ , Гь,) Назовем вектор Ь управлением т конфликтными потоками в циклической системе обслуживания, здесьЬеЖ= {(Гь Т2, , Т^У Т\ >0, Тг>0, . , Гг«>0}

В первой главе диссертации изучены свойства конечномерных распределений управляемой последовательности {(Л, аеу, „ ¿¡¡,1-1), «£ 0} при фиксированном значении

Ь е 31 и доказаны утверждения, приведенные ниже В частности доказано, что при

г = О, 1,. ., для последовательности {(Л. щ ¡, (- О; I й: 0} имеет место рекуррентное соотношение(Г(+1,!ЕЛ(+1, ,) = (!/(Л), тах{0,а5Л,+ ту 4,},шт{ш7,, + »&/,§.(})

Кибернетический подход требует на этапе построения математической модели так выбирать шкалу {г(; I £ 0} тактов времени, чтобы можно было определить конечномерные распределения управляемой последовательности {(Л, аел ¡, ,_ |),« £ 0} Если дискретные моменты времени г( были выбраны удачно, то векторная последовательность {(Г/, щ, I, I -1), I ^ 0}, как правило, обладает свойством марковости Далее нумерация теорем и лемм в автореферате соответствует принятой в диссертации

Лемма 1. При заданном распределении вектора (Го, ж,-, о, .■) управляемая последовательность {(Г/, ее;, 1, &1-1); / £ 0} является марковской Введем обозначения

Р«Л = Л(а>,=у}) = 0.,(Л('>;х,>>), Г(/) = Г\{Гй",Г»+'),Г»+2)}, Г(0 = Г\{Л(ЗД,Г{ч + "};

£У(Г(,))= {(Г(1),х,0) лее X}, Л(5) еГ0); £,(Г<ад)={(Г®, *,(,) хеХ} и {(Г«>,0,у) ^=57^1},

Лемма 4. Пространство состояний последовательности {(Л, ,, , _ О,' £ 0} разбивается на незамкнутое подмножество {(Л®, х, >>): Лм е Г'(/), х е X, у = 1,/у} и и «Л «>, х, у) хеХ\{0},у = 01р1} и {(Л » + х, у) х <= X, у = 1]Щ} и 11 {(Г®+ х, у)- х е X \ {0}, у=0,/} -1} несущественных состояний и на замкнутое

2м , .

подмножество и £у(Л'') существенных периодических состояний с периодом 2т

г-1

В первой главе диссертации получены рекуррентные по I соотношения для одномерных распределений {0, , (Л(5), х, у) Л(1) € Г, х е X, у е У,} последовательности {(Л. аеу 40,1^0}. Также найдены рекуррентные соотношения для производящих

функций Ф, ,(/ч*>,^г)= £ ДЛ^.х.^г' за один такт работы системы и для ПрОИЗ-

^т - О

«о 2м

водящих функций Ф/2»,(Л(1);г.г)= Ее, ^.^'.Х.^Г* за период Т = УТГ, где

I = 0, 1, ., Г(,) б Г, > е Уу, | г | < 1. Данные соотношения использовались при доказа-

тельстве предельных теорем.

Теорема 4. Для существования стационарного распределения последовательности {(Гь гед I, 1 -1), г S 0} необходимо и достаточно выполнение следующего неравенства

^г-/,-/;< 0

Установлено, что в циклической системе обслуживания возможно существование стационарного распределения как для отдельного потока П/, j =1, m, так и для всей системы, в зависимости от выполнения либо только одного неравенства Х,Т -lj- lj<Q при некотором у, или же m неравенств XjT- lj-lj<0, j=l,m.

Во второй главе работы рассматривается приоритетная система управления m пуассоновскими конфликтными потоками ITi, Пг, , П„. Поступающие в систему потоки делятся на три типа* П) — поток малой интенсивности, заявки которого пользуются приоритетом при обслуживании, Щ , I~U._ i — потоки средней интенсивности и без приоритетов, Пя — интенсивный поток без приоритетов Приоритет первого потока заключается в том, что если поступила хотя бы одна заявка по этому направлению, то она должна быть обслужена как можно быстрее, но не прерывая при этом уже проводящееся обслуживание других требований Такой алгоритмы в настоящее время используются, например, для управления интенсивным потоком транспорта на основной магистрали и приоритетным неинтенсивным потоком пешеходов, когда появление пешехода фиксируется кнопкой вызова. Как и в первой главе, предполагается независимость входных потоков Пь П2,. , Пя и потоков насыщения П \, П 'г, , П Характеристики системы также изучались в дискретные моменты времени rh i = 0,1, ., переключений состояний светофора или на каждом из промежутков [r„ г, + |)

Укажем при j = \,m и i = 0,1, основные отличия приоритетной модели от циклической. В случае приоритетной модели обслуживающее устройство имеет 2m + 1 состояние Г(1), Г®,.., Г(2л,), Г{2т +1), длительности Т\, Г2) , Тъ, + i состояний известны Здесь добавляется новое состояние + '' в котором обслуживается только поток П„ с интенсивностью ц"т > ц„ Каждый из элементов Л принимает значения из множества Г = {Г(|), Г®,. , Л'2" + Случайная величина j = 1, m -1, принимает значения из множества {0, lj, lj}, а £»,/ из множества {0, /'„, 1"я, /„), где 1"т — максимальное число требований потока П„, которое может обслужиться в состоянии Г12" + '' обслуживающего устройства и 1"т = [//"„Га, + |], причем 1п > /"„, поскольку ТЬя-\»Т2я^\ Случайная величина , принимает значения из множества Yj = (0, 1, , lj} Для приоритетной модели отличается вид функции fy (v,

/»,<у,Г(г>) = <

1 при v = /y, г = 2/-1, j = l,m, 1 при v = /y, г = 2/, y = l,m; 1 при v-l"„, r = 2m + 1, 7=m,

ЩГ^, wi, ui) =■<

1 при v = 0, re {1,2,. ,2m + l}\{2/~ 1,2/}, j = l,m-l; 1 при v = 0, r 6 {1,2, ,2m+l}l{2m-l,2m, 2m + 1}, j = m, О в остальных случаях

Функция 1/(Г(г), wi, «О определяется следующим образом f Г(1) при r = 2m, Г"+,> при г = 1,2т-2; Г(2я) при ге {2ni-l,2m+l},H>i=0,Ui >0, Г0"0 при г 6 {2т - 1,2т + 1}, wi > 0, ^р{2т +1) при rg {2m-l,2m+l},w, = u,=0.

Соотношение Г, + i = (/(Л, «|, /, 71,,), »= 0,1, ., определяет некоторый однородный алгоритм с упреждением, который управляет изменением структуры обслуживающего устройства по информации о наличии заявок в очереди по потоку üi н по информации о текущем внутреннем состоянии. Данный алгоритм основывается на минимальном количестве информации о состоянии системы и поэтому легко может быть реализован

Случайные величины iji( и § j =l,m, являются независимыми при условии, что состояние обслуживающего устройства известно Во второй главе работы изучаются вероятностные свойства последовательности {(Л, sei,/, §л. / -1); / > 0) Вы-

бор данной последовательности обусловлен тем, что она определяет поведение системы как по информативному потоку Пь так и по наиболее интенсивному потоку П»

Для последовательностей {(Г,, ае,, ,, Х2,,, , aem,/, fi.i-i, . i -1), > 2 0},

{(Г/,агм, £ ,_!);< £0}, {(Г„ №),<>%* §,/-1), '^0}, ./ = 2, т-\, могут быть по-

лучены аналогичные результаты В начальный момент времени ц задано распределение вектора (Го, »1, о, ®м, о> И, -и |я. -О- Ниже приведены основные утверждения, доказанные во второй главе диссертации

Для последовательности {{Г,, ®1,<,»»,,/, &1-1, £¡.,/-1); ¡¿0} прн/ = 0,1, ., имеет место следующее векторное рекуррентное соотношение.

= ({/(Г,, ®1,,, 1} 1,¡), ,, Щ,I, ,), Ут(&т ¡), т I, <Ич), С^т.1,

Г] («у,» % 1> ')= тах {°> I + *Ь. I ~ $ '}• й ь Я. <> ') = / + 1. ь 41},] = 1, т

Лемма 5. При заданном распределении начального вектора (Ль ®1, о, к™, о. £1. -ь 4т, -х) управляемая случайная векторная последовательность {(Л, «|, /. ае»! /. 6./-], ¿¡г./-О, '2:0} является марковской

Проведена полная классификация по Колмогорову состояний управляемой марковской последовательности {(Л. ®1. ь » 4>, I- I» 5т /-1)>1 ^ °}> доказано, что пространство Е ={(Л(,),*|,х„,Л(,) е Г,xi,жяе Х,>>| 6 УьД'« е У*} ее состояний распадается на незамкнутое множество несущественных состояний, и на минимальное замкнутое множество существенных сообщающихся апериодических состояний

Введем обозначение Р({Л +1 =Г('\ ®1,/ + | =х\, ае„ , +1 =хя, |и=}>ь !»,(=%,)) = = й - «С*4*, хл-,у\, у»), Гы 6 Г, xi, 6 X, 6 У,, ут е У« i = 0,1,

Получены рекуррентные соотношения для одномерных распределений Ш. (Л(1), X!; хл, уи у„). Ги) е Г, хь хт е X, ух е У|, уп е Уя} последовательности

{(Л,ае|,„®ш.« ¿»./-О.'^О}.

Доказано, что для {(Л, «1,1, 6 / -1> / -1), (5 0} либо существует стационарное движение, либо )ш{} ,(1*г);х],хя,у1;уя) = 0 для всех (Г<г),хихту1,уя) е Е

Также были найдены рекуррентные соотношения для производящих функций

ФЛГ*'\у1,уя,г1,гя) = Е £ ФЖ'\у„ут.0:гв) =

1.-0 1,-0

= И 1-0,1, , г(1) 6 г, у, 6

е У1, >>„ е Уя, | п | < 1, | 2п | < 1. Полученные соотношения существенно использовались при доказательстве следующих предельных теорем

Теорема 9. Если справедливо Х\Т-1\~1\ > 0, то имеет место предельное равенство 1ип()1(Г*'\х1,хт,у1;ут) = 0 для всех (Ги, хт,уиут) е Е.

Теорема 10. Пусть Х\Т-1\-1'\ =0,тогда ¡1ш2,(Г(г),д:|,хя;>'|,у111) = 0 для любого состояния (ГЧхьдГя.^ьД'т) е Е

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

тогдадля любого (Г'^.хихя,^,^) е Е справедливо 1ш10((Г<',,дс|,дс(1|,>>|;гу111) = 0

Теорема 13. Для существования стационарного распределения марковской последовательности {(Г/, »i, ь аей, (, 1, ¿я, I -1), » S 0} достаточно выполнения двух неравенств Д,Г-/|-/'!<0, XJ-lm-l'm<0

В третьей главе изучение систем продолжается средствами имитационного моделирования Дня рассматриваемых систем не удается аналитически определить законы распределения выходных потоков, найти среднее время ожидания начала обслуживания заявки по потокам и средние длины очередей Чтобы получить численные оценки этих и других характеристик и определить квазиоптимальное управление, была создана имитационная модель систем Программная реализация имитационной модели выполнена на основе Borland Turbo Delphi Explorer При моделировании предполагалось, что машины обслуживаются как группами, так и последовательно по одной по мере поступления в систему В качестве примера в работе приведены численные результаты для последовательного обслуживания двух потоков (от = 2) В случае циклической системы считали, что выбраны два наиболее интенсивных транспортных потока.

С целью оценивания стационарных характеристик, моделирование проводилось в два этапа. На первом этапе определялся момент вхождения системы в квазистационарный режим Для этого вычислялись оценки среднего времени ожидания начала обслуживания произвольной машины для двух систем В первой системе в начальный момент времени очереди были пусты (х, „ = х2 „ = 0), а во второй определялись по форму-

4 _

лам х10 = [Л/Г], j = 1,2, Т = £ Тг На i-м шаге вычислялись значения , и ,

г = I

7 = 1,2 оценок среднего времени ожидания начала обслуживания машины по каждому потоку в первой и второй системе соответственно Затем определялись значения ,

/Г, где = ,+Л2Му% ,)/(А, +Л2), ^ =(Л,М^(+Л2М^ ,)/(А,+Л2) При вы-

полнении условия — yf j > Syf переходили к (j + 1 )-му шагу В противном случае, то есть когда выполнялось < ôyf, считали, что система достигла квазистационар-

ного режима и фиксировали время переходного процесса /„, здесь 5 - 0,05 На втором

этапе, продолжающем траекторию первого, находились значения Му, и оценок среднего времени ожидания начала обслуживания машины по первому и второму потокам в секундах; значения у оценки среднего времени ожидания начала обслуживания произвольной машины в секундах, где /=(Л,Му,+Л2М/2)/(Л1 + Я2),значения М*-, и М*г2 оценок средней очереди перед зеленым светом по первому и второму потокам в

машинах Здесь агу,, = л^, у = 1,2, определяет очередь в квазистационарном режиме по 7-му потоку непосредственно перед переходом светофора в состояние Г® ~ Для выходных потоков вычислялись статистические законы распределения и статистические числовые характеристики В частности для случайной величины ^ , = 1, 2, определяющей в квазистационарном режиме число обслуженных машин за время, пока светофор находится в состоянии вычислялись статистический ряд распределе-

ния, выборочное математическое ожидание М(О^) и выборочная дисперсия Все численные оценки были получены с точностью е = 0,01 и надежностью а = 0,99 Решалась задача оптимизации по критерию у' -> шш Рассматривалась загрузка р) = Х,Т(р)Т1]_х + системы по у-му потоку, у = 1, 2. Общая загрузка системы

определялась как р=тах{р,,р2} Исследовался разброс оценок у при разных загрузках системы Разброс оценок определялся по формуле с* '100%, где у'^ - наибольшее значение оценки у', среди полученных по 10 различным реализациям, а у'^ — наименьшее

Моделирование производилось при значении параметров, удовлетворяющих необходимым и достаточным условиям существования стационарного движения в обеих системах. Из физических соображений на величины Г|, Тг, Т3, Г4, Т5 я Т накладывались ограничения-Г2 > 4, Г4>4, Г5> 4, Г1>Г2, Г3>Г4, Т >60, Т < 120 Таким образом, при существующих ограничениях область поиска квазиоптимальных параметров имела вид Яс= {(ГЬГ3) Г,^4,Г3й4, Г| +Г3 2:52, Г, + Г3 < 112, А|(Г, + Г3 + 8)-/,-/', < 0, Хг(Т\ + Г3 + 8) - к - 12 < 0}. В качестве примера в таблице 1 приведены значения оценок Мух, Му2, у', Мят, и Млг2 в случае циклической системы для различных Г при фиксированных параметрах Тг = Г4 = 4, ц\ = /ь - 1, ц\ = ц'г = 1,2, Х\ = 0,7, Ь. = 0,1 и квазиоптимальных значениях Г| и Г3

Г Л Гз Му, М уг Г М*:, м«-2

120 100 12 6,723 54,528 12,698 12,623 10,845

100 80 12 7,638 41,445 11,864 12,782 8,567

80 64 8 6,409 35,056 10,002 10,011 7,046

60 46 6 6,784 26,127 9,202 9,062 5,265

Таблица 1

В данном случае минимальное значение оценки у равно 9,202 и оно достигается на периоде Т= 60 при 71 = 46 и Гз = б, которые и являются квазиоптимальными При квазиоптимальных значениях параметров для первого выходного потока выборочное математическое ожидание М(0,) = 39,166, а выборочная дисперсия 5(0,) = 28,666 Для второго выходного потока соответственно М(02) = 4,922 и Щв2) = 1,904 На рис 1 изображен полигон частот, построенный по статистическому ряду распределения числа машин, обслуженных по первому потоку за время работы состояния .Г(,) светофора при Тг = Г4 = 4, = /<2 = 1, = ц'г = 1 Л, Л, = 0,7, Л2 = 0,1 и квазиоптимальных Ту, Т3

Рис 1

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

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

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

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

В заключение кратко сформулированы основные результаты работы

3 ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

4 СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях, рекомендованных ВАК Российской Федерации:

1 Федотиш, МА Нелинейная модель процесса циклического обслуживания н выходные потоки / М А Федоткин, Е.В. Пройдакова II Известия высших учебных заведений Прикладная нелинейная динамика. Издание Саратовского университета. — Т 13, №3.-2005 —С. 48-60

2 Пройдахова, Е В Математическая модель управления выходными потоками в циклической системе обслуживания /ЕВ Пройдахова, М А. Федоткин // Вестник Нижегородского университета им. Н И Лобачевского Серия Математическое моделирование и оптимальное управление. — 2005 — Вып 2 (29) — С 201-208

3. Пройдахова, ЕВ Определение условий существования стационарного распределения выходных потоков в системе с циклическим управлением /ЕВ Пройдахова, М А Федоткин // Вестник Нижегородского университета им Н И Лобачевского. Серия Математика —2006. —Вып 1(4) —С 92-102

4 Пройдахова, Е В Достаточное условие существования стационарного распределения выходных потоков в системе с циклическим управлением / ЕВ Пройдахова, М А. Федоткин // Вестник Нижегородского университета им Н И Лобачевского Серия Математическое моделирование и оптимальное управление — 2006 — Вып 3 (32) — С 118-126

В иных печатных изданиях

5 Пройдакова, Е В Изучение выходного процесса при нелинейном обслуживании автомобилей на перекрестке с помощью имитационной модели / ЕВ Пройдакова, М А Федоткин // Прикладная статистика в социально-экономических проблемах Материалы Международной конференции (Нижний Новгород, 14-15 февраля 2003г ) В 2-х томах — Т I. — Нижний Новгород, 2003 — С 97-102

6 Федоткин, М А Нелокальное описание выходных потоков в системе с циклическим обслуживанием и переналадками / М А Федоткин, Е В Пройдакова // Математика и кибернетика 2003 Сборник научных статей юбилейной научно-технической конференции факультета ВМК ННГУ и НИИ ПМК Нижний Новгород, 28-29 ноября 2003г — НижнийНовгород,2003 —С 274-278

7 Projdakova, Е V. Mathematcal model of output flows control m cyclic service system / E V Projdakova, M A Fedotkm // Сборник тезисов докладов VI Международного конгресса по математическому моделированию — Нижний Новгород, 2004 —С 115

8. Пройдакова, Е В Нелокальное описание выходных потоков в системе с циклическим обслуживанием и переналадками /ЕВ Пройдакова, М А. Федоткин; Нижегор ун-т - Нижний Новгород, 2004 — 27 с — Деп. в ВИНИТИ 24 11 04 № 1856-В2004

9 Пройдакова, Е В Анализ свойств выходных потоков в системе с циклическим обслуживанием и переналадками / ЕВ. Пройдакова, М А Федоткин, Нижегор ун-т — Нижний Новгород, 2005 — 32 с — Деп в ВИНИТИ 01 04 05 № 442-В2005

10. Федоткин, М А Нелинейные модели в теорий очередей и выходные потоки / М А Федоткин, Е В Пройдакова II Нелинейный мир. Десятая междисциплинарная научная конференция (Нижний Новгород, 27 июня-2 июля 2005г.) Тезисы докладов. — Выл 10. — Нижний Новгород, 2005 — С. 143.

11 Пройдакова, Е В Статистический анализ свойств выходных потоков, возникающих в циклической системе массового обслуживания /ЕВ Пройдакова, М.А Федоткин; Нижегор. ун-т. — Нижний Новгород, 2005 — 29 с — Деп. в ВИНИТИ 27 12 05 № 1755-В2005.

12 Пройдакова, Е В Нелокальное описание выходных потоков в системе массового обслуживания с приоритетным направлением /ЕВ Пройдакова, М А Федоткин; Нижегор ун-т. — Нижний Новгород, 2006 — 62 с — Деп в ВИНИТИ 21 03 06 № 293-В2006

13 Пройдахова, ЕВ. Анализ свойств выходных потоков в системе массового обслуживания с приоритетным направлением /ЕВ Пройдакова; Нижегор. ун-т. - Нижний Новгород, 2006 — 49 с — Деп. В ВИНИТИ 21.12.06№ 1602-В2006

14 Пройдакова, Е. Выходные потоки в системе массового обслуживания с преимуществом/ Е. Пройдакова, М. Федоткин // Массовое обслуживание, потоки, системы, сети Материалы международной научной конференции «Математические методы повышения эффективности информационно-телекоммуникационных сетей» Гродно, 29 ян-варя-1 февраля 2007 г —Вып 19 —С. 210-215.

15 Пройдакова, Е В Необходимые условия существования стационарного распределения выходных потоков в системе с приоритетным направлением / ЕВ. Пройдакова // Вестник Нижегородского университета им. НИ. Лобачевского — 2007. — №1. — С 167-172

Бумага офсетная Печать офсетная Уел печ л 1 Тираж 100 экз

Типография Нижегородстата 603950, Нижний Новгород, ул Ошарская, 64

Введение.

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

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

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

1.3. Кодирование информации блоков схемы циклической управляющей системы.

1.4. Свойства векторной последовательности {(Л, £еЛ„ ^ i); i > 0} и классификация пространства ее состояний.

1.5. Рекуррентные выражения для производящих функций распределений выходных потоков.

1.6. Необходимые и достаточные условия существования стационарного распределения последовательности {(/}, эеу>^i); / > 0}.

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

II. 1. Описание работы управляемой системы обслуживания на физическом уровне и постановка задачи.

11.2. Исследование свойств случайной векторной последовательности {(Л, аги,,■ 1, i-1); / > 0}.

11.3. Рекуррентные выражения для производящих функций распределений последовательности {(Л, aeisaem, ь /- ь i- i)M, i > 0}.

11.4. Предельные теоремы для случайной векторной последовательности {(Л, i, aem>/, £m-I);/>0}.

III. Численно-качественное исследование систем управления конфликтными потоками с использование имитационного моделирования

III. 1. Цели и задачи исследования.

111.2. Программная реализация имитационной модели.

111.3. Качественное исследование основных характеристик изучаемых систем и их выходных потоков посредством имитационной модели.

111.4. Проблема Вебстера—Алсопа о задержках в циклических системах массового обслуживания.

Общая характеристика изучаемой темы

Теория массового обслуживания строит и изучает математические модели возникновения очередей из заявок требований в системах, используя для этого аппарат математической кибернетики, теории вероятностей, марковских точечных процессов и математической статистики. Появление теории массового обслуживания исторически связано с необходимостью рассмотрения простейших задач о задержке вызовов в телефонных системах. Такие задачи впервые были описаны на физическом уровне в 1907 г. в работе Ф.В. Ио-ханнсена [1] и частично решены датским математиком А.К. Эрлангом [2]. Именно работы А.К. Эрланга, выполненные в 1909, 1917 и 1923 годах и посвященные построению и изучению математической модели работы автоматических телефонных станций, стали пионерскими в теории массового обслуживания.

Фундаментальные результаты в области теории массового обслуживания были получены в XX веке такими учеными как: Ф. Поллачек, А.Н. Колмогоров, А.Я. Хинчин, Б.В. Гнеденко, Л. Такач, T.JI. Саати, Д.Р. Кокс, У.Д. Смитл, JI. Клейнрок, С.Н. Бернштейн, К.Пальм, Д.Дж. Кендалл, B.C. Королюк, А. Кофман. С точки зрения практической ценности важное место в этой области занимают работы Г.П. Башарина, Ю.К. Беляева, А.А. Боровкова, Н.П. Бусленко, О.В. Вискова, В.М. Золотарева, Г.П. Климова, И.Н. Коваленко, Ю.В. Прохорова, А.Д. Соловьева и др. Основные результаты данных авторов представлены во многих работах, например [3—11].

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

Первое направление образуют исследования классической системы массового обслуживания с ожиданием или с потерями, а также различных ее усложнений [12—22]. Напомним, что любую классическую систему массового обслуживания определяют три её составляющих элемента: входной поток, обслуживающее устройство, структура и дисциплина очереди. Исследования по данному направлению связаны в основном с рассмотрением более сложного закона распределения промежутка между последовательными поступлениями требований, более сложного закона распределения длительности обслуживания и, наконец, с рассмотрением более сложной структуры системы (когда задействованы несколько приборов разной производительности, имеется некоторое число ненадежных обслуживающих приборов, введены ограничения на размер очереди, существуют ограничения на время ожидания и на время пребывания требований в системе и т. п.).

Второе направление составляют исследования управляемых систем при обслуживании идентичных требований [23—30]. Данное направление исследований касается систем с изменяемой структурой входного потока требований, систем с управляемым механизмом и длительностями обслуживания, с изменяемым механизмом формирования очереди, систем с управляемой дисциплиной обслуживания и т. п. Общее понятие управляемой системы обслуживания было введено О.И. Бронштейном и В.В. Рыковым. Целью управления в таких системах является оптимизация самых разнообразных параметров, например, среднего числа требований в системе в произвольный момент времени, среднего времени пребывания требований за такт работы системы, т. д. Обзор результатов по управляемым системам массового обслуживания содержится в [31].

В третье направление выделяются исследования процесса обслуживания неоднородных требований [32—47]. Данное направление касается систем с разделением времени, циклических систем, приоритетных систем и т. п.

Исследованию систем с разделением времени посвящены, например, работы [32—34]. Среди работ, посвященных изучению циклических систем массового обслуживания можно отметить следующие [35—43].

Результаты исследования приоритетных систем собраны в [44—48]. Системы приоритетного обслуживания вызывали и вызывают большой интерес. Это в первую очередь связано с тем, что в реальных системах обслуживания присутствуют требования различных типов, например, по характеристикам длительности обслуживания, или по стоимости ожидания в очереди. Задачи, в которых следует принимать в расчет преимущественные требования, встречаются постоянно: междугородний вызов прерывает местный телефонный разговор, к зубному врачу вне очереди принимаются больные с острой зубной болью, самолеты международного класса пользуются преимуществом при посадке, задерживая местные авиарейсы. В последнее время появляются новые исследования в области систем с так называемой "орбитой", на которую отправляются требования, заставшие прибор занятым. Такие требования в случайные моменты времени обращаются с повторными попытками занять прибор и в случае неудачи возвращаются на орбиту. Например, такая система рассматривается в [49].

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

Первые упоминания о результатах исследований простейших моделей систем с ожиданием, в которых динамическое поведение обслуживающего устройства описывается однородным марковским процессом с конечным числом состояний, приводится в работе Парадью [43]. В этих моделях при изменении- состояния обслуживающего устройства происходит изменение интенсивностей поступления и обслуживания требований. Рассматривая процесс обслуживания в таких системах поочередно на промежутках занятости и незанятости, Парадью изучил свойства переходного режима и определил условия существования стационарного движения. Входной поток требований при этом предполагался пуассоновским, а обслуживание заявок - экспоненциальным. Неутс [50] проанализировал подобную систему обслуживания с неэкспоненциальным обслуживанием в предположении, что закон распределения длительности обслуживания каждой заявки не изменяется в процессе обслуживания. В работе Джоэла [51] изучена система с ограниченной очередью, в которой динамика обслуживающего устройства описана условным марковским процессом с двумя состояниями. Вероятностные характеристики переходов между этими состояниями зависят от величины очереди, интенсивность пуассоновского потока заявок и интенсивность экспоненциального обслуживания.

При попытках рассмотреть задачи об управлении потоками требований в системах обслуживания с более сложными структурными изменениями, возникали значительные трудности. В работах Г.П. Климова [52, 53] были рассмотрены вопросы управления независимыми пуассоновскими потоками в системе, в которой допускается неограниченная очередь по любому из потоков. Поведение обслуживающего устройства с течением времени описывается условной марковской последовательностью с конечным числом состояний, равным числу входных потоков заявок. Состояние обслуживающего устройства изменяется в моменты завершения обслуживания требований. Переходные вероятности марковской цепи специальным образом связаны с длинами очередей по каждому из потоков в момент завершения обслуживания. В каждом состоянии обслуживающего устройства разрешено обслуживание требований только из одной определенной очереди. Случайные продолжительности обслуживания требований определяются произвольным законом распределения при конечных значениях двух первых моментов, причем этот закон распределения задается лишь номером состояния обслуживающего устройства. Длительности обслуживания заявок предполагаются независимыми между собой и от входных потоков требований. При определенном состоянии обслуживающего устройства уже обслуженное требование либо направляется в некоторую очередь с вероятностью, зависящей от этого состояния и номера выбранной очереди, либо навсегда покидает систему с вероятностью, зависящей только от указанного состояния. В предположении известной стоимости единицы времени ожидания в каждой очереди одной заявки в [53] предполагается некоторый алгоритм вычисления средних расходов на ожидание заявки в единицу времени в стационарном режиме. При этом оказывается возможным найти по некоторому рекуррентному правилу оптимальные вероятности переходов условной цепи Маркова, которые минимизируют средние потери на ожидание заявок в стационарном режиме. Другие модели задач об управлении потоками заявок в системах с определенными структурными особенностями обслуживающего устройства стали разрабатываться сравнительно недавно. Эти модели в той или иной мере объединяют особенности моделей [49, 52], а исследование в таких задачах, как правило, осуществляется в рамках подхода [52, 54].

К числу первых публикаций, в которых исследуется проблема алгоритмического управления потоками! заявок, и при этом учитываются структурные изменения устройства обслуживания, принадлежит цикл работ М.А. Федоткина [55—57]. Общий подход к анализу и оптимизации систем обслуживания с переменной структурой изложен М.А. Федот-киным в докторской диссертации [58].

Особое внимание среди приложений теории систем обслуживания с переменной структурой занимают задачи о регулировании дорожного движения, что связано с разработкой реальных автоматизированных систем управления транспортом. Актуальность этих задач обусловлена постоянно возрастающим парком автомобилей во всем мире и возникающими в связи с этим весьма острыми экономическими, экологическими и социальными проблемами. К настоящему времени разработано большое число всевозможных алгоритмов управления конфликтными потоками автомобилей на перекрестках. Среди них наиболее известны алгоритмы Данна-Потса [59], Гордона [60], алгоритмы с поиском разрыва [61], алгоритмы управления с прогнозом [62, 63], алгоритмы с жестким переключением [64], а также ряд однородных алгоритмов с обратной связью [65—68]. В работах [65, 69, 70] определены условия существования статистической устойчивости систем управления потоками транспорта, предложены методики определения оптимального управления обслуживанием конфликтных потоков, основанные на итеративных методах Ховарда и Уайта-Швейцера, и изучены свойства оптимального управления. Анализ процессов управления конфликтными потоками для нескольких классов однородных алгоритмов содержится в работах М. А. Федоткина [71—75]. Представляют интерес также работы [76—78] в связи с использованием в них нетрадиционных показателей качества работы системы, называемых функционалами Чжуна, с помощью которых возможно эффективное решение задач оптимизации систем обслуживания с переменной структурой в условиях большой загрузки. Среди известных методов численной оптимизации систем управления дорожным трафиком следует отметить метод Вебстера [79, 80], основанный на эмпирической формуле расчета средних задержек произвольной машины на перекрестке, метод Алсопа [81, 82] и метод имитационного моделирования [83].

Последние годы внимание математиков к теории массового обслуживания в значительной степени стимулировалось необходимостью применения результатов этой теории к важным практическим задачам, возникающим в связи с бурным развитием систем коммуникаций, возникновением информационно-вычислительных систем, появлением и усложнением разнообразных технологических систем, созданием автоматизированных систем управления. Первоначально у ученых интерес вызывал входной поток системы массового обслуживания, характеристики которого исследовались для наиболее простого описания функционирования реальных систем массового обслуживания. Позднее изучался закон обслуживания заявок входных потоков системы. На сегодняшний день уже подробно изучены разнообразные стохастические модели реальных систем и характеристики их функционирования. В современной теории массового обслуживания одним из наиболее актуальных и перспективных направлений является изучение выходных потоков, возникающих в системах массового обслуживания. Первые попытки исследования выходных потоков были сделаны в 60-е годы XX века такими математиками, как Берк [84], Коэн [85], Рейч [86] и Финч [87].

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

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

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

Попытки изучения свойств выходных потоков продолжаются. Например, в работе [88] найдено распределение числа требований, обслуженных за период занятости в стационарной системе Geom/Geom/1 с дискретным временем. Сделана попытка обобщить полученные результаты на случай непрерывного времени.

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

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

В работе [93] авторы изучают распределение промежутков времени в выходящем потоке не обслуженных требований в пакетной системе Gx / G /1 с некоторой дисциплиной, допускающей потери требований, а также в ее дискретном аналоге.

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

1) задают случайный процесс {£(/); / > 0}, где ф) при t > 0 определяет случайное число обслуженных заявок за промежуток времени [0, t) и £(/) = £(/- 0), <^(0) = 0;

2) указывают случайную векторную последовательность {(т/, i > 1}, в которой через г/ и £/ обозначены соответственно /-Й момент появления и число требований, обслуженных системой в этот момент времени;

Следует отметить, что эквивалентность трех вышеперечисленных способов доказана в [9]. Если для описания выходного потока использовать один из предложенных способов, то в общем случае не удается найти конечномерные распределения процесса. Это становится возможным только в исключительно редких случаях [8]. Таким образом, задача исследования распределения выходного потока в общем случае является трудноразрешимой проблемой. Почти очевидно, что выходной поток существенно зависит от системы массового обслуживания, в которой он формируется. Следовательно, в описание выходного потока необходимо включать некоторые элементы самой системы массового обслуживания. Более того, целесообразно следить не за отдельным требованием, а за некоторой случайной группой заявок. Впервые такой подход был предложен в работах М.А. Федоткина [94—96] и назван нелокальным описанием потоков требований.

Основные задачи и содержание работы

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

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

В отличие от большинства известных трудов в этой области, для построения математической модели выходных потоков автор использует так называемое нелокальное описание потока требований, впервые предложенное М.А. Федоткиным [94—96]. В описание выходных потоков включены такие элементы самой системы массового обслуживания как состояния обслуживающего устройства и величины очередей. Стоит отметить, что функционирование рассматриваемых систем управления в непрерывном времени является сложным процессом, и не является при этом марковским процессом, поэтому изучение характеристик систем и свойств выходных потоков в непрерывном времени является трудноразрешимой задачей. Для решения данной проблемы, как правило, используется метод вложенных цепей Маркова. Суть метода состоит в том, что процесс обслуживания рассматривается в специально подобранные дискретные моменты времени, которые выбираются таким образом, чтобы новый процесс обладал свойством марковости. Однако проблема определения указанных моментов является очень сложной, поскольку не существует определенной методики или алгоритма их выбора. В диссертации проблема выбора специальных моментов времени решается уже на этапе построения математической модели. При построении математических моделей изучаемых неклассических систем массового обслуживания использовался так называемый «кибернетический подход», разработанный А.А. Ляпуновым и С.В. Яблонским [97] и развитый М.А. Федоткиным в ряде работ.

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

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

Заключение

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

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

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

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

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

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

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

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

1. Erlang, А.К. Probability and telephone calls / A.K. Erlang // Nut Tidsskrift for Matematik. Ser. B. - 1909. - T. 20 - P. 33-39.

2. Johannsen, F.W. Waiting times and number of calls / F.W. Johannsen // P.O. Elec. Engrs. J. 1907.

3. Хинчин, А.Я. Математические методы теории массового обслуживания / А.Я Хинчин // Труды математического института им. В.А. Стеклова. 1955. - Т. 49. -С. 38-40.

4. Бернштейн, С.Н. О математическом ожидании простоя рабочих единиц при сложном производственном процессе / С.Н. Бернштейн // Уголь. 1935,- № 117. - С. 109-111.

5. Palm, С. Intensitatsschwankungen in Fernsprechverkehr / С. Palm // Ericsson Technics. -1943.-Vol. 1,№44. — P. 1-189.

6. Kendall, D.G. Some problems in the theory of queues / D.G. Kendall // J. Roy. Statist. Soc., Ser. В. 1951.-Vol.13, №2.-P. 151-185.

7. Королюк, B.C. Полумарковские процессы и их приложения / B.C. Королюк, С.М. Броди, А.Ф. Турбин // Итоги науки. Теория вероятностей. Математическая статистика. Теоретическая кибернетика: сб. науч. тр. Москва: ВИНИТИ АН СССР, 1974.-Т. 11.-С. 47-97.

8. Саати, T.JI. Элементы теории массового обслуживания и ее применение / T.J1. Саати. М.: Советское радио, 1971. - 520 с.

9. Гнеденко, Б.В. Введение в теорию массового обслуживания / Б.В. Гнеденко, И.Н. Коваленко 3-е изд., испр. и доп. - М.: КомКнига, 2005. - 400 с.

10. Кофман, Ф. Массовое обслуживание (теория и приложения) / Ф. Кофман, Р. Крюон -М.: Мир, 1965.-302 с.

11. Takacs, L. Investigation of waiting time problems by reduction to Markov processes / L. Takacs // Acta Math. Acad. Sci.Hung. 1953. - Vol. 6. - P. 101-129.

12. Ali Khan, M.S. Infinite dams with inputs forming a Markov chain / M.S. Ali Khan, J. Gani // J. Appl. Probab. 1968. - Vol.5, № 1. - P. 72-83.

13. Gittins, J.C. Stochastic monotonicity and queues subject to tidal interruptions / J.C. Gittins //Proc. Cambridge Philos. Soc. 1971,-Vol.70, № 1,- P. 61-75.

14. Muntz, R. Wating time distribution for round-robin queueing systems / R. Muntz // Proceedings of Symposium on Computer Communications Networks, and Teletraffic. -New York. - 1972. - P. 429-439.1518