КОМБИНИРОВАННЫЙ МЕТОД ПЛАНИРОВАНИЯ ОПЕРАЦИЙ И РАСПРЕДЕЛЕНИЯ РЕСУРСОВ СИСТЕМЫ УПРАВЛЕНИЯ АКТИВНЫМИ ПОДВИЖНЫМИ ОБЪЕКТАМИ
17
УДК 519.8
С. В. КОКОРИН, С. А. ПОТРЯСАЕВ, Б. В. СОКОЛОВ
КОМБИНИРОВАННЫЙ МЕТОД ПЛАНИРОВАНИЯ ОПЕРАЦИЙ И РАСПРЕДЕЛЕНИЯ РЕСУРСОВ СИСТЕМЫ УПРАВЛЕНИЯ АКТИВНЫМИ ПОДВИЖНЫМИ ОБЪЕКТАМИ
Предложены обобщенная динамическая модель и комбинированный метод планирования операций и распределения ресурсов системы управления активными подвижными объектами, позволяющие учесть основные ограничения системы управления на основе реализации концепции комплексного моделирования. Ключевые слова: комплексное планирование, система управления активными подвижными объектами, комбинированные методы моделирования и оптимизации.
Введение. Анализ основных направлений развития современных сложных организационно-технических систем (СОТС) позволил выделить ряд их особенностей, к числу которых относятся: многоаспектность и неопределенность поведения; иерархичность; подобие структур и избыточность основных элементов и подсистем и их взаимосвязей; разнообразие функций управления на каждом уровне системы; территориальная распределенность компонентов системы. Предварительные исследования показывают, что в качестве базового элемента при формальном описании процесса управления СОТС может использоваться активный подвижный объект (АПО) [1]. В общем случае это искусственный объект (аппаратно-программный комплекс), перемещающийся в пространстве и взаимодействующий с другими АПО и внешними объектами обслуживания, в ходе которого формируются информационные, энергетические и материальные потоки [2, 3]. На практике, как правило, из-за достаточно низкого уровня автономности АПО создаются распределенные системы управления АПО (СУ АПО). В этом случае на концептуальном уровне процесс функционирования СУ АПО может быть представлен как процесс выполнения соответствующих целевых и технологических (обеспечивающих) операций и распределения ресурсов в рассматриваемой системе управления.
На содержательном уровне задача комплексного планирования функционирования СУ АПО может быть сформулирована следующим образом: необходимо выбрать такой допустимый план выполнения операций и распределения ресурсов системы, в ходе реализации которого, в рамках заданных сценариев воздействия возмущающих факторов, будут выполнены своевременно и полностью все операции, составляющие соответствующие технологические циклы управления, а уровень сервиса (качества) планирования будет удовлетворять заданным требованиям. При этом если будет получено несколько планов, то необходимо выбрать наилучший план относительно принятых критериев и показателей оптимальности.
Формальная постановка задачи. На основе ранее разработанных частных динамических моделей планирования СУ АПО [1—3] запишем обобщенную динамическую модель процессов функционирования указанной системы в условиях возмущающих воздействий:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
18 С. В. Кокорин, С. А. Потрясаев, Б. В. Соколов
JG
(
x
(t
)
,
u
(t
)
,
β,
ξ
(t
)
,
t
)
→
extr ;
u (t )∈∆
(1)
∆
=
⎪⎪⎨⎧uy
(t (t
) )
| x (t ) = φ (t0 , x (t0 ), x (t ),u = η(x(t),u(t),β,ξ (t),t );
(t
)
,
β, ξ
(t
)
,
t
);
( )⎪⎪⎩x(t0 ) ∈ X0 (β), x t f ∈ X f (β),
(2)
где x (t ) — обобщенный вектор состояния СУ АПО; y (t ) — обобщенный вектор выходных
характеристик (показатели качества функционирования СУ АПО); u (t ) — вектор программ-
ного управления, представляющий план функционирования СУ АПО; β — обобщенный век-
тор параметров СУ АПО, характеризующих основные технические и технологические возможности аппаратно-программных средств, входящих в ее состав; φ , η — соответственно
многомерные переходная и выходная функции, задаваемые в общем случае в аналитико-
алгоритмическом (имитационном) виде; X0 (β) , X f (β) — значение вектора x (t ) в началь-
ный и конечный моменты времени; t ∈ ⎣⎡t0 ,t f ⎤⎦ — заданный интервал планирования работы
СУ АПО; ξ (t ) — вектор возмущающих воздействий, имеющих как объективный, так и субъ-
ективный характер и задаваемых извне в виде соответствующих сценариев ξ (t ) ∈ Ξ .
Для определенности в дальнейшем будем предполагать, что указанные возмущающие
воздействия задаются в виде импульсных стохастических случайных процессов [4].
В состав рассматриваемой динамической модели планирования включим вектор показа-
телей качества планирования
T
J (x (t ) ,u (t ),β,ξ (t ),t ) = J(o)T , J(k)T , J( p)T ,
(3)
где J(o)T , J(k )T , J( p)T — соответствующие векторы показателей качества планирования опе-
раций, распределения ресурсов и потоков при различных сценариях реализации возмущаю-
щих воздействий.
Примеры конкретного описания данных показателей качества для детерминированного
и стохастического вариантов задания исходных данных приведены в работах [1, 2].
Комбинированный метод решения задачи. Предположим, что в задаче векторной оп-
тимизации при решении исходной задачи планирования (см. формулы (1), (2)) будет исполь-
зоваться простейшая линейная свертка вида
hh
∑ ∑J G = Cα Jα , Cα ≥ 0,
Cα = 1.
(4)
α=1 α=1
Более сложные варианты построения указанных сверток для рассматриваемого класса
задач планирования подробно изложены в работах [1, 5].
Динамическая задача комплексного планирования операций и распределения ресурсов
СУ АПО в условиях стохастических возмущающих воздействий (см. формулы (1)—(3)) мо-
жет рассматриваться как многоэтапная задача стохастического программирования. В данной
статье предполагается, что распределение ресурсов СУ АПО в условиях возмущающих воз-
действий можно конструктивно описать с использованием дискретно-событийных стохасти-
ческих моделей, исследуемых в современной теории сетей массового обслуживания [6]. При
этом в соответствии со структурными особенностями СУ АПО задачу стохастического про-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
Комбинированный метод планирования операций и распределения ресурсов СУ АПО
19
граммирования можно декомпозировать на две взаимосвязанные задачи оптимизации процесса функционирования рассматриваемой системы [5, 7]:
— подзадачу оптимизации функционала (1) на основе варьирования вектора ζ приори-
тетов операций обслуживания АПО при фиксированном векторе p параметров, характери-
зующих технические и технологические возможности системы (подвекторе β: см. формулы (1)—(2));
— подзадачу оптимизации функционала (1) на основе варьирования вектора p при фик-
сированном векторе ζ .
Для реализации данного подхода предлагается следующая двухэтапная итерационная процедура.
Этап 1. Оптимизация процесса выполнения операций и распределения ресурсов в СУ АПО с использованием ее аналитико-имитационной (стохастической) модели:
( ( ))f q0 ζ(ν) ,pν
→ min ,
pν∈Ω
(5)
где q0 (⋅) — аналитико-имитационное описание взаимосвязи оптимизируемых параметров
модели планирования; Ω — множество допустимых значений параметров, характеризующих
СУ АПО; ν — номер итерации.
Этап 2. Динамическое планирование операций и распределение ресурсов с фиксирован-
ным вектором параметров pν , полученным на предыдущем этапе:
( ( ))f q0 ζ(ν+1) ,pν
→ min ,
ζ(ν+1)∈Ζ
(6)
где Z — множество допустимых значений приоритетов.
Для реализации рассматриваемой процедуры на нулевой итерации ( ν = 0 ) необходимо
( )задать вектор начальных значений приоритетов ζ(ν) = ζ(0) операций, выполняемых в СУ
АПО. Его можно сформировать, например, алгоритмически (неявно), используя такие эвристические правила диспетчеризации, как FIFO, LIFO. Итерационный процесс поиска опти-
мального плана заканчивается в одном из следующих случаев: при достижении заданного уровня разности значений функционалов на двух последовательных итерациях:
( ( )) ( ( ))f q0 ζ(ν+1) ,p ν+1 − f q0 ζ(ν) ,pν < e ,
(7)
где e — известная величина; либо, если стабильная сходимость не наблюдается, используется эвристическое правило выхода из итерационной процедуры. При этом проверку условия (7) можно проводить, только начиная с первой итерации, так как вектор p0 в начале итерационной процедуры не определен.
Комбинированный метод оптимизации параметров СУ АПО. Рассмотрим более подробно содержание первого этапа предложенной итерационной процедуры. Для оптимизации вектора параметров p целесообразно использовать комбинацию метода глобального по-
иска (метод Ψ-преобразования [8]) и метода численной оптимизации без расчета производных (метод главных осей Брента [9]). Метод Ψ-преобразования — метод поиска глобального экстремума целевой функции (5) — не требует задания начального приближения при решении исходной задачи оптимизации, но характеризуется существенными вычислительными затратами при увеличении размерности вектора оптимизируемых параметров pν . Использо-
вание только метода Ψ-преобразования при оптимизации функционала (5) приводит к
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
20 С. В. Кокорин, С. А. Потрясаев, Б. В. Соколов
большим погрешностям. Поэтому предлагается его дополнить методом локальной оптимизации функционала (5). Применительно к рассматриваемой задаче планирования работоспособность данного метода была продемонстрирована при оптимизации систем с сетевой структурой [6].
Главный недостаток метода локальной оптимизации, точнее, его алгоритмической реализации, заключается в необходимости задания начального приближения, которое должно быть рассчитано для каждой задачи отдельно. Однако первое приближение уже известно
(в результате оптимизации функционала (5) с использованием метода Ψ-преобразования). Метод характеризуется двумя основными параметрами: показателем точности расчета целевой функции, который определяет момент остановки итерационного цикла, и шагом изменения оптимизируемых параметров, определяющим скорость сходимости алгоритма. Теоретическая сходимость данного метода для случая дважды непрерывно дифференцируемых функций была доказана в работе [9]. Применительно к исследуемой задаче планирования вычислительные эксперименты показали хорошую сходимость для более широкого класса оптимизируемых целевых функций, которые не являются в общем случае дифференцируемыми ((2), (3)).
Метод динамического планирования операций и распределения ресурсов СУ АПО. Данный метод предлагается использовать для формирования собственно плана выполнения операций и распределения ресурсов в СУ АПО. В работах [2, 3, 5] показано, что каждому такому плану может быть поставлен в соответствие комбинированный вектор сопряженной системы уравнений, который в данной задаче может интерпретироваться уже как вектор ди-
намических приоритетов ζ0 . Более того, в указанных работах также данный вектор рассмат-
ривается как вектор координирующих воздействий при реализации процедуры интерактивного планирования СУ АПО, оценивании устойчивости планов, а также при выработке корректирующих воздействий, позволяющих адаптировать как детерминированную динамическую модель планирования, так и аналитико-имитационную модель процесса реализации составленных планов с учетом возможных возмущающих воздействий.
Кратко остановимся на общей итеративной схеме формирования вектора динамических приоритетов, основанной на методе локальных сечений и представляющей собой одну из модификаций принципа максимума Понтрягина для случая задания смешанных ограничений [2, 5]. Рассмотрим алгоритм, реализующий данную схему.
(Шаг 1. Задание диспетчерского решения (допустимого плана) uд (t ), t ∈ t0 , t f ⎦⎤ ; в част-
ном случае в качестве допустимого может быть выбран „нулевой“ план — uд (t ) ≡ 0 .
Шаг 2. Интегрирование системы уравнений (2), описывающей процесс функционирования СУ АПО, с заданными начальными условиями, характеризующими ее текущее состояние,
и u = uд (t ) . В работах [2, 5] был описан один из вариантов преставления системы уравнений
(2) в виде детерминированной нестационарной конечномерной дифференциальной динами-
ческой системы x = f (x,u,t ) . В результате интегрирования получаем вектор-функцию xд (t ) .
Также в конечный момент времени рассчитываются значение обобщенного показателя качества планирования JG и значение вектора сопряженной системы уравнений с использованием условия трансверсальности.
Шаг 3. Интегрирование в обратном времени от t = t f до t = t0 при u = uд (t ) сопря-
женной системы уравнений вида
ψl
=
−
∂H ∂xl
+
I1
∑
δ=1
λ
δ
(
t
)
∂gδ(1)
(
x(t)
∂xl
,
u
(
t
)
)
I3
+ ∑ργ γ=1
(
t
)
∂g γ( 2 )
(
x(t
∂xl
)
,
u
(t
))
,
l
= 1,…, n ,
(8)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
Комбинированный метод планирования операций и распределения ресурсов СУ АПО
21
где H = ψT (t )f (x,u,t ) — гамильтониан, λδ (t ) и ργ (t ) — динамические множители Ла-
гранжа;
grad
H
(
x
(
t
)
,
u
(
t
)
,
ψ
(
t
))
=
I1
∑
λδ
(
t
)
grad
gδ(1)
(
x
(t
)
,
u
(t
)
)
+
I2
∑
ρ
γ
(
t
)
grad
g
(2)
γ
(
x
(
t
)
,
u
(
t
)
)
,
(9)
u
δ=1 u
γ=1 u
где ψ (t ) — вектор сопряженной системы уравнений; I1 — множество индексов для ограни-
чений типа равенства gδ(1) (x (t ),u (t )) = 0, δ ∈ I1 ; I2 — множество индексов для ограничений типа неравенства gγ(2) (x (t ),u (t )) ≤ 0, δ ∈ I2 ; I3 — множество активных индексов, для кото-
рых
ограничения
типа
g
(2)
γ
(
x
(t
)
,
u
(
t
))
≤
0
превращаются
в равенства.
В момент времени t = t0 (момент окончания интегрирования системы (8)) формируется
первое приближение значений сопряженной системы уравнений ψi (t0 ) . На этом завершается
итерация r = 0 . Далее — повторение шагов 2 и 3 до тех пор, пока не будут выполнены условия
J G( r +1)
−
J
(r
G
)
≤ε,
где
ε
—
заданная
точность
численного
решения
рассматриваемой
двухто-
чечной краевой задачи. В результате решения рассматриваемой задачи планирования работы СУ АПО, интер-
претируемой как задача оптимального программного управления соответствующей динами-
ческой системой вида (2), формируется вектор динамических приоритетов ζ (t ) = ζ (ψ (t0 )) ,
который функционально (через функцию Гамильтона) связан с вектором сопряженной системы уравнений (8) и однозначно определяет оптимальный план выполнения операций и распределения ресурсов в СУ АПО.
Заключение. В результате проведенных исследований разработана оригинальная многоэтапная процедура комплексного планирования функционирования системы управления активными подвижными объектами с учетом факторов неопределенности. Главное преимущество предложенного подхода по сравнению с существующими заключается в комбинированном динамическом (контекстном) учете при планировании функционирования СУ АПО как различных типов ограничений, накладываемых на указанный процесс, так и возможных классов возмущающих воздействий, влияющих на устойчивость построенных планов, который осуществляется на основе одновременного использования при формировании планов детерминированных и стохастических моделей.
Другое преимущество предложенного комбинированного подхода заключается в том, что как при итеративном поиске параметров СУ АПО с использованием стохастических моделей и методов глобальной оптимизации, так и при формировании собственно плана функционирования системы обеспечивается монотонная сходимость итеративных процессов за счет интерактивной гибкой настройки программного обеспечения, реализующего разработанные методы на компьютере, на основе использования заранее введенной параметрической и структурной избыточности в соответствующие численные алгоритмы оптимизации.
Статья подготовлена по результатам исследований, проводимых при финансовой поддержке Российского фонда фундаментальных исследований (гранты 10-07-00311-а, 11-0801016-а, 11-08-00767-а), Отделения нанотехнологий и информационных технологий РАН (проект № 2.11, 2.12), а также программы ESTLATRUS: проекты 1.2/ELRI-121/2011/13, 2.1/ELRI/184/2011/14.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
22 С. В. Кокорин, С. А. Потрясаев, Б. В. Соколов
СПИСОК ЛИТЕРАТУРЫ
1. Калинин В. Н. Теоретические основы управления активными подвижными объектами. МО СССР, 1974. 130 с.
2. Соколов Б. В., Калинин В. Н. Многомодельный подход к описанию процессов управления космическими средствами // Теория и системы управления. 1995. № 1. С. 149—156.
3. Соколов Б. В., Калинин В. Н. Динамическая модель и алгоритм оптимального планирования комплекса работ с запретами на прерывание // Автоматика и телемеханика. 1985. № 5. С. 106—114.
4. Килин Ф. М. Теория и принципы построения автоматизированных систем управления. М.: Энергоатомиздат, 1985. 288 с.
5. Охтилев М. Ю., Соколов Б. В., Юсупов Р. М. Интеллектуальные технологии мониторинга и управления структурной динамикой сложных технических объектов. М.: Наука, 2006.
6. Кокорин С. В., Рыжиков Ю. И. Оптимизация параметров сетей массового обслуживания на основе комбинированного использования аналитических и имитационных моделей // Изв. вузов. Приборостроение. 2010. Т. 53, № 11. С. 61—66.
7. Краснощёков П. С., Морозов В. В., Федоров В. В. Декомпозиция в задачах проектирования // Изв. АН СССР. Сер. Техн. кибернетика. 1979. № 2. С. 7—18.
8. Чичинадзе В. К. Решение невыпуклых нелинейных задач оптимизации. Метод пси-преобразования. М.: Наука, 1983.
9. Brent R. P. Algorithms for Minimization without Derivatives. NJ, USA: Prentice-Hall Inc., 1973. 195 p.
Сергей Владимирович Кокорин Семен Алексеевич Потрясаев Борис Владимирович Соколов
Сведения об авторах — СПИИРАН, лаборатория информационных технологий в системном
анализе и моделировании; мл. науч. сотрудник; E-mail: kokorins@list.ru — канд. техн. наук; СПИИРАН, лаборатория информационных технологий в системном анализе и моделировании; E-mail: spotryasaev@gmail.com — д-р техн. наук, профессор; СПИИРАН; зам. директора по научной работе; E-mail: sokol@iias.spb.su
Рекомендована СПИИРАН
Поступила в редакцию 10.06.12 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
УДК 519.8
С. В. КОКОРИН, С. А. ПОТРЯСАЕВ, Б. В. СОКОЛОВ
КОМБИНИРОВАННЫЙ МЕТОД ПЛАНИРОВАНИЯ ОПЕРАЦИЙ И РАСПРЕДЕЛЕНИЯ РЕСУРСОВ СИСТЕМЫ УПРАВЛЕНИЯ АКТИВНЫМИ ПОДВИЖНЫМИ ОБЪЕКТАМИ
Предложены обобщенная динамическая модель и комбинированный метод планирования операций и распределения ресурсов системы управления активными подвижными объектами, позволяющие учесть основные ограничения системы управления на основе реализации концепции комплексного моделирования. Ключевые слова: комплексное планирование, система управления активными подвижными объектами, комбинированные методы моделирования и оптимизации.
Введение. Анализ основных направлений развития современных сложных организационно-технических систем (СОТС) позволил выделить ряд их особенностей, к числу которых относятся: многоаспектность и неопределенность поведения; иерархичность; подобие структур и избыточность основных элементов и подсистем и их взаимосвязей; разнообразие функций управления на каждом уровне системы; территориальная распределенность компонентов системы. Предварительные исследования показывают, что в качестве базового элемента при формальном описании процесса управления СОТС может использоваться активный подвижный объект (АПО) [1]. В общем случае это искусственный объект (аппаратно-программный комплекс), перемещающийся в пространстве и взаимодействующий с другими АПО и внешними объектами обслуживания, в ходе которого формируются информационные, энергетические и материальные потоки [2, 3]. На практике, как правило, из-за достаточно низкого уровня автономности АПО создаются распределенные системы управления АПО (СУ АПО). В этом случае на концептуальном уровне процесс функционирования СУ АПО может быть представлен как процесс выполнения соответствующих целевых и технологических (обеспечивающих) операций и распределения ресурсов в рассматриваемой системе управления.
На содержательном уровне задача комплексного планирования функционирования СУ АПО может быть сформулирована следующим образом: необходимо выбрать такой допустимый план выполнения операций и распределения ресурсов системы, в ходе реализации которого, в рамках заданных сценариев воздействия возмущающих факторов, будут выполнены своевременно и полностью все операции, составляющие соответствующие технологические циклы управления, а уровень сервиса (качества) планирования будет удовлетворять заданным требованиям. При этом если будет получено несколько планов, то необходимо выбрать наилучший план относительно принятых критериев и показателей оптимальности.
Формальная постановка задачи. На основе ранее разработанных частных динамических моделей планирования СУ АПО [1—3] запишем обобщенную динамическую модель процессов функционирования указанной системы в условиях возмущающих воздействий:
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
18 С. В. Кокорин, С. А. Потрясаев, Б. В. Соколов
JG
(
x
(t
)
,
u
(t
)
,
β,
ξ
(t
)
,
t
)
→
extr ;
u (t )∈∆
(1)
∆
=
⎪⎪⎨⎧uy
(t (t
) )
| x (t ) = φ (t0 , x (t0 ), x (t ),u = η(x(t),u(t),β,ξ (t),t );
(t
)
,
β, ξ
(t
)
,
t
);
( )⎪⎪⎩x(t0 ) ∈ X0 (β), x t f ∈ X f (β),
(2)
где x (t ) — обобщенный вектор состояния СУ АПО; y (t ) — обобщенный вектор выходных
характеристик (показатели качества функционирования СУ АПО); u (t ) — вектор программ-
ного управления, представляющий план функционирования СУ АПО; β — обобщенный век-
тор параметров СУ АПО, характеризующих основные технические и технологические возможности аппаратно-программных средств, входящих в ее состав; φ , η — соответственно
многомерные переходная и выходная функции, задаваемые в общем случае в аналитико-
алгоритмическом (имитационном) виде; X0 (β) , X f (β) — значение вектора x (t ) в началь-
ный и конечный моменты времени; t ∈ ⎣⎡t0 ,t f ⎤⎦ — заданный интервал планирования работы
СУ АПО; ξ (t ) — вектор возмущающих воздействий, имеющих как объективный, так и субъ-
ективный характер и задаваемых извне в виде соответствующих сценариев ξ (t ) ∈ Ξ .
Для определенности в дальнейшем будем предполагать, что указанные возмущающие
воздействия задаются в виде импульсных стохастических случайных процессов [4].
В состав рассматриваемой динамической модели планирования включим вектор показа-
телей качества планирования
T
J (x (t ) ,u (t ),β,ξ (t ),t ) = J(o)T , J(k)T , J( p)T ,
(3)
где J(o)T , J(k )T , J( p)T — соответствующие векторы показателей качества планирования опе-
раций, распределения ресурсов и потоков при различных сценариях реализации возмущаю-
щих воздействий.
Примеры конкретного описания данных показателей качества для детерминированного
и стохастического вариантов задания исходных данных приведены в работах [1, 2].
Комбинированный метод решения задачи. Предположим, что в задаче векторной оп-
тимизации при решении исходной задачи планирования (см. формулы (1), (2)) будет исполь-
зоваться простейшая линейная свертка вида
hh
∑ ∑J G = Cα Jα , Cα ≥ 0,
Cα = 1.
(4)
α=1 α=1
Более сложные варианты построения указанных сверток для рассматриваемого класса
задач планирования подробно изложены в работах [1, 5].
Динамическая задача комплексного планирования операций и распределения ресурсов
СУ АПО в условиях стохастических возмущающих воздействий (см. формулы (1)—(3)) мо-
жет рассматриваться как многоэтапная задача стохастического программирования. В данной
статье предполагается, что распределение ресурсов СУ АПО в условиях возмущающих воз-
действий можно конструктивно описать с использованием дискретно-событийных стохасти-
ческих моделей, исследуемых в современной теории сетей массового обслуживания [6]. При
этом в соответствии со структурными особенностями СУ АПО задачу стохастического про-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
Комбинированный метод планирования операций и распределения ресурсов СУ АПО
19
граммирования можно декомпозировать на две взаимосвязанные задачи оптимизации процесса функционирования рассматриваемой системы [5, 7]:
— подзадачу оптимизации функционала (1) на основе варьирования вектора ζ приори-
тетов операций обслуживания АПО при фиксированном векторе p параметров, характери-
зующих технические и технологические возможности системы (подвекторе β: см. формулы (1)—(2));
— подзадачу оптимизации функционала (1) на основе варьирования вектора p при фик-
сированном векторе ζ .
Для реализации данного подхода предлагается следующая двухэтапная итерационная процедура.
Этап 1. Оптимизация процесса выполнения операций и распределения ресурсов в СУ АПО с использованием ее аналитико-имитационной (стохастической) модели:
( ( ))f q0 ζ(ν) ,pν
→ min ,
pν∈Ω
(5)
где q0 (⋅) — аналитико-имитационное описание взаимосвязи оптимизируемых параметров
модели планирования; Ω — множество допустимых значений параметров, характеризующих
СУ АПО; ν — номер итерации.
Этап 2. Динамическое планирование операций и распределение ресурсов с фиксирован-
ным вектором параметров pν , полученным на предыдущем этапе:
( ( ))f q0 ζ(ν+1) ,pν
→ min ,
ζ(ν+1)∈Ζ
(6)
где Z — множество допустимых значений приоритетов.
Для реализации рассматриваемой процедуры на нулевой итерации ( ν = 0 ) необходимо
( )задать вектор начальных значений приоритетов ζ(ν) = ζ(0) операций, выполняемых в СУ
АПО. Его можно сформировать, например, алгоритмически (неявно), используя такие эвристические правила диспетчеризации, как FIFO, LIFO. Итерационный процесс поиска опти-
мального плана заканчивается в одном из следующих случаев: при достижении заданного уровня разности значений функционалов на двух последовательных итерациях:
( ( )) ( ( ))f q0 ζ(ν+1) ,p ν+1 − f q0 ζ(ν) ,pν < e ,
(7)
где e — известная величина; либо, если стабильная сходимость не наблюдается, используется эвристическое правило выхода из итерационной процедуры. При этом проверку условия (7) можно проводить, только начиная с первой итерации, так как вектор p0 в начале итерационной процедуры не определен.
Комбинированный метод оптимизации параметров СУ АПО. Рассмотрим более подробно содержание первого этапа предложенной итерационной процедуры. Для оптимизации вектора параметров p целесообразно использовать комбинацию метода глобального по-
иска (метод Ψ-преобразования [8]) и метода численной оптимизации без расчета производных (метод главных осей Брента [9]). Метод Ψ-преобразования — метод поиска глобального экстремума целевой функции (5) — не требует задания начального приближения при решении исходной задачи оптимизации, но характеризуется существенными вычислительными затратами при увеличении размерности вектора оптимизируемых параметров pν . Использо-
вание только метода Ψ-преобразования при оптимизации функционала (5) приводит к
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
20 С. В. Кокорин, С. А. Потрясаев, Б. В. Соколов
большим погрешностям. Поэтому предлагается его дополнить методом локальной оптимизации функционала (5). Применительно к рассматриваемой задаче планирования работоспособность данного метода была продемонстрирована при оптимизации систем с сетевой структурой [6].
Главный недостаток метода локальной оптимизации, точнее, его алгоритмической реализации, заключается в необходимости задания начального приближения, которое должно быть рассчитано для каждой задачи отдельно. Однако первое приближение уже известно
(в результате оптимизации функционала (5) с использованием метода Ψ-преобразования). Метод характеризуется двумя основными параметрами: показателем точности расчета целевой функции, который определяет момент остановки итерационного цикла, и шагом изменения оптимизируемых параметров, определяющим скорость сходимости алгоритма. Теоретическая сходимость данного метода для случая дважды непрерывно дифференцируемых функций была доказана в работе [9]. Применительно к исследуемой задаче планирования вычислительные эксперименты показали хорошую сходимость для более широкого класса оптимизируемых целевых функций, которые не являются в общем случае дифференцируемыми ((2), (3)).
Метод динамического планирования операций и распределения ресурсов СУ АПО. Данный метод предлагается использовать для формирования собственно плана выполнения операций и распределения ресурсов в СУ АПО. В работах [2, 3, 5] показано, что каждому такому плану может быть поставлен в соответствие комбинированный вектор сопряженной системы уравнений, который в данной задаче может интерпретироваться уже как вектор ди-
намических приоритетов ζ0 . Более того, в указанных работах также данный вектор рассмат-
ривается как вектор координирующих воздействий при реализации процедуры интерактивного планирования СУ АПО, оценивании устойчивости планов, а также при выработке корректирующих воздействий, позволяющих адаптировать как детерминированную динамическую модель планирования, так и аналитико-имитационную модель процесса реализации составленных планов с учетом возможных возмущающих воздействий.
Кратко остановимся на общей итеративной схеме формирования вектора динамических приоритетов, основанной на методе локальных сечений и представляющей собой одну из модификаций принципа максимума Понтрягина для случая задания смешанных ограничений [2, 5]. Рассмотрим алгоритм, реализующий данную схему.
(Шаг 1. Задание диспетчерского решения (допустимого плана) uд (t ), t ∈ t0 , t f ⎦⎤ ; в част-
ном случае в качестве допустимого может быть выбран „нулевой“ план — uд (t ) ≡ 0 .
Шаг 2. Интегрирование системы уравнений (2), описывающей процесс функционирования СУ АПО, с заданными начальными условиями, характеризующими ее текущее состояние,
и u = uд (t ) . В работах [2, 5] был описан один из вариантов преставления системы уравнений
(2) в виде детерминированной нестационарной конечномерной дифференциальной динами-
ческой системы x = f (x,u,t ) . В результате интегрирования получаем вектор-функцию xд (t ) .
Также в конечный момент времени рассчитываются значение обобщенного показателя качества планирования JG и значение вектора сопряженной системы уравнений с использованием условия трансверсальности.
Шаг 3. Интегрирование в обратном времени от t = t f до t = t0 при u = uд (t ) сопря-
женной системы уравнений вида
ψl
=
−
∂H ∂xl
+
I1
∑
δ=1
λ
δ
(
t
)
∂gδ(1)
(
x(t)
∂xl
,
u
(
t
)
)
I3
+ ∑ργ γ=1
(
t
)
∂g γ( 2 )
(
x(t
∂xl
)
,
u
(t
))
,
l
= 1,…, n ,
(8)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
Комбинированный метод планирования операций и распределения ресурсов СУ АПО
21
где H = ψT (t )f (x,u,t ) — гамильтониан, λδ (t ) и ργ (t ) — динамические множители Ла-
гранжа;
grad
H
(
x
(
t
)
,
u
(
t
)
,
ψ
(
t
))
=
I1
∑
λδ
(
t
)
grad
gδ(1)
(
x
(t
)
,
u
(t
)
)
+
I2
∑
ρ
γ
(
t
)
grad
g
(2)
γ
(
x
(
t
)
,
u
(
t
)
)
,
(9)
u
δ=1 u
γ=1 u
где ψ (t ) — вектор сопряженной системы уравнений; I1 — множество индексов для ограни-
чений типа равенства gδ(1) (x (t ),u (t )) = 0, δ ∈ I1 ; I2 — множество индексов для ограничений типа неравенства gγ(2) (x (t ),u (t )) ≤ 0, δ ∈ I2 ; I3 — множество активных индексов, для кото-
рых
ограничения
типа
g
(2)
γ
(
x
(t
)
,
u
(
t
))
≤
0
превращаются
в равенства.
В момент времени t = t0 (момент окончания интегрирования системы (8)) формируется
первое приближение значений сопряженной системы уравнений ψi (t0 ) . На этом завершается
итерация r = 0 . Далее — повторение шагов 2 и 3 до тех пор, пока не будут выполнены условия
J G( r +1)
−
J
(r
G
)
≤ε,
где
ε
—
заданная
точность
численного
решения
рассматриваемой
двухто-
чечной краевой задачи. В результате решения рассматриваемой задачи планирования работы СУ АПО, интер-
претируемой как задача оптимального программного управления соответствующей динами-
ческой системой вида (2), формируется вектор динамических приоритетов ζ (t ) = ζ (ψ (t0 )) ,
который функционально (через функцию Гамильтона) связан с вектором сопряженной системы уравнений (8) и однозначно определяет оптимальный план выполнения операций и распределения ресурсов в СУ АПО.
Заключение. В результате проведенных исследований разработана оригинальная многоэтапная процедура комплексного планирования функционирования системы управления активными подвижными объектами с учетом факторов неопределенности. Главное преимущество предложенного подхода по сравнению с существующими заключается в комбинированном динамическом (контекстном) учете при планировании функционирования СУ АПО как различных типов ограничений, накладываемых на указанный процесс, так и возможных классов возмущающих воздействий, влияющих на устойчивость построенных планов, который осуществляется на основе одновременного использования при формировании планов детерминированных и стохастических моделей.
Другое преимущество предложенного комбинированного подхода заключается в том, что как при итеративном поиске параметров СУ АПО с использованием стохастических моделей и методов глобальной оптимизации, так и при формировании собственно плана функционирования системы обеспечивается монотонная сходимость итеративных процессов за счет интерактивной гибкой настройки программного обеспечения, реализующего разработанные методы на компьютере, на основе использования заранее введенной параметрической и структурной избыточности в соответствующие численные алгоритмы оптимизации.
Статья подготовлена по результатам исследований, проводимых при финансовой поддержке Российского фонда фундаментальных исследований (гранты 10-07-00311-а, 11-0801016-а, 11-08-00767-а), Отделения нанотехнологий и информационных технологий РАН (проект № 2.11, 2.12), а также программы ESTLATRUS: проекты 1.2/ELRI-121/2011/13, 2.1/ELRI/184/2011/14.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11
22 С. В. Кокорин, С. А. Потрясаев, Б. В. Соколов
СПИСОК ЛИТЕРАТУРЫ
1. Калинин В. Н. Теоретические основы управления активными подвижными объектами. МО СССР, 1974. 130 с.
2. Соколов Б. В., Калинин В. Н. Многомодельный подход к описанию процессов управления космическими средствами // Теория и системы управления. 1995. № 1. С. 149—156.
3. Соколов Б. В., Калинин В. Н. Динамическая модель и алгоритм оптимального планирования комплекса работ с запретами на прерывание // Автоматика и телемеханика. 1985. № 5. С. 106—114.
4. Килин Ф. М. Теория и принципы построения автоматизированных систем управления. М.: Энергоатомиздат, 1985. 288 с.
5. Охтилев М. Ю., Соколов Б. В., Юсупов Р. М. Интеллектуальные технологии мониторинга и управления структурной динамикой сложных технических объектов. М.: Наука, 2006.
6. Кокорин С. В., Рыжиков Ю. И. Оптимизация параметров сетей массового обслуживания на основе комбинированного использования аналитических и имитационных моделей // Изв. вузов. Приборостроение. 2010. Т. 53, № 11. С. 61—66.
7. Краснощёков П. С., Морозов В. В., Федоров В. В. Декомпозиция в задачах проектирования // Изв. АН СССР. Сер. Техн. кибернетика. 1979. № 2. С. 7—18.
8. Чичинадзе В. К. Решение невыпуклых нелинейных задач оптимизации. Метод пси-преобразования. М.: Наука, 1983.
9. Brent R. P. Algorithms for Minimization without Derivatives. NJ, USA: Prentice-Hall Inc., 1973. 195 p.
Сергей Владимирович Кокорин Семен Алексеевич Потрясаев Борис Владимирович Соколов
Сведения об авторах — СПИИРАН, лаборатория информационных технологий в системном
анализе и моделировании; мл. науч. сотрудник; E-mail: kokorins@list.ru — канд. техн. наук; СПИИРАН, лаборатория информационных технологий в системном анализе и моделировании; E-mail: spotryasaev@gmail.com — д-р техн. наук, профессор; СПИИРАН; зам. директора по научной работе; E-mail: sokol@iias.spb.su
Рекомендована СПИИРАН
Поступила в редакцию 10.06.12 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2012. Т. 55, № 11