Адаптивное управление конфликтными потоками тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Литвак, Нелли Владимировна

• Литвак, Нелли Владимировна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Литвак, Нелли Владимировна

Оглавление

Введение

1 Математическая модель системы адаптивного управления конфликтными потоками 19 §1.1. Постановка задачи на содержательном уровне

§1.3. Рекуррентные соотношения для последовательности

{(Г,-, л'г-);г > 0} и для ее одномерных распределении

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

§2.2. Критерии существования предельного распределения

для {(Г,-, к,-); ъ > 0}

§2.3. Итеративно-мажорантный метод получения необходимых условий существования стационарного режима 63 §2.4. Достаточные условия существования предельного

распределения

3 Качественное исследование системы

§3.1. Графическая интерпретация предельных свойств адаптивного алгоритма .управления потоками

§3.2. О загрузке изучаемой системы

§3.3. Практические рекомендации по выбору наилучших

параметров алгоритма

4 Численное исследование системы методом имитационного моделирования

§4.1. Основные задачи исследования и методика их решения112

§4.2. Определение квази-оптимальных параметров

§4.3. Анализ адаптивных свойств системы на переходном

процессе

Заключение

Список использованной литературы

Приложения

А Дополнение к аналитическому исследованию

А.1 Выводы формул

А.2 Доказательства некоторых утверждений

В Иллюстрации качественного исследования системы

С Результаты имитационного моделирования

D Текст программы

Е Некоторые частные случаи изучаемого алгоритма

Е.1 Система с до обслуживанием по информации о длине

очереди

Е.2 Управление конфликтными потоками по информации

об интервалах поступления

Введение диссертации (часть автореферата) на тему «Адаптивное управление конфликтными потоками»

Введение

Характеристика изучаемой темы в целом

Задачи теории массового обслуживания возникли в начале XX века в связи с развитием и постоянным расширением телефонных сетей в крупных городах. Такие задачи впервые были описаны в 1907 г. Ф. В. Йоханнсеном /1/, а первые результаты были получены в 1909 г. датским математиком А. К. Эрлангом /2/. Работы Эрланга, которые относятся к 1909, 1917 и 1923 гг., стали основой классической теории массового обслуживания. Начиная с этого времени и по сегодняшний день теория массового обслуживания постоянно и интенсивно развивается, вызывая неизменный интерес у большого количества исследователей. Ведущую роль в развитии этой теории сыграли работы Ф. Поялачека, А. Н. Колмогорова, А. Я. Хинчина, Б. В. Гнеденко, И. Н. Коваленко, К. Пальма, Д. Кендалла, Д. Линдли, П. Морана, Л. Такача, Д. Кокса, В. С. Королюка, А. А. Боровкова. Различные системы массового обслуживания подробно рассмотрены в монографиях /3-13/ и других.

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

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

Широкий класс систем с несколькими потоками (или типами) заявок представляют из себя различные приоритетные системы. Исследование таких систем отражено в работах /14 -19/. В последнее время П. П. Бочаровым /20/ и А. В. Печинкиным /21/ были рассмотрены приоритетные системы при марковских входных потоках. Приоритетные системы вызывают значительный интерес, поскольку именно приоритетные алгоритмы управления оказываются оптимальными в системах с разделением времени при обслуживании нескольких конфликтных потоков заявок. Соответствующие результаты при различных предположениях о входных потоках и свойствах обслуживающего устройства были получены Г. П. Климовым /22, 23/, В. В. Рыковым /24/, М. А. Федоткиным /25, 26/, Е. А. Тимофеевым /27/, А. А. Высоцким /28/.

Другой широкий класс систем с несколькими потоками заявок представляют из себя системы с циклическим обслуживанием /10/, или циклические системы /29/. В таких системах переключения происходят в заданном заранее периодическом порядке. Основные результаты по циклическим системам массового обслуживания принадлежат таким исследователям, как П. Куен, Л. Клей-нрок, О. Боксма, В. С. Жданов, Е. А. Саксонов, X. Леви, М. Сиди, У. Ехиали и др. В циклических системах при обслуживании каждого из потоков могут применяться различные алгоритмы (режимы, стратегии). Наиболее распространенными являются следующие четыре алгоритма: 1) алгоритм полного освобождения, когда очередь каждого потока обслуживается до конца (exhaustive policy);

2) пакетный алгоритм, при котором обслуживающее устройство, подключившись к потоку, обслуживает все заявки, поступившие в систему до момента подключения (gated policy); 3) алгоритм, при котором обслуживающее устройство, подключившись к потоку, обслуживает не больше одной заявки этого потока (limited-1 policy); 4) обобщение третьего алгоритма - алгоритм, при котором обслуживающее устройство, подключившись к потоку, обслуживает не больше к заявок этого потока (^-limited policy). Более развернутая классификация дана в работах /30, 31/.

Для первых двух алгоритмов условия существования стационарного режима найдены и обоснованы в работе /32/. Эти условия сводятся к тому, что суммарная загрузка по всем потокам должна быть меньше единицы (под загрузкой для каждого потока здесь подразумевается отношение среднего времени обслуживания заявки к среднему промежутку времени между двумя последовательными поступлениями). Для систем с первым или вторым алгоритмом при различных предположениях о законах поступления и обслуживания получено много аналитических результатов, в том числе распределение длин очередей в стационарном режиме и среднее время ожидания /33-37/. Для третьего и четвертого алгоритмов условия существования предельного распределения выглядят по-другому /38, 39/. Кроме того, для четвертого алгоритма практически невозможно выразить стационарные характеристики системы через ее параметры. Циклическим системам и сравнению перечисленных выше традиционных алгоритмов посвящены обзоры /29/ и /40/. В работе /40/ показано, что из первых трех алгоритмов оптимальным с точки зрения средних задержек является алгоритм полного освобождения.

Наиболее распространенным реальным примером системы с конфликтными потоками является перекресток, регулируемый

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

В настоящее время на большинстве перекрестков используется алгоритм с фиксированным ритмом, когда длительности зеленого и красного света, а также порядок переключений заданы заранее и всегда одинаковы. Первые теоретические результаты для систем с подобным алгоритмом были получены Ю. И. Неймар-ком и М. А. Федоткиным /41/, а также А. Дж. Миллером /42/ и Д. Р. Мак Нейлом /43/. Эмпирическая формула для среднего времени ожидания была получена Ф. В. Вебстером /44, 45/. Подобные системы с различными предположениями о входных потоках и различными критериями оптимального управления рассмотрены в работах /46 - 51/. Алгоритм с фиксированным ритмом, безусловно, является самым простым и дешевым способом управления транспортом. Однако, к сожалению, даже при оптимальных параметрах

этот алгоритм далеко не всегда оказывается самым эффективным.

За последние двадцать лет было создано и изучено немало адаптивных алгоритмов управления конфликтными транспортными потоками с помощью автомата-светофора. При адаптивном алгоритме управления длительность зеленого света и порядок переключений зависят от той или иной информации о текущем состоянии перекрестка, что позволяет значительно лучше регулировать движение. Различные адаптивные алгоритмы описаны в работах /52 - 55/. В работах /49, 56, 57/ рассматривается алгоритм с приоритетным направлением. При таком алгоритме зеленый свет для неприоритетного направления имеет фиксированную длительность, а зеленый свет для более интенсивного (приоритетного) направления длится сначала некоторое заданное время, а затем продлевается, если очередь по неприоритетному направлению пуста. Для таких 'систем получены условия существования стационарного режима, построены имитационные модели и изучены свойства оптимального управления. В работах /58, 59/ рассматривается циклический алгоритм для двух транспортных потоков, где суммарная длительность цикла фиксирована, а длительности зеленого света для первого и второго потоков перераспределяются в зависимости от соотношения длин очередей. В работах /60, 61/ рассматривается циклический алгоритм, где зеленый свет продлевается, если по "зеленому" направлению поступает машина. Для такого алгоритма получен критерий существования стационарного режима в системе, а также найдены некоторые формулы и оценки для

4

средней длины очереди по каждому потоку. В работах /62 - 67/ рассмотрена система, где зеленый свет продлевается, если длина очереди по "зеленому" направлению превышает некоторое критическое значение.

Заметим, что пример перекрестка порой используется для ин-

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

В данной работе будет изучен класс алгоритмов управления транспортом, где длительность зеленого света зависит от длины очереди и наличия поступлений по "зеленому" направлению, а порядок переключений при определенных условиях зависит от очередности подхода машин. Для адекватного математического описания управления транспортом с помощью предлагаемого алгоритма будут использованы методы теории систем массового обслуживания с переменной структурой, которая разработана М. А. Федоткиным и обстоятельно изложена в работе /68/. Эта теория успешно применялась при анализе реальных систем управления конфликтными потоками. Сюда прежде всего относятся системы управления транспортом на перекрестке /58 - 67/, системы управления микросвар очными комплексами /69/, системы управления воздушным транспортом в аэропортах с несколькими взлетно-посадочными полосами /70/ и системы с разделением времени, которые являются адекватной моделью вычислительных систем /25, 26, 28/.

Общая схема СМО с переменной структурой изображена на рис. 1. В систему поступают входные потоки требований П^ П2, ..., Пт. Заявки каждого из потоков направляются в соответствую-

Рис. 1. Общая схема СМО с переменной структурой

щие накопители 0Ь 02, ..От ограниченной или неограниченной емкости. Требования из накопителей поступают на обслуживание согласно соответствующим стратегиям механизма обслуживания /Зь /32, ..., /Зт. При построении математической модели реальной системы эти стратегии нужно выбирать так, чтобы они как можно лучше отражали реальный процесс обслуживания. Обслуживающее устройство имеет п состояний Г^1), Г^2^, ..Г^, изменяющихся согласно некоторому алгоритму управления потоками. Для каждого из состояний определено свое функциональное назначение. Так, состояние ОУ может соответствовать обслуживанию одного из потоков или режиму переналадки, когда ОУ переключается от одного потока к другому /25/. При построении математических моделей реальных систем правильный выбор множества состояний ОУ не всегда очевиден, но всегда очень важен для получения удобного и в то же время полного математического описания системы. При описании СМО с переменной структурой различают два вида выходных потоков. Это реальные выходные потоки Пь Пг, . •Пто и потоки насыщения П'1? П'2, ..., П^, которые являются выходными потоками при максимальной загруженности и эксплуатации системы. Такие выходные потоки, например, возникают, если в системе всегда есть очередь, и ОУ работает с максимальной интенсивностью. Для математического описания систем обслуживания с переменной структурой используется нелокальный подход /68/. При таком подходе система рассматривается в специально выбранные случайные моменты вр'емени, и исследователь не интересуется, что происходит с системой между этими моментами.

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

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

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

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

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

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

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

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

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

Во второй главе получен ряд необходимых и достаточных условий существования предельного распределения изучаемой марковской последовательности. Для этого используется итеративно-мажорантный метод /68/, который предполагает анализ последовательностей производящих функций. В рассматриваемом случае эти производящие функции являются функциями двух переменных. В § 2.1 получены рекуррентные соотношения для различных производящих функций изучаемой марковской последовательности. В § 2.2 найдены необходимые и достаточные условия существования предельного распределения. Чтобы проверить эти условия, вообще говоря, нужно знать свойства одномерных распределений изучаемой марковской последовательности. В § 2.3 с помощью результатов § 2.2 найдены необходимые условия существования предельного распределения, которые зависят лишь от заданных параметров, то есть являются легко проверяемыми, или эффективными. Для получения этих условий был использован итеративно-мажорантный метод. Рассуждения в рамках этого метода были основаны на айализе рекуррентных соотношений для многомерных производящих функций при различных предположениях о значениях аргументов. Все полученные

условия объяснены на содержательном уровне. Кроме того, показано, как связаны найденные эффективные необходимые условия при различных ограничениях на параметры. В параграфе § 2.4 найдены и обоснованы легко проверяемые достаточные условия существования предельного распределения. Основные результаты главы 2 опубликованы в работах /80 - 82/. Громоздкие выводы формул, а также доказательства некоторых вспомогательных утверждений приведены в приложении А.

Третья глава содержит качественное исследование изучаемой системы. В § 3.1 предложена графическая интерпретация необходимых и достаточных условий существования в системе стационарного режима. Найдено несколько признаков, позволяющих понять, какой вид имеют множества наборов параметров, удовлетворяющих всем эффективным необходимым или достаточным условиям. Соответствующие иллюстрации приведены в приложении В. В § 3.2 рассмотрены вопросы, связанные с загрузкой изучаемой системы. Получить точное выражение для загрузки практически невозможно. Однако в § 3.2 найдена функция, значения которой позволяют судить о значении реальной загрузки системы. Исходя из вида этой функции, можно дать практические рекомендации по выбору квази-оптимальных параметров. Эти рекомендации приведены и обоснованы в § 3.3. Результаты главы 3 опубликованы в работах /83 - 85/.

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

положениями из § 3.3. Далее, в § 4.3 даны численные результаты, связанные с длительностью переходного процесса и временем моделирования. Кроме того, в этом параграфе рассмотрены адаптивные свойства предлагаемого алгоритма. Показано, что этот алгоритм, ориентируясь на конкретную ситуацию, автоматически находит наилучший способ управления. Приведен пример, доказывающий экономическую эффективность изучаемого алгоритма. Результаты главы 4 опубликованы в работах /85 - 87/. Конкретные численные результаты приведены в приложении С в виде рисунков и таблиц. Текст программы дан полностью в приложении Б.

Приложение А содержит выводы формул и доказательства некоторых утверждений. В приложении В приведены иллюстрации к главе 3. Приложение С содержит численные результаты, а в приложении Б дан текст программы, имитирующей работу системы. Наконец, в приложении Е коротко изложены и доказаны результаты, относящиеся к более простым алгоритмам, каждый из которых можно рассматривать как частный случай предлагаемого обобщенного адаптивного алгоритма управления конфликтными потоками. В разделе Е.1 рассмотрен циклический алгоритм управления конфликтными потоками по информации о длине очереди. Система, где используется такой алгоритм, подробно рассмотрена в работах /62, 63/. В разделе Е.2 дано исследование системы, где применяется циклический алгоритм управления потоками по информации об интервалах поступления /60/.

Данная работа выполнялась в рамках следующих г/б и хоздоговорных тем, а также грантов, выполняемых на кафедре прикладной теории вероятностей ННГУ и в лаборатории теории вероятностей и математической статистики НИИ прикладной математики и кибернетики при ННГУ: "Построение и анализ нетрадиционных вероятностных моделей процессов обслуживания и адаптивно-

го управления" (К гос. регистрации 0191.0041837); "Изучение функционалов от случайных процессов в задачах построения статистических решающих правил, вероятностного представления решений дифференциальных и интегральных уравнений и массового обслуживания" (Ы гос. регистрации 0191.10054234); "Алгоритмические процессы управления в конфликтных системах обслуживания" (И гос. регистрации 0196.0008548); грант РФФИ "Управляемые системы обслуживания дискретного типа" (номер проекта 93-01-01579); грант конкурсного центра по фундаментальным исследованиям в области автоматики и телемеханики, вычислительной техники, информатики, кибернетики, метрологии, связи при Санкт-Петербургском государственном электротехническом университете "Системный анализ процессов обслуживания с разделением времени при входных потоках Бар-тлетта" (срок исполнения гранта 1996-1997 гг.); хоздоговорная тема "Разработка вероятностно-статистических методов построения, анализа и синтеза моделей конфликтных управляемых систем обслуживания" в рамках программы "Университеты России" (номер темы 1.3.26, направление "Фундаментальные проблемы математики и механики", раздел "Вероятностно-статистический анализ").

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

1. Девятая Белорусская зимняя школа-семинар по теории массового обслуживания "Математические методы исследования систем и сетей массового обслуживания" (Минск, Беларусь, 1993).

2. Одиннадцатая Белорусская зимняя школа-семинар по теории массового обслуживания "Исследование сетей связи и компьютерных сетей методами теории массового обслуживания" (Минск, Беларусь, 1995).

л

3. Вторая Международная конференция "Математические алгоритмы" (Нижний Новгород, 1995).

4. Международная научная конференция "Компьютерный анализ данных и моделирование - CDAM'95" (Минск, Беларусь, 1995).

5. VII Белорусская математическая конференция (Минск, Беларусь, 1996).

6. Международная конференция "Distributed Computer Communication Networks (DCCN'96)" (Тель-Авив, Израиль, 1996). Поездка поддержана департаментом образования и науки администрации Нижегородской области.

7. Тринадцатая Белорусская зимняя школа-семинар по теории массового обслуживания (Минск, Беларусь, 1997).

8. Конкурсная конференция молодых преподавателей факультета вычислительной математики и кибернетики ННГУ, посвященная памяти проф. Г. В. Арановича (Нижний Новгород, 1997).

9. XXIII научная конференция факультета физико-математических и естественных наук Российского университета Дружбы Народов (Москва, 1997).

10. Международная конференция "Control of Oscillations and Chaos - COC'97" (Санкт-Петербург, Россия, 1997).

11. Международная конференция "Distributed Computer Communication Networks (DCCN'97)" (Тель-Авив, Израиль, 1997).

12. Четырнадцатая Белорусская зимняя школа-семинар по теории массового обслуживания (Минск, Беларусь, 1998).

13. XXIV научная конференция факультета физико-матема-ти-ческих и естественных наук Российского университета Дружбы Народов (Москва, 1998).

14. Международная конференция "Prague Stocliastics'98" (Прага, Чехия, 1998). Поездка поддержана РФФИ (N проекта 9801 -10944).

Заключение диссертации по теме «Теоретические основы информатики», Литвак, Нелли Владимировна

Заключение

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Литвак, Нелли Владимировна, 1998 год

Список использованной литературы

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

2. Erlang А. К. Probability and telephone calls// "Nut Tidsskrift for Matematik.". - Ser. В. - 1909 - Vol. 20 - pp. 33-39.

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

4. Кофман А., Крюон Р. Массовое обслуживание. Теория и приложения. - М.: "Мир", 1965.

5. Кокс Д. Р., Смит У. Л. Теория очередей. - М.: "Мир", 1966.

6. Гнеденко Б. В., Коваленко И. Н. Введение в теорию массового обслуживания. - М.: Наука, 1966.

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

8. Климов Г. П. Стохастические системы обслуживания. - М.:

с/

Наука, 1966. - 243 с.

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

10. Саати Т. Л. Элементы теории массового обслуживания и ее применение. - М: Советское радио, 1971.

11. Такач Л. Комбинаторные методы в теории случайных процессов. - М.: "Мир", 1971.

12. Боровков А. А. Вероятностные процессы в теории массового обслуживания. - М.: "Наука", 1972.

13. Бочаров П. П., Печинкин А. В. Теория массового обслуживания. - М.: Издательство РУДН, 1995.

14. Даниелян Э. А. Однолинейные стохастические системы обслуживания с приоритетами. - Сер. Статистические и стохастические системы. - М.: Изд-во МГУ, 1969. - Вып. 7.

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

16. Рыков В. В. Регенерирующие процессы с вложенными периодами регенерации и их применение при исследовании приоритетных систем массового обслуживания// "Кибернетика". -

1975. - N 6. - с. 105-111.

17. Конвей Р. В., Максвел В. Л. Теория расписаний. - М.: Наука,

1976.

18. Клейнрок Л. Вычислительные системы с очередями. - М.: Мир, 1979.

19. Климов Г. П., Мишкой Г. К. Приоритетные системы обслуживания с ориентацией. - М.: Изд-во МГУ. - 1979.

20. Альборес Ф. X., Бочаров П. П. Анализ системы массового обслуживания МАР2\02\1\г с абсолютным приоритетом// "Автоматика и телемеханика". - 1997. - N 11. - с. 102-117.

21. Печинкин А. В. Стационарные вероятности состояний в системе с входящим потоком марковского типа, относительным приоритетом и раздельными очередями// "Автоматика и телемеханика". - 1998. - N 1. - с. 107-119.

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

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

24. Рыков В. В. Применение регенерирующих процессов при исследовании управляемых систем. - В сб. Теория массового обслуживания. Тр. III Всесоюзной школы-совещания по теории массового обслуживания. Т. 1. - М.: Изд-во МГУ, 1976. - с. 135148.

25. Федоткин М. А. Оптимальное управление конфликтными потоками и маркированные точечные процессы с выделенной дискретной компонентой. I// "Литовский математический сборник". - 1988. - Вып. 28, N 4. - с. 783-794.

26. Федоткин М. А. Оптимальное управление конфликтными потоками и маркированные точечные процессы с выделенной дискретной компонентой. II// "Литовский математический сборник". - 1989. - Вып. 29, N 1. - с. 148-159.

27. Тимофеев Е. А. Оптимизация средних длин очередей в системе обслуживания с ветвящимися потоками вторичных требований// "Автоматика и телемеханика". - 1995. - N 3. - с. 60-67.

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

29. Levy H., Sidi M. Polling systems: application, modelling and optimisation// "IEEE Transactions on Communications". -1990. - Vol. 38, N 10. - pp. 1750-1760.

30. Levy H., Sidi M., Boxma О. J. Dominance relations in polling systems// "Queueing systems". - 1990. - N 6. - pp. 155-172.

31. Levy H., Kleinrock L. Polling systems with zero switch-over periods: a general method for analyzing the expected delay// "Perfomance Evaluation". - 1991. - N 13. - pp. 97-107.

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

33. Eisenberg М. Queues with periodic service and change-over time// "Oper.Res.". - 1972. - N 20. - pp. 440-451.

34. Mevert P. Traffic delays at a computer-controlled intersection// "J. Oper. Res.". - 1972. - vol. A16. - pp. 145-152.

35. Konheim A. G., Meister B. Waiting times and lines in systems with polling// "J. Assoc. Comput. Math.". - 1974. - N 21. - pp. 470 -490.

36. Kleinrock L., Levy H. The analysis of random polling systems// "Oper. Res.". - 1988. - N 36(5). - pp. 716-732.

37. Boxma O. J., Weststrate J. A., Yechiali U. A globally gated polling system with server interruptions, and applications to the repairman problem// "Probability in the Engineering and Informational Sciences". - 1993. - N 7. -pp. 187-208.

38. Kuehn P. J. Multiqueue systems with nonexhaustivc cyclic service// "The Bell System Technical Journal". - 1979. - Vol. 58, N 3. - pp. 671-698.

39. Borst S. С., Boxma О. J., Levy H. The use of service limits for efficient operation of multi-station single-medium communication systems. - Report BS-R93xx. 1993. - pp. 1-24.

40. Campbell G. M. Cyclical queueing systems// "Eur. J. Oper. Res.". - 1991. - vol. 51. - pp. 155-167.

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

42. Miller A. J. Settings for fixed-time traffic signal// "Operational Research quarterly". - 1963. - vol.14. - pp. 373-386.

43. McNeil D. R. A solution to the fixed-cycle traffic light problem for compound Poisson arrivals// "Journal of Applied probability". -1968. - vol. 5. - pp. 624-635.

44. Webster F. V. Traffic signal settings// "Road Res. Technical Paper". - London. - 1958. N. 2. - pp. 164-185.

45. Webster F. V., Cobbe В. M. Traffic signals// "Road Res. Technical Paper, HMSO". - London. - 1966. N. 56. - pp. 1-111.

46. Федоткин M. А., Княжицкий Б. Я. Оптимизация параметров автомата с жестким переключением, управляющего потоками машин на перекрестке со сложной геометрией переезда// Межвузовский сборник "Динамика систем, оптимизация и адаптация". - Горький, ГГУ, 1978. - N 14. - с. 33-56.

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

48. Якушев Ю. Ф. Об оптимальном обслуживании конфликтных потоков// "Теория вероятностей и ее применения". - 1990. -Т. 35, вып. 1. - с. 161 - 166.

49. Куделин А. Н. Модели управления конфликтными потоками в случайной среде. - Диссертация на соискание ученой степени кандидата физ.-мат. наук. - Нижний Новгород, 1997.

50. Grycko Е., Moeschlin О. A concept of optimal control of a bottleneck with symmetric volume of traffic// to appear in "Stochastic Models". - 1998.

51. Moeschlin 0., Poppinga C. Controlling traffic lights at a bottleneck with renewal input streams// Proceedings of the International Conference "Prague Stochastics'98", Vol. 2, pp. 407412. - Prague, 1998.

52. Dunne M. C., Potts R. B. Algorithm of traffic control// "Opens. Res.". - 1964. - N 12. - pp. 870-871.

53. Gordon R. L. A technique for control of traffic at critical intersections// "Transp. Sci.". - 1969. - Vol. 3., N 4 - pp. 279 -288.

54. Неймарк Ю. И., Черток Д. М. Исследование значения уровня информации при управлении обслуживанием конфликтных потоков// " Обучакнциеся алгоритмы в системах управления и обработки информации". - Новосибирск, "Наука", 1978. - с. 3 -

I.

55. Неймарк Ю. И., Эвин М. Р. Управление обслуживанием конфликтных потоков заявок при возможности прогнозирования их поступления// "Изв. АН СССР. Техн. кибернетика". -1983. - N 6. - с. 188-190.

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

57. Федоткин М. А., Народицкая Е. В. Управление потоками по информации о моментах поступления требований и нелокальное описание потоков// "V Всесоюзн. совещ. по статист, методам в процессах управления". Тезисы доклада. - М., 1981.

58. Федоткин М. А. Строение пространства состояний случайного процесса, описывающего динамическое поведение систем с переменной структурой обслуживания при управлении конфликтными потоками в классе нелинейных однородных алгоритмов// "Литовский математический сборник". - 1977. -т.17. - N 2. - с. 203-217.

59. Кувыкина Е. В., Федоткин М. А. Изучение предельных свойств процесса управления конфликтными потоками Бартлетта в классе однородных алгоритмов с ориентациямп и переналадками/ / "Сети связи и сети ЭВМ как модели массового обслуживания". Тезисы докл. - Минск, 1991. - с. 80.

60. Литвак Н. В., Федоткин М. А. Циклическое управление конфликтными потоками по информации об интервалах поступления. - ННГУ, Нижний Новгород, 1996, 30 с. - Деп. в ВИНИТИ 07.06.96 N1896 - В96.

61. M. A. Fcdotkin, N. V. Litvak. On one class of algorithms for adaptive traffic control// Proceedings of the International Conference "Distributed Computer Communication Networks (DCCN'96)", pp. 73-77. - Tel-Aviv, Israel, 1996.

62. Литвак Н. В., Федоткин М. А. Математическая модель системы с до обслуживанием по информации о длине очереди. - ИНГУ, Нижний Новгород, 1997, 30 с. - Деп. в ВИНИТИ 17.03.97 N 747-В97.

63. Литвак Н. В., Федоткин М. А. Предельные свойства системы с до обслуживанием по информации о длине очереди. - ИНГУ, Нижний Новгород, 1997, 31 с. - Деп. в ВИНИТИ 13.06.97 N 1951-В97.

64. М. A. Fedotkin, N. V. Livak. An analysis of a queue lengths reacting traffic light with limited green durations// Сборник трудов Тринадцатой Белорусской зимней школы-семинара по теории массового обслуживания, с. 33-36. - Минск, 1997.

65. Литвак Н. В. Математическая модель гибкого алгоритма управления транспортными пот,оками// Тезисы XXIII научной конференции факультета физико-математических и естественных наук Российского университета Дружбы Народов, с. 62. -Москва, 1997.

66. Fedotkin М. A., Litvak N. V. A conflict flows control by an information about queue lengths// Proceedings of the International Conference "Distributed Computer Communication Networks (DCCN'97)", pp. 68-72. - Tel-Aviv, Israel, 1997.

67. Литвак H. В. Автоматическое регулирование перекрестка по информации о наличии "пробок" и очередности подхода машин// Сборник трудов Четырнадцатой Белорусской зимней школы-семинара по теории массового обслуживания, с. 71-76. -Минск, 1998.

68. Федоткин М. А. Теория дискретных систем с переменной структурой обслуживания квазирогенерирующих пото-

ков: "Теория вероятностей и математическая статистика. Диссертация на соискание уч. степени доктора ф.-м. н.". - М., МГУ, 1984. - 303 с.

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

70. Fedotkin М. A. On a class of stable algorithms for control of conflicting flows of arriving airplanes// "Problems of Control and Information Theory". - 1997. - Vol. 6. - N 1. - pp. 13-22.

71. Гершт A. M., Map бух В. В. Системы массового обслуживания с переналадкой. - Известия АН СССР. Техническая кибернетика. - 1975. - N 4. - с. 74-82.

72. Doshi В. Queueing systems with vacations - a survey. - Queueing systems. -1986. - pp. 29 -66.

73. Kella O., Yechiali U. Priorities in M\G\l queue with server vacations. - Nav. Res. Log. - 1988. - Vol. 15, N 1. - pp. 23-34.

74. Калашников К. К., Печинкин А. В. Марковское обслуживание в системе с несколькими входящими пуассоновскими потоками. - Вероятностные задачи дискретной математики. - М.: Моск. ин-т электрон, машиностр. - 1990. - с. 85-97.

75. Federgruen A., So К. С. Optirnality of threshold policies in single-server queueing systems with server vacation. - Adv. Appl. Probab. - 1991. - Vol. 23, N 2. - pp. 388-405.

76. Talme Т., Takagi H., Haseguwa T. Sojourn times in vacation and polling systems with Bernoulli feedback. - J. Appl. Probab. -1991. - Vol. 28, N 2. - pp. 422-432.

77. Borst S. С., Boxma О. J. Polling models with and without switchover times. - Report CWI, Amsterdam, 1993.

78. Правила дорожного движения Российской Федерации. - ИПК "Московская правда", 1996.

79. Литвак Н. В., Федоткин М. А. Математическая модель адаптивного управления транспортом с учетом правил дорожного движения и психологии водителей. - ННГУ, Нижний Новгород, 1998, 58 с. - Деп. в ВИНИТИ 08.01.98, N 13-В98.

80. Литвак Н. В., Федоткин М. А. Предельные свойства системы адаптивного управления транспортом с учетом правил дорожного движения и психологии водителей. - ННГУ, Нижний Новгород, 1998, 51 с. - Деп. в ВИНИТИ 29.05.98, N 1636-В98.

81. Fedotkin M. A., Litvak N. V. Random processes of adaptive control for conflict Poisson flows// Proceedings of International Conference "Prague Stochastics'98", pp. 147-152. - Prague, Czech Republic, 1998.

82. Литвак H. В., Федоткин M. А. Вероятностная модель адаптивного управления конфликтными потоками// "Автоматика и телемеханика" (в печати).

83. Литвак Н. В., Федоткин М. А. Качественное исследование системы адаптивного управления транспортом с учетом правил дорожного движения и психологии водителей. - ННГУ, Нижний Новгород, 1998, 42 с. - Деп. в ВИНИТИ 29.05.98, N 1635-В98.

84. Литвак Н. В. О загрузке конфликтной системы обслуживания/ / Тезисы XXIV научной конференции факультета фпоико-математичеекпх и естественных наук Российского университета Дружбы Народов, с. 14-15. - Москва, 1998.

85. Литвак П. В., Федоткин М. А. Вероятностная модель адаптивного управления конфликтными потоками. Качественное и численное исследование// "Автоматика и телемеханика" (в печати).

86. Литвак П. В., Федоткин М. А. Компьютерное моделирование адаптивного управления транспортом на локальном перекрестке/ / Сборник статей Международной научной конференции "Компьютерный анализ данных и моделирование -CDAM'95", том 2, с.170-174. - Минск: БГУ, 1995.

87. Fedotkin M. A., Litvak N. V. An adaptive nonlinear robust traffic control// Proceedings of the International Conference "Control of Oscillations and Chaos - COC'97", pp. 360-361. - St. Petersburg, 1997.

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

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

90. Литвак Н. В., Федоткин М. А. Алгоритмы при оптимальном управлении траффиком// Сборник трудов Второй Международной конференции "Математические алгоритмы", с. 108117. - Нижний Новгород, 1997.

91. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. Т.2. - М.: Наука, 1969.

92. Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. Т.1. - М.: Наука, 1969.

93. Народицкая Е.В. Исследование методом имитационного моделирования управления конфликтными потоками в классе одно-

родных алгоритмов с упреждением.// Третья школа по автоматизированным системам массового обслуживания. Тезисы докл. - М., 1981.

94. Кувыкина Е.В. Об имитационных моделях систем управления конфликтными потоками с изменяющейся вероятностной структурой.// VIII Всесоюзн. конфер. по проблемам теоретической кибернетики. - Горький, 1988.

95. Ширяев А. Н. Вероятность. М.: Наука, 1989.

96. Чжун К. JI. Однородные цепи Маркова. - М.: Мир, 1964.

97. Биллингсли П. Сходимость вероятностных мер. - М.: Наука, 1977.

98. Алгоритмические процессы управления в конфликтных системах обслуживания: Отчет о НИР (промежуточный)/ Научно-исследовательский институт прикладной математики и кибернетики (НИИ ПМК); М.А. Федоткин, A.A. Высоцкий, Н.В. Литвак. - N ГР 0196.0008548. - Н. Новгород, 1998. - 71 с.