Введение к работе
Объект исследования и актуальность темы. Под управляемой динамической системой в данной работе понимается объект управления вместе с управляющей системой, работающие в динамическом режиме. В данной работе исследуются такие управляемые динамические системы, как управляемые системы массового обслуживания (СМО) и управляемые деградирующие системы (ДС). Эти системы активно используются в прикладных задачах оптимального управления, принятия решений, обработки информации и системного анализа производительности и надежности, например, при управлении различными системами, производственными линиями, компьютерными и телекоммуникационными сетями, в задачах организации профилактического ремонта ненадежных узлов и агрегатов. Управляемые СМО и ДС принадлежат классу стохастических систем или систем с вероятностным законом движения, изучаемых в рамках объединения теории массового обслуживания, теории надежности и теории управляемых марковских процессов.
Система массового обслуживания представляет собой систему, в которую случайным образом поступают заявки для получения обслуживания на приборе. Термины "заявка", "прибор" и "обслуживание" имеют довольно широкое толкование. Заявкой может быть клиент такой системы обслуживания как банк или супермаркет, где в качестве прибора можно рассматривать сотрудника банка или кассира. В компьютерных системах прибором может служить, например, центральный процессор (CPU), обрабатывающий заявки в виде запросов пользователей, в телекоммуникационных сетях прибором может быть канал связи, по которому передаются пакеты информации и т.д. Деградирующая система описывает такую систему, которая, начиная работу в абсолютно новом состоянии, до момента попадания в состояние полного отказа проходит через последовательность промежуточных состояний деградации. В этих состояниях система сохраняет работоспособность, хоть и с меньшей эффективностью, чем абсолютно новая система. Такие системы можно использовать, например, для описания процесса постепенного уменьшения толщины защитного покрытия, процесса
роста усталостных трещин, процесса аккумулирования некоторого дефекта и т.д. Очевидно, что для улучшения производительности и надежности этих систем невозможно по экономическим причинам беспредельно увеличивать их ресурсы, например, число обслуживающих серверов, пропускную способность телекоммуникационного канала или толщину защитного покрытия. Таким образом, одним из основных вопросов при решении прикладных задач, является нахождение некоторого баланса между улучшением производительности и надежности системы и допустимыми затратами на это улучшение.
Для широкого класса математических моделей, описывающих вероятностную природу реальных систем, с помощью теории массового обслуживания и теории надежности было получено большое число аналитических и численных результатов, характеризующих эксплуатационные и надежностные качества СМО и ДС. К этим результатам можно отнести формулы для функций распределения длины очереди и времени ожидания, вероятность потерь, среднее время пребывания в системе, а также вероятность отказа, среднее время до отказа, функции надежности и риска, коэффициента готовности системы и т.д. В классических СМО и ДС контроллер отсутствует, то есть невозможно осуществлять управление или принимать какое-либо решение, влияющее на работу системы. Но в реальной жизни существует множество систем, основной отличительной чертой которых является именно возможность динамического управления ими в процессе работы, так как за счет внешнего воздействия на поведение системы можно достичь значительного улучшения производительности и надежности системы, например, за счет уменьшения длин очередей, увеличения пропускной способности, увеличения времени жизни, уменьшения вероятности отказа или уменьшения эксплуатационных затрат.
В качестве теоретического аппарата исследования многих типов управляемых СМО и ДС применяется теория управляемых марковских процессов, так как поведение этих систем описывается некоторым случайным процессов (в диссертации мы ограничимся в основном марковскими процессами), а выбор управления приводит к изменению его траекторий. Нахождение оптимального управления даже для простейших марковских
систем требует объемной вычислительной работы. Поэтому возникает желание уменьшить вычислительную составляющую исследований за счет анализа структурных свойств (пороговой структуры), которые, в свою очередь, позволяют получить аналитические результаты для оптимальных порогов и соответствующих характеристик производительности и надежности.
Несмотря на то что существует большое число научных трудов, посвященных различным типам управляемых динамических систем и анализу их производительности и надежности, многие темы этого направления науки не достаточно представлены в мировой научной литературе, что является стимулом для продолжения исследования и развития этой области прикладной математики. Более того, существующие работы в основном концентрируются либо на вычислении оптимальных стратегий и изучении их свойств, либо на вычислении характеристик производительности и надежности при условии заранее заданной фиксированной стратегии управления. В данной диссертации производится объединение этих двух больших задач, что способствует более глубокому пониманию закономерностей и связей, возникающих в СМО и ДС при наличии возможности динамического управления этими системами.
Заметим, что исследуемые в работе СМО и ДС хоть и принадлежат к разным типам динамических систем, но они имеют много общего. Во-первых, все системы исследуются в стационарном режиме и являются управляемыми, т.е. они снабжены контроллером, который, используя информацию о состояниях системы, динамически управляет этой системой. В качестве управления, решения или управляющего воздействия контроллер может, например, включать/отключать прибор и ремонтное оборудование, выбирать определенную очередь или прибор при размещении заявок, начинать и завершать профилактический ремонт и т.д. Целью такого управления является поиск оптимальной стратегии относительно некоторого заданного критерия, о котором будет сказано ниже. Во-вторых, динамическое поведение этих систем описывается с помощью управляемых марковских процессов. Более того, во всех случаях оптимальная стратегия управления ищется в классе пороговых стратегий, зависящих от одного или нескольких
порогов, например, числа заявок в очереди, системе или числа пройденных промежуточных состояний деградации. В-третьих, анализ производительности и надежности систем включает в себя вычисление схожих характеристик и, тем самым, необходимость использования аналогичных методов и алгоритмов из теории массового обслуживания, надежности и управляемых марковских процессов. В-четвертых, СМО могут также интерпретироваться как ДС, если предполагается, что приборы, контроллер или другие компоненты системы являются ненадежными и постепенно деградируют. В свою очередь, ДС могут рассматриваться как СМО с конечным источником заявок, где заявками являются промежуточные состояния деградации, а приборами - ремонтное оборудование. Все это объясняет представление результатов анализа этих систем в рамках одной исследовательской работы.
Цель работы: разработать комплекс методов и алгоритмов для вычисления оптимальных стратегий управления различными типами управляемых СМО и ДС, для исследования структурных свойств этих стратегий, а также для получения аналитических результатов, включающих формулы различных характеристик производительности и надежности, используемые для проведения системного анализа. Для достижения поставленной цели необходимо решить следующие задачи:
Формализация управляемого марковского процесса и определение его компонентов для исследуемых систем;
Формулировка задачи оптимизации для заданного критерия и разработка алгоритмов вычисления оптимальной стратегии управления и оценки ее эффективности;
Разработка методов исследования структурных свойств оптимальной стратегии управления и получение выражений для вычисления оптимальных порогов в явном виде;
Получение условий существования стационарного режима для соответствующих систем;
Выведение формул для стационарных вероятностей состояний при фиксированной стратегии управления;
Разработка методов и алгоритмов системного анализа производительности и надежности, включая получение аналитических результатов для средних и зависящих от времени характеристик систем;
Проведение численного и сравнительного анализа управляемых систем с различными стратегиями управления.
Методы исследования. В качестве теоретического аппарата для исследования рассматриваемых систем применяются методы теории вероятностей и математической статистики, теории случайных процессов в том числе управляемых марковских процессов, теории массового обслуживания и теории надежности.
Научная новизна и результаты. Главным результатом диссертации является объединение и решение для широкого класса динамических систем двух основных задач, которые обычно рассматриваются по-отдельности: задачи исследования структурных свойств оптимальной стратегии управления и ее фактического нахождения, и задачи исследования характеристик производительности и надежности для заданной стратегии управления, включая выведение явных аналитических формул. В рамках этой обобщенной задачи разработаны новые и усовершенствованы имеющиеся методы и алгоритмы, необходимые для вычисления пороговых стратегий управления, оптимизирующих работу различных типов управляемых динамических систем, таких как СМО и ДС, а также получены формулы для различных средних и зависящих от времени характеристик, необходимых для проведения системного анализа производительности и надежности. К наиболее важным результатам относится:
1. Для широкого класса СМО и ДС определены компоненты управляемого марковского процесса, с помощью которого формулируется задача оптимизации относительно заданного критерия, например критерия средних потерь. Рассмотрены два типа систем: системы с известной и неизвестной структурой оптимальной стратегии управления. Для систем первого типа, с пороговой стратегией управления,
задача нахождения оптимальной стратегии сведена к задаче минимизации представимой в явном виде функции средних потерь. Для вычисления оптимальной стратегии в системах второго типа применен итерационный алгоритм Ховарда, основанный на принципах динамического программирования и сводящийся к решению системы линейных уравнений оптимальности для функции оценок.
-
Для систем с неизвестной структурой стратегии управления показано, что между функцией оценок и управлением существует взаимнооднозначное соответствие, позволяющее для многих видов рассматриваемых систем из свойств монотонности этой функции делать выводы о пороговой структуре оптимальной стратегии. Таким образом установлено, что многие системы с заранее неизвестной структурой также принадлежат к системам первого типа, где оптимальную стратегию управления следует искать в классе пороговых.
-
Для отдельных систем при минимизации функции средних потерь получены явные формулы оптимальных порогов в виде функций, аргументами которых являются параметры системы. Представлен также метод, позволяющий для большого класса систем получить явные эвристические формулы оптимальных порогов с помощью оценки границ между областями оптимальности этих порогов.
-
Показано, что для многих исследуемых систем, многомерный марковский процесс, описывающий динамическое поведение систем с пороговой стратегией управления, принадлежит классу ОПРГ с трехдиаго-нальной блочной инфинитезимальной матрицей, имеющей большое число пограничных состояний. Таким образом, появилась возможность применять эффективный аппарат матрично-аналитических решений для большого класса управляемых систем.
-
Получены условия существования стационарного режима для систем со счетным числом состояний и выведены формулы стационарных вероятностей состояний для фиксированной пороговой стратегии. Получены аналитические результаты для средних характеристик произ-
водительности и надежности, в том числе и функции средних потерь.
-
Представлен метод дополнительной переменной для получения стационарных распределений времени ожидания и пребывания в управляемых СМО. Этот метод использован также для выведения стационарного распределения времени до отказа в управляемых ДС.
-
Проведен численный и сравнительный анализ различных типов управляемых систем. Для этого используются специально разработанные таблицы и диаграммы.
Научная и практическая ценность. Полученные в диссертации результаты позволяют расширить класс реальных моделей, которые могут быть описаны управляемыми СМО и ДС. В соответствии с полученными результатами, управляемые системы значительно превосходят по производительности и надежности свои неуправляемые аналоги. Пороговая структура оптимальной стратегии управления позволяет существенно упростить процедуру ее нахождения, так как в этом случае стратегия зависит лишь от одного или нескольких порогов. Во многих случаях удается получить точные или эвристические формулы оптимальных порогов, выраженные в виде функций от параметров системы. С помощью такой стратегии появляется возможность проведения более глубокого системного анализа, так как многие характеристики производительности и надежности вычисляются в явном виде или с использованием эффективных алгоритмов.
Апробация работы. Результаты работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, Институте проблем передачи информации РАН, Российском университете дружбы народов, в университетах Будапешта, Дебрецена, Линца, Трира, а также на следующих конференциях: XXXV-XXXVIV Всероссийские научные конференции по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных дисциплин (Москва, Россия, 1999-2003 гг.); Первая и вторая мадридские конференции по теории массового обслуживания, MCQT02 (Мадрид, Испания, 2002 г. и 2006 г.); научный семинар "Прикладные стохастические модели и информационные процессы" (Петрозаводск, Россия, 2002 г.); конференция "Распределен-
ные компьютерные коммуникационные сети", DCCN03 (Москва, Россия, 2003 г.); международная конференция "Модели долговечности, старения и деградации в теории надежности, здравоохранении, медицине и биологии", LAD2004 (Санкт-Петербург, Россия, 2004 г.); Четвертая международная конференция по математическим моделям теории надежности, MMR04 (Санта-Фе, США, 2004 г.); XXV Международный семинар по проблемам стабильности в стохастических моделях (Майори, Италия, 2005 г.); XXVI Международный семинар по проблемам стабильности в стохастических моделях (Совата-Бей, Румыния, 2006 г.); 12-ая Международная конференция по прикладным стохастическим моделям и анализу данных, ASMADA07 (Хания (Крит), Греция, 2007 г.); Пятая международная конференция по математическим методам в теории надежности, MMR07 (Глазго, Великобритания, 2007 г.); 7-ая Международная конференция по системам массового обслуживания с повторными заявками (Афины, Греция, 2008); Четвертая международная конференция по управляемым процессам (Москва, Россия, 2009 г.); Международная конференция по математическим методам анализа и оптимизации в информационных телекоммуникационных сетях (Минск, Беларусь, 2009 г.); Шестая международная конференция по математическим методам в теории надежности, MMR09 (Москва, Россия, 2009 г.); Международные конференции по ультрасовременным телекоммуникационным системам ICUMT (Санкт-Петербург, Россия, 2009 г. и 2010 г.); конференция "Распределенные компьютерные коммуникационные сети", DCCN09 (София, Болгария, 2009 г.); Третья мадридская конференция по теории массового обслуживания MCQT10 (Толедо, Испания, 2010 г.); Третья международная конференция по проблемам кибернетики и информатики (Баку, Азербайджан, 2010 г.); Седьмая международная конференция по математическим методам в теории надежности, MMR11 (Пекин, Китай, 2011 г.); XXIX Международный семинар по проблемам стабильности в стохастических моделях (Светлогорск, Россия, 2011 г.); 10-ый Общегерманский семинар по теории вероятностей и статистики (Майнц, Германия, 2012 г.); 9-ая Международная конференция по системам массового обслуживания с повторными заявками (Севилья, Испания, 2012 г.).
Отдельные результаты, представленные в диссертации, выполнены в
рамках проектов РФФИ: №№01-07-90259, 01-07-902596, 04-07-901156, 10-01-92501ИКа, Австрийско-Венгерского научного фонда: №№66oul, 6I011I6, 72ou6, 77oul0.
Публикации работ. По теме диссертации опубликовано 53 работы, среди которых 18 - статьи в ведущих рецензируемых журналах (список ВАК России) [3-7, 12-16, 19, 21, 29, 33, 36, 43, 50, 53], 1 - монография [18], 3 - статьи в других изданиях [11, 34, 35], 14 - статьи в рецензируемых сборниках конференций [2, 24, 26-28, 30, 31, 38, 39, 41, 44-46, 51], 17-тезисы докладов (объемом не более 3 страниц) [1, 8-10, 17, 20, 22, 23, 25, 32, 37, 42, 47-49, 52, 54], 1 - работа из списка ВАК [40], опубликована по смежной теме - оптимальная оценка функциональных зависимостей параметров в физической задаче анализа свойств поверхности материалов.
Объем работы и структура. Диссертация состоит из введения, семи глав, заключения, списка литературы, число наименований в котором - 210, и шести приложений, в которых приводятся результаты численного анализа управляемых систем, исследуемых соответственно в главах 2-7. Основное содержание работы изложено на 334 страницах. Приложения размещены на 42 страницах. Каждая глава состоит из разделов и имеет отдельную нумерацию для формул, рисунков и таблиц, а также отдельную сплошную нумерацию для теорем, лемм, следствий и т.д. (первая цифра указывает номер соответствующей главы). Доказательства утверждений помещены в последний раздел соответствующей главы.
