автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование и оптимизация выходных процессов при циклическом управлении конфликтными потоками Гнеденко - Коваленко

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

ФЕДОТКИН АНДРЕЙ МИХАЙЛОВИЧ

МОДЕЛИРОВАНИЕ И ОПТИМИЗАЦИЯ ВЫХОДНЫХ ПРОЦЕССОВ ПРИ ЦИКЛИЧЕСКОМ УПРАВЛЕНИИ КОНФЛИКТНЫМИ ПОТОКАМИ ГНЕДЕНКО—КОВАЛЕНКО

05.13.18 — Математическое моделирование, численные методы и комплексы программ (физико-математические науки)

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

- 9 ЛЕН 2010

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

004616941

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

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

кандидат физико-математических наук, доцент Зорин Владимир Александрович (Нижегородский государственный университет им. Н.И. Лобачевского)

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

доктор физико-математических наук, профессор Ушаков Владимир Георгиевич (Московский государственный университет им. М.В. Ломоносова), доктор технических наук, профессор Федосенко Юрий Семенович (ФГОУ ВПО «Волжская государственная академия водного транспорта»)

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

Защита состоится / _2010 г. в /^"час. -1- мин. на заседании дис-

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

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

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

« II » //

Автореферат разослан «_ *Ь » // 2010г.

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

диссертационного совета Д 212.116.13 кандидат физико-математических наук, доцент

В.П. Савельев

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

Актуальность исследования. Первые задачи теории массового обслуживания или теории очередей описаны на физическом уровне в 1907 г. Ф.В. Иоханнсеном и были успешно рассмотрены сотрудником Копенгагенской телефонной компании, датским математиком А.К. Эрлангом в период между 1908 и 1923 годами. Фундаментальные исследования в этой области, которые уже стали классическими, выполнены А.Н. Колмогоровым, А.Я. Хинчиным, Ф. Поллачеком, Б.В. Гнеденко, С.Н. Бернштейном, К. Пальмом, Д. Кендаллом, Л. Тахачем, Ю.В. Прохоровым. Важные теоретические и практические результаты в теории массового обслуживания получены Г.П. Башариным, Ю.К. Беляевым, A.A. Боровковым, Н.П. Бусленко, О.В. Висковым, Н. Джейсуолом, В.М. Золотаревым, Л. Клейнроком, Г.П. Климовым, И.Н. Коваленко, Д.Р. Коксом, B.C. Королюком, А. Коф-маном, Н. Прабху, Т.Д. Саати, Б.А. Севастьяновым, У.Д. Смитом, А.Д. Соловьевым и др.

В последнее время возрос интерес к теории массового обслуживания благодаря ее многочисленным приложениям к анализу и организации работы: 1) реальных компьютерных и коммутационных сетей; 2) информационно-вычислительных систем; 3) автоматизированных систем управления; 4) различных транспортных систем и т. д. Сети массового обслуживания служат, как правило, адекватными моделями для такого рода систем. Каждая сеть массового обслуживания включает несколько связанных между собой узлов (систем массового обслуживания). Поэтому при рассмотрении конкретной сети массового обслуживания всегда необходимо изучить вероятностные свойства выходного потока одного узла (одной системы обслуживания), который затем будет входным потоком для следующего узла (другой системы обслуживания).

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

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

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

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

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

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

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

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

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

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

Публикации и личный вклад автора. Результаты по теме диссертации автором опубликованы в [1—11], в том числе 4 в изданиях, рекомендованных ВАК РФ. Постановка задачи и основные методы исследования принадлежат соавтору в пяти совместно опубликованных работах и научному руководителю. Вывод формул для числовых характеристик

потока Гнедснко—Коваленко в [4] принадлежит соавтору. Вкладом диссертанта являются: а) формулировка и доказательства утверждений; б) теоретические расчеты и вывод формул для распределений и их числовых характеристик стационарного режима; в) получение оценки для загрузки системы по потокам; г) компьютерная реализация имитационной модели; д) разработка и обоснование методики исследования имитационной модели с целью определения квазиоптимальных параметров циклического управления потоками требований; е) интерпретация результатов исследований на имитационной модели.

Апробация результатов диссертации. Основные результаты работы были представлены на Международной конференции «Модели долговечности, старения, и деградации в теории надежности, здравоохранения, медицине и биологии» (Санкт-Петербург, СПбГПУ, 2004 г.), на VI Международном конгрессе по математическому моделированию (Нижний Новгород, ННГУ, 2004 г.), на VI Международной конференции «MMR 2009 — Математические методы в теории надежности: Теория. Методы. Приложения» (Москва, РУДН, 2009 г.), на X Международном семинаре «Дискретная математика и ее приложения» (Москва, МГУ, 2010 г.).

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

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

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

В первой главе предложен способ описания потоков неоднородных требований. Эффективность такого подхода показывается на примере построения вероятностной модели пространственного движения машин по свободной от перекрестков магистрали. При удовлетворительном состоянии дорожного полотна и хороших метеорологических условиях движение неоднородных автомобилей по магистрали может оказаться беспрепятственным и пуассоновским. При плохих погодных условиях (туман, снег, гололед и т. д.) обгон быстрыми машинами медленных является уже рискованным, зависимым и занимает значительное время. В этом случае на интенсивных магистралях будут возникать автоколонны (группы) машин или транспортные пачки. Обозначим через т|о(/) случайное число быстрых машин, которые поступают по закону Пуассона с параметром \0 в транспортную пачку за промежуток времени [0, /). При этом случайная величина ж0(/) измеряет число всех типов машин в транспортной пачке в момент времени t > 0, размер которой всегда не

превышает постоянной величины N> 1. Пусть В,о(', АО есть случайное число быстрых машин, которые совершают обгон медленной машины за промежуток времени [t, t + ДО-

Естественно предположить, что при малых At > 0 условные вероятности событий, которые порождаются случайной величиной Ьщ(>, Al), определяются соотношениями:

PßoC, ДО = 0|®о(0 = 1, Ло(/, ДО = 0) = 1; Рйо(/. ДО = 0|аго(0 = 1, ПоС, ДО = 1) = 1 - 0(At); Р(^о(г, ДО = 0|аг0(0 = 2, По(Л А/) = 0) = 1 - ц,,»Дг + о(Д0; ДО = 1|ж0(') = 2, ло(', ДО = 0) = = т,„д/ - о(Д0; ЩоС, ДО = 0|ю0(г) = к, t)o(i, ДО = 0) = 1 - ц2.оДt + o{ht)\ ц2,оД/ - о(Д0 = = Р(4о(/,ДО = 1|»о(0 = к, г)о(/, Д/) = 0) для всех 3 < к < N- 1; и, наконец, 1 - Цг,оД' + о(Д0 = = Р($о(/, ДО = 0|шо(0 = N, г,0(/. ДО = 0); Pßo(f, ДО = 1|»о(0 = JV, т|о(г, ДО = 0) = Ц2,оД' - о(М); P(4o(i, ДО = 1|®о(0 = N, r)o(i, ДО = 1) = 1. Таким способом моделируется механизм обгона, и зависимость среднего времени обгона от числа машин в транспортной пачке. Параметры Hl. о и Ц2,о будем называть интенсивностями обгона. При любых фиксированных / > 0 и к= 1, 2, ..., N обозначим через функцию Q(t, к) вероятность Р(аг0(0 = к). Принятый механизм обгона позволяет получить для функций Q(t, к) дифференциальные уравнения

dQ(t, 1)/Л = -\oQ(t, 1) + ni, о Q(t, 2), dQ(t, 2 У dt = X0Q(t, 1) - (Я* + m,o)ß(f, 2) + ц2,о Q(t, 3), dQ(l, k)/At = X0Q(l, к - 1) - + ц2.»)Q{t, к) + ц2.0Q{t, к + 1)Д = 3, 4,.... N - 1, dQ(t, N)!dt = X„Q(t, N - 1) - ц2, iV),

которые определяют динамику распределения числа ае0(0 машин в транспортной пачке.

В первой главе рассмотрен весьма важный для практики частный случай, когда интенсивность Хо поступления быстрых машин в транспортную пачку существенно меньше как интенсивности 0 обгона, так и интенсивности X медленных машин. В этом случае можно допустить, что ж0(г) < 2. Изучены эргодические свойства случайного процесса {аз0(0: t > 0}, например, получены предельные равенства: lim Q(t, 1) = ni,0(Xo + Hi.o)1 = p,

/-»ос

lim Q(t, 2) = Xo(Xq + Hi,0)~' = q■ Получены условия, при которых транспортный поток неод-

О

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

Теорема 1. Пусть л(0 — число всех типов машин, которые пересекают некоторую поперечную линию автомагистрали за промежуток [0, t). Тогда вероятности Р(л(0 = к) =

[к/2] . IXt)k~'

= ехр{-Я/} £ Ci.sP 'q' -—--, t > 0, к> 0, определяют одномерные распределения

ы> (*"')!

потока Гнеденко—Коваленко с параметрами X пуассоновского прибытия медленных машин и р = ni, 0(Яо + Ц1, о)-1, где q = 1 -р есть вероятность поступления сразу двух заявок.

Лемма 1. Пусть X, и pj являются параметрами исходного потока Гнеденко— Коваленко с номером j = 1, т. Тогда сумма m независимых такого типа потоков будет потоком Гнеденко—Коваленко с параметрами X = 2 ар = Я"1 £ .

;=о /=о

Получены в явном виде формулы для вычисления таких основных числовых характеристик потока Гнеденко—Коваленко, как математического ожидания, дисперсии, начальных и центральных моментов, коэффициента асимметрии и эксцесса.

В последнем разделе этой главы рассмотрен метод нелокального описания потока неоднородных требований. При i = 1, 2,... обозначим через т',- момент ¡'-го появления в систему требования с номером г. Последовательности {т',-; ; > 1} взаимно однозначно соответствует считающий случайный процесс {r\(t): t > 0}, в котором г)(г) определяет случайное число неоднородных требований, поступающих в систему за промежуток [0, t). Как правило, случайные интервалы т',- + ] - t'y, г > 1, являются зависимыми и имеют различные функции распределения. В этом случае практически не удается определить конечномерные распределения считающего случайного процесса {г|(ф t> 0}.

В работе рассматривается именно такая сложная ситуация. Строится последовательность случайных точек т,-, i = 0, 1,... на оси времени с помощью выбора функциональной зависимости каждого элемента т,- от моментов т'„ i> 1. На содержательном уровне это означает, что происходит разбиение потока {т',-; / > 1} моментами т,-, i = 0,1,... с целью более простого его описания. Тогда нелокальное описание входного потока представляется в виде векторной случайной последовательности {(т,-, г),); i > 0}, где случайная величина г|, задает число поступивших заявок за промежуток [t,-, т, + i). Предложены и изучены четыре способа разбиения потока {т',-; i > 1} или получения маркированного точечного процесса {(т„ г),); i > 0}. Для примера рассмотрим четвертый способ разбиения i > 1}.

Пусть при фиксированном с = 0,1,... моменты т/с), i > 0, на оси времени [0, <ю) совпадают с некоторыми моментами т'„ i > 1 поступления требований в систему. Другими словами, моменты т/с), i > 0, совпадают с некоторыми точками разрыва исходного считающего случайного процесса {r)(/): t > 0}, т. е. т/с) = %'к , kcj е {1, 2,...}. Тогда при каждом

с, I

с > 0 величина r]/c) = fc, ; + i - кс,, задает число поступивших требований на промежутке [т/с), т/ + \1с>) первоначального потока и является величиной i-ой группы виртуального потока {(т/с), Т1/(С)); /' > 0}. Величина 5/с) = х'к - _ j определяет временной интер-

с, i + 1 с, i + 1

вал между последовательными группами с номерами г и i + 1 исходного входного потока {ri(/): / > 0} при его нелокальном описании в виде векторной последовательности

{(т/с), т]/'*); /> 0}. Тогда при каждом фиксированном с > 0 элементы т/с), < > 0, потока {(т/с), Т1,(с)); г > 0} будем строить с помощью рекуррентных соотношений вида:

ко,,+1 = М {к: к> кй,т'*- т'*_1 ^ /г0},

В этих формулах t|_ i(c) = 1 при каждом с > ОДо.о = 1, d — некоторое натуральное число, и постоянные величины /го, /ii, удовлетворяют условию ho<h\. Подбирая соответствующим образом параметры ho, hi, d разбиения, как правило, удается построить последовательности {т, +1 - тг > 0} и {г|,; / > 0}, каждая из которых составлена из независимых и одинаково распределенных случайных величин. Разработан комплекс компьютерных программ, который позволяет не только проверить выдвинутые теоретические предположения нелокального описания, но и применить предложенные формальные методы статистического анализа входного потока неоднородных требований к обработке данных наблюдений за реальными потоками.

Метод нелокального описания проиллюстрирован на примере потока машин, который реально наблюдал Бартлетт вблизи Лондона в 1963 г. Исследования статистических данных Бартлетта, которые приведены в виде конечной реализации последовательности {x'i + 1 - т',; / > 1} из интервалов, позволяют определить конечную реализацию последовательности {xi +1 - т,; i > 0}, и сделать следующий вывод. Во-первых, последовательность {т, +1 - т,; i > 0} составлена из независимых случайных величин, каждая из которых имеет смещенное экспоненциальное распределение Р(т; +1 - т,- < /) = 1 - ехр{-(/ - h)/a}, t> h с параметром смещения h = 0,0006 и параметром масштаба ст = 23,9312. Во-вторых, последовательность {г|,; i > 0} составлена из независимых случайных величин, каждая из которых распределена по закону Бернулли с параметром р, т. е. принимает значение единица с вероятностью р = 441/841 или значение два с вероятностью q = 400/841. Так как параметр смещения h приближенно равен нулю, то наблюдаемый Бартллетом вблизи Лондона транспортный поток можно нелокально описывать потоком Гнеден-ко—Коваленко.

sc = mi{k:k>0, ru{c)<d, пмStw < hu т/> = ^ -i(c)},

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

На этой схеме исходными составляющими элементами являются:

1) входные потоки Пь ГЬ, ..., П„;

2) стратегии 81, 52, ...., 8„ механизмов обслуживания требований из неограниченных накопителей очередей 0\, О2, ..., Ои по потокам соответственно; 3) структура 5(Г) обслуживающего устройства, которая включает набор Г(1), Г<2), ..., Г(2т) его состояний и циклический алгоритм смены этих состояний; 4) потоки насыщения П ь П2, ... , П, (выходные потоки системы при максимальной загруженности системы и ее эффективном функционировании). Основными искомыми составляющими элементами

гт )-^ ги> \— ...

П',

П-,

Рис. 1

системы являются выходные потоки П'ь П'г,..., П'т.

Пусть вызывающие моменты потока Пу с номером / = 1,т представляют собой пу-ассоновский процесс с параметром Xj, и в каждый из этих моментов появляется одна заявка с вероятностью /),- или появляются две заявки с вероятностью ф = 1 - ру. Из рис. 1 видно, что обслуживающее устройство меняет свои состояния согласно периодической последовательности вида: Г*1' -> Г(2) -» ... Г(2т) -> Г*", ... При этом для любого 5 = 1,2т в состоянии Г^1 обслуживающее устройство находится Г, > 0 единиц времени. Будем полагать, что для каждого фиксированного у = 1 ,т в состоянии Г®" 4 в течение времени Ту-1 происходит акт обслуживания только требований потока П; и в состоянии Г®1 в течение времени Ту потоки не обслуживаются. На оси времени выберем момент То > 0. В этот момент

случайным образом включаем одно из состояний обслуживающего устройства. Тогда на оси времени получим случайную последовательность {т,;; = 0, 1, ...} из моментов окончаний переключений состояний обслуживающего устройства.

При j = \,т,Х = {0, 1, ...} и ; е А-введем следующие случайные величины и элементы: а) ту,; — случайное число заявок потока Пу, поступивших в систему за промежуток [т„ т/ + ¡), где ту, I е X; Ь) Еу, у — максимально возможное число заявок потока Пу, которые система может обслужить на промежутке [т,-, т,- + 0, где Еу,е {0, /у} и /у есть заданное натуральное число; с) Г, — состояние обслуживающего устройства на промежутке времени [т„ +1), где Г, € Г = {Г(1), Г(2), ..., Г42"1'}; с!) — число требований потока Пу, находящихся в системе в момент т,, где агу, ,■ е X; е) %'у,— число заявок потока Пу, которые в действительности покидают систему на промежутке [т,, т,- +1), где ¡;'у,; е }у = {0, 1, ..., /у}; /) ¡;'у, -1 — число заявок потока Пу, которые реально покидают систему на промежутке [О, т0), где^'у,-! 6 У;.

По величине агу, ,■ очереди в накопителе Ор входному потоку Пу и потоку насыщения Пу требования из этого накопителя в порядке поступления отбираются на обслуживание в соответствии с экстремальной стратегией 5у, т. е. имеет место соотношение вида ¡;'у,= тш {агу,+ ту, „ ,} для у = 1, т и / е X. Для случайной векторной последовательности {(Г„ агу,^'у, , _,);/ = 0, 1, ...} установлено фундаментальное рекуррентное по /' б X соотношение (Г, +1, / + ь Ц], ¡) = ("(Г.), тах{0, эгу, ; + г(у,, - ;}, тю}аеу,+ ту, „ Еу,,}), в котором функция ЦГ<5>) принимает значение Г<1 +'' при к {1, 2,..., 2т - 1} и значение Г(1) при ^ = 2т. Заметим, что первая компонента этой последовательности определяет динамику состояний обслуживающего устройства, вторая компонента задает флуктуацию длины очереди по потоку Пу и третья компонента отвечает за выходной поток Пу. В нелокальное описание {(Г„ агу, ¡, , _ 1); г > 0} выходного потока включены описания таких важных характеристик системы, как функционирование состояний обслуживающего устройства и изменение длины очереди. Первые две компоненты последовательности {(Г^ агу, ;, ¡;'у,; _ 1); ¡' > 0} играют роль меток. Так как время Т5> 0 пребывания обслуживающего устройства в каждом состоянии е Г можно выбирать, то математической моделью процесса обслуживания по потоку Пу является управляемая случайная векторная последовательность {(Г,-, агу,4'у,; - 1); / > 0}. Обозначим теперь условную вероятность Р(гу / = и|Г,- = Г«") через

<Ру(и; Г5), где функция фу(и; /) = к-0 "~к ] (п - к)\ ' " е ' > 0, и вероят-

ность Р(Г, = Гм, агу, ,• = х, 4'у, ,• _ 1 = у) через £у, , (Гм, л:, у) для любых у = Т^п,; е X, е Г,

х е X и у е Yj. В силу периодической смены состояний обслуживающего устройства есте-

9

ственно допустить, что Г(0) = Г(2т), Г<2т + » = Г<», Т<2т+2) = Г<2), Г(2т+3)3Г*3),..., Г*4"1-2'^ Г<2"-2) И Т0 = Т2„, Т2,„ + 1 = 7"ь Г2т + 2 = т2, Т2т + 1 = Тз,..., Г4т-2 7"2т_2- Основные результаты доказаны в следующих утверждениях.

Лемма 3. При заданном распределении начального вектора (Го, аз у, о, ^¿-О векторная случайная последовательность {(Г,-, агу,¡;'у,1); г = 0, 1, ...} является управляемой однородной марковской цепью со счетным числом состояний.

Теорема 3. Пусть условное распределение ,■ = й|Г, = Г(,)) случайной величины равно единице при Ь = /у и Г(1) = или при Ь = 0 и Г(1> е Г \ Г (1*~и равно нулю в остальных случаях. Тогда для одномерных распределений векторной последовательности {(Г/, азу,,-, 1); /=1,2,...} выполняются рекуррентные соотношения

/ + 1(Г(2Л, о, = I 2;, V, 0)ф/у - V; Ту. О,

V = О

Х + Ь

/ + 1(Г(2Л, х, /у) = I бу, КГ®- V, 0)Фу(х + /у - у; Ту- О,

V = О

/у - 1

б, I + 1(Г(2; + X, 0) = I <2,. ,<Г(2Л, 0, М,)ф; Т2/) + I <2 , ,{Г<2Л, V, /у)Ф/х - V; Г2у), ц/ = 0 >'=0

Су. , + кг"», х, 0) = I ЙА .{Г"" V, 0)Ф/х - V; Тг-1),

у = 0

где Г(г> е ГСО = г \ {Г(2Л, Г<2-/ + 1)},хеХ,,у е {0, 1,..., //- 1}.

Теорема 4. При любых ] = \,т, ¡> 1, |г| < 1, Г4'"1 £ Г(/) для производящих функций

00 00

фу., (Г(2Л, 7, /у) = X а, ,<Г(2Л, х, /у)/, Фу,(Г® + г, 0) = I & ,<Г® +1)), X, 0)/, Фу. ,(Гм, 2,0) = * = 0 * = 0

со

= 2 0/, ,<Г(", х, 0)/, которые соответствуют одномерным распределениям выходного по-

х = 0

тока П'у, выполняются рекуррентные по I соотношения

Фу,/+ ,(Г<2Л, г, /у) = 2-(/Фу,,{Г®- 2, ОШТу-,, 2)-/у - 1 I, - V - 1

О ¿=0

ч -1

Фу,+ ,(Г® + ■», 2, 0) = Фу, <Г®> 2, /у) У/Г2У, 2) + I 2„ ,<Г(2Л 0, IV) %{Ту, 2),

н' = 0

Фу,/+ КГ«, 2, 0) = Фу,,<г<г" 2, 0)%(ТГ- ь 2),

где Ч'/Гд г) = ехр{Х,уГ1(ру2 + да2 - 1)} и Г5 = Г,, Г2,..., Т2т. 10

Теорема 5. При Г(г) е Г(/) и | г | < 1 для производящих функций Фу, 2т(/ + 1)(ГЙ), г, /у), Фу, 2ти + 1)(Г(3; +!), 2, 0), Фу. ¡то + цСГ^, 2, 0) выполняются следующие соотношения:

Фу,2»(/ + ЫГ®', г, 4) = г-'Уехр{У <Д* + 9у22 - 1)}ФЛ2,„,(Г®), 2, /у) +

ь ->

н> = О

Ь - 1 - V - 1

-г-Ь I е,-,^,,)-,^®-1^^)/ I 1кф-,ТУ-г), у=и к=0

Фу, г* + !)(Г® + г, 0) = г" Ьехр{Х;Т(дг + %22 - 1)}Ф,,¿„.(Г®+1), 0) + %{Ту, г) *

/у - 1 - 1 - V - 1

№ = 0 * = 0 к - О

Фу.+ 1)(ГМ, 2, 0) = 2- Ь ехр {уг (р, 2 + 5,22 - 1)}Фу, 2т1{Г(0,2, 0) -

-1 /у - V - 1

- г''; Ч'/Г,- ь 2) х ... х У/Гзу- ь I Й.2»<н1) —г(Г®~", V, 0)2" I ¿ф; Ту.,) +

V = О Аг = О

- 1

+ Ч'у(Гг-Ь2)х ... х^у(Г2у_,,г) I 1(^.0

» = О

где$ = г~2]~ 1, если г > 2/ + 1, или 5 = г+ 2т- 2/- 1, если г < 2/

В третьей главе изучаются арифметические и предельные свойства одномерных распределений выходных потоков рассматриваемой управляемой системы обслуживания с переменной структурой. Используя полученные во второй главе рекуррентные соотношения для одномерных распределений выходных потоков, проведена классификация по Колмогорову пространства состояний каждого из т выходных потоков системы. При ] = 1т и Г<5) е Г \ {Г®} введем теперь такие обозначения: Я//*") = {(Г<5), х, 0): х еХ),

2т

£у(/«>)={(Г^л-,/у):*б*} 11 {(Г<2Л, 0,у):у = 0, 1,..., /;-1}и£} = I) Я/Г40).

Г=1

Теорема 6. Пространство Г х Хх Yj состояний управляемой векторной марковской последовательности {(Г„ щ,¡;'у,, _ 0; / = 0,1,...} разбивается на незамкнутое подмножество О, = {(Гм, х, у): Г(г) б Г \ Г<2Л, х е X, у = Ц]} I) {(Г(2у), х, у): х > 0, у = 0, 1, ..., Ь - 1} несущественных состояний и на единственное замкнутое подмножество Е) существенных периодических состояний с периодом 2т.

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

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

Теорема 7. Для существования единственного стационарного распределения последовательности {(Г;, а;,.,-, 0; / = 0, 1,...} необходимо выполнение следующего неравенства Л/Г(1 + (],) - ¡] < 0.

Теорема 8. Для существования единственного стационарного распределения последовательности {(Г„ ж,,„ ,-]);/= 0, 1, достаточно выполнение неравенства вида А,Г( 1+Ф)-/,<0.

Интересно отметить, что если рассматривать векторную последовательность вида {(Г,-, ж,-, §'¡-0; г" = 0, 1,...}, где случайный вектор ж, = (»!,;, х^п..., ж,„,,) и случайный вектор =(^'1.1-1. ¡,'2.1-1, ..., .-О» то имеет место следующее утверждение.

Теорема 9. Для существования стационарного распределения управляемой марковской последовательности {(Г/, ае,-, ]);= 0, 1,...} необходимо и достаточно выполнение неравенств Х/Г(1 + д.) - /, < 0, ] е {1,2,..., /и}.

Из теорем 8 и 9 следует, что в рассматриваемой модели возможно существование стационарного распределения как для отдельного потока П;, так и во всей системе. Это обстоятельство зависит от выполнения неравенства + </у) - /, < 0 только лишь для потока П7 при каком-либо значении у, или от выполнения всех неравенств + д,) - ¡] < 0, / = 1 ,т. Более того, этот факт является следствием независимости входных потоков, потоков насыщения и циклической смены состояний обслуживающего устройства или автомата-светофора для конкретной задачи об управлении транспортом на перекрестке. Аналогичный вопрос постоянно рассматривается в классической теории сетей массового обслуживания, когда в некоторых случаях сеть удобно представить в виде т независимо функционирующих систем массового обслуживания. При этом каждая из т таких виртуально функционирующих систем массового обслуживания как бы моделирует работу конкретного узла сети в стационарном режиме. Это дает возможность представить стационарное распределение векторного случайного процесса, который определяет флуктуацию количества заявок по всем узлам сети, в мультипликативном виде. Однако в общем случае компоненты указанного векторного случайного процесса могут оказаться зависимыми и принцип мультипликативности уже не выполняется.

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

довательности {(Г,-, зе„ 0; г > 0} в мультипликативном виде представляет значительные трудности, хотя бы в чисто техническом плане. Более того, даже получение стационарного распределения каждой последовательности {(Г„ х,,¡, ^'у,1); г = 0, 1, ...} связано с выполнением большого объема вычислений. Заметим, что последовательности {(®у,1); ; > 0} и {(«£/, 1); г > 0}, где у = \,т, не являются марковскими. Ясно, что рассмотрение задачи управления конфликтными потоками неоднородных требований на сети узлов уже вызывает значительные трудности как теоретического, так и вычислительного характера.

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

Лемма 5. Случайная последовательность {Г,-; г > 0} является марковской с конечным числом состояний из множества Г = {Г*1', Г<2),..., Г(2т)} и с периодом 2т.

Из этой леммы непосредственно следует, что для случая стационарного функционирования системы обслуживания справедливо равенство Р(Г, = Г(г)) = М2т, Г(г) е Г.

Для вычисления стационарного распределения управляемой векторной марковской последовательности {(Г,-, 1); г > 0} имеет большое значение лемма 6.

Лемма 6. Пусть Х,Т( 1 + с;,)-/,<0 и 8 — достаточно малое положительное число. Тогда внутри круга <1 + 5} существует /у различных корней 20 = 1, 2\, ... уравнения (г!/ - %(Т, 2)) = 0, где производящая функция г) = ехр{Х,Т(дг + qjZ2 - 1)}.

Теорема 10. При Г(1) б Г стационарные вероятности ^(Г'1', 0, 0) векторной марковской последовательности {(Г/, аг;-,1); г = 0, 1,...} вычисляются по формулам:

¡1

£{Г(2л, 0, 0) = (1 - ехр{-А,Т})Лхр{-^Г} I (Щ™, 0,у),

у = 1

б/г®^, 0, 0) = (1 - юфНЛГ'ехрН^ + 7VI + -+ Ту,г-0} ¿ а<Г(2л, 0,у),

у = 1

где г = \,2т -1.

Теорема 11. Пусть +%) - /, <0, Г^' е Г, у е }у и \ г\ < 1, то производящие функ-

00

ции Ф/Г(5), 2, у) = £ е/г(1), х, у)г" для стационарной векторной марковской последова-

х = 0

тельности {(Г„ зе,-,,-, 1); г = 0, 1,...} определяются следующими равенствами:

'у -1

Ф/Г(2Л, 2, /,) = (г Ь - %{Т, 2))"1 I (У/Г, 2) - г")а(Г(2Л, о, и

Ф,(Г<о,г,0) = (2!(-Ч'ХГ,2))-1Ч'ХГг_ьгЩГг.2,2) х ... х ЧДТу,г) *

>1

х I (г'' ~ О, Ч где Г(г)е Г \ Г(2у).

IV = О

Теорема 12. Если - /, < 0, то стационарные вероятности 0, у),

у е векторной марковской последовательности {(Г„ щ ¡, , _ 0; г = 0, 1, ...} находятся однозначно из решения системы уравнений

О/Г'2", 0, 0)-ехр{-/,Т} I. 0, _>>)/ (1 - ехр{-Я.у7"}) = 0,

у = 1

-1

2»! I Й(Г<2Л, 0, И>) (/, - Н>) = /у - ХуГ(1 + ф),

и> = 0

-1 и> = 0

При /, = 1 были получены в явном виде формулы для стационарных вероятностей и для некоторых числовых характеристик состояний системы обслуживания неоднородных требований и управления конфликтными потоками. Этот случай важен в приложениях для управляемых систем с малыми значениями интенсивностей обслуживания или с малыми значениями длительностей пребывания обслуживающего устройства в состояниях. В качестве примера можно привести задачу о сортировке корреспонденций из т ячеек в отделении связи. Работник почты берет изу'-ой ячейки одну корреспонденцию, читает адрес и переносит ее в соответствующийу-ый бункер для транспортировки. Затем он непременно переходит к ячейке с номером (/ + 1) при 1 < у < т и к первой ячейке при у = т. Корреспонденция в каждую ячейку поступает случайным образом и не зависит от поступлений корреспонденций в другие ячейки. Время на чтение корреспонденции из ячейки с номерому и перемещение ее в бункер с номером у равно Тц- \. Время перехода от бункера с номером у к ячейке с другим номером равно Тп,. Основные теоретические результаты по этому вопросу содержатся в следующих утверждениях.

Лемма 7. Пусть /у = 1 и Х,Т(1 + - 1 < 0. Тогда справедливы следующие формулы:

е/г*»,о,о) = е/г®,о, 1) = (ехр{Я,.г}-1),

2т 2т

2т

С(г®+1),1,0) = 1 - +^) + ХТ ( +1} + ехр{Хл _ х п +1}) х

2т

х ехр{Я/Т}ехр{-Х.уГ2у}.

Лемма 8. Если /у = 1 и ЛуГ( 1 + #у) - 1 < 0, то для второй компоненты стационарной марковской цепи {(Г,-, а;у,;, ¡;'у,,-- 0; / = 0, 1,...} выполняются следующие равенства:

Р(£В;, = 0) = + (еу + ецт-ту + £цт - Ту- ^,) + ___ + ,)>

2т

Р(ж. ,= 1)= + (^/-^Гд- 1) х (е>-/+ »У + - №•> + + +

2т

+ + еХ'(Т~^ + (Ту + Ту +,) ^ +... + ЦТ-Ту- 0е^"').

2т

Лемма 9. Если /у = 1 и Я,Т(1 +([,) - 1 < 0, то для математического ожидания Магу., второй компоненты стационарной марковской цепи {(Г,-, аг,-./, ¡;'у,¡-1); ( = 0, 1, ...} имеет место равенство: Магу,, = - ЦГ{\ + + (ХуГ)2(1 + ^у)2) + (2т)',Х1(\ + х х ((2т - 1 )Ту + (2да - 2)Г2у + ] + ... + Г^).

В четвертой главе методами имитационного моделирования проведено численное исследование выходного процесса системы с целью определения квазиоптимальных параметров циклического управления конфликтными потоками Гнеденко—Коваленко. Для рассматриваемых в этой работе систем в общем случае аналитическим путем не удается получить такие ее важные вероятностные характеристики, как законы распределения длин очередей, времени ожидания начала обслуживания требований по потокам и законы распределения выходных потоков. Поэтому важно найти численные оценки этих и других характеристик. Принцип поэлементного строения управляемых систем обслуживания с переменной структурой позволяет построить имитационную модель такого рода систем. Результаты исследований на имитационной модели проинтерпретированы на задаче управления конфликтными транспортными потоками на пересечении магистралей. С использованием теоретических результатов первых трех глав и метода имитационного моделирования решается задача определения квазиоптимального управления транспортными потоками на изолированных перекрестках. В этом случае за счет укрупнения некоторых состояний Г(1), Г<2), ..., Г<гт) светофора задача управления т потоками легко сводится к задаче управления двумя наиболее интенсивными потоками. Итак, в имитационной модели, ради простоты, полагаем, что т = 2 и интенсивными потоками будут П1 и П 2.

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

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

На имитационной модели в квазистационарном режиме вычислялись с заданной надежностью (доверительной вероятностью Р) и заданной точностью следующие основные характеристики: а) оценки М (уу) с точностью ei.y и D (у,) с точностью szj для среднего значения и соответственно дисперсии времени у,- ожидания начала обслуживания произ-

— ~ и i п ~

вольной заявки потока Пу; Ь) оценка М(у) = (£ X (1 + q •)) £ Я - (1 + ^ • )М(у •) среднего

_/=! j=\

взвешенното времени у ожидания начала обслуживания требования произвольного потока; с) оценки М (аеу) с точностью ёз. , и D (ж,) с точностью Zn_¡ для математического ожидания и соответственно дисперсии длины агу очереди машин потока Пу в произвольный момент начала его обслуживания; d) оценки М (¡;'у) с точностью z¡j и D (¡;'у) с точностью Еб.у математического ожидания и соответственно дисперсии числа ¡j'y заявок, которые покидают систему за произвольный акт обслуживания потока Пу; е) статистический закон распределения и гистограмма относительных частот числа требований, которые покидают систему за произвольный акт обслуживания потока Пу; f) значение р, оценки загрузки системы по каждому потоку Пу и значение pi,2* оценки для общей загрузки системы по двум потокам П i и П 2. Динамика оценок M(yi)> М(у2), М (у), б (у0, б(у2), М(®0> М (жг), D (asi), D(®2), М (с/,), M^y, D(^'i), D (с,'2) основных характеристик системы представлена в виде графиков.

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

Рассмотрим теперь плоскость с прямоугольной системой координат вида Т1ОТ3. На кривой равных оценок загрузок отдельно по потокам значение общей оценки pi>2 для загрузки системы уменьшается с увеличением длительности Т периода циклического управления потоками. При этом на кривой равных оценок загрузок отдельно по потокам максимальное значение оценки М (у) отличается от минимального значения оценки М (у) не более чем на 10%. На основании этих выводов предложен простой алгоритм поиска квазиоп-

тимальных длительностей Т\ , Гз фаз светофора с использованием модифицированного метода покоординатного спуска и сокращенного перебора. Этот алгоритм состоит из следующих этапов. Сначала специальным образом выбираем точки на кривой равных оценок загрузок отдельно по потокам. Затем методом перебора среди этих точек определяем такую точку (Г/1', Гз'"), для которой величина М(у) принимает минимальное значение. Наконец, строим равномерную сетку на прямой {(Т1, Гз): Г1 + Гз = Г/1' + Гз(1)} с заданным шагом и среди узлов этой сетки выбираем квазиоптимальную точку вида (Т\ , Гз ) по условию минимума оценки М(у). Приведены рекомендации по определению квазиоптимальных параметров циклического управления конфликтными транспортными потоками на перекрестке и указаны свойства квазиоптимального управления. Установлено, что квазиоптимальное управление обеспечивает стандартизацию выходных потоков.

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

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

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

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

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

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

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

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

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

1.Федоткш1, A.M. Свойства управляемой векторной марковской цепи со счетным числом состояний, удовлетворяющей рекуррентным соотношениям / A.M. Федоткин // Вестник Нижегородского университета им. Лобачевского. -2009. - № 3. - С. 152-161.

2. Федоткин, A.M. Определение стационарного режима рекуррентных марковских цепей итеративно-мажорантным методом / A.M. Федоткин // Вестник Нижегородского университета им. Лобачевского. -2009. - № 4. - С. 130-140.

3.Федоткин, М.А. Анализ и оптимизация выходных процессов при циклическом управлении конфликтными транспортными потоками Гнеденко-Коваленко / М.А. Федоткин, A.M. Федоткин // Автоматика и телемеханика. РАН. - 2009. - № 12. - С. 92-108.

4. Федоткин, А.А. Изучение свойств потока Гнеденко-Коваленко / А.А. Федоткин, A.M. Федоткин // Вестник Нижегородского университета им. Лобачевского. -2008. - № 6. -С. 156-160.

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

5. Fedotkin, A.M. Model for Refusals of Elements of a Controlling System / A.M. Fedotkin, M.A. Fedotkin // Transactions of the first French-Russian Conference on "Longevity, Aging and Degradation Models in Reliability, Public Health, Medicine and Biology, LAD 2004", St. Petersburg State Politechnical University, Saint Petersburg, 2004. - Vol. 2. -P. 136-151.

6. Fedotkin, M.A. Mathematical Models of a Flow of a Controlling System Refusals / M.A. Fedotkin, A.M. Fedotkin // Book of Abstracts of the VI International Congress on Mathematical Modeling, University of Nizhny Novgorod, Russia, 2004. - P. 80.

7. Федоткин, A.M. Математические модели транспортных потоков на автомагистрали и на управляемом по циклическому алгоритму перекрестке / A.M. Федоткин; Нижегородский государственный университет им. Н. И. Лобачевского, Нижний Новгород. 2009. - 30 с. - Деп. в ВИНИТИ 11.01.09, № 5-В2009.

8. Федоткин, М.А. Статистический анализ потока отказов восстанавливаемых систем и проблема профилактики / М.А. Федоткин, A.M. Федоткин // Сборник научных статей VI Международной конференции "MMR 2009 -Математические методы в теории надежности: Теория. Методы. Приложения", М.: РУДН, 2009. - С. 322-326.

9. Федоткин, A.M. Арифметические свойства распределений выходного процесса при циклическом управлении потоками Гнеденко — Коваленко / A.M. Федоткин; Нижегородский государственный университет им. Н. И. Лобачевского, Нижний Новгород. 2009. -24 с. - Деп. в ВИНИТИ 14.04.09, № 213-В2009.

10. Федоткин, A.M. Предельные свойства распределений выходного процесса при циклическом управлении потоками Гнеденко-Коваленко / A.M. Федоткин; Нижегород-18

ский государственный университет им. Н. И. Лобачевского, Нижний Новгород. 2009. -26 с. - Деп. в ВИНИТИ 22.06.09, № 389-В2009.

11. Федоткин, М.А. Кодирование потока сбоев и надежность управляющих систем / М.А. Федоткин, A.M. Федоткин // Сборник научных статей X Международного семинара "Дискретная математика и ее приложения", М.: МГУ, 2010. - С 145-147.

Публикации, определенные ВАК России по смежным специальностям:

12. Федоткин, A.M. Способ автоматического управления аэрацией при культивировании микроорганизмов, культур клеток и тканей / A.M. Федоткин, Д.В. Зудин, С.Б. Котова, О.Ю. Гадалов // Авторское свидетельство СССР на изобретение № 1632045 AI приоритет изобретения 20.06.1989 от 01.11.1990.

13. Федоткин, A.M. Об одной оптимизационной задаче для нелинейной системы с ограничениями / A.M. Федоткин // Материалы IV Научной конференции молодых ученых НИИ ПМК при ГГУ и факультета ВМК ГГУ, Горьковский госуниверситет им. Н.И. Лобачевского, Горький. 1985. - 6 с. - Деп. в ВИНИТИ.

14. Зудин, Д.В. Оптимальное управление одним классом биотехнологических процессов / Д.В. Зудин, A.M. Федоткин // Сборник тезисов докладов Совещания-семинара "Использование вычислительных средств в экологии, экономике медицине", Горький: Горьковский госуниверситет им. Н. И. Лобачевского, 1986. - С. 43—45.

15. Федоткин, A.M. Идентификация математических моделей и управление процессом ферментации / A.M. Федоткин, Д.В. Зудин // Математическое моделирование, управление и оптимизация: Сборник статей / Под ред. A.B. Сергиевского. Горьковский государственный университет им. Н.И. Лобачевского. Горький. 1988. - 11 с. - Деп. в ВИНИТИ 15.07.88, №5714-В88.

16. Федоткин, A.M. Синтез особой экстремали и ее оптимальность в одной задаче оптимального управления / A.M. Федоткин // Тезисы докладов Восьмой Всесоюзной конференции "Проблемам теоретической кибернетики", Горький: ГГПИ, 1988. - Ч. 2. -С.145-146.

17. Федоткин, A.M. Адаптивные алгоритмы управления для робототехнических систем научных исследований биотехнологических процессов / A.M. Федоткин, Д.В. Зудин // Сборник тезисов докладов V Всесоюзного совещания по робототехническим системам, Москва - Геленджик, 1990.-С. 148-149.

Федоткин Андрей Михайлович

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

конфликтными потоками Гнеденко—Коваленко В диссертации предложен простой механизм динамики образования неординарных потоков требований. Дано обоснование использования потока Гнеденко—Коваленко для адекватного описания процесса транспортного движения на автомагистрали с учетом его пространственных и временных характеристик. Поставлена и решена задача нелокального описания выходных потоков в неклассических системах массового обслуживания неоднородных требований. Разработан итеративно-мажорантный метод изучения особенностей и эргодических свойств вероятностной модели систем управления конфликтными потоками в классе циклических алгоритмов с переналадками. Для такого рода систем предложен алгебраический метод получения аналитических выражений стационарных характеристик. Эти характеристики являются аналогами известных формул Поллачека—Хинчина для классических систем. С использованием теоретических результатов и средств имитационного моделирования решена задача оптимизации циклического управления по условию минимума среднего взвешенного времени ожидания начала обслуживания произвольного требования в стационарном режиме.

Fedotkin Andrey Mikhajlovich

Simulation and optimization of output processes under cyclic control over conflict Gnedenko-Kovalenko flows In this thesis we propose a simple mechanism for formation dynamics of nonordinary flows of demands. We justify the use of the Gnedenko-Kovalenko flow for an adequate description of the traffic on a highway with regard to its spatial and temporal characteristics. A problem of nonlocal description of output flows in the non-classical queueing systems with non-homogeneous demands has been posed and solved. An iterative majorating method for studying characteristics and ergodic properties of a probabilistic model of control systems with conflict flows in a class of cyclic algorithms with readjusments has been developed. An algebraic method of obtaining analytical expressions for stationary characteristics is proposed for such systems. These characteristics are analogous to the known Pollaczek-Khintchine formulas for classical systems. Using the theoretical results and means of computer-aided simulation an optimization problem for the cyclic control with the minimum weighted average waiting time for service start by an arbitrary demand in the steady state as an objective function has been solved.

Подписано в печать 03.11.2010. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Тираж 100 экз. Заказ № 681.

Отпечатано в Центре цифровой печати Нижегородского госуниверситета им. Н.И. Лобачевского 603000, Н. Новгород, ул. Б. Покровская, 37.

Введение.

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

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

1.2. Изучение свойств эргодического распределения числа неоднородных машин в транспортной пачке.

1.3. Определение транспортного потока Гнеденко—Коваленко и его вероятностные свойства.

1.4. Числовые характеристики потока Гнеденко—Коваленко.

1.5. Нелокальное описание входных потоков неоднородных требований.

И. Математическая модель выходного процесса при циклическом управлении конфликтными потоками Гнеденко—Коваленко.

II. 1. Постановка задачи на содержательном уровне.

11.2. Нелокальное описание составляющих элементов системы.

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

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

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

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

111.2. Условия существования стационарного режима в системе.

111.3. Алгебраический метод определения инвариантного распределения выходного потока.

III.4. Вычисление стационарных вероятностей состояний системы.

IV. Численное исследование и оптимизация выходных процессов при циклическом управлении конфликтными потоками.

IV. 1. Обоснование методики численного исследования системы на имитационной модели.

IV.2. Программная реализация имитационной модели и качественное исследование системы на имитационной модели.

IV.3.Определение квазиоптимального управления транспортными потоками на перекрестке с помощью имитационного моделирования.

Общая характеристика особенностей темы исследования

Основным интуитивным понятием в естественных науках является понятие системы. Система в каждом конкретном случае может быть физической, биологической, технической, экологической, экономической и т. п. Для многих реальных систем одна из важнейших функций — выполнение за некоторый случайный промежуток времени вполне определенной работы. Такая работа очень часто называется обслуживанием требований или заявок, которые возникают в случайные моменты времени. Можно сказать, что имеется массовый спрос на исполнение системой разного рода работ или, другими словами, имеется входной поток на обслуживание требований некоторым прибором. В силу такого функционального назначения такие системы называют системами массового обслуживания. Так как имеет место поток случайных моментов появления требований, и каждая заявка требует случайное время обслуживания, то в системе могут возникать задержки начала обслуживания, образовываться очереди из заявок и, наконец, могут происходить потери необслуженньтх требований. Каждому из нас в жизни в той или иной мере приходилось иметь дело с такой ситуацией. Например, можно наблюдать различные очереди: а) покупателей в магазинах и у касс; Ъ) больных на прием к врачу; с) судов перед шлюзами; б() автомобилей перед светофорами и станциями технического обслуживания; ё) самолетов на взлет и посадку; ]) станков на ремонт, вычислительных программ на обработку компьютером и т. п. Основные проблемы изучения таких систем заключаются в определении картины изменения во времени величины задержки начала обслуживания произвольной заявки, объема конкретной очереди, размера потерь необслуженных требований и величины обслуженных заявок. Теория массового обслуживания, используя методы теории вероятностей, математической статистики и математической кибернетики, позволяет частично или полностью решить эти проблемы.

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

За последние годы в теории очередей подробно изучены очень сложные и разнообразные модели реальных систем обслуживания. К таким системам, прежде всего, следует отнести: 1) системы с изменяемыми интенсивностями поступления и обслуживания требований; 2) системы с ненадежным прибором обслуживания; 3) системы с включением и выключением дополнительных устройств (линий) обслуживания; 4) системы с изменяемой дисциплиной формирования очереди; 5) системы по обслуживанию неоднородных требований, например, в классе приоритетных требований, в классе циклических алгоритмов, в классе алгоритмов с разделением времени; 6) управляемые системы массового обслуживания; 7) конфликтные системы обслуживания с переменной структурой. Методы построения и исследования математических моделей указанных и других реальных систем обслуживания в основном исчерпываются следующими тремя подходами.

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

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

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

В основе указанных подходов лежит так называемый локальный принцип, когда исходные и искомые характеристики системы обслуживания относятся к каждой отдельно взятой заявке, к каждому моменту времени. Это означает, что при построении вероятностной модели локальный принцип существенно затрудняет в полной мере отображение физической природы процесса обслуживания и его важных возможностей и особенностей. Например, не удается отобразить функции обслуживающего устройства по управлению потоками заявок и его функции ориентации и переналадок, неоднородность требований, адаптивную изменчивость с течением времени вероятностной структуры входных потоков, изменчивость длительности обслуживания и логической структуры системы. Необходимо также принимать во внимание конфликтность ситуаций при управлении потоками и при обслуживании требований. Поэтому при первом подходе не решена проблема математического описания структуры системы, а при втором подходе возникают большие трудности определения совместного распределения числа получивших отказ в обслуживании заявок и числа обслуженных требований по реальным вероятностным свойствам составляющих элементов системы обслуживания (входного потока требований, длительностей обслуживания заявок и структуры системы). Более того, если построение модели системы обслуживания основано на локальном принципе, то даже при достаточно простых законах распределения входных потоков и длительностей обслуживания приходится решать очень трудные вопросы теории случайных процессов обслуживания. Еще более усложняется проблема, если системе требуется обслуживать неоднородные требования конфликтных потоков. В этом случае параметры составляющих элементов системы массового обслуживания допускают применение воздействий для достижения некоторой поставленной цели, например, для получения наименьшего среднего времени пребывания произвольного требования в системе. В последнем случае рассматривают циклические системы, системы с разделением времени, приоритетные системы и, наконец, управляемые системы массового обслуживания [45—68], математическими моделями которых являются как управляемые марковские случайные процессы [69], так и управляемые случайные процессы общего вида [70]. Обзор результатов с очень обширной библиографией по управляемым системам массового обслуживания приводится в [58, 59].

На кафедре прикладной теории вероятностей Нижегородского госуниверситета разрабатывается третий подход [71—103], который учитывает недостатки предыдущих подходов. В основе построения, анализа и оптимизации моделей реальных систем обслуживания при таком подходе лежат следующие положения: принцип поэлементного строения системы из внешней среды, входных потоков, потоков насыщения, очередей (накопителей) заявок по потокам, стратегий механизма отбора на обслуживание требований из очередей по потокам, обслуживающего устройства, алгоритма изменения структуры составляющих элементов системы, выходных потоков; принцип дискретности актов функционирования модели системы обслуживания в моменты времени т,-, г = 0, 1, ., которые специальным образом связаны с моментами поступления требований или с моментами изменения структуры составляющих элементов системы; принцип интегральности (нелокальности) в математическом описании составляющих элементов системы обслуживания, когда исходные и искомые ее характеристики рассматриваются либо на интервалах [х,-, т; + 1), г > 0, оси времени [0, либо в строби-рующие моменты г,-, / > 0.

Третий подход позволяет на этапе построения модели учесть в дальнейшем решение сложных вопросов определения и анализа конечномерных распределений случайных процессов, которые описывают функционирование системы обслуживания с точки зрения ее искомых характеристик. Эффективность этого подхода была показана при рассмотрении следующих реальных процессов: 1) адаптивного регулирования транспортных потоков на перекрестках со сложной геометрией переезда [94, 96, 99, 100]; 2) управления технологическими и информационными сигналами микросварочного комплекса при сборке интегральных схем на кристаллах [84]; 3) диспетчерского и экспертного контроля за последовательностью взлетов и приземлений самолетов [88]; 4) обработки информационных потоков программ в локальных вычислительных сетях [97, 98]; 5) управления конфликтными потоками самолетов при прохождении пересекающихся воздушных коридоров [76, 86]; 6) управления потоками с неоднородными и повторными вызовами в системах с переменной структурой обслуживания [102, 103]; 7) управления потоками транзакций в центре авторизации магнитных пластиковых банковских карточек [101]. Для большинства из указанных здесь реальных процессов обслуживания, пользуясь третьим подходом, представляется возможным решить известную в классической теории очередей проблему выходных потоков. Первые результаты в этом направлении представлены в работах [104, 105]. В следующем абзаце более подробно остановимся на важности и решении проблемы выходных потоков.

В последнее время возрос интерес к теории массового обслуживания благодаря ее многочисленным приложениям к анализу и организации работы: 1) реальных компьютерных и коммутационных сетей; 2) информационно-вычислительных систем; 3) автоматизированных систем управления; 4) различных транспортных систем и т. д. Сети массового обслуживания служат, как правило, адекватными моделями для такого рода систем. Каждая сеть массового обслуживания включает несколько связанных между собой узлов (систем массового обслуживания). Поэтому при рассмотрении конкретной сети массового обслуживания всегда необходимо изучить вероятностные свойства выходного потока одного узла (одной системы обслуживания), который затем будет входным потоком для следующего узла (другой системы обслуживания). Первые исследования [106—109] по теории выходных потоков появились в середине XX века.

Для стационарного состояния системы MIMIC Берк [106] показал, что промежутки времени между требованиями, покидающими систему, взаимно независимы. В этой системе обслуженные требования, покидающие систему, образуют пуассоновский поток с тем же параметром X, который характеризует распределение входного потока. Это обстоятельство ожидалось ранее интуитивно, на основании свойств распределения стационарного состояния системы. Берк установил, что в стационарном режиме длительность случайных промежутков времени между моментами, когда требования покидают систему, не влияет на состояние системы в конце этого промежутка. Рейч [108], применяя другие методы, доказал, что если промежутки времени между требованиями, поступающими в од-ноканальную систему, и промежутки времени их обслуживания распределены по нормированному закону Х4 с четырьмя степенями свободы (некоторое изменение допущений Берка), то распределение промежутков времени между требованиями, покидающими систему, не подчиняются закону с четырьмя степенями свободы. Значит, в общем случае не стоит ожидать, что выходной поток будет совпадать с входным потоком даже для стационарного режима работы системы. Кроме того, Рейч показал, что в одноканальной системе с пуассоновскими входным и выходным потоками время обслуживания либо с вероятностью единица равно нулю, либо имеет экспоненциальное распределение. Эта теорема является обратной по отношению к теореме Бёрка. Финч [109] показал, что выходящий поток будет в точности пуассоновским только в том, случае, когда допускается очередь бесконечной длины при экспоненциальном времени обслуживания.

В связи с результатами Финча [109] следует отметить, что помимо задачи определения и исследования свойств выходных потоков при полностью заданной системе существует и в некотором смысле обратная проблема. Обратная проблема естественно возникает, когда по наблюдаемым свойствам выходного потока требуется восстановить неизвестные характеристики самой системы обслуживания. Некоторые вопросы этой проблемы решались, например, в работе [110]. На трудность прямой и обратной задачи указывают результаты работ [111, 112]. В работе [111] изучаются свойства выходного потока для однолинейной системы с ожиданием, марковским входным потоком и показательным законом обслуживания. В работе [112] доказывается, что основные результаты работы [111] являются ошибочными. В работе [ИЗ] для системы с ожиданием типа MIGI1 и M/G/i/K получено совместное распределение определенного числа последовательных интервалов времени между моментами ухода требований из системы. Аналогичные результаты приведены в [113] для системы с ожиданием типа M/G/l/К. В работе [114] рассматривается система из конечного числа накопителей бесконечного объема, в каждый из которых независимым образом поступает пуассоновский поток. В момент времени, когда все накопители оказываются непустьми, из каждого накопителя мгновенно удаляется одно требование. В этой работе доказывается, что выходной поток таких моментов в стационарном режиме является пуассоновским. В работе [115] авторы изучают распределение промежутков времени в выходящем потоке необслуженных требований в пакетной системе GJG! 1 с некоторой дисциплиной, допускающей потери требований. Решена также аналогичная задача в ее дискретном варианте, т. е. для системы GDJGD/1.

В работе [116] изучается распределение числа требований, обслуженных в течение периода занятости для однолинейной системы с дискретным временем, пакетным геометрическим входящим потоком и дискретным распределением времени обслуживания требований. В статьях [117—119] рассматривается также однолинейная система массового обслуживания, но уже с произвольным распределением времени обслуживания, неограниченной очередью и неординарным входным потоком требований (моменты поступления требований образуют процесс восстановления). В [117—119] найдены только формулы для преобразований Лапласа длительности периода занятости и распределения числа требований, обслуженных на периоде занятости. В работе [120] для стационарного режима системы массового обслуживания типа Geom/Geom/1 с дискретным временем получено распределение числа требований, обслуженных на периоде занятости. В работах [121, 122] изучается асимптотическое поведение системы с ожиданием и одним прибором в случае, когда распределения интервалов между поступлениями заявок и времен обслуживания являются субэкспоненциальными. Показано, что асимптотика хвостов распределения интервалов между выходами требований из системы массового обслуживания в основном определяется более тяжелым из хвостов распределений интервалов между поступлениями заявок и времен обслуживания. В работе [123] для системы массового обслуживания типа М{С)Ю1\ доказано, что выходной поток всегда более регулярен, чем входной.

Приведенный обзор результатов по теории выходных потоков касался в основном простейших систем: рассматривались одноканальные системы обслуживания с неограниченной очередью, входные потоки полагались пуассоновскими, обслуживание требований осуществлялось по показательному закону. Дальнейшие исследования выходного потока для систем, которые даже незначительно отличаются от классического случая, не приводили к сколько-нибудь существенным результатам. Отсюда и возникла известная в литературе проблема выходного потока. В нашей стране выходными потоками в разное время занимались Б.В. Гнеденко, И.И. Ежов, И.Н. Коваленко, М.А. Федоткин, Г.Ш. Цициашвили и др. Данные авторы, как правило, также рассматривали одноканальные системы, но уже с некоторыми усложнениями, касающимися вида входного потока, дисциплины формирования очереди и механизма обслуживания. При этом выходной поток в работах Б.В. Гнеденко, И. И. Ежова, И.Н.Коваленко, Г.Ш. Цициашвили всегда описывался аналогично входному, используя для этого один из следующих эквивалентных классических способов: 1) задавали так называемый считающий случайный процесс {<;'(/); / >0}, где неотрицательная целочисленная случайная величина при О0 определяет число обслуженных системой заявок за промежуток времени [0, и £;'(/) = ¡;'(/ - 0), £,'(0) = 0; 2) указывали векторную случайную последовательность {(<;'„ г > 1}, в которой через <;',■ и обозначены соответственно г'-й момент появления требований на выходе и число требований обслуженных системой в этот момент времени; 3) определяли векторную последовательность {(<;',- - <;',- 1, 1); / > 1}, где д'0 = 0. Эквивалентность трех вышеперечисленных способов описания потоков заявок доказана в [8]. Если для описания выходного потока использовать один из этих способов, то не удается найти конечномерные распределения выходного процесса даже применительно к несложным управляемым системам обслуживания. Это становится возможным только в исключительно редких случаях [29], а задача исследования распределения выходного потока в общем случае является трудноразрешимой проблемой. Поэтому имеет большое значение разработка нетрадиционных подходов для получения теоретических и практических результатов в этой области.

Ясно, что выходной поток существенно зависит от системы массового обслуживания, в которой он формируется. Значит, в описание выходного потока необходимо включать некоторые составляющие элементы и искомые характеристики системы массового обслуживания. Более того, целесообразно следить не за отдельным требованием, покидающим систему, а за некоторой случайной группой обслуженных заявок. Впервые такой подход был предложен в работах [85, 87, 92, 95] и назван нелокальным способом описания входных и выходных потоков требований.

Основные положения и краткий обзор работы

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

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

В отличие от большинства известных трудов, для построения математической модели выходных потоков в работе используется так называемое нелокальное описание потока требований, предложенное в [85, 87, 92, 95]. В описание выходных потоков включены состояние обслуживающего устройства и величины очередей по конфликтным потокам. Заметим, что функционирование рассматриваемой системы обслуживания неоднородных требований и управления конфликтными потоками в непрерывном времени является сложным немарковским процессом. Поэтому изучение характеристик системы и свойств выходных потоков в непрерывном времени является трудноразрешимой задачей. Для решения данной проблемы, как правило, используется метод вложенных цепей Маркова. Суть метода состоит в том, что процесс обслуживания рассматривается в специально подобранные дискретные моменты времени, которые выбираются таким образом, чтобы новый процесс обладал свойством марковости. Однако проблема определения указанных моментов является очень сложной, поскольку не существует определенной методики или алгоритма их выбора. В диссертации проблема выбора специальных моментов времени решается уже на этапе построения математической модели системы обслуживания с переменной структурой.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

2. Erlang, A.K. Probability and telephone calls / A.K. Erlang // Nut Tidsskrift for Matematik. Ser. В. 1909.-Vol. 20. - P. 33-39.

3. Колмогоров, A.H. Sur le problème d attente / A.H. Колмогоров // Математический сборник. 1931.-T. 38. -№ 1-2.-С. 101 - 106.

4. Хинчин, А.Я. Математическая теория стационарной очереди / А.Я. Хинчин // Математический сборник. 1932. - Т. 39. - № 4. - С. 73 - 84.

5. Хинчин, А.Я. Работы по математической теории массового обслуживания / А.Я. Хинчин. -М.: Физматгиз, 1963. 236 с.

6. Pollaczek F. Zur Theorie desWartens von Schaltergruppen / F. Pollaczek // Elek. Nachr. -Tech. 1932. - Vol. 9. - P. 434 - 454.

7. Гнеденко, Б.В. Вычисление среднего перехода между станками / Б.В. Гнеденко // Иваново, Бюллетень ИВНИТИ. 1934. - № 1 - 2. - С. 117 - 122.

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

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

10. Palm, С. Intensitätsschwankungen in Fernsprechverkehr / С. Palm // Ericsson Technics. -1943.-Vol. 1,№44. P. 1-189.

11. 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.

12. 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.

13. Прохоров, Ю.В. Переходные явления в теории массового обслуживания / Ю.В. Прохоров // Литовский математический сборник. 1963. - Т. 3. - № 1. - С. 199 - 206.

14. Башарин, Г.П. Анализ очередей в вычислительных сетях / Г.П. Башарин, П.П. Бочаров, А.Я. Коган. М.: Наука, 1989. - 336 с.

15. Беляев, Ю.К. Предельные теоремы для редеющих потоков / Ю.К. Беляев // Теория вероятностей и ее применения. 1963. - Т. 8. - № 2. - С. 175 - 184.

16. Беляев, Ю.К. О развитии теории массового обслуживания и теории надежности в СССР / Ю.К. Беляев, Б.В. Гнеденко, И.А. Ушаков // Изв. АН СССР, Техническая кибернетика. 1977 - № 6. - С. 69 - 87.

17. Боровков, A.A. О дискретных системах массового обслуживания / A.A. Боровков // Теория вероятностей и ее применения. 1963. - Т. 8. - № 3. - С. 251 - 263.

18. Бусленко, Н.П. О суперпозиции стационарных ординарных потоков с ограниченным последействием / Н.П. Бусленко // Проблемы передачи информации. 1961. - № 8. -С. 79-82.

19. Висков, О.В. Вероятность потери вызова при большой интенсивности потока / О.В. Висков, Ю.В. Прохоров // Теория вероятностей и ее применения. 1964. - Т. 9. -№ 1.-С. 99- 104.

20. Джейсуол, Н. Очереди с приоритетами / Н. Джейсуол. М.: Мир, 1973. - 280 с.

21. Золотарев, В.М. Распределение длины очереди и числа действующих линий в системе типа Эрланга со случайными поломками и восстановлениями линий / В.М. Золотарев//Труды Математического института им. В. А. 1964.-Т. 71.-С. 51 -61.

22. Клейнрок, Л. Теория массового обслуживания / JI. Клейнрок. М.: Машиностроение, 1979.-432 с.

23. Климов, Г.П. Стохастические системы обслуживания / Г.П. Климов. М.: Наука, 1966.-244 с.

24. Коваленко, И.Н. Некоторые задачи массового обслуживания с ограничениями / И.Н.Коваленко // Теория вероятностей и ее применения. 1961. - Т. 6, № 2. -С.222 - 228.

25. Кокс, Д. Теория очередей / Д. Кокс, У. Смит. М.: Мир, 1966. - 220 с.

26. Королюк, B.C. Полумарковские процессы и их приложения / B.C. Королюк, А.Ф. Турбин. Киев: Наукова думка, 1976. - 184 с.

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

28. Прабху, Н. Методы теории массового обслуживания и управления запасами / Н. Прабху. М.: Машиностроение, 1969. - 356 с.

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

30. Севастьянов, Б.А. Задача о влиянии емкости бункеров на среднее время простоя автоматической линии станков / Б.А. Севастьянов // Теория вероятностей и ее применения. 1962. - Т. 7, № 4. - С. 438-447.

31. Smith, W.L. On the distribution of queueing times / W.L.Smith // Proc. Cambridge Phil. Soc. 1953. - Vol. 49. - P. 449 - 461.

32. Соловьев, А.Д. Резервирование с быстрым восстановлением / А.Д. Соловьев // Изв. АН СССР. Техн. кибернетика. 1970,- № 1 - С. 56 - 71.

33. 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.

34. 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.

35. Müntz, R. Wating time distribution for round-robin queueing systems / R. Müntz // Proceedings of Symposium on Computer Communications Networks, and Teletraffic. - New York. - 1972.-P. 429-439.

36. Huk, J. Cykliczne systemy obslugi masowej / J. Huk, J. Lukaszewicz // Roczniki Polskiego Towarzystwa Matematycznego, Matematyka Stosowana. 1973. - Ser. 3, № 1. -P. 85- 104.

37. Siegel, G. The stationary waiting time and other variables in single-server queues with specialities at the beginning of a busy period / G. Siegel // Zastosowania Matematyki, Appli-catones Mathematicae. 1973. - Ser. 13, № 4. - P 463 - 479.

38. Collings, T. W. R. A queueing problem in which customers have different service distributions / T. W. R. Collings // Applied Statistics. 1974. - Vol.23, № 1P. 75 - 82.

39. Freyer, В. Ein Bedienungssystem (M/G/+°°) mit zeitabhängiger Eingangsintensitat und Bedienungszeitverteilung / B. Freyer // Mathematische Operationsforschung und Statistik. 1974. - Vol.3, № 9. - P. 701 - 708.

40. Boxma, OJ. The single-server queue with random service output / O.J. Boxma // J. Appl. Probab. 1973. - Vol. 12, № 4. - P. 763 - 778.

41. Gergely, T. Investigation on the discrete GI/G/I/ queue with and without loss / T. Gergely, T.L. Torok // Kozponti fisikai Kutato intezet. Pubis. 1973. - № 39 - P. 1 - 30.

42. Cohen, J.W. On regenerative processes in queueing theory / J.W. Cohen // Lecture Notes in Economics and Mathematical Systems. Berlin & Heidelberg & New York. - 1976. -Vol.121. -P. 1-93.

43. Puke, T. Some exact results for dams with Markovian inputs / T. Puke, R.M. Phatarfod // J. Appl. Probab. 1976. - Vol. 13, № 2. - P. 329 - 337.

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

45. Suzuki, Т. On a queueing process with service depending on queue-length / T. Suzuki // Comment. Math. Univ. St. Pauli. 1961. - Vol. 10, № 1. - P. 1 - 12.

46. Неймарк, Ю.И. О работе автомата, регулирующего уличное движение на перекрестке / Ю.И. Неймарк, М.А. Федоткин // Автоматика и телемеханика. 1966 - Т. 17, № 3. -С. 78-87.

47. Neuts, M.F. A queue subject to extraneous phase changes / M.F. Neuts // Adv. Appl. Probab. 1971. - Vol.3, № 1. - P. 78 - 119.

48. Гнеденко, Б.В. Приоритетные системы обслуживания / Б.В. Гнеденко, Э.А. Дание-лян, Б.Н. Димитров, Г.П. Климов, В.Ф. Матвеем. М.: Издательство Московского университета, 1973.-447 с.

49. Meyer, K.H.F. Ein Wartesystem mit heterogenen Kanalen unter (s,S)-Regel / K.H.F. Meyer // Proceedings in Operations Res. 2. Wiir/burg-Wien. 1973. - P. 293 - 317.

50. Szczotka, W. M/G/I queueing system with "fagging" service channel / W. Szczotka // Zas-tosowania Matematyki. Applications Mathematicae. 1973. - Ser. 13, № 4. - P. 439 - 463.

51. Gaur, R.S. An intermittant MI(X)/G'Y)/I system with muliphased capacity of the service channel / R.S. Gaur // Automatique Informatique Recherche Operationnelle. 1973. - Vol. 7, № l.-P. 97- 106.

52. Purdue, P. The М/М/l/ queue in a Markovian environment / P. Purdue // Operatin Research. 1974. - Vol. 22. - № 3. - P. 562 - 569.

53. Prabhu, N.U. Stochastic control of queueing systems / N.U. Prabhu // Naval Research Logistics Quarterly. 1974. - Vol. 21, №3,-P. 411-418.

54. Климов, Г.П. Системы обслуживания с разделением времени I / Г.П. Климов // Теория вероятностей и ее применения. 1974. - Т. 19, № 3. - С. 358 - 376.

55. Волковинский, М.И. Обслуживание с абсолютным приоритетом в системах с потерями на переключение / М.И. Волковинский, А.Н. Кабалевский // Автоматика и телемеханика,- 1975. № 10. - С. 35 - 42.

56. Goel, L.R. A limited space, fluctuating (0, A,) input source queueing problem with death and birth rates of the input source depending on queue length / L.R. Goel // Mathematische Operationsforschung und Statistic. 1975. - Vol. 6, No 3. - P. 437 - 444.

57. Andreatta, G. Problemi di ottimizzazione nella teoria delle code / G. Andreatta // Rend. Sem. Mat. Univ. Padova. 1975. - Vol. 53. - P. 123 - 134.

58. Рыков, B.B. Управляемые системы массового обслуживания / В.В. Рыков // Итоги науки и техники. М.: ВИНИТИ, 1975. - Т. 12. - С. 43 - 153.

59. Файнберг, М.А. Управление в системах массового обслуживания / М.А. Файнберг, Е.А. Файнберг // Зарубежная радиоэлектроника. 1975. - № 3. - С. 3 - 34.

60. Deb, R.K. Optimal control of batch service queues with switching costs / R.K. Deb // Adv. Appl. Probab. 1976. - Vol. 8, № 1. - P. 177 - 194.

61. Robinson, D.R. Markov decision chains with unbounded costs and applications to the control of queues / D.R. Robinson // Adv. Appl. Probab. 1976. - Vol.8, № l.-P. 139 - 176.

62. Harrison, J.M. Dynamic scheduling of a two-class queue: small interest rates / J.M. Harrison // "SLAM J. Appl. Math. 1976. -Vol. 31, № 1. - P. 31 - 61.

63. Климов, Г.П. Системы обслуживания с разделением времени II / Г.П. Климов // Теория вероятностей и ее применения. 1978. - Т.23. - № 2. - С. 331 - 339.

64. Жданов, B.C. Условия существования установившихся режимов в циклических системах массового обслуживания / B.C. Жданов, Е.А. Саксонов И Автоматика и телемеханика. 1979. - № 2. - С. 29 - 38.

65. Ушаков, В.Г. Приоритетиые системы с рекуррентными входящими потоками / В.Г. Ушаков, Н.Г. Ушаков. М.: Изд-во фак. ВМиК МГУ, 2000. - 44 с.

66. Bocharov. P.P. A queueing system of finite capacity with the server requiring a priority search for customers / P.P. Bocharov, C. D'Apice, B.D'Auria, S. Salerno // Вестник РУДН, сер. Приклада, матем. и информ. 2000.- №. 1. - С. 49 - 59.

67. Ilajiyen Asat, Y. Mathematical models of queueing systems with cyclic services / Y. Haji-yen Asat, A. Ibadova Irada // Proc. Inst. Math, and Mech. Azerb. Acad. Sci. 2003. - Vol. 19-P. 75-80.

68. Афанасьева, Л.Г. Системы массового обслуживания с циклическими управляющими процессами / Л.Г. Афанасьева // Кибернет. и систем, анал. 2005. - № 1 - С. 54 - 69.

69. Дынкин, Е.Б. Управляемые марковские процессы и их приложения / Е.Б. Дынкин, А.А. Юшкевич. М.: Наука, 1975. - 338 с.

70. Гихман, И.И. Управляемые случайные процессы / И.И. Гихман, А.В. Скороход. -Киев: Наукова думка, 1977.-252 с.

71. Федоткин, М.А. Выбор экстремальных параметров автоматизированной системы "Спрут", управляющей транспортными потоками / М.А. Федоткин, Б.Я. Княжицкий // Материалы VI Всесоюзной конференции по экстремальным задачам. Таллин, 1973.-С. 42-43.

72. Федоткин, М.А. Теоретико-множественный подход при анализе дискретных нелинейных систем массового обслуживания / М.А. Федоткин // Автоматика и вычислительная техника. 1975. - № 2. - С. 58 - 64.

73. Федоткин, МА. Алгебраические свойства распределений для функционалов Чжуна от однородных марковских цепей со счетным множеством состояний / М.А. Федоткин // Докл. АН СССР. 1976. - Т. 227, № 1. - С. 43 - 46.

74. Федоткин, М.А. О существовании эргодического распределения в системе с переменной структурой обслуживания конфликтных потоков / М.А. Федоткин // Теория вероятностей и ее применения. — 1976. Т. 21, № 4. - С. 792 — 801.

75. Fedotkin, М.А. On a class of stable algorithms for control of conflicting flows of arriving airplanes / M.A. Fedotkin // Problems of Control and Information Theory. — 1977. Vol.6, № l.-P. 13-22.

76. Федоткин, М.А. Управление конфликтными потоками заявок по минимальной информации о состоянии системы с переменной структурой обслуживания / М.А. Федоткин // Изв. АН СССР. Техн. кибернетика. 1977. - № 6. - С. 65 - 71.

77. Федоткин, М.А. Построение модели и исследование нелинейных алгоритмов управления интенсивными конфликтными потоками в системе с переменной структурой обслуживания. I / М.А. Федоткин // Литовский математич. сборник. 1977. - Т. 17, № 1,-С. 193-204.

78. Fedotkin, М.А. On limiting theorems for a certain class of service stochastic processes / M.A. Fedotkin // Second Vilnius Conference on Probability Theory and Mathematical Statistics. 1977. - Vol. 3. - P. 52 - 55.

79. Федоткин, M.A. Оптимизация параметров автомата с жестким переключением, управляющего потоками машин на перекрестке со сложной геометрией переезда / М.А. Федоткин, Б.Я. Княжицкий // Динамика систем. Горький. - 1978. - Вып. 14. -С. 35-53.

80. Федоткин, М.А. Задача управления пересекающимися потоками / М.А. Федоткин // Изв. АН СССР. Технич. кибернетика. 1978. - № 3. - С. 85 - 91.

81. Ваганов, А.О. Изучение систем обслуживания с мгновенным переключением прибора по запросу одного из конфликтных потоков / А.О. Ваганов, М.А. Федоткин // Изв. АН СССР. Техн. кибернетика. 1980 - № 2 - С. 60-68.

82. Федоткин, M.А. Неполное описание потоков неоднородных требований / М.А. Фе-доткин В кн.: Теория массового обслуживания. М.: МГУ, ВНИИСИ, 1981. -С. 113-118.

83. Федоткин, М.А. Теория дискретных систем с переменной структурой обслуживания квазигенерирующих потоков: дис. . доктора ф.-м. наук / Федоткин Михаил Андреевич М., МГУ, 1984. - 352 с.

84. Голышева, Н.М. Циклическое управление конфликтными потоками в условиях гибели и рождения очередей критических размеров / Н.М. Голышева, М.А. Федоткин // Автоматика и телемеханика. 1990. - № 4. — С. 68 - 75.

85. Fedotkin, М.А. On the class of algorithms for adoption traffic control / M.A. Fedotkin, Lit-vak N.V. // Proceedings of the International conference "Distributed computer communication networks (DCCN'96)", Tel Aviv, University, 1996. - P. 73 - 77.

86. Высоцкий, А.А. Предельные свойства и оптимизация процессов с разделением времени / А.А. Высоцкий, М.А. Федоткин // Доклады РАН. 1996. - Т. 350, № 3. -С.295 - 297.

87. Федоткин, М.А. Процессы обслуживания и управляющие системы / М.А. Федоткин // Математические вопросы кибернетики. М.: Наука, 1996. — Вып. 6 - С. 51 - 70.

88. Федоткин, M.A. Нелокальный способ задания управляемых случайных процессов / М.А. Федоткин // Математические вопросы кибернетики. М.: Наука, 1998. -Вып. 7.-С. 333-344.

89. Fedotkin, M.A. Random processes of adaptive control for conflict flows / M.A. Fedotkin, N.V. Litvak // Proceeding of the International conference "Prague Stochastic'98", Prague, Czech Republic, 1998.-P. 147- 152.

90. Федоткин, M.A. Конфликтные сети связи и управляющие системы обслуживания / М.А. Федоткин // Сборник трудов X научно-технической конференции «Проблемы радиосвязи», ГУЛ НПП "Полет", Н. Новгород, 1999. С. 28 - 31.

91. Fedotkin, M.A. Conflict networks of a queuing in conditions of callbacks and random medium / M.A. Fedotkin // Proceedings of the International conference "Computer science and information technologies (CSIT'99)", Yerevan, Armenia, 1999. P. 47 - 55.

92. Литвак, H.B. Вероятностная модель адаптивного управления конфликтными потоками / Н.В. Литвак, М.А. Федоткин // Автоматика и телемеханика. РАН. — 2000. № 5. -С. 67-76.

93. Литвак, Н.В. Вероятностная модель адаптивного управления конфликтными потоками. Качественное и численное исследование / Н.В. Литвак, М.А. Федоткин // Автоматика и телемеханика. РАН. 2000. - № 6. - С. 69 — 78.

94. Зорин, А.В. Оптимизация управления дважды стохастическими неординарными потоками в системах с разделением времени / А.В. Зорин, М.А. Федоткин // Автоматика и телемеханика. РАН 2005. - № 7. - С. 102 - 111.

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

96. Пройдакова, Е.В. Управление выходным потоками в системе с циклическим обслуживанием и переналадками / Е.В. Пройдакова, М.А. Федоткин // Автоматика и телемеханика. РАН. 2008. - № 6. - С. 96 - 106.

97. Burk, P.J. The Output of Queueing System / P.J. Burk // Operations Research. 1956. -Vol. 4,- P. 699 - 704.107108109110111112113114115116117.118,119.120,121.

98. Cohen, J.W. On the Queueing Process of Lanes / J.W. Cohen // Philips Tech. Rept. 1956. Reich, E. Waiting Times When Queues are in Tandem / E. Reich // Ann. Math. Statist. -1957.-Vol. 28, №3.-P. 768.

99. Finch, P.D. The Output Process of the Queueing System M/G/l / P.D. Finch // J. Roy. Statist. Soc. Ser. B. - 1959. - Vol. 21, № 2. - P. 375 - 380.

100. Takagi, H. Correlation of inderreparture M/G/X and MIGIMK / H. Takagi, T. Nishi // J. Oper. Res. Soc. Jap. 1998. - Vol. 41, № 1. -P. 142-151.

101. Prabhakar, B. The Ssynhronization of Puasson process and queuens networks with service and synchronization nodes / B. Prabhakar, N. Bambos // Adv. Appl. Probability. — 2000. — Vol. 32, №3,-P. 824-843.

102. Georgieva, M. Some characteristics of output stream of unserved customers in GJGIX and GDJGD/1 systems / M. Georgieva, V. Bakeva // Мат.билт. Cojy3 мат. и инф. Македонка. 2000. - Vol. 24. - С. 131 - 140.

103. Georgieva, М. Busy period and number of customers served during the busy period in a GeomJGD/1 queueing system / M. Georgieva, V. Bakeva // Мат.билт. Cojy3 мат. и инф. Македонка. 2000. - Vol. 24. - C.l21 - 130.

104. Ежов, И.И. Система обслуживания GJG/1 / И.И. Ежов, В.Ф. Каданков // Мат. студия. 2001. - Вып. 16, № 2. - С. 199 - 212.

105. Цициашвили, Г.Ш. Асимптотические характеристики выходных потоков в сетях массового обслуживания / Г.Ш. Цициашвили, Н.В. Маркова // Дальневост. мат. ж. -2003.-Вып. 4, № 1.-С. 36-43.

106. Маркова, Н.В. Асимптотические характеристики выходных потоков в сетях массового обслуживания / Н.В. Маркова, Г.Ш. Цициашвили // Сборник докладов Межд. науч. конф., 8-11 окт., 2003, Хабаровск, ХГТУ. 2003. - С. 365 - 368.

107. Владимиров, Свойство самоусреднения систем массового обслуживания / Владимиров, Рыбко, Шлоссман // Проблемы передачи информации. — 2006. — Т. 42, № 4. -С. 91-103.

108. Любимов, А.Д. Выходной поток в системе М/G/l с повторными вызовами / А.Д. Любимов // Обозрение прикладной и промышленной математики. — 2006. — Т. 13,№4.-С. 673-674.

109. Fedotkin, M.A. Mathematical Models of a Flow of a Controlling System Refusals / M.A. Fedotkin, A.M. Fedotkin // Book of Abstracts of the VI International Congress on Mathematical Modeling, University of Nizhny Novgorod, Russia, 2004. P. 80.

110. Федоткин, A.A. Изучение свойств потока Гнеденко-Коваленко / А.А. Федоткин,

111. A.M. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского.2008,- №6. -С. 156- 160.

112. Bartlett, М. S. The spectral analysis of point processes / Bartlett, M. S. // J. R. Statist. Soc.

113. B. 1963. - Vol. 25, № 2. - P. 264 - 296.

114. Федоткин, A.M. Свойства управляемой векторной марковской цепи со счетным числом состояний, удовлетворяющей рекуррентным соотношениям / А.М. Федоткин // Вестник Нижегородского университета им. Н.И. Лобачевского. 2009. - № 3. -С. 152-161.

115. Федоткин, A.M. Определение стационарного режима рекуррентных марковских цепей итеративно-мажорантным методом / A.M. Федоткин // Вестник Нижегородского университета им. Н. И. Лобачевского. -2009. № 4. - С. 130 - 140.

116. Федоткин, М.А. Анализ и оптимизация выходных процессов при циклическом управлении конфликтными транспортными потоками Гнеденко-Коваленко / М.А. Федоткин, A.M. Федоткин // Автоматика и телемеханика. РАН. 2009. - № 12. -С. 92- 108.

117. Хейт, Ф. Математическая теория транспортных потоков / Ф. Хейт. М.: Мир, 1966. -288 с.

118. Дрю, Д. Теория транспортных потоков и управление ими / Д. Дрю. М.: Транспорт, 1972.-424 с.

119. Иносэ, X. Управление дорожным движением / X. Иносэ, Т. Хамада. М.: Транспорт, 1983.-248 с.

120. Буслаев, А.П. Вероятностные и имитационные подходы к оптимизации автодорожного движения / А.П. Буслаев, A.B. Новиков, В.М. Приходько, А.Г. Таташев, М.В. Яшина. М.: Мир, 2003. - 368 с.

121. Беляев, Ю.К. Об упрощенной модели движения без обгона / Ю.К. Беляев // Изв. АН СССР. Техн. кибернетика. 1969. - № 3. - С. 17-21.

122. Федоткин, М. А. О работе автомата, регулирующего уличное движение на перекрестке при показательном законе обслуживания машин / М. А. Федоткин // Изв. ВУЗ. Радиофизика. 1967. - Т. 10, № 7. - С. 912 - 925.

123. Ширяев, А.Н. Вероятность / А.Н. Ширяев. М.: Наука, 1980. - 576 с.

124. Федоткин, МА. Основы прикладной теории вероятностей и статистики / Федоткин М.А. М.: Высшая школа, 2006. - 368 с.

125. Боровков, А. А. Теория вероятностей / А. А. Боровков. М.: Эдиториал УРСС, 1999. - 472 с.

126. Кокс, Д. Статистический анализ последовательностей событий / Д. Кокс, П.Льюис. -М.: Мир, 1969.-312 с.

127. Закс, Л. Статистическое оценивание / Л. Закс. — М.: Статистика, 1976. 600 с.

128. Ивченко, Г.И. Математическая статистика / Г.И. Ивченко, Ю.И. Медведев. — М.: Высшая школа, 1984. 248 с.

129. Айвазян, С.А. Прикладная статистика: Основы моделирования и первичная обработка данных / С.А. Айвазян, И.С. Енюков, Л.Д. Мешалкин. М.: Финансы и статистика, 1983. 472 с.

130. Крамер, Г. Математические методы статистики / Г. Крамер. М.: Мир, 1975. - 648 с.

131. Канторович, Л.В. Функциональный анализ / Л.В. Канторович, Г.П. Акилов. М.: Физматгиз, 1984. - 752 с.

132. Титчмарш, Е. Теория функций / Е. Титчмарш.-М.: Наука, 1980.-464 с.

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

134. Downton, F. On Limiting Distributions Arising in Bulk Service Queues / F. Downton // J. Roy. Statist. Soc. — Ser. В. —1956. — Vol. 18. — P. 265 274.

135. Webster, F.V. Traffic signal settings / F.V. Webster // Road Research Technical Paper. -London. 1958. - № 39. - P. 1 - 43.

136. Webster, F.V., Traffic signals / F.V. Webster, D.N. Cobbe // Road Res. Technical Paper, HMSO.-London.-1966.-№56.-P. 1-111.

137. Allsop, R.F. Delay-minimizing settings for fixed-time traffic signals at a single road junction / R.F. Allsop // J. Inst. Math. Applies. 1971. - Vol.8, № 2. - P. 164 - 185.

138. Allsop, R.F. Delay at a fixed-time traffic signal-I: theoretical analysis / R.F. Allsop // Trans. Sci. 1972. - Vol. 6, № 3, P. 164 - 185.