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

РОССИЙСКИЙ УНИВЕРСИТЕТ ДРУЖБЫ НАРОДОВ

На правах рукописи УДК 519.217:519.218:519.857

Ефросинин Дмитрий Владимирович

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

Специальность: 05.13.01 — Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

"8 АВГ 2013

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

Москва — 2013

005532018

005532018

Работа выполнена в Российском университете дружбы народов.

доктор физико-математических наук профессор В. В. Рыков

доктор физико-математических наук, Л. Б. Рапопорт

доктор физико-математических наук, профессор А. Н. Дудин

доктор технических наук, профессор В. М. Вишневский

Московский государственный институт электроники и математики (технический университет)

Защита состоится "24" октября 2013 г. в 14 ч. 00 мин. на заседании Диссертационного совета Д 002.226.02 при Институте проблем управления им. В.А. Трапезникова РАН по адресу: 117997, г. Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В.А. Трапезникова РАН.

Автореферат разослан "_"_2013 г.

Научный консультант

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

Ведущая организация:

Ученый секретарь диссертационного совета Д 002.226.02

кандидат технических наук В. Н. Лебедев

Общая характеристика работы

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

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

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

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

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

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

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

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

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

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

• Формализация управляемого марковского процесса и определение его компонентов для исследуемых систем;

• Формулировка задачи оптимизации для заданного критерия и разработка алгоритмов вычисления оптимальной стратегии управления и оценки ее эффективности;

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

• Получение условий существования стационарного режима для соответствующих систем;

• Выведение формул для стационарных вероятностей состояний при фиксированной стратегии управления;

• Разработка методов и алгоритмов системного анализа производительности и надежности, включая получение аналитических результатов для средних и зависящих от времени характеристик систем;

• Проведение численного и сравнительного анализа управляемых систем с различными стратегиями управления.

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

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

1. Для широкого класса СМО и ДС определены компоненты управляемого марковского процесса, с помощью которого формулируется задача оптимизации относительно заданного критерия, например критерия средних потерь. Рассмотрены два тина систем: системы с известной и неизвестной структурой оптимальной стратегии управления. Для систем первого типа, с пороговой стратегией управления,

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

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

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

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

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

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

6. Представлен метод дополнительной переменной для получения стационарных распределений времени ожидания и пребывания в управляемых СМО. Этот метод использован также для выведения стационарного распределения времени до отказа в управляемых ДС.

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

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

Апробация работы. Результаты работы докладывались и обсуждались на научных семинарах в Институте проблем управления РАН, Институте проблем передачи информации РАН, Российском университете дружбы народов, в университетах Будапешта, Дебрецсна, Липца, Трпра, а также на следующих конференциях: ХХХУ-ХХХУ1У Всероссийские научные конференции по проблемам математики, информатики, физики, химии и методики преподавания естественнонаучных днецинлин (Москва, Россия, 1999-2003 гг.); Первая и вторая мадридские конференции по теории массового обслуживания, МСдТ02 (Мадрид, Испания, 2002 г. и 2000 г.); научный семинар "Прикладные стохастические модели и информационные процессы" (Петрозаводск, Россия, 2002 г.); конференция "Распредслен-

ные компьютерные коммуникационные сети", БССШЗ (Москва, Россия, 2003 г.); международная конференция "Модели долговечности, старения и деградации в теории надежности, здравоохранении, медицине и биологии", ЬАБ2004 (Санкт-Петербург, Россия, 2004 г.); Четвертая международ-пая конференция по математическим моделям теории надежности, ММШМ (Санта-Фс, США, 2004 г.); XXV Международный семинар но проблемам стабильности в стохастических моделях (Маиори, Италия, 2005 г.); XXVI Международный семинар по проблемам стабильности в стохастических моделях (Совата-Бей, Румыния, 2006 г.); 12-ая Международная конференция по прикладным стохастическим моделям и анализу данных, А8МАБА07 (Хання (Крит), Греция, 2007 г.); Пятая международная конференция по математическим методам в теории надежности, ММГШ7 (Глазго, Великобритания, 2007 г.); 7-ая Международная конференция по системам массового обслуживания с повторными заявками (Афины, Греция, 2008); Четвертая международная конференция по управляемым процессам (Москва, Россия, 2009 г.); Международная конференция по математическим методам анализа и оптимизации в информационных телекоммуникационных сетях (Минск, Беларусь, 2009 г.); Шестая международная конференция по математическим методам в теории надежности, ММ1109 (Москва, Россия, 2009 г.); Международные конференции по ультрасовременным телеКОММУ никационным системам 1С1ШТ (Санкт-Петербург, Россия, 2009 г. н 2010 г.); конференция "Распределенные компьютерные коммуникационные сети", ОССШЭ (София, Болгария, 2009 г.); Третья мадридская конференция по теории массового обслуживания МСС}Т10 (Толедо, Испания, 2010 г.); Третья международная конференция по проблемам кибернетики и информатики (Баку, Азербайджан, 2010 г.); Седьмая международная конференция по математическим методам в теории надежности, MMR.11 (Пекин, Китай, 2011 г.); XXIX Международный семинар по проблемам стабильности в стохастических моделях (Светлогорск, Россия, 2011 г.); 10-ый Общегсрманскип семинар по теории вероятностей и статистики (Майнц, Германия, 2012 г.); 9-ая Международная конференция но системам массового обслуживания с повторными заявками (Севилья, Испания, 2012 г.).

Отдельные результаты, представленные в диссертации, выполнены в

рамках проектов РФФИ: №№01-07-90259, 01-07-902596, 04-07-901156, 10-01-92501ИКа, Австрийско-Венгерского научного фонда: №№66ои1, 61би16, 72оиб, 776и10.

Публикации работ. По теме диссертации опубликовано 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, и шести приложений, в которых приводятся результаты численного анализа управляемых систем, исследуемых соответственно в главах 27. Основное содержание работы изложено на 334 страницах. Приложения размещены на 42 страницах. Каждая глава состоит из разделов и имеет отдельную нумерацию для формул, рисунков и таблиц, а также отдельную сплошную нумерацию для теорем, лемм, следствий и т.д. (первая цифра указывает помер соответствующей главы). Доказательства утверждений помещены в последний раздел соответствующей главы.

Содержание диссертации

Используемая далее нумерация определений, теорем, формул, рисунков - как в диссертационной работе.

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

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

деления теории управляемых марковских процессов, главным объектом изучения которой является управляемый марковский процесс задаваемый пятыо компонентами: пространством состояний Е, пространством управлений А, семейством подмножеств управлений (Л(г),х € Е), нптепсивностямн переходов Аху{а),а е А{х) и ожидаемыми потерями с(х:а),х е Е, а в А(х). Траектории марковского процесса за-

висят от выбора стратегии управления /.

Определение 1.3 Детерминированная стационарная стратегия управления задастся функцией / : Е -> А, определяющей независимое от прошлых состояний процесса управление /(х) € А(х) С А всякий раз, когда процесс в момент выбора управления находится в состоянии х £ Е.

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

дГ = Ит = V с(у, ¡{у))1г', где (1.1)

с I

общие ожидаелше потери в течение времени t при условии, что начальное состояние процесса х и выбрана стратегия /, = lim p/[X(i) = у] - стационарные вероятности состояний для стратегии /. Предполагается,

что Y. IС(У' 1(у))\пу < Для фиксированной стратегии / предполагается

ся, что {X(i)}i>o - неприводимый положительно возвратный марковский процесс с ннфшштезпмалыюй матрицей Af = [ЛТ!/(/(ж))] и функцией ожидаемых потерь c{x,f{x)). В главе рассматриваются два типа задач оптимизации: для систем с известной пороговой структурой и для систем с заранее неизвестной структурой оптимальной стратегии /*. В задаче первого тина стратегия /* имеет структуру в виде зависимости от одного или нескольких порогов. В этом случае функция средних потерь д} определяется в явном виде, используя правую часть формулы (1.1). В задаче второго типа оптимальная стратегия ищется среди всех допустимых стратегий.

Для вычисления оптимальной стратегии /* в этом случае используется итерационный алгоритм Ховарда, основанный на принципе динамического программирования.

Теорема 1.12 (Итерационный алгоритм Ховарда)

Шаг 0 (Инициализация). Выбор начальной стратегии /.

Шаг 1 (Решение системы уравнений). Вычисление единственного регие-

ния д* и функции оценок уЦх), х € Е, системы уравнений

Ц£Е

Шаг 2 (Улучшение стратегии г^равления). Вычисление новой стратегии /, минимизирующей выражение

ется с результатом /. В противном агучае стратегия / заменяется па /, и происходит переход на Шаг 1.

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

Во второй главе рассматриваются управляемые одноканальные ненадежные СМ О М/М/1 с пороговой стратегией включения/отключения прибора или ремонтного оборудования, см. рисунок 2.1. В таких системах приборы могут отказывать и восстанавливаться через случайное время. Предполагается, что системы могут быть с обычной очередью или с повторными заявками.

Определение 2.1 Стратегия управления / включением/отключением прибора имеет пороговую структуру с заданным порогом д8 > 1. В соответствии с этой стратегией прибор отключается всякий раз, когда он обслужил последнюю заявку в системе. Как только в системе число заявок достигло порога д„, прибор включается через случайное время.

(1.6)

}{х) = а^ппп с(х, а) + ^ ЛХ1/(а)у/(у) - д1 , х е Е.

аел(т) .

Шаг 3 (Проверка сходимости). Если / = /, то алгоритм останавлива-

(а)

(б)

Орбита

Ремонтное оборудована!

Орбита

Ремонтное Включение/ оборудование отключение

Включение/

Рис. 2.1. Схема СМО с отключаемым прибором (а) и рем. оборудованием

Время подготовки к работе распределено экспоненциально с параметром 7. Отказ прибора возможен только во время обслуживания. Время до отказа и время до восстановления распределены экспоненциально с параметрами а и /?. В систему поступает иуассоновский поток заявок с интенсивностью А. Заявка принимается свободным прибором с вероятностью р, с вероятностью 1 - р заявка занимает место в очереди повторных заявок (орбите) и через экспоненциально распределенное время с параметром т + qd (т > 0,0 > 0, т + в ^ 0), где q— число заявок на орбите, независимо от остальных заявок пытается запять обслуживающий прибор. Дисциплина с такой интенсивностью повторов объединяет два наиболее распространенных случая: дисциплину с постоянной интенсивностью повторов (в = 0) и дисциплину с классической интенсивностью повторов (г = 0). Время обслуживания распределено экспоненциально с параметром д. После неудачной попытки занять прибор заявка возвращается на орбиту.

Состояния системы в момент времени t описываются вектором {Q(t.),D(t),B(t)}, где Q(t) - число заявок на орбите, D(t) и B{t) - состояния работоспособности и занятости прибора, причем

(б)

0, прибор отключен,

1, прибор включен,

2, прибор восстанавливается,

прибор свободен, прибор занят.

Случайный процесс

{X(t)}t>o = m),n(t),B(t)}t>o 14

(2.1)

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

Теорема 2.2 Марковский процесс {Х(£)},>0, определенный в (2.1), является эргодическим тогда и только тогда, когда

1)/, = К1 + |)+Л^Т7<1' еслит>°'в = °> (2-5)

2)р = -(1 + < 1, если т > 0, в > 0. (2.6)

(X \ р/

Для вычисления стационарных вероятностей из СУР для случая

в = 0 используется метод производящих функций для \г\ < 1,

9»"1 ос ЭС

ра>(г) = ^ г?7Г(«.о.о), рф) = £ г%(?д.о), р21{г) = ^ 2%(9.2л), (2.12)

9=° 9=1 9=0

ос ос

Рт{г) = ХУ^АО), рп(г) = л).

9=9» 9=0

Теорема 2.4 Частичные ПФ определенные выражениями (2.12),

удовлетворяют соотношениям,

1 - -г«» „ , , Аг9'

Рю(г) = г _ г 7Г(0.0.0), Р01(г) = д+ д^о.о.о), Рш(г) = г\((г4, - 1)7 + (г ~ 1)А)((/? + А - гА)/г+ + (1-*)А(а + /?+А-*А))М

Ри(г) = А((г* - 1)7 + (л - 1)А)(гА - (3 - А)(ргА + т)^,

F(z)

Я21(г) = аА((г* - 1)7 + (г - 1)А)(ргА + где

Р(г) = (г~ 1)(7 + А - г\){г\Н{г) + в{г)т),

Н{2) = (2-1- ргЩа + Р + \-г\) + {р-1)(0 + \- ¿А)/х,

в(х) = г2А2 - г\(а + /3 + А + /и) + (/3 + Х)ц.

Вероятность 7Г(0.ао) получается как единственное решение условия нормировки Рг1(1) + Е/=о Е)=о^(1) = 1 и вычисляется по формуле

7 /V/?- А(а + /?) Л \ 7Г(П 0 0) ~ А + ?Л V 1Ф рЬ + тУ

Для решения СУР в общем случае (в > 0) предлагается матрично-аналитический метод для систем типа М/С/1. Такой подход широко известен в литературе и основан на идее сенсорных цепей Маркова.

Теорема 2.5 СУР имеет матричное представление

7ГЛ = О, 7Г0С0 + 7Г1С1 4- 7Г2С2 Н----= 1, (2.18)

где макро-вектор тг = (тт0, ...) состоит из подвекторов = (Т(0.0.0),1'(0.1.1))> = (Щ.1.0),Щ.1Л))> ?> 1 «с»= (?»+ > сч =

, д > 1. Матрица А - блочная инфинитезимальная матрица

/<30.0 (?0.1 С?0.2 <?0.3

I Ч 1.0 <?1.1 <?1.2 <?1.3

Л _ I ° ?!1 02.2 (?2.3

_ I О О Оз.г <3з.з

(2.19)

Теорема 2.6 Подвекторыттч, д > 0, стационарных вероятностей состояний вычисляются по формуле

7Г, = 7Г д>1, (2.20)

г£?е = /, Г, = ЕЙ^Ои(-Ом)-1, 1 £ 1. матрицы г = 6Д I > О,

определяются следующим образом,

ёао = ("А 4) , ^л = а , = (о а ' ' =

V 0 аШ )

0 N - - _ /А(1 — р) о

= V0 * (х^П ' 4 = М " 2' = V 0 ' а - м; '

и вектор 7Го является единственным решением системы

КоС^о.о = 0,

7Г0 £ Рдсд = 1. (2-21)

9=о

Задача оптимизации,

(?; = аг&ттд(д,). (2.22)

Теорема 2.7 Функция средних потерь д{ц„) вычисляется по формуле

дЫ = 0)Ы + схРт(1) + с2Лл-(о.о:о), (2.23)

где N обозначает среднее число заявок в системе, причем

Й = Т,\ ЕЕ + ^21(^)1 |г=1+Рц(1) + Р21(1)

1 1

1=0

РМ( 1)= + А ч

А + <2лЛ /4? рА + т/

/х /Зц

Теорема 2.8 Оптимальный порог при котором средние потери д(д„) принимают минимальное значение, удовлетворяет соотношению

<Л = (2.24)

"2ЛГС1 I . У/?М-А(а + /3) Л V АЛ ЛМ1/2 Л

со V 7 ^ С2/ \-Щ--+ 7

Для системы с отключаемым ремонтным оборудованием стратегия определяется следующим образом.

Определение 2.10 Пороговая стратегия / задается порогом <),- > 0. Согласно этой стратегии контроллер включает ремонтное оборудование только если число заявок в системе превысит порог и выключает это оборудование, если число заявок сократится ниже данного порога.

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

{X(t)}t>0 = {N(t),D(t)}t>0, (2.25)

где N{t) - число заявок в системе и D(t) - состояние прибора, причем

{О, прибор свободен,

1, прибор занят,

2, прибор восстанавливается.

Пространство состоянии Е = {х = (q,d,b);q g N0, (d,b) g {(0,0), (1,0), (1,1), (2,1)}}. Структура штрафов: со - штраф за единицу времени пребывания заявки в системе, с1;0 и си - штрафы за единицу времени функционирования системы, когда прибор находится в рабочем состоянии и число заявок в системе N(t) < qr и N(t) > qr, С2.0 - штраф за единицу времени пребывания прибора в состоянии восстановления с отключенным ремонтным оборудованием, с3 - фиксированный штраф за включение/отключение ремонтного оборудования.

Для С M О с орбитой, где в = 0, р = 1, СУР решается с помощью объединения метода производящих функций и метода разностных уравнений,

pm(z) = £ z'\n.0), Pw(z) = х; Л(в. 1), P№(z) = Znir(n.2), (2.39)

71=1 П = 1 П=1

3C DC 3C

Poi(z) = Y, Z"4n.0h pn(z) = J2 1)' =

n=qr n=qr "=4r

Теорема 2.12 Частичные ПФ Pij(z), определенные выражениями (2.39), удовлетворяют соотношениям,

(г) = ^±--UGx{z,qr)-g2Gi{z,qr)), (2.40)

72 - 71 т ^ '

Pw{z) = -^^-(l'29iGi{z,qr) - 7iff2G2(z,gr)), 72 - 7i v '

72-71

^ = 72 - 7! А(1 - г)+ ЪдгОгЦ,*) - ъяСЬЦ,«)), гОе

(2.41)

_ (А + г)(Л + /х + а) - А/х ± ^/((Л + г)(А + /х + а) - А/х)2 - 4/хтА(А + т) 11,2 2/хт '

ад -„[(„

32 К'1 А2(1 — г) + А/3^'

А \ v > (А + 0)г А(1 — г) + ¡3/

Вероятность 7Г(11) является единственным решениель условия нормиров-7Г(о,о) = 1 и вычисляется по формуле

тг(1Д) = (72 - 71) [р1(п(1, Яг) (72~{А + 1) + - (2.42)

■92С2(1,Яг)(Ъ^(А+1)

^ ' Т )

А\ л._1 ( д А

+ 517Г1 (а - - ,27Г1 (л - + ^(73 - 71)]

?ЛР Д _ ЗрА+А(А+е)(а+3) л фА-А(А+Й)(а+^)'

Помимо метода производящих функций, альтернативным методом решения СУР является матрично-аналитический метод. Для СМО с орбитой и р > 0 введем 7Г = (7Г0,7Г1,7Г2,...) макро-вектор строку стационарных вероятностей состояний, где тг„ = (тг(,г.0), тг(1г+1Л), тт(?г+!.2)).

Теорема 2.13 Для заданного порога ду марковский процесс (2.25) принадлежит классу ОПРГ с пограничными состояниями и блочной трех-диагональной матрицей А = [А^(дг)],

/ <? 1.0 Со о О О <?2 <?1.1 <?о О О О С32 (3,л (?о О

л =

О О ... \ О О .. О О

О <?2 <}1.2 во О О О <?2 «1.2 <?0

V

<7г - 1

(2.42)

и макро-вектор стационарных вероятностей п удовлетворяет системе

7гА = 0, 7ге = 1.

Теорема 2.15 Суб-векторы 7Г„ стационарных вероятностей состояний удовлетворяют соотношениям

Яг~П

Кп = П Мч*~и п = 9г - 1,

(2.44)

¡=1

7Г„ = ТГ9г Д" Чг, П > Яг, где матрицы А/; вычисляются рекуррентно

Л/о = ___(2-45)

м,- = -д2(л/г_1д0 + диГ\ »= 1,9г - 2, л/,г_1 = -<З2(М9г_2(Зо + ^1.2)_1-

Вектор 7Г?г является единственным решением системы уравнений,

■кЧг{МЧг-хЯа + «?1.2 + ВД = 0, (2.46)

?г-1 ?г-П

¡ + (/-Д)"1)е=1. (2.47)

71=0 1 = 1

Матрица В. является минимальным неотрицательным решением матричного квадратного уравнения Я2<52 +^С? 1.2 + <Зо = О и Я<32е = Я^е. Из структуры матриц <2о, <21.2, (?2 следует явный вид матрицы Я,

Я =

/ А(1-р) А2(1—р) оА2(1-р) ^ т ЦТ цт(3+А)

Л А(А+6>) А(А+т)а

V

т-(3+А] Ьг)а+А;| рт(гЗ+А)

ДТ , .

А(А+т) А(А+г)а+А;1Г

(2.48)

/

Анализ производительности систем включает вычисление в явном виде различных средних характеристик системы, например, среднего числа заявок в системе, среднего времени ожидания и т.д. Задача оптимизации,

q* = argmin5(9r). (2.57)

Чг

Теорема 2.24 Функция средних потерь g{qr) для СМО с орбитой и произвольной вероятностью р вычисляется по формуле

qr-2

g{qr) = cuN + ^7rn(co.o,ci.o,c2.o)' + 7r?r_i(co.o,ci.i,c2.i)'+ (2.58)

71=0

+ Н)~1(Со.1,С1Л,С2.1У,

где 7ГП,п = 0,qr, и R вычисляются по формулам (2-44) " (2-48).

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

{X(t)W = (7V(i), D(t), J(i)W, (2.63)

с пространством состояний Ê для вычисления условного времени ожидания маркированной заявки после ее поступления в систему. J(t) - положение маркировано!*! заявки в очереди повторных заявок. ПЛС времени ожидания w(s),

х ос 2

w(s) = J2 Чп.0) + Е X) 4n,d)W(n+i.d.n){s), (2.64)

п=0 >j=l d= 1

гДе û(n.d.j)(s) ~ ПЛС времени до поглощения при условии начального состояния х = (n,d,j) б Ê. Обозначим через

w„j(s) = (îZ)(„.o.j)(s), w(n+i,i.j)(5), w(jt+I.2.J-)(s))/, n = j, qr +j - 2 вектор-столбец условных ПЛС.

Теорема 2.25 Вектор условных ПЛС wnJ(s),n = j, qr+j- 2, удовлетворяет рекуррентному соотношению

wM(S) = Mrn~\s)Ml(s)wQr+j.1J(s) + AI^-'i-1(s)x

(2.67)

Чг-п-2

X 1ОО + М'^Ь^з^п+г-и-^з), п < Яг - 2,

qr-n+j-2

+ ¿/^^(^„-н-!..,-!^), П > - 1,

¡=0

= 0{-Ч8)(Ма),М*)М*))', = (0,1,1)', ^е (2.69)

Мк(8) = -(д1к - 31)^0, Ыа) = -((?!/ь - з/)"1д2, Л = 1,2, (2.70)

-__ртЪМ_ т м + а)

2(8) "" 03 + в)(г + А(1-М8)) + 5)' ^ (/^ + « + ^ + -

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

В третьей главе рассматриваются управляемые СМО М/М/К, которые состоят из одной общей очереди и К > 2 неоднородных приборов с интенсивностямн ] = 1, К. см. рисунок 3.1. В систему поступает пуас-

(а) (б)

Рис. 3.1. Схема СМО с обычной очередью (а) и орбитой (б)

ооновский поток заявок с интенсивностью Л. Обслуживание на приборе происходит без прерывания. Контроллер управляет размещением заявок на неоднородных приборах. Моментами управления являются моменты сразу после поступления заявки в систему и сразу после окончания обслуживания на приборе. Состояния системы в момент времени г описываются марковским процессом {Х(*)Ь>0 = {<?(*), #(*)}/>о, где ф(г) - число заявок в очереди и £>(*) = • • •' ~ состояния приборов, причем

22

0, прибор свободен,

1, прибор занят

3 = 1, К.

Пространство состояний Е = {х = е Щ, <1 е £} и управлений

А = {0,1,..., К}. Структура штрафов: Со - штраф за единицу времени ожидания заявки в очереди, с} - штраф за единицу времени обслуживания на приборе причем

Структура стратегии / : Е -> А предполагается неизвестной. Для вычисления оптимальной стратегии /* используется итерационный алгоритм Ховарда. Для функции оценок ь(х) и ее приращений установлены свойства монотонности, из которых следует утверждение.

Теорема 3.5 Оптимальная стратегия /* имеет пороговую структуру, т-е• /* = (<72> • • • > 1к)> задаваемую порогами 1 = < < ■.. < < оо. Согласно /* для порядка (3.7) первые к приборов должны быть заняты в состоянии х е Е, если ц(х) = - 1, к = Т^К, где д*к+1 = оо.

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

Теорема 3.19 Для заданных порогов 1 < < • • ■ < Цк < оо марковский процесс {Х(г)}(>0 принадлежит классу ОПРГ с большим числом пограничных состояний, вектором стационарных вероятностей п и блочной трехдиагона^гъной инфинитезимальной матрицей Л = [Хху(д2, -.., Цк)\,

О < схцх 1 < с2ц2 1 < • • • < скцк1 О < ^ <ц2х <■■■ < цк\

(3.7)

... \

л =

— л ч;(Ы1 <32.0 <?1.1 <?0.1 о О о о о О о ...

О <32.1 «1,2 <Зо,2 О о о о О о ...

О О «2.2 <?1.3 <Зо.2 о о о О о

о <32.2 41.3 <?0.3 о о о о о ...

о О <32.3 <31.4 <Зо.4 о о о о ...

о о о <?2.1 «1.5 <Зо.5 о о о ...

о о о О <32.3 51.5 00.5 о о ...

о <Зг.2*—1 Qo.3J.-3 о о О о о ...

о О <3г.з|;-з Qi.it <?0.3А--2 о о о о ...

о о о Qi.3l.-2 <?1.2А+1 <?0. ЗА — 1 о о о

о о о О <32.31-1 <?1.2А + 1 <Зо.ЗА— 1 о о ...

о о о О О <?2.3/( —4 (31.2К-1 С?о.зк--з о ...

о о О о о О <?2.3К-3 -(Л + /1) А

>ема 3.20 Подвекторы г > 0, вычисляются по формулам

<72 + 1

Чк ~ Я2+ +к-2

ЧК - <». + +К -к

ЧК + К-1-1 _

тг; = тт0к+к-1 П Мчк+к-1-ь 1 = Чк + к - 2,

(3.27)

где 1гЧк+к-1 = 7Г(,к-1.1 1), матрицы Мп удовлетворяют соотношениям

М0 =

(3.28)

ЛД = -<22.1(МО<2О.О + <Э1Л)"\

Л/2 = -^(М^ол + ^ьг)"1, _

М; = -<Э2.зк-4(Л/г-1<Зо.з*г-4 + Яг,2к-1)~\ г = + к, % + к ■

Мщ+к-2 = -Я2.3к-з{Щк+к-зЯоЛк-А + Я\.2к-\)~1,

МЧк+к-1 = ~(Э2.3к-2(М<1к+к-2<Э0.3к-3 + <?1.2Аг)-1,

= -ф2.з*-1(А/«г,.+*-1<Эо.з*-2+ <?1.2*+1) '

причем к = 2, К для всех равенств кроме последнего, где к = 2, К — 1. Вероятность -КдК+К-1 является единственным решением уравнения, полученного из условия нормировки,

1Гчк+к-1 [ £ П Мяк+К-1Ч е + — ] = 1.

¡=0 1=1

(3.29)

Следствие 3.21 Средние потери системы,

к

9 ■■= 9(я2, • • •, Як) = - <*№] + СоДг,

j=1

{/,• - коэффициент готовности прибора j и N - среднее число заявок.

Оценка границ между областям оптимальности порогов приводит к эвристическому решению.

Теорема 3.23 Оптимальные пороги ц*к, к = 2, К, задаются формулой

(3.30)

Як ~ Як = | — с0

к-1

^ и

где

к-1

Е »ь а = о,

5 (Е Н ~ А + Л (Е 14 - А)2 + 4(Л - 1)цк\ ), Л > 0.

(3.31)

Для систем с повторными заявками получены следующие формулы.

Теорема 3.56 Оптимальные пороги к = 2, К, задаются формулой 1. В случае дисциплины с классической интенсивностью повторов

1

Як-Як

к-1

Ск „ Со Е>=1 N ^

---п--/С)

1СоЩк в 1

]=1

(3.86)

£ В случае дисциплины с постоянной интенсивностью повторов

Як ~ Як =

А-1

(3.87)

Функция Рк определена в (3.31).

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

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

{X(i)}(>(+ = (Q(i), D{t), J(t)}t>t+, (3.33)

с пространством состояний Ê = Е х {0,1,.. .,q(x);x g Е} ПЛС времени ожидания вычисляется по формуле

w(s) = ^х + 7ri'5(9(l)+l,d(l),9(x)+l)(s)i (3.34)

xçE\Ew xeEn-

û\q(x)+i.d(x).q(x)+i){s) - ПЛС остаточного времени ожидания до поглощения, Ew = E\{x-, q(x) = di(x) = 0} - подмножество состояний для ожидания.

Теорема 3.31 ПЛС W(q.dl.....dK.j)(s) времени ожидания удовлетворяют

системе уравнений

wx(8) = (—Y, ж = eÊ,q-j>qK- h (3.35)

45 + \l)

y \Xy(q2й (s), x = (g,d,j)eÊ, (3.36)

yeE\{x}

g - j <qk - 2, wz(s) = l,x = (q,d,j) G Ê, j = 0.

Период занятости и число обслуженных на нем заявок используются для оценки эффективности структуры или управления системой. Этот период означает время от момента, когда заявка поступает в пустую систему, до момента, когда после завершения обслуживания система вновь становится пустой. Вводятся обозначения: Ç>x(s) - ПЛС времени первого возвращения

впулевое состояние, тогда ПЛС периода занятости ф(з) := <¿3(0.1,0.....o)(s)-

Сформируем также макро-вектор tp(s) = №i(s),..., ФЧк+к-i(s))'î компоненты которого содержат ПЛС фх(s), упорядоченные также как -кх.

Теорема 3.33 Вектор ПЛС (p{s) времен первого возвращения в нулевое состояние в системе с пороговой стратегией управления удовлетворяет трехдиагональной блочной системе.

ф(з) = ЫвГ'т, (3.42)

где Ajr(s) - квадратная матрица вида ЛL{s) = Ф — s// + \Ç(s)Ei, Ei = е\{1) ® е,(0, г = -(Л^О^^О)', I = 2(д2 + <7з) + 3 (7С = 3j,

1-3

Ф) =

s + A+/i - v/(s + А + /i)2 -4A/i

2А

(3.43)

Матрица Ф получена из Л путеА1 удаления первой блочной строки и столбгщ, а также всех блочных строк и столбцов начиная с (дк + К + \)-ой. Для К = 3 матрица Ф имеет вгьд

Ф =

Q 1л <?0.1 о о о о о о о О \ Л

Q2A Q 1.2 Qll.2 О о о о о о о

о Q2.2 Q 1.3 QO.2 о о о о о о [ Q2

о О Q'2.2 Qi.3 Qa-з о о о о J

о о О «2.3 Q 1.4 Уо.1 о о о \

о о о О Q2.1 Qi.3 Qo.3 о о

о о о о О Q2.0 Q1.3 Qo.3 ... о 1 <13

о о о о о О О <32.5 Ql.3 Qa я \

\ о

О О О О О О О Q2.C -(Л + р) /

Теорема 3.35 Вектор моментов L(n), п > 0, условных времен первого возвращения в нулевое состояние в системе с пороговой стратегией управления удовлетворяет рекуррентному соотношению, имеющелц) блочный трехдиагоналъный вид,

L{n) = -(Ф + A£,)_1x

(3.47)

/Л

х (п(/г + АЁ(1)£',)£(гг - 1) + (^)Ё.(п-т)Е1Цтп)У п > 1,

т=е(1),

где I = 2(<72 + 9з)

+ 3, Н(гг) - момент п-го порядка периода занятости системы М/М/1 с интенсивностью обслуживания /г.

Пусть 1рх(г) - ПФ числа обслуженных за период занятости заявок и ~ф(г) = (^1(2),... ,г/>Чз+2(г)У - макро-вектор ПФ.

Теорема 3.37 Вектор условных ПФ тр(г) числа обслуженных за период занятости заявок в системе с пороговой стратегией управления удовлетворяет трехдиагональной блочной системе

tKz) = zA¿{z) г, (3.55)

где Лл-(г) = Ф - Л(г) + АС(г)£*, = (1 - z)A(Q2,i, Q2.2, • • •, Q2.2, Q2,3,

92-1

Q2 4, Q25, ■ ■ ■, Q2.5j Q2.g); A(ai - ■ -1 am) обозначает нулевую матрицу с под-

73 -92-1

диагональными элементами, представленными блоками ai...,am, и

ф) = А + + (3 56)

¿Л

Теорема 3.40 Вектор моментов 1Ч(п), п > 0, числа обслуженных заявок в системе с пороговым управлением удовлетворяет рекуррентной трехдиагональной блочной системе,

Щп) = _(ф + АЕ1У1 х (п{А(0) + \2{1)Е[)Щп - 1)+ (3.62)

п—2 , ч

+ А " ) 2(п - тпЩЩт) - ¿„Лг], п > 1,

т=О

N(0) = е(0,

г<9е / = 2(</2 + <?з) + 3, ^(п) - п-й момент числа обслуженных заявок в системе М/М/1 с интенсивностью обслуживания ¡1.

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

(а)

(б)

л

Пороп) Ц,

Окончание обслуживания

Р1 Восстановление

о, Отказ

Рис. 4.1. Схема СЫО с ненадежными приборами (а) и процесс обслуживания Б] прибора j

В четвертой главе исследуются управляемые СМО с неоднородными ненадежными приборами. Рассматриваются два основных лит систем: системы с двумя неоднородными приборами и одной общей очередью и системы, представляющие собой две неоднородные многоканальные СМО в тандеме. Приборы могут отказывать и восстанавливаться через случайное время либо с некоторой вероятностью, причем отказы могут быть как полными, так и частичными. В последнем случае прибор остается работоспособным, но с более низкой производительностью. В главе рассматривается СМО М/М/2 с отказом всех приборов, см. рисунок 4.1. Интенсивность обслуживания прибора ] - . Поступающие заявки формируют пуассоновскнй поток с интенсивностью А. Приборы отказывают и восстанавливаются с интенсивиостями 04 и /3,-. Задача контроллера, как и в предыдущей главе, состоит в размещении заявок на неоднородных приборах. Структура оптимальной стратегии /* предполагается неизвестной. Состояния системы в момент времени I описываются марковским процессом {Х(г)},>о = {<5(0, с пространством состояний Е = {х = (<?,£?);д 6 N0, й е £>}, где (^(г) - число заявок в очереди и = {/?!(<), ~~ состояния приборов,

Структура штрафов: со - штраф за единицу времени ожидания заявки в очереди, с,м - штраф за единицу времени обслуживания на приборе - штраф за единицу времени восстановления прибора Приборы перенумерованы в следующем порядке,

А«1 > /42, СпМ! 1 < С21М2 С12/?1 1 < С22/?2 \ (4-6)

«1 < «2, А > > А, № > /?2-

Теорема 4.3 Оптимсигъная стратегия /* имеет пороговую структуру, задаваелщю порогами 1 < <71 < <7г < Согласно /* й/гл порядка (4-6) прибор 1 должен быть всегда занят при непустой очереди. Прибор 2 в состоянии х = (9, /с, 0) 6 Е должен быть занят, если д(х) >Ц*к, к = 1,2.

Для фиксированной пороговой стратегии / процесс {Х(<)},>о принадлежит классу ОПРГ с блочной трехдиагональной ннфшштезиыалыюй матрицей Л = [\Ху(Я1,Я2)}-

Теорема 4.7 Необходимое и достаточное условие существования стационарного режима марковского процесса задается неравен-

<>- У* Ч„ <»■ <4л6>

¿-¡¡=1

Теорема 4.8 Векторы 7Гд, д > 0, стационарных вероятностей состояний системы вычисляются по формулам

Ч1-Ч

= п<11 П 9 = 111 - 1> (417)

j=0

где матрицы А/, зависят от блоков матрицы Л и вычисляются рекур-рентно, 7Г91 является единственным решением системы уравнений

[х п дНе=(4л9) -5=0 ^=0 -1

щЛМ^-хЯо .5 + д1.5 + ОДм) = 0-Матрица Я является минимальным неотрицательным решением квадратичного матричного уравнения,

Д2<3г.б + Я<?1.5 + Яо.б = 0. (4.20)

С помощью явной формулы для средних потерь д получим.

Теорема 4.10 Оптимальные пороги к = 1,2, задаются формулой 1 /?1/И

1к ~ Як =

с0 аг + А

С2.1^1 - С1.к

к =1,2,

где

(4.21)

=

14

1( _ \ I

+ 4-^Л

Л = О, А > О,

(4.22)

01С1.2 + ДСц _ («1 +^1)С1.2 +АС1.1 с1.1 = -Я-) с1.2 = -

¡Зф\

02С2.2 +/?2С2.1 _ С2.1 = -—-, С2.2 =

Рт

(а2 + ц2)с2.2 + /З2С2.1

Для другого вида СМО М/М/2 с ненадежными приборами, см. рисунок 4.2 вводится случайный внешний фактор, влияющий на работоспособность прибора. Отказы быстрого прибора 1 могут быть как полными, так и ча-

(а) (б)

м,(во))

Поступление СМередь

—Н 1 1 |

Пороги <к •■• Я.

Оюнчание обслуживания

Рис. 4.2. Схема СМО с ненадежным прибором 1 (а) и процесс обслуживания прибора 1 в зависимости от процесса ТЦ1)

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

с*!,..., ат_1. Из состояний внешнего фактора к = 2. т — 1, приводящих к частичному отказу прибора 1, и из состояния т, приводящего к полному отказу, возможен переход в начальное состояние с интенсивностями /?!,..., /Зт-\. Заявка, обслуживание которой прерывается полным отказом, покидает прибор и становится во главе очереди. В нормальном состоянии

внешнего

фактора интенсивность обслуживания прибора 1 равна цц, а в

состояниях частичного отказа - /гц-, к = 2, m — 1. Интенсивность обслуживания прибора 2 равна ц?. Состояния системы в момент времени t описываются марковским процессом {^(i)}f>o = {Q(t),D(t), B(t)}f>0 с пространством состоянии Е = {х = (g, d, b); g 6 N0, d € D, b e {1,..., m}}, где Q(t) - число заявок в очереди и D(t) = {Di(t), D2(t)} - состояния приборов, причем

приоор свооодеи, . = ^

приоор занят,

Б(1.) е {1,..., тп} - состояние внешнего фактора, причем 1 означает нормальное состояние, {2,..., т — 1} - состояния частичного отказа и т -состояние полного отказа. Задача оптимизации рассматривается для критерия среднего числа заявок в системе. Перенумеруем приборы и состояния внешнего фактора следующим образом,

Ни <■■■< < &>•••> рт-1. (4.28)

Теорема 4.16 Оптимальная стратегия /* имеет пороговую структуру, задаваемую порогами 1 < д*п < < • • • < д\ < оо, где порог д*к,к = 1 ,т, соответствует состоянию к внешнего фактора. Согласно /* для порядка (4-28) прибор 1 должен быть всегда занят при непустой очереди, если он находится в рабочем состоянии. Прибор 2 в состоянии х = (<?, 1,0, к) 6 Е должен быть занят, если д(х) > дк, к = 1, т.

Для фиксированной пороговой стратегии / процесс {^"(£)}(>о принадлежит классу ОПРГ с блочной трехдиагональной ннфшштезпмалыюй матрицей А = [А^(9„„..., 91)].

Теорема 4.20 Необходимое и достаточное условие существования стационарного режима процесса задается неравенством

р =-=1---< 1. (4.40)

(1 + ЕГ/^) (дп + Е

Применим матрично-аналитический метод.

Теорема 4.21 Векторы -ло.о и 7Г9л, <? > 0, стационарных вероятностей состояний системы вычисляются по формулам

тго.о = 7Г„Л ЛЛ/,,^, (4.41)

j=o

91-9-1

= П < <7 < ^ - 1, А- = 17т,

пчл =тсд1лК'~41, Ч > 7ь

где матрицы Л/,- зависят от блоков матрицы А и вычиагяются рекур-рентно, 7Г91.1 является единственным решением системы уравнений

Е П Л/*-.> + (7 - д)-1 е =

^¿(-Л/^фо.гт + <?1.2т+1 + Щ2.2т+\) = О.

(4.43)

Матрица Я является минимальным неотрицательным решением квадратичного матричного уравнения,

Я <?2.2т+1 + + <3().2т+1 = 0.

(4.44)

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

Предположение 4.23 Оптимальные пороги к = 1, т, задаются формулой

<1к~% =

Р2

, где

(4.45)

А = 0,

I (/'ц1 - А + у/(ГНк - Л)2 + 4/'2А ), А > 0,

(4.46)

к = -е'к_хМ 1е, к = 1,т,

/-(«Н+ЕК1«!)

-(Р12+Л) 0

О -((113 + 32)

О О

м =

Э,„- 2 \ Лт-1

о о

-(М1ТП-1 + Ап-2)

О

О

С помощью метода дополнительной перельенной вычисляется ПЛС времени ожидания. Вводятся обозначения: ^(в) = (^(в),...,)'- вектор условных ПЛС, подвектор = (wj.j(s),vrj+lj(s),... вектор v/q.j состоит из ПЛС для состояний х, где = </.

Лемма 4.25 ПЛС ч/ч.]{з), д— 3 >д\ — 1, удовлетворяет соотношению

где <Э1.2т+1(з) = С?1.2т+1 - + <5о.2т+1-

Если с/ — _/ < г/1 — 2, то векторы ^w,| j(s) вычисляются рекурреитио.

Теорема 4.26 Вектор ПЛС' ^(в), ] > 1, остаточного времени ожидания удовлетворяет рекуррентной блочной системе

где ЛДз) = Ф^ — в/ и Г^- обозначают двухдиагоналъные блочные матрицы. Матрицы состоят из —1-ой блочной строки и <71 — 1-го блочного столбца из матрицы Л, где первые j + l блочные строки и столбцы удалены. Если j = + 1,^ — 2, эти матрицы имеют вид

Фj = <Иад{С2 и, . . . , <51.,-, . - - , (¿1.2т-1, §>1.2т+1, <?1.2т+1) +

= (-<31.2т+1(«)<Э2.2т+1)',е,

(4.48)

Л^в)^(в) = -Г^-^в) - Л,-(в), ^о(в) = е,

(4.49)

+ (Над (¿Зг.Ь • • • , Q2.i1 <2о.1+Ь ■ ■ ■ > Q2.2m-l■,Q2.2m■,Q2.2m+\^ • ■ ■ т02£т+1_)1

Г/ = <Иад((52.м - • • , Q2.it С?2.1'+1, ■ • • 1 <Зг.2т-Ь ^2.2т, <?2.2т+Ь • • ■ > Я2.2т+\) +

ч.

м

+ (Иад+ (0^.. . ,0, (?!.;+1 - «Эй, 0,..., 0, <2 1.2т - Я^т-и

91-2

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

В пятой главе проводится анализ управляемых деградирующих систем, которые полностью отказывают после последовательного посещения п > 1 промежуточных состояний деградации. Предполагается, что эти системы являются многоразового использования, т.е. они полностью восстанавливаются (становятся абсолютно новыми) после ремонта в состоянии полного отказа Е, а также и после профилактического ремонта. Контроллер на основе наблюдаемых состояний деградации управляет профилактическим ремонтом. Управление производится в соответствии с пороговой стратегией /д. с порогом к = 1 , п, инициирующей начато профилактического ремонта системы после перехода в состояние деградации к. В этом состоянии система восстанавливается и переходит в начальное состояние процесса 0. Предполагаются различные типы систем: система с абсолютно надежным контроллером, система с наблюдаемыми и ненаблюдаемыми состояниями ненадежного контроллера. Д.чя данных систем выводятся явные формулы стационарных вероятностей состояний и средних характеристик производительности и надежности, таких как функция средних

потерь д(к), коэффициент готовности системы а(к) (вероятность, что система работоспособна), вероятность отказа пр(к) н т.д. Решаются задача

оптимизации гшп<7(/с), таха(к) и тт7г^(/с). к к к Динамическое поведение систем с ненадежным контроллером описывается марковским процессом {^(£)}<>о = {О^), -Ог(£)}(>о, где Б\{1) -состояние контроллера, причем

-ft

. , _ I контроллер в рабочем состоянии, > 1 контроллер в состоянии отказа,

и £ состояние деградации. Диаграмма переходов

для системы с ненаблюдаемыми состояниями представлена на рисунке 5.4. Структура штрафов: ср - штраф за единицу времени восстановления в

il Ао Ак

(0,0)

Щ-1

Afc-i

¡J-k

(0,fc-lT (0, к)

1 Л-1,

т% х PV \ \

Ао Лк-2 ^ Лк-\ ^ Лк лт~ 1

(1,0)1 И, {l,k-l\vk-i(l,k]vk {l,m)\vn,

Рис. 5.4. Диаграмма ннтенснвностеП переходов для стратегии fk

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

Теорема 5.6 Стационарные вероятности состояний системы с ненаблюдаемыми состояниями контроллера удовлетворяют соотношениям

Vf qojfJ-F . г.—г ¡г

*<м> = J^VWk ^ = IZa^BS3 = hk' (5'23)

qij^F . п— вк

TT(I.J) = -Л ■ И ' J = -Л . Д ' где

к J> p,FAk + Bk цГАк + Вк

Poi = . — г = 1, k - 1, pot = g0j = IT Poi, j = 1, <?oo = 1, А,- + г/,- + 7; Wt

A¡-1 . ,-=- i

Pu = v-;—> ^ = i,n -1, pin = —, A¡ 4- v¡ un

7o 7j<7oj + Aj_i<7ij_i . —----Л- . __

lio = . , = \ _¿„ J = 0,fc - 1, <7ij = И pi¡<7ijt-i, J = fc,) Ao + ¡Л) A ¡ + ^Í -*■ t

fc n fr—1 n

Л*' = £ 9oí + J2 Пк = £ ^//»J + I] vj4ij- (5-24)

j=O j=0 J=0 j=o

Теорема 5.7 Функция средних потерь g(k) для системы с пенаблюдае-мыми состояниями контроллера,

ÍU\ ckQ0kfíF + CFBk --

9{k)= A¡,hf + Bk (5'26)

В шестой главе

исследуются управляемые деградирующие систе-

мы, в которых, в отличие от предыдущей главы, профилактический ремонт приводит к полному нлн частичному восстановлению. Системы снабжены контроллером, который принимает решение о начале профилактического ремонта в соответствии с пороговой стратегией /н-

Определение 6.1 Пороговая стратегия /н с порогами I = 0. к — 1 и к = 1 ,п, инициирует профилактический ремонт системы после перехода в состояние деградации к. В этом состоянии система восстанавливается полностью, если 1 = 0, пли частично, I > 0, и переходит в состояние деградации I.

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

функции надежности и риска, ФР СВ времени и числа профилактических ремонтов до отказа и т.д. Марковский процесс описывает состо-

яния деградации системы.

Диаграмма нитснсивностей переходов одной из систем изображена на рисунке 6.1. Структура штрафов: сР - штраф за единицу времени восста-

/хг 11Щ Ч

Ао А;_1 X А; А^_2 ^ А^-1

— «—. ... ~

/

к — 1 к

т

Рис. 6.1. Диаграмма интсисивностсй переходов для стратегии /и

новления в состоянии полного отказа и сы - штраф за единицу времени профилактического ремонта в состоянии к, приводящего в состояние /.

Теорема 6.17 Стационарные вероятности состояний системы удовлетворяют соотношениям

Мг !Ч7

А ,Ъ=Я1Л = (6.42)

Л ндг + ¿»и + £>ы

Вы (Ш Цу . у-г ТТр = -, 7Г; =----=г—, I = I, К,

Акщг + Вы <27 - ацк1{1>1] Лкц1Г + Вы

где

А,-

I -Т-, '¿=1,7/4-1, Лк-1 т ТТ , ,а ,„\

г-1 ^ Аг—1 Лг = V'/, Н---— V (¡п Вы = —--У) <ц.

и >и -а<1к

Задача оптимизации состоит в минимизации функции средних потерь д(к,1), т.е. в нахождении оптимальной пороговой стратегии /к[ = (к*,1*).

Теорема 6.18 Функция средних потерь д(к,1) вычисляется по формуле

д(к,1) = (6.44)

_ {сы + с2Цк1 ~ ср&а/хг + (сг + с3дг - с{)(д1 - <7(&1{;>1}).Ви | ^

- сг<йД{г>1}) И/иРг + Вы) Обозначим через Г СВ продолжительности жизни системы. Функцию надежности Щ.р^) = Р[Т > ¿|Х(0) = г] можно получить вычисляя ФР (¿) СВ остаточного времени жизни системы. Для марковской системы справедливо следующее утверждение.

Теорема 6.19 ПЛ функции надежности удовлетворяет соотно-

шению

ПЛС /¡^(з) вычисляются по формулам ЛИ«) = —--.—-4--7-г^-р-г-ГТ--, г = 0, т - 1,

(6.47)

ЛН«) = —--+-гЬ-П-ГТГ' г = т,к-1,

Ф-Цв) (в)(дг_!(в)-^(в))

ЛИ«) =--гт-, где

А;

Р;(5) = ——Г' г = 0,т - 1, р,-(в) = —, г = т,к- 1, (6.48)

в + Л,' в + Л; +

^ г

= о Л ' =1 I „' = П/^)' я^) =ь

5 + )Ш Я + Л; + V ^

Соответствующие средние значения вычисляются по формуле

В седьмой главе исследуются управляемые н неуправляемые деградирующие системы со случайным начальным ресурсом жизни II. Системы предполагаются одноразовыми н наблюдаются до момента попадания в состояние полного отказа. В случае управляемых систем контроллер принимает решение на осуществление профилактического ремонта. Различаются два типа систем: с дискретной р^ = Р[[/ = к],к = 1,2,... и непрерывной С (и) = Р[[/ < и] ФР случайного ресурса.

В системах первого типа случайный процесс расходования ресурсов обозначим через {Л"(£)}(>0. СВ времени жизни системы Т представляет собой время до первого достижения процессом {Х^)}(>0 значения С/,

т = ы{г-.х{г)>и}. (7.1)

Предположим, что процесс является процессом восстановления

с пространством состояний Е = No- Пусть процесс генерируется последовательностью НОР СВ Ак с ФР A(t) = P[/li: < t], соответствующей ПР a(t) = -¡¡¡A(t) и средним значением а = Е[Л*]. Контроллер принимает решения в соответствии с пороговой стратегией /„.

Определение 7.3 Пороговая стратегия /„, п 6 N, инициирует профилактический ремонт системы после достижения процессом {X}t>0 состояния п. После ремонта процесс переходит в начальное состояние 0.

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

Âk = с Ак, с < 1. Для ФР Ac(t) СВ Âk получим

Ac(t) = Р[сАк <t]= Р[Ак < с~Н] = А{сгЧ).

Отсюда следует, что ФР Fc(t) СВ остаточного времени жизни Т = сТ определяется соотношением

Fc(t) = Р[Т <t]= Р[Т < с~Н] = F{c~H).

Таким образом, задача оптимизации состоит в поиске оптимальной стратегии /* = п* для максимизации среднего остаточного времени жизни тахд Еf"[T}. Обозначим через Т(п) := Еf"[T].

Теорема 7.4 Среднее остаточное временя жизни Т{п) дм стратегии управления /„ вычисляется по форльуле

a(j2kZlkpk + n¥[U>n})

1 — cP[i/ > п] '

где P[U > п] = £к=пРк-

В системах второго типа процесс расходования ресурса {X(t)}t>o представляет собой функцию накопления,

т

X(i) = X>, (7.8)

к=О

где Вк,к е N - неотрицательные НОР СВ с ФР В(х), N(t) - процесс восстановления, сгенерированный НОР СВ Л,, г G N, с ФР A(t). Обозначим через a(s) н b(s) ПЛС ФР A(t) и B(t), через {Si-J^eN и O^/tHeN.

1=1 !=1

вместе с Sq = П о = 0, случайные блуждания, генерируемые случайными величинами Д- и В,, г = 1, к. Вводится обозначение ттк,

лк = P[IV0 < u, wi <[/,..., wk_! < u, wk >u],ke N, (7.10)

для распределения времени первого пересечения ресурса u процессом {Щ}кеп, и n(z),

X *=1

для соответствующей ПФ. Для вычисления значения щ вводится обозначение

7Гк{и) = P[Uq < и, Wi < и,..., Wk-i < и, Wk > и] (7.12)

условной вероятности (7.10) при условии {U = и}. Для процесса {И'д}*.гн справедливо

щ(и) = P[« е [Щ-1, wk)} = В^-'Ни) - В*к(и), (7.13)

и отсюда получим выражение для щ,

щ = Trk(u)dG(u) = £ - B**(u)]dG(u). (7.14)

Для непрерывного случая используется пороговая стратегия /,,.

Определение 7.12 Пороговая стратегия /( .г; > 0, инициирует профилактический ремонт системы после достижения процессом {X(t)}t>o значения большего чем порог V. После ремонта процесс переходит в начальное состояние 0.

Профилактический ремонт системы приводит к тому, что значения случайных величин Ак уменьшаются, а Вк - увелнчиваюся, т.е.

Ак = С1 Ак, Вк = с2Вк, к е К, (7.17)

где С1 < 1 и сг > 1. Таким образом, задача оптимизации состоит в поиске оптимальной стратегии /* = V* с целью максимизации среднего остаточного времени жизни тах/,. [Т]. Обозначим через Т(у) := Е^'[Т]. Рассмотрим условную вероятность 7Гк(и),к € М, определенную в (7.12). Применяя для этой функции ПФ, получим

х

7г(г;и)=^7г*(и)г*. (7.18)

Теорема 7.13 ПЛС /(й) времени жизни неуправляемой системы удовлетворяет соотношению

}{з) = Г тг(ф);и)С(с1и). (7.19)

Уо

Заметим, что вероятности 7Гк(и) могут быть вычислены по формуле (7.13).

Теорема 7.14 ПЛС ¡(в) времени жизни управляемой системы со стратегией /у удовлетворяет соотношению

/(«;»)= Г п{а(а);и)С{йи) + {1-в(у))тг(а(а);ь)т(сз-,у), (7.20) Jo

где с = С1 ¿Г1.

Следствие 7.15 Среднее время жизни Т(у) удовлетворяет соотношению

(7.21)

из

Относительно заданных стратегий решаются задачи оптимизации для среднего времени жизни, соответственно тахТ(п) и тахТ(г').

В заключении диссертации подведены итоги проведенных исследований и кратко изложены основные выводы.

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

1. Разработана методика описания широкого класса управляемых моделей СМО и ДС с помощью управляемых марковских процессов. Рассмотрены два типа систем: системы с известной н неизвестной структурой оптимальной стратегии управления. Для систем первого типа

п

Основные результаты диссертационной работы

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

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

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

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

5. Найдены условия существования стационарного режима для систем со счетным числом состояний и выведены формулы для стационарных вероятностей состояний системы с фиксированной пороговой

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

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

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

Публикации по теме работы

|1| Ефросинии Д.В. Вычисление оптимальных порог в управляемой системе АР/ РН/К с повторными заявками /Тезисы докладов ХХХУ1У Всероссийской парной конференции по проблемам физики, химии, математики, информатики и методики преподавания. — М: Издательство РУДН, 2003. ;

[2| Ефросинии Д.В. Вычисление характеристик производительности управляемого узла сети с неоднородными. Сборник докладов IV Международной конференции по проблемам управления (МКПУ-1У). - М: Издательство ИПУ РАН, 2009. - С. 1759;1766.

[3] Ефросинии Д.В. Анализ периода занятости в системе с пороговым управлением // Автоматика и Те^гемеханика. — 2010. — — С. 99-117.

(4| Ефросмиии Д.В. Стационарные характеристики многоканальной неоднородной системы с ЕСЕЗ орбитой и пороговым управлением /7 Вестник РУДН. Серия Математика, Информатика, Физика. — 2010. — №3. — С. 44-&4.

[5| Ефросинии Д.В. Распределение времени ожидания в системе с РСРЭ орбитой и пороговым управлением / .' Вестник РУДН. Серия Математика, Информатика, Физика. — 2011. - №1. - С. 34-46.

[6{ Ефросинии Д.В., Рыков В.В. Численное исследование оптимального управления системой с неоднородными приборами /7 Автоматика и Телемеханика. — 2003. — №2. — С. 143-151.

|7| Ефросинии Д.В., Фархадов М.П. Оптимальное управление системой с постепенными и внезапными отказами // Надежность. — 2009. — №1(29). — С. 27-41.

|8| Рыков В.В., Ефросинии Д.В. Оптимальная гистерезисная политика управление системой М/М/1/п с несколькими режимами работы и платой за переключение // Тезисы докладов XXXV Всероссийской научной конференции по проблемам физики, химии, математики, информатики и методики преподавания. — М: Издательство РУДН, 1999. — С. 37-38.

[9| Рыков В.В., Ефросинии Д.В. Сравнительный анализ систем массового обслуживания с различными типами управления /7 Тезисы докладов XXXVI Всероссийской научной конференции по проблемам физики, химии, математики, информатики и методики преподавания. - М: Издательство РУДН, 2000. - С. 24-25.

|10| Рыков В.В., Ефросинии Д.В. Исследование оптимального управления системой неоднородных приборов с наблюдаемой общей очередью // Тезисы докладов XXXVII Всероссийской научной конференции по проблемам физики, химии, математики, информатики и методики преподавания. — М: Издательство РУДН, 2001. — С. 35.

|11| Рыков В.В., Ефросинии Д.В. Задача минимизации средних потерь в многоканальной системе с неоднородными приборами /7 Информационные процессы. — 2002. — №2(2). —

С. 252-256.

[12] Рыков В.В., Ефросинии Д.В. К анализу характеристик производительности СМО с неоднородными приборами /7 Автоматика и Телемеханика. — 2008. — №1. — С. 64-82.

|13| Рыков В.В., Ефросинии Д.В. К проблеме медленного прибора // Автоматика и Телемеханика. - 2008. - №12. - С. 81-91.

[14| Штрик Я., Ефросииин Д.В. Анализ надежности систем массового обслуживания с повторными заявками и конечным числом требований при помощи инструментальных программных систем // Автоматика и Телемеханика. — 2010. — №7. — С. 119-125.

|15| Фархадов М.П., Петухова Н.В.. Ефросииин Д.В., Семенова О.В. Двухфазная модель с неограниченными очередями // Проблелт управления. — 2010. — №0. — С. 53-58.

|16| Фархадов М.П., Петухова Н.В., Eifipocunuu Д.В., Се.ш:нова О.В. Моделирование гибридного центра связи с сервисами самообслуживания и пороговым управлением размещением заявок /7 Управление большими системами. Специальный выпуск 30.1 "Сетевые модели в управлении". — М: ИПУ РАН, 2010. — С. 352-370.

|17| Efrosinin D. Threshold behavior of optimal policies in controlled queueing systems /; Abstracts of the conference "Distributed Computer Communication Networks" (DCCN03), Moscow. — 2002.

[18] Efrosinin D. Controlled queueing systems with heterogeneous servers. Dynamic optimization and inonotonicity properties. Saarbriicken: VDM Verlag, 2008. — 240 P.

[19] Efrosinin D. Queueing model of a hybrid channel with faster link subject to partial and complete failures // Annals of Operations Research. — 2011. — Pp. 1-28. doi:10.1007 sl0479-011-0939-7.

[20] Efrosinin D. On the optimal allocation problem for a data transmission channel with two types of links subject to failures// Proceeding of the 10th German Probability and Statistics Days, Mainz, Germany. — 2012.

|21| Efrosinin D., Breuer L. Threshold policies for controlled retrial queues with heterogeneous servers /'/ Annals of Operations Research. — 2006. — Vol. 141. - Pp. 139-162.

[22] Efrosinin D., Rykov V. On performance characteristics for queueing systems with heterogeneous servers // Abstracts of the Second Madrid Conference on Queueing Theory (MCQT0G). - Madrid: University of Madrid, 2006. - P. 50.

|23| Efrosinin D.. Rykov V. Structural properties of the optimal policy for the multi-server controlled retrial queueing systems /7 Abstracts of the 7th International Workshop on Retrial Queues / Ed. by Economou A., Artalojo J. — Athens: University of Athens, 2008. — P. 15.

[24| Efrosinin D., Rykov V. The busy period analysis of a queue with heterogeneous servers and threshold-based service policy // Proceedings of the International Conference "Mathematical Methods for Analysis and Optimization of Information Telecommunication Networks" / Ed. by Dudin A., Klimcnok V. - Minsk: Rivsh, 2009. - Pp. 61-GG.

|25] Efrosinin D.. Rykov V. Queueing model of the FSO./RF hybrid channel with heterogeneous links subject to failures ,'/ Abstracts of the Second Madrid Conference on Queueing Theory (MCQT10), Toledo, Spain. - Madrid: University of Madrid, 2010. - P. 34.

|26| Efrosinin D., Rykov V. Queueing model of the non-reliable hybrid data transmission channel with heterogeneous links // Proceedings of the International Conference "Mathematical Methods in Reliability" (MMR11), Beijing, China / Ed. by Lirong C., Xian Z. — Beijing: Institute of Technology Press, 2011. — Pp. 272-279.

|27| Efrosinin D., Semenova. O. Optimal control of M/AI/l queueing system with constant retrial rate // Proceeding of the International Conference on Ultra Modern Telecommunications (ICUMT09),St. Pctcrburg. - IEEEXplore. 2009- Pp. 1-6. doi: 10.1109/ICUMT.2009.5345415.

¡28] EJrosinin D., Semenova O. Queueing model with non-reliable server and threshold-based recovery . / Proceedings of the International Conference "Mathematical Methods in Reliability" (MMR09), Moscow / Ed. by Rykov V., Nikulin M. - Moscow: PFUR. 2009. -Pp. 546-550.

|29| Efrosinin D., Semenova O. An il/M/l system with an unreliable device and a threshold recovery policy / Journal of Communications Technology and Electronics. — 2010. — Vol. 55(12). - Pp. 1526-1531.

|30] Efrosinin D.. Seme-nova O. Matrix-analytical approach to analysis of a single-server retrial queue with non-reliable removable server / / Proceeding of the International Conference on Ultra Modern Telecommunications (ICUMT09), St. Peterburg. - IEEEXplore, 2010. - Pp. 1145-1149. doi: 10.1109,TCUMT.2010.5676526.

[31] Efrosinin D.. Sztrik J. Controllable damage model with gradual failures// Proceedings of the International Conference "Mathematical Methods in Reliability" (MMR09), Moscow / Ed. by Rykov V., Nikulin M. - Moscow: PFUR, 2009. - Pp. 130-133.

|32| Efrosinin D., Sztrik J. Tool supported reliability analysis of finite-source retrial queues// Proceedings of the International Conference "Mathematical Methods in Reliability" (MMR09), Moscow Ed. by Rykov V., Nikulin M. - Moscow. PFUR, 2009. - P. 551.

|33] Efrosinin D., Sztrik J. Performance analysis of a two-server heterogeneous retrial queue with threshold policy // Quality Technology and Quantitative Management. — 2011. — Vol. 8(3).

- Pp. 211-236.

]34] Efrosinin D., Sztrik J. Stochastic analysis of controlled retrial queues with heterogeneous servers and constant retrial rate // Information processes. — 2011. — Vol. 11(1). — Pp. 114139.

[35] Efrosinin D., Winkler .4. Telefonat mit dein Computer // Univationen. — 2010. — Vol. 3(10).

- P. 29.

[36] Efrosinin D., Winkler A. Queueing system with a constant retrial rate, non-reliable server and threshold-based recovery ,'/ European Journal of Operational Research. — 2011. — Vol. 210(3). - Pp. 594-605.

|37] Efrosinin D., Winkler .4., Pinzger M. Confidence intervals for performance measures of queueing systems with a constant retrial rate and a non-reliable server // Proceedings of the 9th International Workshop on Retrial Queues, Seville, Spain. — 2012.

[38] Farhadov M., Petukhova N.. Efrosinin D.. Semenova O. Mathematical model of a call-center with self-service facility /,' Proceedings of the International Workshop "Distributed Computer Communication Networks" (DCCN'09), Sofia, Bulgaria. — Moscow: R&D Company "Information and Networking Technologoes 2009. — Pp. 86-95.

[39] Farhadov M.. Pctuklwva N.. Efrosinin D., Semenova O. A model to control a queue in a voice selfe-service portal with fast and slow servers // Proceedings of the Third International Conference on Problems of Cybernetics and Informatics, Baku, Azerbaijan. — Baku: Elm, 2010. - Pp.239-243.

[40[ Primetzhofer D., Markin S., Efrosinin D., Steinbauer E., Andrzejewski It.. Bauer P. Influence of screening length modification on the scattering cross section in LEIS // Nuclear Instruments and Methods in Physics Research B. - 2011. — Vol. 269(11). - Pp. 1292-1295.

[41] Rykov V., Efrosinin D. Numerical analysis of optimal control policies for MAP/PH/K queiieing systems with heterogeneous servers // Proceedings of the memorial seminar dedicated to the GOth birthday of Kalashnikov V. "Applied Stochastic Models and Information Processes";' Ed. by Korolcv V.. Morozov E., Norbcrg R..Schmidt H. Petrozavodsk: Karelian Research Center RAS. 2002. - Pp. 136-140.

[42] Rxjkov V.. Efrosinin D. Numerical analysis of optimal control policies for queueing systems with heterogeneous servers // Abstracts of the First Madrid Conference on Queueing Theory (MCQT02), Madrid, Spain. - Madrid: University of Madrid, 2002.

[43] Rykov V., Efrosinin D. Optimal control of queueing systems with heterogeneous servers / Queueing Systems. - 2004. - Vol. 46. - Pp. 389 407.

[44[ Rykov V., Efwsinin D. On reliability control of fault tolerance units / / Abstracts of the Fourth International Conference on Mathematical Methods in Reliability (MMR04). Los Alamos: Los Alamos National Laboratory, 2004.

[4-5] Rykov V., Efrosinin D. Reliability control of biological systems with failures /, Proceedings of the conference "Longevity, Aging and Degradation Models". Ed. by Antonov V., Hubcr C.. Nikulin M., Polischook V. St.Petcrburg: St.Peterburg State Politeclmical University, 2004. — Vol. 2. - Pp. 241-255.

[46] Rykov V., Efrosinin D. On stability of parameters estimation of MAP . / Proceeding of the XXV International Seminar on Stability Problems for Stochastik Models/Ed. by Bocharov P.. D'Apice C., Korolev V.,Pechinkin A. Salerno: University of Salerno, Fisciano (SA), 2004. - Pp. 242-249.

[47[ Rykov V., Efwsinin D. The waiting time distribution for controlled queueing systems with heterogeneous servers // Abstracs of the XXVI International Seminar on Stability Problems for Stochastik Models. — Sovata-Bai, Romania, 2006.

[48[ Rykov V., Efrosinin D. Risk analysis of controllable degradation model with preventive repair // Abstracs of the international conference "Mathematical Methods in Reliability" (MMR07) / Ed. by Bedford T., Walls L.; Ouiglcy J., Alkali B., Dancshkhah A., Hardman G. - Glasgow: Ubniversity of Strathclyde, 2007. — P. 136.

[49] Rykov V., Efrosinin D. Degradation models with random life resources /7 Abstracs of the XII International Conference on Applied Stochastic Models and Data Analysis (ASMADA) / Ed. by Skiadas II. - Chania: IBM, IASC, MAICh, 2007. - P. 162.

[50] Rxjkov V.. Efrosinin D. Degradation models with random life resources /, Communications in Statistics - Theory and Methods. — 2010. — Vol. 39. — Pp. 398-407.

[51] Rykov V., Efrosinin D. On optimal control of systems with random life resources// Proceedings of the International Conference "Mathematical Methods in Reliability" (MMR11), Beijing, China / Ed. by Lirong C., Xian Z. — Beijing: Institute of Technology Press, 2011. - Pp. 414-420.

[52] Rykov V., Efrosinin D. On a slow server problem: solution and applications , Abstracs of the XXIX International Seminar on Stability Problems for Stochastik Models. Svetlogorsk, Russia/ Ed. by Korolev V., Shorgin S. — Moscow: Institute of Informatic Problems. 2011. — Pp. 45-46.

[53] Rykov V., Efrosinin D. On optimal control of systems on their life time /7 Recent advances in system reliability / Ed. by Lisnianski A., Frcnkcl I. — Berlin: Springer-Verlag, 2012. — Springer Series in Reliability Engineering. — Pp. 307-319.

[54] Hykov V.. Efrosinin D.. Breuer L. Optimization algorithm application for queue system MAP/PH/K with heterogeneous servers // Abstracts of the XXXVIII All-Russian Scientific Conference. - Moscow: PFUR, 2002. - P. 41.

Вклад автора в работы, опубликованные в соавторстве.

В работах [6, 8-11, 41-43] автором нолучены результаты и наннса-иы разделы, относящиеся к численному анализу оптимальных стратегии управления. В [12] автором нолучены формулы вычисления характеристик производительности в явном виде для управляемых неоднородных СМО, в [13, 52] автору принадлежат промежуточные результаты, использованные в доказательствах свойств монотонности функции оценок динамического программирования, в [14, 32] - выведение формул для характеристик производительности, в [15, 16, 38, 39] - разработка математических моделей, формулировка задач оптимизации и получение аналитических результатов для анализа производительности соответствующих систем, [21-31, 3337, 54] - постановки задач, формулировки и доказательства основных результатов, в [40] - оптимальная оценка функциональных зависимостей параметров в задаче анализа свойств поверхности материалов, в [44, 45, 51] -разделы, посвященные исследованию частных случаев управляемых ДС и их численному анализу, в [46] - вывод доверительных интервалов для оценок параметров входящего потока и численные результаты их построения, в [47] - формулировка и решение задачи вычисления распределения времени ожидания н пребывания, [48-50] - разработка математических моделей и применение процессов восстановления для решения задачи оптимального управления ДС. В [53] автору принадлежат разделы, посвященные вычислению функций распределений времени до отказа н числа профилактических восстановлений управляемых ДС, а также численному анализу этих систем.

российский университет дружбы народов

На правах рукописи УДК 519.217:519.218:519.857

05201351879

Ефросинин Дмитрий Владимирович

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

Специальность: 05.13.01 — Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

Диссертация на соискание ученой степени доктора физико-математических наук

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

Москва 2013

Содержание

Введение 7

Глава 1. Управляемые динамические системы 27

1.1 Типы систем массового обслуживания (СМО) и деградирующих систем (ДС)................................................27

1.2 Примеры применения управляемых СМО и ДС ..............29

1.3 Управляемый марковский процесс..............................38

1.4 Задача оптимизации и критерий средних потерь..............40

1.5 Анализ производительности и надежности систем............48

1.6 Используемые обозначения и сокращения......................52

Глава 2. Одноканальные ненадежные СМО 55

2.1 Введение и обзор литературы....................................55

2.2 Системы с отключаемым прибором и повторными заявками 59

2.2.1 Математическая модель..................................60

2.2.2 Условие эргодичности и стационарные вероятности . 63

2.2.3 Матрично-аналитический метод для сенсорных процессов ......................................................66

2.2.4 Средние характеристики производительности и задача оптимизации............................................68

2.3 Системы с отключаемым ремонтным оборудованием..........69

2.3.1 Математическая модель..................................70

2.3.2 Условие эргодичности и стационарные вероятности . 73

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

2.3.4 Средние характеристики производительности..........79

2.3.5 Задача оптимизации......................................81

2.3.6 Распределение времени ожидания и пребывания ... 82

2.3.7 Статистическая оценка характеристик системы .... 87

2.4 Доказательство полученных результатов ......................90

Глава 3. Многоканальные неоднородные СМО 107

3.1 Введение и обзор литературы....................................107

3.2 Типы систем с неоднородными приборами ....................108

3.3 Типы стратегий управления размещением заявок ............110

3.4 Система с обычной очередью....................................111

3.4.1 Математическая модель..................................112

3.4.2 Задача оптимизации, структурные свойства стратегии управления и оценка эффективности....................114

3.4.3 Стационарные вероятности. Применение метода разностных уравнений и матрично-аналитического метода 122

3.4.4 Средние характеристики производительности..........127

3.4.5 Эвристическое решение для оптимальных порогов . . 128

3.4.6 Распределение времени ожидания и пребывания . . . 135

3.4.7 Распределение длительности периода занятости . . . 137

3.4.8 Распределение числа обслуженных заявок ............141

3.4.9 Обращение характеристических преобразований . . . 146

3.4.10 Метод максимальной энтропии для вычисления функций распределения........................................148

3.5 Система с повторными заявками................................149

3.5.1 Математическая модель..................................149

3.5.2 Задача оптимизации и структурные свойства стратегии управления............................................151

3.5.3 Стационарные вероятности. Применение матрично-аналитического метода....................................153

3.5.4 Метод спектрального разложения матриц в матрично-аналитическом решении..................................157

3.5.5 Средние характеристики производительности..........159

3.5.6 Эвристическое решение для оптимальных порогов . . 160

3.5.7 Распределение времени ожидания......................162

3.5.8 Распределение времени пребывания....................172

3.5.9 Распределение числа повторных попыток..............177

3.6 Доказательство полученных результатов ......................182

Глава 4. Многоканальные ненадежные неоднородные СМО 199

4.1 Введение и обзор литературы....................................199

4.2 Система с отказами всех приборов...............201

4.2.1 Математическая модель.................202

4.2.2 Задача оптимизации и структурные свойства стратегии управления......................204

4.2.3 Стационарные вероятности. Применение матрично-аналитического метода..................207

4.2.4 Средние характеристики производительности и надежности ..................................................210

4.2.5 Эвристическое решение для оптимальных порогов . . 211

4.3 Система с частичными и полными отказами одного прибора 212

4.3.1 Математическая модель.................212

4.3.2 Задача оптимизации и структурные свойства стратегии управления............................................216

4.3.3 Стационарные вероятности. Применение матрично-аналитического метода..................221

4.3.4 Средние характеристики производительности и надежности .........................224

4.3.5 Эвристическое решение для оптимальных порогов . . 225

4.3.6 Распределение времени ожидания ...........226

4.3.7 Распределение времени пребывания..........230

4.3.8 Совместное распределение периода занятости и числа обслуженных заявок...................231

4.4 Система с отказами и двумя обслуживающими узлами . . . 233

4.4.1 Математическая модель.................233

4.4.2 Стационарные вероятности. Мультипликативное представление ......................23-5

4.4.3 Средние характеристики производительности и надежности .........................238

4.4.4 Задача оптимизации...................240

4.5 Доказательство полученных результатов ...........240

Глава 5. ДС с полным восстановлением 249

5.1 Введение и обзор литературы..................249

5.2 Неуправляемая система.....................251

5.2.1 Математическая модель.................251

5.2.2 Стационарные вероятности и функция средних потерь 252

5.3 Система с управляемым восстановлением...........253

5.3.1 Математическая модель.................253

5.3.2 Средние характеристики надежности и задача оптимизации ..........................255

5.4 Система с управляемым восстановлением и ненадежным контролером .............................256

5.4.1 Математическая модель системы с наблюдаемыми состояниями контроллера.................257

5.4.2 Математическая модель системы с ненаблюдаемыми состояниями контроллера................259

5.4.3 Средние характеристики надежности и задача оптимизации ..........................260

5.5 Сравнительный анализ деградирующих систем........262

5.6 Доказательство полученных результатов ...........264

Глава 6. ДС с частичным восстановлением 267

6.1 Введение и обзор литературы..................267

6.2 Система с управляемым восстановлением...........268

6.2.1 Математическая модель.................268

6.2.2 Средние характеристики надежности и задача оптимизации ....................................................270

6.2.3 Временные характеристики и функция надежности . 272

6.3 Система с управляемым восстановлением и случайным временем до текущего ремонта...................274

6.3.1 Математическая модель.................275

6.3.2 Средние характеристики надежности и задача оптимизации ....................................................277

6.3.3 Временные характеристики и функция надежности . 278

6.4 Система с управляемым восстановлением и случайным временем до внезапного отказа...................279

6.4.1 Математическая модель.................279

6.4.2 Задача оптимизации...................281

6.4.3 Вычисление функции потерь с помощью регенириру-ющего процесса......................282

6.4.4 Среднее время до отказа.................284

6.4.5 Асимптотическая функция надежности........287

6.4.6 Вычисление функции потерь с помощью стационарных вероятностей.....................287

6.4.7 Временные характеристики и функция надежности . 290

6.5 Система с управляемым восстановлением и поглощающим состоянием после отказа.....................292

6.5.1 Математическая модель.................292

6.5.2 Средние характеристики надежности и задача оптимизации ..........................294

6.5.3 Временные характеристики и функция надежности . 296

6.5.4 Число управляемых восстановлений..........297

6.6 Доказательство полученных результатов ...........298

Глава 7. ДС со случайным ресурсом жизни 305

7.1 Введение и обзор литературы..................305

7.2 Система с дискретным распределением ресурса .......306

7.2.1 Математическая модель.................306

7.2.2 Условная функция риска................307

7.2.3 Задача оптимизации...................309

7.3 Система с непрерывным распределением ресурса.......311

7.3.1 Математическая модель.................312

7.3.2 Условная функция риска ................314

7.3.3 Задача оптимизации...................316

7.4 Доказательство полученных результатов ...........318

Заключение 321

Литература 323

Приложение 1 339

Приложение 2 345

Приложение 3 365

Приложение 4 369

Приложение 5 373

Приложение 6 381

Введение

Объект исследования и актуальность темы.

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

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

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

Для многих математических систем, описывающих вероятностную природу реальных систем, с помощью теории массового обслуживания (см., например, Бочаров и Печинкин [1], Гнеденко и Коваленко [3], Кофман и Крюон [15], Гросс и Харисс [107], Кижима [114], Кляйнрок [116], Нельсон [148]) и теории надежности (см. Гнеденко [2], Герцбах [100], Половко и Гуров [16]) было получено большое число аналитических и численных результатов, характеризующих эксплуатационные и надежностные качества СМО и ДС. К этим результатам можно отнести формулы для функций распределения длины очереди и времени ожидания, вероятность потерь, среднее время пребывания в системе, а также вероятность отказа, среднее

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

В качестве теоретического аппарата для исследования многих типов управляемых СМО и ДС применяется теория управляемых марковских процессов (см. Рыков [17|. Гуо и Хернандес-Лерма [110], Китаев и Рыков [115], Лерма и Лассере [135], Майне и Осаки [143], Путерман [155], Росс [160], Сенотт [181]), так как поведение этих систем описывается некоторым случайным процессов (в диссертации мы ограничимся в основном марковскими процессами), а выбор управления приводит к изменению его траекторий. Нахождение оптимального управления даже для простейших марковских систем требует объемной вычислительной работы. Поэтому возникает желание уменьшить вычислительную составляющую исследований за счет анализа структурных свойств (пороговой структуры), которые, в свою очередь, позволяют получить аналитические результаты для оптимальных порогов и соответствующих характеристик производительности и надежности.

Несмотря на то что существует большое число научных трудов, посвященных различным типам управляемых динамических систем и анали-

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

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

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

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

• Формализация управляемого марковского процесса и определение его компонентов для исследуемых систем;

• Формулировка задачи оптимизации для заданного критерия и разработка алгоритма вычисления оптимальной стратегии управления и оценки ее эффективности;

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

• Получение условий существования стационарного режима для соответствующих систем;

• Выведение формул для стационарных вероятностей состояний при фиксиров