close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Информатика, вычислительная техника и управление
А.Ф. Самороковский,
кандидат технических наук,
доцент
В.В. Меньших,
доктор физико-математических наук,
профессор
МОДЕЛИ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
ПРИ РЕШЕНИИ ЗАДАЧ УПРАВЛЕНИЯ
OPTIMIZATION OF RESOURCE ALLOCATION IN SOLVING
THE PROBLEMS OF MANAGEMENT
Рассмотрена задача формализации оптимизации выбора варианта
распределения ресурсов для сокращения времени выполнения задач управления и предложены алгоритмы решения общей задачи распределения ресурса.
The problem of formalization of optimizing the choice of resource allocation options to
reduce time management tasks and algorithms of solving the general problem of resource allocation.
Введение. При решении задач управления особая роль отводится работе управляющей системы, в состав которой входит логико-вычислительная подсистема, информационная подсистема, исполнительная подсистема. Логико-вычислительная подсистема
представляет совокупность элементов для переработки информации и синтеза решений;
информационная подсистема представляет собой совокупность элементов для восприятия и представления информации, необходимой для синтеза решений; исполнительная
подсистема представляет совокупность элементов для формирования управляющих воздействий на объект управления [1].
Одним из способов оптимизации управления является оптимизация работы
исполнительной подсистемы. Данная подсистема при решении задач управления
выполняет некоторые действия с целью формирования управляющих воздействий на
управляемую систему. Эти действия выполняются в определенной последовательности,
выполнение отдельных последующих действий может зависеть от предыдущих.
Отдельные действия могут выполняться параллельно.
166
Вестник Воронежского института МВД России №2 / 2016
В качестве критерия оптимизации выступает время выполнения всей
совокупности действий по принятию решения [2]. Для сокращения времени выполнения
всех действий могут использоваться различные варианты распределения ресурсов. С
этой целью необходимо определить оптимальный выбор распределения ресурсов.
Целью работы является разработка математической модели оптимизации
распределения ресурсов для сокращения времени на принятие управленческих решений
и алгоритмов решения общей задачи распределения ресурса.
Содержательная постановка и формализация задачи оптимизации выбора
варианта распределения ресурсов.
Рассмотрим задачу оптимизации выбора варианта распределения ресурсов для
сокращения общего времени выполнения некоторого задания.
Будем считать, что задание предполагает выполнение некоторой совокупности
частично упорядоченных действий группами исполнителей. При этом каждое действие
закреплено за конкретной группой исполнителей. В свою очередь действие представляет
собой совокупность частично упорядоченных операций (поддействий), каждую из
которых может выполнять любой исполнитель из соответствующей группы.
Следовательно, время выполнения действия зависит от количества исполнителей.
Под распределением ресурса будем понимать увеличение числа исполнителей в
группах. Это может приводить к сокращению времени выполнения действий группами,
в которые добавлены исполнители, а следовательно, и общего времени выполнения всей
совокупности действий. Указанная задача является сложной трёхуровневой
комбинаторной задачей, для решения которой необходимо осуществить решение
следующих частных задач:
1) оценить длительность выполнения каждого действия в зависимости от числа
исполнителей, входящих в группу, выполняющую это действие;
2) оценить общее время выполнения всех действий в зависимости от количественного состава групп исполнителей;
3) найти такое распределение имеющегося ресурса исполнителей по группам,
чтобы минимизировать общее время выполнения всех действий [3].
Осуществим формализацию этой задачи. Обозначим Δ  D1,D2 ,...,Dn  –
множество действий (n – количество действий). На множестве Δ определим отношение
частичного порядка E  Δ  Δ такое, что Di ,D j  , если действие Di должно
предшествовать действию D j . Будем считать, что для каждого произвольного действия
D  Δ задана группа исполнителей G(D) Θ  G1,...,Gm  (m — количество групп
исполнителей, m ≤ n) и время выполнения действия T D  .
Каждое действие Di  Δ предполагает выполнение множества операций

Di  di1,...,diki

( ki — количество операций при выполнении действий Di ). В свою
очередь каждая операция d i j характеризуется временем ее выполнения ti j .
Будем считать, что на множестве Di также задано отношение частичного порядка


Ei  Di  Di такое, что di j , dik  Ei , если операция d i j должна предшествовать операции d ik .
Для каждого варианта распределения ресурса каждая группа G j характеризуется
имеющимся количеством исполнителей N G j  .
167
Информатика, вычислительная техника и управление
Оценка длительности выполнения каждого действия.
Первоначально рассмотрим задачи оценки длительности выполнения всей
совокупности действий для заданных количеств исполнителей каждой группе
N1 , N 2 ,..., N m .
На первом этапе необходимо оценить длительность Ti выполнения каждого
действия Di . Очевидно Ti определяется значениями длительности операций ti j ,
отношением частичного порядка Ei и количеством исполнителей N i в группе, которая
выполняет это действие. Учитывая, что ti j и Ei в дальнейшем не изменяются, а
количество исполнителей при распределении ресурса может варьироваться, будем
считать Ti  f Ni  .
Рассмотрим вопрос оценки величин Ti  f Ni  . Представим процесс выполнения
операций действия Di как последовательность шагов такую, что каждый шаг —
выполнение одной операции одним исполнителем. Обозначим исполнителей группы
G  Θ , выполняющей действие Di . Обозначим
1, если на k - м шаге исполнител ь g s выполняет операцию di j ;
X kjs  
0, если иначе.
Обратимся к описанию функциональных зависимостей между операциями и
исполнителями. Обозначим Ai j — момент начала выполнения операции d i j , тогда
Ai j  tij — момент ее окончания. Действие заканчивается после последнего шага
выполнения операций. Следовательно,
(1)
Ti  max (Ai j ( X )  tij ) X kjs , где i  1,...,n.
Зададим отношение частичного порядка Ei матрицей Bi  (bsti ), s, t  1,..., k j , где
s
t

1, если операции d i предшествует операция d i ;
b 

0, если иначе.
Опишем ограничения на последовательность выполнения шагов:
bsti ( Ais ( X )  tis )  Ait ( X ) —
i
st
(2)
условие того, что операция disдолжна заканчиваться раньше начала операции d ;
t
i
Ais ( X )  tis ) X sjk 1 X tjk  Ait X sjk 1 X tjk —
(3)
условие того, что если на k  1 шаге выполняется операция d is , а на k-м шаге — операция
d it , то d is должна завершиться до начала d it ;
X sjk X tjk  0, s  t —
условие того, что на каждом шаге выполняется только одна операция.
ki
ki
 X
j 1 k 1
k
sj
1 —
(4)
(5)
условие того, что каждая операция выполняется только на одном шаге.
168
Вестник Воронежского института МВД России №2 / 2016
Общая задача оценки времени выполнения действия Di имеет вид задачи
нелинейного булева программирования нахождения X * , минимизирующего (1) при
ограничениях (2)—(5).
Оценка общего времени выполнения всех действий.
Значение T определяется значениями длительностей Ti отдельных действий,
определенных на предыдущем этапе, а также отношением частичного порядка E и
распределением групп исполнителей по действиям.
Вновь будем считать, что выполнение действий представляет собой
последовательность шагов такую, что каждый шаг — выполнение одного действия
соответствующей группой исполнителей. Обозначим
1, если на k-м шаге группойисполнител ей Gm выполняется действие Di ,
Yi km  
0, если иначе.
1, если действие Di выполняется группойисполнител ей Gm ,
Pi m  
0, если иначе.
AY  — момент начала выполнения действия Di .
Вся совокупность действий завершается, когда завершилось последнее действие, т.е.
T  max( Ai (Y )  Ti ), где i  1,..., n.
(6)
Зададим отношение частичного порядка E матрицей B  bst ,s,t,...,ki, , где
1, если действие Ds предшествует действию Dt ,
bst  
0, если иначе.
По аналогии с предыдущим этапом определим
последовательность действий
bst ( As (Y )  Ts )  At (Y )
( k 1) m km
s
t
( A(Y )  Ts )Y
p
p
Y
k 1 s 1
km
t
Y
( k 1) m k
s
t
 At (Y ), где Y
Y  0, s  t ,
 1.
ограничения
на
(7)
(8)
(9)
Кроме того, однозначность задания группы исполнителей для каждого действия
определяется условием
p
Y
k 1
t
km
 1.
(10)
Распределение ресурса исполнителей для минимизации общего времени
выполнения всех действий.
Обозначим Z  Z1,...,Z m  — вариант распределения ресурса исполнителей по
группам Z j , — ресурс, выделяемый группе G j .
Тогда время выполнения действия Di , осуществляемое группой G j определяется как
Ti  Ti ( X , Z ), где Ti — функция, описывающая решение задачи (1)—(6).
Общее время выполнения всех действий определяется как
T  T Y ,Ti  X , Z , где T - функция, описывающая результат решения задачи (1) —
(6) на втором этапе[4].
169
Информатика, вычислительная техника и управление
Для значений Z  Z1,...,Z m , таких, что Zi  Ζ ,где Z — множество целых чисел,
должны быть выполнены следующие ограничения
m

 Zi  Z ,
(11)
i 1
(12)
Zi  0 .
Таким образом, общая задача распределения ресурса имеет следующий вид вид:
Найти ( X  , Y  , Z  )  Argmin T (Y , Ti ( X , Z )) при ограничениях(2) — (5), (7)—(12).
X ,Y , Z
Алгоритмы решения общей задачи распределения ресурса. Для построения
алгоритма нахождения оптимального варианта распределения ресурса необходимо
определить группы Gi , которые выполняют свои действия Di за максимальное время
T D  . Это обусловлено тем, что использование ресурса при максимальной
продолжительности выполнения действий приводит к более значительному сокращению
времени выполнения действий. ti j M i  — длительность операции при добавлении M
количества исполнителей. Необходимо найти максимальное количество исполнителей
M imax , которое целесообразно добавлять в группы Gi , для максимального сокращения
времени выполнения всех действий T D  .
Если количество единиц ресурса невелико, то задача может быть решена полным
перебором. В остальных случаях может быть найдено только приближённое решение. В
рамках данной работы приведём общее описание двух алгоритмов без их детализации [5].
1. На первом этапе с помощью алгоритма, относящегося к классу «жадных
алгоритмов», найдём приближенное решение использования выделенного ресурса,
max
который позволяет максимально использовать имеющийся ресурс Z .
Будем считать, что все группы исполнителей упорядочены по убыванию
суммарной длительности выполняемых операций.
Первоначально выделим такую минимальную часть ресурса, которая обеспечивает
максимальное сокращение суммарного времени выполнения всех действий.
Аналогично выделяем ресурс для второй и последующих групп исполнителей до
тех пор, пока он не будет исчерпан. Графически это выглядит следующим образом
(рис.1).
На последующих этапах осуществляется улучшение полученного результата на
основе выбора альтернативных вариантов распределения ресурса по группам.
Сначала рассматриваются все рациональные, т.е. приводящие к сокращению
общего времени, варианты распределения последних исполнителей из ресурса. Если при
этом улучшается общее время T , то запомним новый вариант.
Далее рассматриваем варианты распределения двух последних исполнителей и
т.д. Процесс продолжается до тех пор, пока не будут рассмотрены все варианты или,
исчерпан лимит времени на решение задачи.
2. Другой алгоритм решения задачи может быть основан на идеях алгоритмов
«градиентного спуска». Каждый раз распределяется одна единица ресурса и выбирается
вариант, обеспечивающий максимальное сокращение времени (рис. 2). Алгоритм продолжается до тех пор, пока не будет исчерпан весь ресурс.
170
Вестник Воронежского института МВД России №2 / 2016
G
Сокращение
общего времени
не происходит
G1
+1
G1
+2
G1
+3
G2
+1
G1
+4
G3
+1
G2
+2
Gi
+1
G3
+2
Gi
+
m
Рис. 1. Вариант распределения ресурса на основе «жадного» алгоритма
G
G
G
G
1
3
6
+
1
T1
>
G
1
+
1
<
T1
G
G
3
6
+
1
+
2
T3
>
i
+
1
T6
>
Ti
G
+
1
+
1
T3
…
<
G
…
i
+
1
Ti
G
G
1
3
6
+
1
+
2
+
2
…
Вариант
распределения
2-х единиц ресурса
T6
<
G
Вариант
распределения
1-й единицы
ресурса
…
G
i
Вариант
распределения
3-х единиц ресурса
+
1
Рис. 2. Алгоритм распределения ресурса методом «градиентного спуска»
171
Информатика, вычислительная техника и управление
Заключение. Разработанные модель и алгоритмы могут быть использованы для
оптимизации выбора варианта распределения ресурсов в подсистемах органа управления
с целью сокращения общего времени выработки управляющих воздействий в системах
управления различного назначения.
ЛИТЕРАТУРА
1. Меньших В. В., Сысоев В. В. Структурная адаптация систем управления. — М. :
Радиотехника, 2002. — 150 с.
2. Оперативно-боевая деятельность органов внутренних дел : монография / под
ред. Ю.М. Антоняна. — М. : Издание ОИД МВД России, 2007. — 416 с.
3. Меньших В. В., Самороковский А. Ф. Обоснование выбора последовательности
действий оперативного штаба при возникновении чрезвычайных обстоятельств // Вестник Воронежского института МВД России. — 2016. — № 1. — С. 86—95.
4. Меньших В. В., Никулина Е. Ю. Оптимизация временных характеристик информационных систем. — Воронеж : ВИ МВД России, 2011. — 127 с.
5. Коршунов Ю. М. Математические основы кибернетики: учебное пособие для
вузов. — 2-е изд., перераб. и доп. — М. : Энергия, 1980. — 424 с.
REFERENCES
1. Menshikh V. V., Sysoev V. V. Strukturnaya adaptatsiya sistem upravleniya. — M. :
Radiotekhnika, 2002. — 150 s.
2. Operativno-boevaya deyatelnost organov vnutrennikh del : monografiya / pod red.
Yu.M. Antonyana. — M. : Izdanie OID MVD Rossii, 2007. — 416 s.
3. Menshikh V. V., Samorokovskiy A. F. Obosnovanie vybora posledovatelnosti
deystviy operativnogo shtaba pri vozniknovenii chrezvychaynykh obstoyatelstv // Vestnik Voronezhskogo instituta MVD Rossii. — 2016. — № 1. — S. 86—95.
4. Menshikh V. V., Nikulina Ye. Yu. Optimizatsiya vremennykh kharakteristik in-formatsionnykh sistem. — Voronezh : VI MVD Rossii, 2011. — 127 s.
5. Korshunov Yu. M. Matematicheskie osnovy kibernetiki: uchebnoe posobie dlya
vuzov. — 2-e izd., pererab. i dop. — M. : Energiya, 1980. — 424 s.
172
Вестник Воронежского института МВД России №2 / 2016
СВЕДЕНИЯ ОБ АВТОРАХ
Самороковский Андрей Федорович. Начальник кафедры тактико-специальной подготовки. Кандидат технических наук, доцент.
Воронежский институт МВД России.
E-mail: samorokovskii_an@mail.ru
Россия, 394065, г. Воронеж, проспект Патриотов, 53. Тел. 8-905-656-16-34.
Меньших Валерий Владимирович. Начальник кафедры математики и моделирования систем. Доктор физико-математических наук, профессор.
Воронежский институт МВД России.
E-mail: menshikh@list.ru
Россия, 394065, г. Воронеж, пр-т Патриотов, 53. Тел. 8-915-582-64-46.
Samorokovskiy Andrey Fedorovich. Head of the chair of Special Tactical Training. Candidate of Technical Sciences, Associate Professor.
Voronezh Institute of the Ministry of the Interior of Russia.
Work address: Russia, 394065, Voronezh, Prospect Patriotov, 53. Tel. 8-905-656-16-34.
Menshikh Valery Vladimirovich. Chief of the chair of Mathematics and Systems Modeling. Doctor of
Physical and Mathematical Sciences, Professor.
Voronezh Institute of the Russian Ministry of the Interior of Russia.
Work address: Russia, 394065, Voronezh, Prospect Patriotov, 53. Tel. 8-915-582-64-46.
Ключевые слова: задача управления; распределение ресурса исполнителей; оптимизация выбора
варианта распределения ресурса; оценка длительности действий.
Key words: task management; resource allocation implementing; optimizing the choice of resource allocation options; estimate duration of action.
УДК 351.74; 519.711
173
Документ
Категория
Без категории
Просмотров
22
Размер файла
1 554 Кб
Теги
решение, оптимизация, управления, задачи, модель, распределение, ресурсов
1/--страниц
Пожаловаться на содержимое документа