Теория дискретных систем с переменной структурой обслуживания квазирегенерирующих потоков тема диссертации и автореферата по ВАК РФ 01.01.05, доктор физико-математических наук Федоткин, Михаил Андреевич

• Федоткин, Михаил Андреевич
• доктор физико-математических наук
• 1983

Оглавление диссертации доктор физико-математических наук Федоткин, Михаил Андреевич

ГЛАВАПЕРВАЯ Стр ВВЕДЕНИЕ

§ 1.1. Общая характеристика особенностей работы

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

ГЛАВА ВТОРАЯ

О ВХОДНЫХ ПОТОКАХ ТРЕБОВАНИИ В СИСТЕМАХ С ПЕРЕМЕННОЙ СТРУКТУРОЙ ОБСЛУЖИВАНИЯ

§ 2.1. Неполное описание потоков

§ 2.2. Определение квазирегенерирующих потоков. Примеры квазирегенерирующих потоков

§ 2.3. Определение регенерирующего входного потока однородных требований.

§ 2.4. Применение квазирегенерирующих потоков для описания реальных потоков заявок

ГЛАВА ТРЕТЬЯ

ФУНКЦИОНАЛЬНО-МАТЕМАТИЧЕСКАЯ МОДЕЛЬ УПРАВЛЕНИЯ ПОТОКАМИ В ДИСКРЕТНЫХ СИСТЕМАХ С ПЕРЕМЕННОЙ СТРУКТУРОЙ ОБСЛУЖИВАНИЯ

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

§ 3.2. Потоки насыщения и их классификация

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

§ 3.4. Получение векторного рекуррентного соотношения для случайного процесса образования очередей по потокам и эволюции обслуживающего устройства

ГЛАВА ЧЕТВЕРТАЯ

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

§ 4.1. Теоремы об условной марковости систем с переменной структурой обслуживания заявок

§ 4.2. Итерационные процессы для условных распределений состояний системы и классификация систем с переменной структурой обслуживания. III

§ 4.3. Неполное описание векторного потока обслуженных системой требований

§ 4.4. Условия инвариантности векторного входного потока.

ГЛАВА ПЯТАЯ

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

§ 5.1. Формулировка задачи об оптимальном управлении потоками заявок и определение функционалов Чжуна

§ 5.2. Вероятностные свойства функционалов Чжуна

§ 5.3. Алгебраические свойства условных математических ожиданий от функционалов Чжуна

§ 5.4. Метод вычисления вероятностей достижения с запретами и условных математических ожиданий от функционалов Чжуна. Иллюстративные примеры

ГЛАВА ШЕСТАЯ

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

§ 6.1. Конструктивные основы задания однородных алгоритмов управления с ориентацией и переналадками

§ 6.2. Строение пространства состояний векторного случайного процесса, определяющего динамику очередей по потокам и эволюцию обслуживающего устройства

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

§ 6.4. Итеративно-мажорантный метод определения необходимых условий существования инвариантного условного распределения состояний системы

§ 6.5. Получение достаточных условий статистической устойчивости однородных алгоритмов с ориентацией и переналадками

§ 6.6. Об управлении конфликтными потоками самолетов при организации цроцесса посадки

ГЛАВА СЕДЬМАЯ

УПРАВЛЕНИЕ КОНФЛИКТНЫМИ ПОТОКАМИ ЗАЯВОК ПО МИНИМАЛЬНОЙ ИНФОРМАЦИИ О СОСТОЯНИИ СИСТЕМЫ С ПЕРЕМЕННОЙ СТРУКТУРОЙ

ОБСЛУЖИВАНИЯ

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

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

§ 7.3. Классификация в целом системы с переменной структурой обслуживания потоков по однородному алгоритму с упреащением

§7.4. Неравенства для времени пребывания в системе синхронного момента наблюдения и управление пересекающимися потоками по алгоритму с упреждением

§ 7.5. Системы с переменной структурой обслуживания требований и эффект изменения интенсивности потоков насыщения

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

Классифицируя становление теории массового обслуживания и прогресс ее приложений к реальнытл задачам, целесообразно выделить следующие направления исследований.1. Исследование классической схемы обслуживания с ожиданием или с потерями и изучение различных ее обобщений L-i-5-<ioJ ^ которые связаны с рассмотрением более сложного закона распределения промежутка между последовательными поступлениями требований, с рассмотрением более сложного закона распределения длительности обслуживания и, наконец, с рассмотрением более сложной структуры системы (несколько приборов разной производительности, несколько ненадежных приборов, ограничения на размер очереди, ограничения на время ожидания и на время пребывания требований, ограничения на механизм образования очереди и т.п.), 2. Исследование управляемых систем при обслуживании идентичных требований i^^-^^i (системы с изменяеьшм входным потоком заявок, системы с изменяемой длительностью обслуживания, системы с изменяемым режимом работы обслуживающего устройства, системы с изменяемым механизмом образования очереди и т.п.).3. Исследование процесса обслуживания неоднородных требований L^ "^"^ 'J (приоритетные системы, системы с разделением времени, циклические системы и т.п.).8 4, Исследование алгоритмов управления потоками в системах с переменной структурой обслуживания.Если по первым трем направлениям исследований к настоящему моменту имеется значительное число монографий L'JO-O4J ^ обзоров Loo69J Q очень обширной библиографией, то по четвертому направлению исследований, к сожалению, накопленный в публикациях сравнительно небольшой материал пока не суммирован. С другой стороны, в обзорной работе -^ ^ было указано, что исследование алгоритмов управления потоками заявок является одним из современных и перспективных направлений развития общей теории систем массового обслуживания. По этой причине ниже ограничимся рассмотрением только тех работ, содержание которых наиболее близко примыкает к вопросам изучения процессов обслуживания требований в системах с переменной структурой.К числу первых публикаций, в которых рассматривается проблема алгоритмического управления потоками заявок и при этом существенно учитываются структурные изменения обслуживающего устройства, принадлежит цикл работ U^'^^i автора. Теперь можно полагать, что начинает развиваться новое научное направление, связанное с изучением и оптимизацией систем с переменной структурой обслуживания потоков. Исследование систем с переменной структурой обслуживания потоков представляется особенно актуальным, ибо такие системы математически описывают поведение сложных реальных процессов обслуживания с управлением в условиях случайных факторов, В то же время теория систем с переменной структурой обслуживания потоков посвящена одному из актуальных вопросов в общей теории управляемых случайных процессов - проблеме изучения предельных свойств условных распределений дискретных управляемых многомерных случайных процессов специального вида.В нашей задаче естественно считать, что вероятностная структура системы массового обслуживания определяется вероятностной структурой векторного входного потока, вероятностной структурой - 13 векторных потоков насыщения и вероятностной структурой выбранного вектора начальных условий. Логическая структура системы определяется структурой о (Г)обслуживающего устройства, структурой управляющего алгоритма oL и, наконец, структурой стратегии 5" механизма обслуживания. Как правило, при неприоритетном управлении порядком обслуживания различных типов потоков в таких задачах массового обслуживания значительная доля времени теряется вследствие изменения логической и вероятностной структуры систелш. Следовательно, существуют такие внутренние состояния обслуживающего устройства, в которых система осуществляет переналадки, ориентацию, разогрев и т.п. Отмеченная ситуация с изменением структуры очень часто встречается в реальных системах передачи информации, вычислительных комплексах с разделением времени, в системах управления качеством сварки перемычек при сборке интегральных микросхем, в системах управления различными транспортными потоками и т.п. Например, в системах управления потоками самолетов при посадке в крупных аэропортах или в системах управления потокагли транспортных единиц на перекрестках со сложной геометрией переезда. Можно с уверенностью сказать, что изучение управляемых систем с переменной структурой связано не только с естественным желанием рассмотреть новые и обобщенные теоретические схемы процессов обслуживания, но и с запросами реальных систем. Итак, изменение логической и вероятностной структуры системы массового обслуживания в процессе функционирования является второй существенной ее особенностью.В основе различных методов исследования классических моделей систем массового обслуживания лежит, по существу, основное ограничение о том, что структура системы не меняется в процессе ее функционирования. Поэтому цри анализе классических систем мае- 14 сового обслуживания традиционно априори задают закон распределения длительности обслуживания любой заявки из каждого потока.Более того, естественно и можно предполагать, что однородные заявки определенного потока обслуживаются по одному и тоглу же вероятностному закону, например, экспоненциальному. Такое предположение совершенно не пригодно при изучении систем с переменной структурой, ибо в таких системах длительности обслуживания заявок также зависят от внутреннего состояния обслуживающего устройства. Даже, если потребовалось бы все же априори задать закон распределения продолжительности обслуживания каадой заявки, то не ясно, как эффективно и разумно следует использовать эту громоздкую информацию при построении и изучении математической модели систем с переменной структурой. В связи с этими обстоятельствами в данной работе механизм обслуживания заявок априори задается с помощью некоторого семейства I I из векторных потоков насыщения. При этом случайный процесс поступления заявок и случайный процесс обслуженных системой требований в случае ее бесконечной загрузки в некотором смысле симметричны по отношению к системе с переменной структурой и в некотором смысле могут быть обращены. Т.е. векторный входной поток требований может выполнять роль векторных выходных потоков в случае бесконечной загрузки системы и, тем самым, оцределять потоки насыщег-г(Н) ния. Наоборот, семейство! I из векторных потоков насыщения может играть роль векторного входного потока заявок. Рассмотрение потоков насыщения и связанное с этим отмеченная симметричность поступления и обслуживания требований являются следующими важными отличительными признаками построения модели систем с переменной структурой.Настоящая диссертационная работа по своей цели посвящена - 15 конструктивному построению общей дискретной математической модели реальных систем с переменной структурой обслуживания неоднородных требований, созданию основ теории алгоритмического управления потоками заявок, детальноглу исследованию класса однородных алгоритмов управления потоками. Вместе с тем особое внимание уделяется использованию полученных теоретических результатов для организации процесса обслуживания потоков в конкретных реальных системах и для объяснения некоторых известных в практике фактов. Математическая основа описания и исследования модели систем с переменной структурой обслуживания требований и алгоритмического управления потоками базируется на результатах классической теории массового обслуживания, теории условных регулярных вероятностей, теории управляемых случайных процессов, теории функционального анализа, теории бесконечных систем линейных алгебраических уравнений, эргодической теории, теории функции комплексного переменного. § 1.2, Основные положения и краткий обзор работы Основные научные положения и результаты, защищаемые в работе, могут быть сформулированы следующим образом. I. Впервые предложен и экспериментально апробирован новый способ описания потоков заявок, названный в работе неполным описанием. Принципиальное отличие неполного описания от традиционного заключается в том, что информация о потоке при его неполном описании скорее носит глобальный по времени характер, чем локальный. Это дает возмолсность рассмотреть с единой точки зрения потоки однородных и неоднородных требований. Предложенный подход к описанию потоков позволяет также ставить вопрос о выборе такого неполного описания, которое упрощало бы решение задачи анализа систем с переменной структурой обслуживания требований и решение задачи оптимального управления потоками в таких системах. Вводится новый достаточно широкий класс квазирегенерирующих входных потоков. Дается определение регенерирующего входного потока и доказывается, что всякий регенерирующий входной поток является квазирегенерирующим. Квазирегенерирующие потоки требований могут быть успешно использованы в качестве математического описания реальных потоков, например, транспортного потока Бартлетта •^ ^ и потока реальных ошибок, возникающих при передаче сообщений в виде двоичной информации по телефону ^ ^ . Вторая глава диссертации подробно раскрывает тезис о неполном описании потоков заявок.2. Впервые в литературе поставлена и решена проблема конструктивного построения функционально-математической модели алгоритмического управления потоками в дискретных системах с переменной структурой обслуживания заявок. Сущность такого конструктивного построения состоит в том, что изменение структуры системы определяется через алгоритмическое изменение внутренних состояний обслуживающего устройства. При этом понятие внутренних состояний обслуживающего устройства играет важную роль на этапе описания всего процесса обслуживания. Следовательно, в противовес существующим представлениям обслуживащее устройство не только выполняет функции по обслуживанию требований, но и алгоритмически управляет потоками заявок. Результаты по конструктивному определению процессов управления потоками и процессов формирования очередей в дискретных системах с переменной структурой обслуживания приведены в третьей главе. В этой же главе разработаны основные теоретико-вероятностные положения о векторных потоках насыщения и на этой основе впервые дано формализованное - 17 определение конфликтных входных потоков заявок. Определение конфликтных входных потоков, отражающее противоположные интересы неоднородных требований, оказалось чрезвычайно удачным в связи с рассмотрением конкретных систем обслуживания с переменной структурой. Исходя из некоторой концепции общего понятия состояния управляемой системы с переменной структурой, в третьей главе получен конечный результат в виде векторных рекуррентных соотношений для случайного процесса образования очередей по потокам и эволюции обслуживающего устройства.3. Одним из центральных пунктов диссертации является проблема создания основ общей теории дискретных систем с переменной структурой обслуживания заявок и алгоритмического управления потоками. Специфика этой теории очень сильно связана как с конструктивным построением модели обслу}кивания по неполной информации о компонентах системы с переменной структурой, так и с более широким применением общей концепции условных регулярных вероятностей в изучении свойств рассматриваемого класса векторных случайных процессов дискретного типа, В рамках указанной проблемы выделены ряд самостоятельных задач, которые и решены в четвертой главе этой работы. Прежде всего в результате общих теоретических исследований были получены доказательства теорем об условной марковости систем с переменной структурой обслуживания и найдены итерационные процессы для условных распределений состояний таких систем. В соответствии с этигл введено понятие отдельной вероятностной траектории системы и затем рассмотрена задача о классификации систем с переменной структурой. В четвертой главе также установлены оригинальные утверждения о неполном описании векторного потока обслуженных системой требований. В частности, приведены условия инвариантности векторного входного потока при его - 18 обслуживании системой с переменной структурой, при которых векторный входной поток и векторный выходной поток принадлежат классу квазирегенерирующих потоков.4. Сформулирована общая постановка вопроса об оптимизации алгоритмов управления потоками заявок и проведено обоснование целесообразности рассмотрения функционалов Чжуна, которые могут быть выбраны в качестве показателей эффективности систем с переменной структурой обслуживания. При анализе систем с переменной структурой обслуживания требований и управления потоками были использованы условные марковские векторные последовательности. Поэтому в основу общей постановки задачи оптимизации положена идея Д.Блекуэлла ^ ^ о (Р , б ) - оптимальности.Кроме общих вопросов оптимизации в пятой главе диссертации приведены исследования алгебраических свойств распределений для функционалов Чжуна от однородных марковских цепей со счетным множеством состояний. Ряд доказанных в этой главе общих теорем позволяет построить простой метод вычисления вероятностей достижения с запретами и условных математических ожиданий от функционалов Чжуна. Рассмотрены иллюстративные примеры на применение полученных теоретических результатов по функционалам Чжуна. Б том числе, установлено, что множество элементов, каждый из которых есть вероятность первого достижения марковской цепью за конечное число шагов выбранного замкнутого множества возвратных состояний из некоторого несущественного состояния, может и не быть единственным ограниченным решением соответствующей системы линейных алгебраических уравнений.5. Процедура задания систем с переменной структурой управления потоками в классе однородных алгоритмов с ориентацией и переналадками описана в шестой главе. Алгоритмы с ориентацией и - 19 переналадками связахш с управлением реальными конфликтными потоками в системах обслуживания с большой нагрузкой. Предложен итеративно-мажорантный метод исследования систем с переменной структурой управления конфликтными потоками в классе однородных алгоритмов с ориентацией и переналадками. Этот метод позволяет сравнительно простыми аналитическими средствами наиболее обстоятельно изучить особенности и эргодические свойства такого рода систем обслуживания. Так, например, с помощью этого метода получены необходимые и достаточные условия существования инвариантного условного распределения для состояний системы обслуживания. Конкретные приложения полученных в этой главе математических исследований связаны с решением задачи об управлении конфликтными потоками самолетов при функционировании аэропорта с несколькими взлетно-посадочными полосами и одной системой посадки ^ •' .6. Наконец, в соответствии с общей конструкцией систем с переменной структурой обслуживания неоднородных требований в последней, седьмой главе диссертации определен новый специфический тип однородных алгоритмов с упреждением. Алгоритм с упреадением управляет входными потоками заявок лишь по информации о наличии очереди в некотором фиксированном потоке и по информации о текущем структурном состоянии системы. Алгоритм такого типа может быть легко реализован, так как его задание основывается на минимальном количестве информации о состоянии систеьш с переменной структурой. На основе развиваемой в диссертации общей теории дискретных систем с переменной структурой доказаны предельные теоремы для случайного процесса обслуживания потоков по алгоритму с упреадением. Эти предельные теоремы позволили провести классификацию в целом систем с переменной структурой управ- 20 ления потоками в классе однородных алгоритмов с упреадением.Особое внимание уделено приложениям аналитических результатов этой главы для исследования реальной задачи управления пересекащимися потоками по алгоритму с упреждением.Отметим теперь некоторые оригинальные результаты исследований в работе, которые дали возможность существенно продвинуться в понимании некоторых явлений реальных систем обслуживания.1. Принцип неполного описания потоков, например, потока Бартлетта, явился основой для понимания причины использования библиотеки управляющих алгоритмов в транспортных и других системах с переменной структурой обслуживания, 2, Условия и доказанное утверждение теорелш 3.1 позволили обосновать постановку предложенного инженерами-транспортш-шами эксперимента, определяющего эмпирические условные распределения векторного потока насыщения.3, Полное описание выходного потока заявок не включает описание классической системы обслуживания. Напротив, неполное описание векторного выходного потока существенно учитывает описание системы с переменной структурой обслуживания. Поэтому в результате доказательства ряда фундаментальных теорем о неполном описании векторного выходного потока более понятны стали трудности определения выходного потока в классических системах обслужива4. Аналитическое и численное изучение свойств функционирования специальных систем обслуживания потоков по однородному алгоритму с упреждением позволило объяснить эффек-т значительного уменьшения среднего времени пребывания произвольного требования в некоторых реальных системах с большой нагрузкой.Данная работа в основном содержит теоретические результаты. - 21 Однако при решении проблемы конструктивного построения модели управления потоками требований автор шел от общих представлений о реальных процессах обслуживания с переменной структурой.Лобачевского в соответствии с координационным планом НИР АН СССР - 22 по гфоблеме "Кибернетика" и по проблеме "Системный анализ, исследование операций и имитационное моделирование". Основные результаты теории дискретных систем с переменной структурой обслуживания неоднородных требований и алгоритмического управления потоками - нового научного направления в теории массового обслуживания, имеющего важное црикладное значение, докладывались и обсуждались на следующих совещаниях, конференциях и школах.1. Пятое Всесоюзное совещание по проблемам управления с участием иностранных ученых (Москва, I97I г.).2. Всесоюзная конференция "Методы Монте-Карло и их црименения" (Новосибирск, I97I г.).3. Всесоюзная конференция "Экстремальные задачи и их приложения к вопросам планирования, проектирования и управления сложными системами" (Горький, I97I г.).4. Всесоюзная конференция "Опыт разработки и внедрения АСУ на объектах непромьшленной сферы" (Тула, 1972 г.).5. Шестая Всесоюзная конференция по экстремальным задачам (Таллин. 1973 г.).6. Третья Всесоюзная школа-совещание по теории массового обслуживания (Пущино-на-Оке, 1974 г.).7. Вторая Международная Вильнюсская конференция по теории вероятностей и математической статистике (Вильнюс, 1977 г.).8. Седьмое Всесоюзное совещание по цроблемам управления (Минск, 1977 г.).9. Всесоюзная конференция "Моделирование процессов уцравления транспортными системами" (Владивосток, 1977 г.).10. Третья Всесоюзная конференция по исследованию операций (Горький, 1978 г.).11. Четвертое Всесоюзное совещание "Статистические методы теории управления (Фрунзе, 1978 г.). - 23 12. Четвертая Всесоюзная школа-совещание по теории массового обслуживания (Баку, 1978 г.).13. Вторая Всесоюзная школа по автоматизированным системам массового обслуживания (Фрунзе, 1980 г.).14. Третья Международная Вильнюсская конференция по теории вероятностей и математической статистике (Вильнюс, I98I г.).15. Пятое Всесоюзное coвeщш^иe по статистическим методам в процессах управления (Алма-Ата, I98I г.).16. Третья Всесоюзная школа по автоматизированным системам массового обслуживания (Винница, I98I г.).17. Всесоюзное совещание по автоматизированным системам массового обслуживания (Нальчик, 1982 г.).18. Шестая Всесоюзная конференция по теоретическим проблемам кибернетики (Саратов, 1983 г.).19. Вторая Всесоюзная конференция по управлению воздушньм движением (Москва, 1983 г.).На опубликованные работы автора имеются прямые ссылки, напршер. в монографиях 146.49.50.96.97] „ „ggopax [59.67.69.98. J . Предварительный вариант диссертации был подготовлен в 1980 г. По материалам, этого варианта в течение I980-I983 гг. были сделаны доклады на различных семинарах в Московском, Вильнюсском и Горьковском госуниверситетах. Институте математики СО АН СССР, Институте математики АН УССР, Институте математики и кибернетики АН Литовской ССР. Окончательно работа была оформлена в 1983 г. с учетом замечаний и пожеланий участников этих семинаров, которым автор выражает глубокую признательность. - 24

Заключение диссертации по теме «Теория вероятностей и математическая статистика», Федоткин, Михаил Андреевич

Результаты работы теперь просуммируем в таком виде.

I. Введены и изучены маркированные точечные процессы на [0,°°) вида {(Ти ' с меткой и дискретной компонентой X, ( . Важнейший класс таких процессов характеризуется независимостью элементов X. ^ , 1>/0 при заданном значении и называется классом квазирегенерирующих последовательностей. Интерпретация Т - ^ соответствует дискретной шкале тактов времени функционирования системы. Смысл и X,. ^ может быть самым различным. В самом простом случае X и определяет на промежутке [Ти ,Т + л вектор ^ ^ поступления требований общего типа \) { - , или вектор максимально возможного обслуживания требований типа В более сложном случае задает на промежутке ^ ^ > В вектор Е, ^ в действительности обслуженных требований общего типа - 1 Гс » и ^ . Квазирегенерирующие последовательности позволяют разработать ^03^ ВОПрОС 0 нелокальном описании потоков насыщения, входных и выходных потоков. Доказано представление в виде соответствующей квазирегенерирующей последовательности каждого из процессов: а) кусочно-постоянного, неотрицательного, монотонного и целочисленного процесса с независимыми приращениями, б) точечного процесса, в) квазирекуррентного процесса восстановления. Получены ус/ювия (теорема 2.1), при которых процессы со ступенчатыми реализациями, имеющими неотрицательные и целочисленные скачки, являются квазирегенерирующими. Квазирегенерирующие последовательности были успешно использованы при статистической обработке реальных потоков с зависимыми интервалами, в частности, решена известная задача Бартлетта о транспортных потоках. В связи с нелокальным описанием потоков возникает проблема формализации выбора X . Остается открытым вопрос о динамике и суммировании потоков. Другая важная здесь проблема состоит в определении общих условий, в силу которых могут появляться потоки Бартлетта.

2. Исследованы свойства условий марковости (теоремы 4,1, 4.2) маркированного точечного процесса {(Т\> ^ с выделенной дискретной компонентой ( > ЭС (.• с ); ? удовлетворяющей функционально-рекуррентным соотношениям (3.3), (3.15), (4.2) и определяющей, например, вероятностную динамику состояний обслуживающего устройства, флуктуацию длин очередей и выходные потоки в системах с изменяющейся во времени структурой. Получены условия (теорема 4.3), при которых последовательность ' ^ I\ является квазирегенерирующей с меткой С ' ' I ) и дискретной компонентой X. ^ = ^. Установлены алгебраические свойства (теоремы 5.1 - 5.7) распределений и первых моментов функционалов Чжуна - функционалов достижения с запретами на траекториях последовательности {( Г|, Ж. » Е, ^ ; 1>/0 \ . Определены условия, при которых системы уравнений, задающих вероятности достижения с запретами, имеют единственное решение, а математические ожидания от функционалов Чжуна равномерно ограничены. Предложен и проиллюстрирован метод вычисления табу-вероятностей и математических ожиданий от функционалов достижения с запретами. Результаты в области вероятностных свойств функционалов Чжуна относятся к граничной теории марковских процессов с запретами. С прикладной точки зрения такого рода функционалы характеризуют выбор алгоритма управления потока -ми в условиях гибели и рождения очередей критических размеров.

Используя класс маркированных точечных процессов с дискретной компонентой, дано конструктивное построение модели алгоритмического управления потоками в дискретных системах обслуживания с переменной структурой через нелокальное описание входных потоков и потоков насыщения, через функциональные описания алгоритма управления потоками и стратегии механизма обслуживания. Введены, формализованы и были использованы в работе такие понятия, как квазирегенерирующие потоки, потоки насыщения, конфликтные потоки, однородные по времени управляющие алгоритмы, экстремальные стратегии механизма обслуживания, функционалы Чжуна, последовательность синхронных моментов наблюдения. Найдены ограничения (теорема 3.1) и соответствующие этим ограничениям формулы, которые выражают распределение потока обслуженннх требований через распределение потока насыщения. Установлены условия инвариант -ности, при которых входной и выходной потоки принадлежат классу квазирегенерирующих. Проведена классификация марковских систем обслуживания с переменной структурой на эргодические, периоди -ческие, периодические с запаздыванием, рекуррентные и диссипа -тивные. Задача об оптимальном управлении потоками в таких системах поставлена и может быть решена непосредственно в терминах вероятностей перехода цепи { ( Г\ > > Предложен -ный способ задания процессов обслуживания выдвинул проблему двойственности в теории массового обслуживания, которая состоит в изучении образования длины очереди и размера дефицита из требова -ний. Наконец, такой способ задания поставил задачу адекватного представления системы обслуживания с переменной структурой в виде управляющей системы [204,2051 ^

3. Для различных наборов отображений и (класс наборов с ориентацией и переналадками г класс наборов с упреждением ^2] ^ класс циклических наборов ) соотношений (3.3) и (3.15), каждый из которых играет важную роль в реальных процессах обслуживания, предложенным в работе интератив-но-мажорантным методом выяснены особенности и предельные свойства (теоремы 6.1 - 6.11, 7.1 - 7.6, 7.9 - 7.11) квазирегенериру-ющих последовательностей {(Т¡»> Г\ > X и > О; ^ 0 } с существенно более простым строением распределений 1 / ^ ^ Результаты исследования по конкретным процессам обслуживания с переменной структурой доведены до простых формул, расчетных программ, программ оптимизации и связаны с внедрением: а) получены необходимые и достаточные условия существования инвариантного условного распределения для такого рода процессов; б) в условиях большой загрузки процессов с ориентацией и переналадками получены формулы для виртуальной загрузки, меры статистической устой -чивости, времени пребывания обслуживающего устройства в каждом состоянии и числа его состояний; в) с использованием численных методов решена задача об управлении условно-пуассоновскими конфликтными потоками самолетов и задача об управлении пересекающимися транспортными потоками автомобилей; г) получены неравенства для характеристик установившегося режима системы с упреждением, которые являются инвариантными относительно локальных изменений процессов поступления и обслуживания требований (теоремы 7.7 , 7.8); д) обнаружен эффект значительного уменьшения оценки среднего времени пребывания произвольного требования в циклических системах с изменяющейся интенсивностью потоков насыщения и, следовательно, предложен вариант решения транспортной проблемы Веб-стера-Алсопа; е) показана возможность анализа и оптимизации систем с разделением времени, используя для этого методы настоящей работы.

- 300 -.ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования доктор физико-математических наук Федоткин, Михаил Андреевич, 1983 год

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

2. Erlang A.K. Probability and telephone calls. "Nut Tids-skrift for Matematik", Ser.B, 1909, vol. 20, pp. 33-39«

3. Pollaczek E. TJber eine Aufgabe der Wahrscheinlichkeitstheorie. "Mathematik Zeitschrift", 1930, vol. 32, pp.64-100, 729-750.

4. Колмогоров A.H. Sur le probleme d'attente. "Математический сборник", 1931, т. 38, J£ 1-2, с. I0I-I06.

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

6. Гнеденко Б.В. Вычисление среднего перехода между станками. -"Иваново, Бюллетень ИВНИТИ", 1934, 1-2, с. II7-I22.

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

8. Palm С. Intensitatsschwarikungen in Fernsprechverkehr. -"Ericsson Technics", 1943, vol. I, No 44, pp. I-I89.

9. Kendall D.G. Some problems in the theory of queues.

10. J.Roy.Statist.Soc.", Ser.B, 1951, vol.13, No 2, pp.I5I-I85.

11. Lindley D.V. The theory of queues with a single server. -"Proc.Cambridge Philos.Soc.", 1952, Vol.48, pp.277-289.

12. Moran P.A.P. A probability theory of dams and storage systems. "Australian J.Appl.Sci.", 1954, vol.5, pp.II6-I24.

13. Takacs L. Investigation of waiting time problems by reduction to Markov processes. "Acta Math. Acad. Sci. Hung.", 1955» vol.6, pp.IOI-129.

14. Cox D.R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables. "Proc.Cambridge

15. Philos.Soc.", 1955, vol.51, pt.J, pp.433-441.

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

17. Ali Khan M.S., Gani J. Infinite dams with inputs forming a Markov chain. "J.Appl.Probab.", 1968, vol.5, No I, pp.72-83.

18. Gittins J.C. Stochastic monotonicity and queues subject to tidal interruptions. "Proc.Cambridge Philos.Soc.", 1971, vol.70, No I, pp.61-75.

19. Muntz R. Waiting time distribution for round-robin queuing systems. "Proceedings of the Symposium on Computer-Communications Networks and Teletraffic", New York, 1972, pp.429-439.

20. Huk J., Lukaszewicz J. Cykliczne systemy obslugi masowej. -"Roczniki Polskiego Towarzystwa Matematycznego, Matematyka Stosowana", 1973, ser.3, No I, str.85-104.

21. Siegel G. The stationary waiting time and other variables in single-server queues with specialities at the beginning of a busy period. "Zastosowania Matematyki, Applicationes Mathematical, 1973, ser.I3, No 4, str.463-479.

22. Collings T.W.R. A queueing problem in which customers have different service distributions. "Applied Statistics", 1974, vol.23, No I, pp.75-82.

23. Prey er B. Ein Bedienungssystem (M/G/+°o) mit zeitabhängiger Eingangsintensität und Bedienungszeitverteilung. "Mathematische Operationsforschung und Statistik", 1974, vol. 5,1. No 9, S. 701-708.

24. Boxma O.J. The single-server queue with random service output. "J.Appl.Probab, 1975, vol.12, No pp.763-778.

25. Gergely T., Török T.L. Investigation on the discrete GI/G/I queue with and without loss. "Központi fizikai Kutato intezet.Pubis.", 1975, No 59, pp. 1-50.

26. Cohen J.W. On regenerative processes in queueing theory. -"Lecture Notes in Economics and Mathematical Systems", Berlin & Heidelberg & New York, 1976, vol. 121, pp. 1-93.

27. Puke T., Phatarfod R.M. Some exact results for dams with Markovian inputs. "J.Appl.Probab.", 1976, vol. 13, No 2, pp. 329-337.

28. Suzuki T. On a queueing process with service depending on queue-length. "Comment.Math.Univ.St.Pauli", 1961, vol.10, No I, pp. I—12.

29. Meyer K.H.F. Ein Wartesystem mit heterogenen Kanälen unter (s,S)-Regel. "Proceedings in Operations Research, 2", Würzburg-Wien, 1973, S. 295-317.

30. Szczotka W. M/G/I queueing system with "fagging" service channel. "Zastosowania Matematyki, Applicationes Mathema-ticae", 1973, ser. 13, No 4, str. 439-463.

31. Gaur R.S. An intermittant MI^/G^/I system with multi-phased capacity of the service channel. "Automatique Informatique Recherche Opérationnelle", 1973, vol.7,No I,pp.97-106.

32. Prabhu N.U. Stochastic control of queueing systems. -"Naval Research Logistics Quarterly", 1974, vol.21, No 3, pp.4II-4I8.

33. Andreatta G. Eroblemi di ottimizzazione nella teoria delle code. Rend.Sem.Mat.Univ.Padova", 1975, vol.53, pp.123-134.

34. Deb R.K. Optimal control of batch service queues with switching costs. "Adv.Appl.Probab.", 1976, vol.8, No I, pp.177-194.

35. Robinson D.R. Markov decision chains with unbounded costs and applications to the control of queues. "Adv.Appl. Probab.", 1976, vol.8, No I, pp.159-176.

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

37. Броди С.М., Погосян И.А., Касян А.А. Об одном алгоритме оптимальной динамической диспетчеризации в вычислительных системах. "Кибернетика", 1976, $ 4, с. 44-48.

38. Harrison J.M. Dynamic scheduling of a two-class queue: small interest rates. "SIAM J.Appl.Math.", 1976, vol.31, No I, pp. 51-61.

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

40. Хинчин А.Я. Работы по математической теории массового обслуживания. М., "ГИФМЛ", 1963.

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

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

43. Риордан Дж. Вероятностные системы обслуживания. М., "Связь", 1966.42