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

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 681. 34
ОПТИМИЗАЦИЯ СЕТЕВОГО ПЛАНА МЕТОДОМ СЛУЧАЙНОГО ПОИСКА С ПЕРЕСЧЕТОМ С ПЕРЕМЕННОЙ ВЕЛИЧИНОЙ ШАГА
Черниговский А. С., Царев Р. Ю.
ФГАОУ ВПО «Сибирский федеральный университет», Красноярск, Россия (660 074, Красноярск, ул. Академика
Киренского, 26, УЛК), e-mail: tsarev. sfu@mail. ru_
В статье рассматривается подход к формированию оптимального плана выполнения задач информационно-управляющей системы на основе сетевого моделирования. Разработана и описана математическая модель формирования плана выполнения задач информационно-управляющей системы с учетом имеющихся ресурсов, сроков выполнения и трудоемкости как отдельных задач, так и всего проекта в целом. Представлена многоэтапная процедура получения оптимального плана задач, выполняемых в системе, который дает оптимальную загрузку всех видов ресурсов на всем протяжении работы информационно-управляющей системы, а также позволяет минимизировать сроки выполнения проектов. Предложенная процедура реализует метод случайного поиска с пересчетом с переменной величиной шага, осуществляя направленный поиск как при достижении допустимой области поиска, определяемой заданными ограничениями, так и непосредственно в допустимой области. Ключевые слова: сетевая модель, планирование, метод случайного поиска
OPTIMIZATION OF A NET SCHEDULE BY RANDOM SEARCH METHOD WITH RECALCULATION WITH VARIABLE STEP SIZE
Chernigovskiy A.S., Tsarev R.Y.
Siberian Federal University, Krasnoyarsk, Russia (660 074, Krasnoyarsk, street A. Kirenskogo, 26, ULK), e-mail:
tsarev. sfu@mail. ru_
The article considers the approach to formation of an optimal task schedule for information control system based on network simulation. The mathematical model of formation of the task execution schedule for information control system taking into account available resources, periods of execution and complexity of both separate tasks, and the project in general is developed and described. Multi-stage procedure of formation of the optimal schedule of tasks executed in system is presented. The schedule gives an optimal loading of all types of resources throughout information control system activity, and also allows minimizing periods of execution of the project. Presented procedure based on a random search method with recalculation with variable step size realizes directional search as in case of achievement of the acceptable search region determined by the given limitations, and directly in acceptable region. Keywords: net model, scheduling, random search method.
Широкое применение алгоритмов параллельной обработки информации в современных информационно-управляющих системах привело к открытию новой области исследований, связанной с проблемами эффективного формирования параллельных процессов в системах данного класса. Между реализацией алгоритмов на классической однопроцессорной архитектуре ЭВМ и реализацией тех же алгоритмов на параллельных вычислительных системах существуют принципиальные различия [1, 7]. В [8] показано, что, чем выше быстродействие параллельной вычислительной системы, достигаемое за счет архитектурных решений, тем более ограничен класс управляющих алгоритмов информационно-управляющих систем, которые на ней могут быть эффективно реализованы.
Эффективное формирование параллельных процессов программного обеспечения является сложной, но крайне важной и актуальной на сегодняшний день задачей [9]. На ее
решение существенно влияют индивидуальные особенности параллельных систем. Несомненно, такие задачи можно решать для каждой информационно-управляющей системы в отдельности, но уже сейчас существует большое количество различных методов и средств, применяемых в информационно-управляющих системах, и создание конкретного программного обеспечения для каждой системы является неприемлемым. Поэтому эффективное формирование параллельных процессов должно начинаться с построения математической модели работы большого числа узлов с изменяемыми (в общем случае) связями и с анализа на основе данной модели особенностей информационных потоков, проходящих через всю совокупность узлов [6]. Это позволит разработать методы и алгоритмы формирования параллельных процессов в информационно-управляющих системах, а также предложить методы их оптимизации [4].
Одним из способов описания процессов в информационно-управляющей системе является представление структуры выполнения задач системы с помощью сетевой модели [3]. Математический аппарат сетевого моделирования позволяет описать процессы, протекающие в системе, и произвести оптимизацию с целью получения такого плана выполнения работ системы, который бы позволял рационально использовать ресурсы системы и минимизировать время выполнения всего проекта [2, 5].
Далее будет рассмотрена задача формирования оптимального расписания выполняемых операций в информационно-управляющей системе, объединенных общими ограничениями на ресурсы.
Модель формирования оптимального плана
Положим, что имеется план, который содержит множество логически взаимосвязанных между собой операций (задач) V. В информационно-управляющей системе присутствует Ь видов ресурсов, все они используются для выполнения данного плана задач.
Операции (задачи) обозначаются как (/, у), где / - начальное, а у — конечное событие задачи. Каждая операция может выполняться только одним определенным типом ресурса.
Ь
Работы, выполняемые одним видом ресурса, выделяются во множество V1 (ЦУ1 = V).
1=1
Далее, для каждой операции (/, у) обозначим: ((?, у) — продолжительность ее выполнения,н (1, у) — наиболее ранний момент начала операции, у) — наиболее поздний момент окончания операции. Известны директивные сроки начала Пн и окончания По проекта. Для корректности задачи необходимо выполнение условия К & lt- По — Пн, где К -длина критического пути плана.
Планируемый период [Гн, Го] (Гн и То совпадают с директивными сроками)
разбивается на / интервалов, каждый продолжительностью тк (к = 1, /). Задается наличное
количество используемых ресурсов для каждого вида Sf на k-м интервале, суммарная трудоемкость выражается как Wlk = Sk tk.
Примем следующие обозначения: tH (i, j) и to (i, j) — моменты времени начала и окончания работ, w (i, j) k — трудоемкость, c (i, j) k — полезные трудозатраты в стоимостном выражении. Данные характеристики относятся к той части продолжительности работы t (i, j), которая покрывается результатом тк. В связи с тем, что в произвольный момент времени состояние процесса формирования характеризуется значениями t^i, j) и ^(i, j), & quot-(i, j), эти значения можно рассматривать как фазовые координаты объекта управления.
Получаем задачу нахождения таких значений ^(i, j) и to (i, j), & quot-(i, j), которые позволяли бы достичь с учетом всех ограничений номинальную и, по возможности, равномерную загрузку всех видов ресурсов на протяжении всего планируемого периода.
Представленную выше задачу формализуем следующим образом.
Необходимо, чтобы движение объекта в фазовом пространстве удовлетворяло ограничениям на сроки выполнения проекта:
тах (^(i, j) +1(i, j)) & lt- Do, min tB (i, j) & gt- По, (1)
(i, iW (i, jW
и ограничениям на порядок выполнения задач, которые заданы топологией сетевой модели (комплексом информационно и по управлению взаимосвязанных задач информационно-управляющей системы):
G (J, V), (2)
где J — множество вершин.
Положим Rk — подмножество задач, которые покрываются k-м интервалом времени
длительностью Tk, k= 1, f, Rk = Rl.
l=1
Данная задача представляет собой задачу сетевого планирования на подмножестве Rl с учетом (1) и (2), которую можно представить в виде целочисленной модели: 2 jk (l)c (i, j) kx (i, j) k, (3)
(i, j & gt-vl
k
где
x (i, j) k
2 w (i, j) kx (i, j) k & lt- wk, l = 1, L, (4)
[1, если (/, у) выполняется на к — м интервале, [ 0, в противном случае.
Здесь фк (/) — функция штрафа, далее о ней будет сказано подробнее.
(i, j) eVl
Чтобы достичь оптимального управления на всем планируемом периоде [Гн, То], необходимо также достичь оптимальности управления на каждом интервале Tk. Получаем функцию, характеризующую эффективность управления, следующего вида:
F = Е Е Е jk (l)c (i, j) kx (i, j) k. (5)
k=1 l=1 (i, j) k eVl
Задача (1)-(5) полностью охватывает специфику процессов информационно-управляющих систем, а также их особенности.
В результате, максимизируя функционал (5), можно получить минимум себестоимости выполнения всех операций.
Для решения описанной выше задачи предлагается использовать метод случайного поиска с пересчетом с переменной величиной шага. Данный метод осуществляет направленный поиск как при достижении допустимой области поиска, определяемой заданными ограничениями, так и непосредственно в допустимой области.
Перейдем к поэтапному описанию процедуры решения задачи.
Многоэтапная процедура оптимизации сетевой модели
Этап I. На основе топологии сети (2) и известных tрн (i'-, j) и t^(i, j) производим расчет длины критического пути — k, а также резервов времени всех работ:
P (i)=о (/, j) — tрн (i'-, j) + А — А — k.
Берем величину шага Шо = 1 max P (i). Максимум вычисляется по всем задачам
плана.
Этап II. Положим начальную точку поиска То (положение начал задач) по следующему правилу:
t°°(/, j) = tрн (i'-, j) + 1 P (i), & quot-(i, j).
Этап III. В полученной на предыдущем шаге точке проверяем, выполняется ли условие (4) для каждого k-го интервала k = 1, f. Это необходимо, чтобы проверить, не превышает ли ожидаемая потребная трудоемкость наличную трудоемкость по каждому виду ресурса (l = 1, L):
d =
0, если Z WC, j) k х ('-, j)? W& quot-(i, j), l = 1, L,
(i, j) eVl
1, в противном случае
Этап IV. На данном этапе выясним, на каких интервалах условие (4) не выполняется. Определим
А =? 8 Г.
к=1
Целочисленная функция, А представляет собой функцию качества при достижении допустимой области. Если значение А, полученное в новой точке, меньше, чем в предыдущей, значит, шаг является подходящим.
При, А & gt- 0 переходим к этапу VIII, поскольку допустимая область уже достигнута- если же, А = 0, то переходим к вычислению функции качества (5), так как найденная точка находится внутри допустимой области.
Этап V. В функционале (5) фк (/) — функция штрафа за невыполнение условия:
— А2 & lt- ?п (-, у) кх (-, у) к & lt- ^ +А1, / = й, к = 17 (6)
Это условие устанавливает некоторые допуски А1 и А2 для наличного ресурса /-го вида в произвольный момент.
Функция фк (/) определяется по формуле:
Фк (/) = 1-
ь?! ь (и-) — ^ (и-)+ь ь) — ^)
/ ^г
где и — моменты времени, в которые происходит изменение потребного количества ресурса ($ 1 = ?н (/, у) или и =н (/, у) + 1(1, у)) — ~(^) — суммарное количество /-го вида ресурса, требуемого
в момент времени и--? — сумма по тем и, в которых происходит нарушение условия (6)
справа (перегрузка) — Ь1 и Ь1- коэффициенты штрафа за недогрузку и перегрузку, соответственно, I/ - число моментов и на к-м интервале — тк.
Запоминаем значение = ^(70) и переходим этапу VI. Если л & gt-1 (Л — номер шага поиска), то переходим к этапу Х.
Этап VI. На данном этапе моделируется М-мерный единичный случайный вектор X. Данный вектор является равномерно распределенным по всем направлениям фазового пространства. Обозначим координату этого вектора как Х (-, у), она соответствует работе (-, у). Этап VII. Определим переход из точки Тц в точку Тц + 1 по формулам:
?У1^ у) =& lt-
инЛ+1(-, у)
иЛ (-, у) + ШлХ (/, у), если ирн (-, у) & lt- иЛ (-, у) + ШД-, У) & lt- ипо (-, у) — иЛ (-, у), если (-, у) + ШлХ (-, у) & lt- С (-, у) или? н (-, у) + ШЛ Х (-, у) & lt- С (-, у).
?V1 & lt-Лу), если +1 & lt-Лу) & lt- тахГ^рн (i, у) + г (/, у)) —
о-, у^ рн
тах (и рм (-, у) + и (-, у)),& quot-(-, у), в противном случае. Для осуществления возврата в точку Т необходимо вычислить величины
8(/, у) = С у) —? (/, у),& quot-(/, у), которые хранятся в памяти до следующего шага. Переходим к этапу III.
Этап VIII. Функция, А вычисляется в первый раз в начале поиска или же после вычисления функции качества (5) (алгоритм работал в допустимой зоне). В этом случае, когда, А вычислена впервые, присваиваем Ао значение, А (Ао = А) и переходим к этапу VI. Иначе рассчитываем новую величину шага по следующей формуле:
Ш1Ч, если, А & lt- А0 и У (А) & lt- 8(А) или, А & gt- А0Н (А) & lt- х (5) — Ш = I а (А)Ш, если, А & lt- Ао и У (А) = 8(А) —
1 | р (А)Ш^ если, А & gt- Ао, Н (А) = Х (А), Ш^ & gt- е (А) — ()
Ш0, если, А & gt- А0, Н (А) = х (5), рШ 1−1 & lt- е (А) & lt- 1(А).
Здесь У (Л) — число удачных подряд шагов, 5(Д) — целое, заранее известное число, определяющее количество удачных подряд шагов для увеличения величины шага, а (Д) -коэффициент увеличения шага, а (Д) & gt- 1- Н (Д) — число неудачных подряд шагов, х (5) — целое, заранее известное число, которое определяет число неудачных шагов для уменьшения шага, Р (Д) — коэффициент уменьшения шага, Р (Д) & gt- 1- е (Л) — заданная точность, делать шаг меньше которой не имеет смысла- целое число р (Д) определяет, сколько раз шаг уменьшался до заданной точности, если р (Д) = 1(Д), которое задается заранее, то поиск прекращается, и точка Т принимается за оптимальную.
В случае, когда был получен удачный шаг (А & lt- А0), значение Н (Д) необходимо обнулить и перейти к этапу VI- иначе, когда шаг получен неудачный (А & gt- А0), необходимо обнулить У (Д) и перейти к этапу IX.
При попадании в допустимую область поиска (этап V) обнуляется как У (Д), так и Н (Д). Для того чтобы достичь наибольшей надежности поиска, необходимо обнулять и р (Д).
Этап IX. Здесь происходят возврат в исходную точку по следующей формуле:
с+2а 7)=с+1а 7) -8& lt-/, у),& quot-(/, 7)
и переход на этап VI.
Этап X. После того как было получено новое значение функции качества F (Tц), его необходимо сравнить с наилучшим значением, которые было занесено в память — После этого формируется величина шага поиска в допустимой зоне.
В том случае, когда F (Tц) & gt- считается, что шаг выбран удачно, и необходимо изменить на значение F (Tц) — иначе шаг является неудачным, и остается без изменения. В результате этого наилучшее значение постоянно хранится в памяти.
Процедура формирования шага аналогична правилу (7):
Ш1
Ш1−1, если F (Т") & gt-0 и У^) & lt- с (F) или F (Т") & lt- F0 и Н (^) & lt-) — а (F)Ш 1−1, если F (Т") & gt- Fо и У (^) = Х (^) — р (А)Ш 1−1, если F (Т") & lt- Fо, H (F) = 5(F), р (F)Ш^ & gt- e (F) — Шо, если F (Т) & lt- Fо, H (F) = 8(F),|3^)Ш^ & lt- е^) & lt- e (F), р^) & lt- 1(А).
где все параметры имеют тот же смысл, что и в (7).
При получении удачного шага переходим к этапу VI, иначе к этапу IX. При р (^ = в качестве оптимальной принимается точка (совокупность моментов начал всех операций задач в информационно-управляющей системе) у), соответствующая Fо, которая хранится в памяти вместе со значением То.
Имея набор величин tн (i, у), соответствующих оптимальному технологическому процессу, и зная продолжительность всех работ — у), нетрудно рассчитать сроки окончания у), и оптимальный план будет определен полностью.
Заключение
В статье предложены целочисленная модель и процедура формирования оптимального плана выполнения задач информационно-управляющей системы, реализующая метод случайного поиска с пересчетом с переменной величиной шага. Формируемый план задач информационно-управляющей системы представлен в виде сети. Предлагаемый подход позволяет получить оптимальный сетевой план задач информационно-управляющей системы в виде расписания начала времени выполнения задач системы, соответствующий минимальному времени выполнения всех задач информационно-управляющей системы и оптимальному использованию вычислительных ресурсов.
Список литературы
1. Ковалев И. В. Параллельные процессы в информационно-управляющих системах. Формирование и оптимизация: монография / И. В. Ковалев, Р. Ю. Царев, Ю. Г. Шиповалов // Под ред. д.т.н., проф. А. В. Медведева. — Красноярск: НИИ СУВПТ, 2001. — 143 с.
2. Планирование периодичных задач при распределенной обработке информации / Н. А. Алексеев, О. В. Богданова, И. В. Ковалев, Р. Ю. Царев // Информационно-измерительные и управляющие системы. — 2010. — Т. 8. — № 3. — С. 11−14.
3. Царев М. Ю. Модификация ОБЯТ-сети для анализа временных характеристик сетевых моделей / М. Ю. Царев, Р. Ю. Царев, С. Ф. Шевчук // Вестник Сибирского государственного аэрокосмического университета им. академика М. Ф. Решетнева. — 2009. — № 1−2. — С. 74−78.
4. Черниговский А. С. К проблеме формирования планов выполнения задач в системах управления реального времени / А. С. Черниговский // Теоретические и прикладные аспекты современной науки. — 2015. — № 7−3. — С. 145−147.
5. Bendraouche M., Boudhar, M., Oulamara, A. Scheduling: Agreement graph vs resource constraints (2015) European Journal of Operational Research, 240 (2), pp. 355−360.
6. Koehler F., Khuller, S. Optimal batch schedules for parallel machines (2013) Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8037 LNCS, pp. 475−486.
7. Kushwaha S., Kumar, S. Analysis of list scheduling algorithms for parallel system (2015) 2014 International Conference on High Performance Computing and Applications, ICHPCA 2014, art. no. 7 045 327.
8. Li, Z. The study of key technologies and the performance of the parallel computer system (2014) WIT Transactions on Information and Communication Technologies, 46 VOLUME 3, pp. 20 112 016.
9. Shah D., Tse, D.N.C., Tsitsiklis, J.N. Hardness of low delay network scheduling (2011) IEEE Transactions on Information Theory, 57 (12), art. no. 6 094 268, pp. 7810−7817.
Рецензенты:
Бронов С. А., д.т.н., профессор, руководитель научно-учебной лаборатории систем автоматизированного проектирования кафедры систем искусственного интеллекта Сибирского федерального университета, г. Красноярск-
Ченцов С. В., д.т.н., зав. кафедрой «Системы автоматики, автоматизированное управление и проектирование» Сибирского федерального университета, г. Красноярск.

ПоказатьСвернуть
Заполнить форму текущей работой