Эффективное формирование параллельных процессов программного обеспечения является сложной, но крайне важной и актуальной на сегодняшний день задачей [9]. На ее решение существенно влияют индивидуальные особенности параллельных систем. Несомненно, такие задачи можно решать для каждой информационно-управляющей системы в отдельности, но уже сейчас существует большое количество различных методов и средств, применяемых в информационно-управляющих системах, и создание конкретного программного обеспечения для каждой системы является неприемлемым. Поэтому эффективное формирование параллельных процессов должно начинаться с построения математической модели работы большого числа узлов с изменяемыми (в общем случае) связями и с анализа на основе данной модели особенностей информационных потоков, проходящих через всю совокупность узлов [6]. Это позволит разработать методы и алгоритмы формирования параллельных процессов в информационно-управляющих системах, а также предложить методы их оптимизации [4].
Одним из способов описания процессов в информационно-управляющей системе является представление структуры выполнения задач системы с помощью сетевой модели [3]. Математический аппарат сетевого моделирования позволяет описать процессы, протекающие в системе, и произвести оптимизацию с целью получения такого плана выполнения работ системы, который бы позволял рационально использовать ресурсы системы и минимизировать время выполнения всего проекта [2, 5].
Далее будет рассмотрена задача формирования оптимального расписания выполняемых операций в информационно-управляющей системе, объединенных общими ограничениями на ресурсы.
Модель формирования оптимального плана
Положим, что имеется план, который содержит множество логически взаимосвязанных между собой операций (задач) V. В информационно-управляющей системе присутствует L видов ресурсов, все они используются для выполнения данного плана задач.
Операции (задачи) обозначаются как (i, j), где
i
– начальное, а j
– конечное событие задачи. Каждая операция может выполняться только одним определенным
типом ресурса. Работы, выполняемые одним видом ресурса, выделяются во множество
.
Далее, для каждой операции (i, j) обозначим: t(i, j) – продолжительность ее выполнения, tрн(i, j) – наиболее ранний момент начала операции, tпо(i, j) – наиболее поздний момент окончания операции. Известны директивные сроки начала Dн и окончания Dо проекта. Для корректности задачи необходимо выполнение условия K ≤ Dо – Dн, где K – длина критического пути плана.
Планируемый период [Tн, То]
(Tн и То
совпадают с директивными сроками) разбивается на f интервалов, каждый продолжительностью τk (
). Задается
наличное количество используемых ресурсов для каждого вида 
на k-м интервале, суммарная трудоемкость
выражается как 
.
Примем следующие обозначения: tн(i, j) и tо(i, j) – моменты времени начала и окончания работ, w(i, j)k – трудоемкость, c(i, j)k – полезные трудозатраты в стоимостном выражении. Данные характеристики относятся к той части продолжительности работы t(i, j), которая покрывается результатом τk. В связи с тем, что в произвольный момент времени состояние процесса формирования характеризуется значениями tн(i, j) и tо(i, j), "(i, j), эти значения можно рассматривать как фазовые координаты объекта управления.
Получаем задачу нахождения таких значений tн(i, j) и tо(i, j), "(i, j), которые позволяли бы достичь с учетом всех ограничений номинальную и, по возможности, равномерную загрузку всех видов ресурсов на протяжении всего планируемого периода.
Представленную выше задачу формализуем следующим образом.
Необходимо, чтобы движение объекта в фазовом пространстве удовлетворяло ограничениям на сроки выполнения проекта:
, 
,
(1)
и ограничениям на порядок выполнения задач, которые заданы топологией сетевой модели (комплексом информационно и по управлению взаимосвязанных задач информационно-управляющей системы):
G(J, V), (2)
где J – множество вершин.
Положим Rk – подмножество задач, которые
покрываются k-м
интервалом времени длительностью τk, k=
, 
.
Данная задача представляет собой задачу сетевого планирования на подмножестве Rl с учетом (1) и (2), которую можно представить в виде целочисленной модели:
(3)
, (4)
где
Здесь jk(l) – функция штрафа, далее о ней будет сказано подробнее.
Чтобы достичь оптимального управления на всем планируемом периоде [Tн, То], необходимо также достичь оптимальности управления на каждом интервале τk. Получаем функцию, характеризующую эффективность управления, следующего вида:
(5)
Задача (1)-(5) полностью охватывает специфику процессов информационно-управляющих систем, а также их особенности.
В результате, максимизируя функционал (5), можно получить минимум себестоимости выполнения всех операций.
Для решения описанной выше задачи предлагается использовать метод случайного поиска с пересчетом с переменной величиной шага. Данный метод осуществляет направленный поиск как при достижении допустимой области поиска, определяемой заданными ограничениями, так и непосредственно в допустимой области.
Перейдем к поэтапному описанию процедуры решения задачи.
Многоэтапная процедура оптимизации сетевой модели
Этап I. На основе топологии сети (2) и известных tрн(i, j) и tпо(i, j) производим расчет длины критического пути – k, а также резервов времени всех работ:
P(i)= tпо(i, j) – tрн(i, j) + Dо – Dн – k.
Берем величину шага Ш0 = 
. Максимум вычисляется по всем задачам плана.
Этап II. Положим начальную точку поиска То (положение начал задач) по следующему правилу:
tрн(i, j) +
, "(i, j).
Этап III. В полученной на предыдущем шаге точке
проверяем, выполняется ли условие (4) для каждого k-го интервала . Это необходимо,
чтобы проверить, не превышает ли ожидаемая потребная трудоемкость наличную
трудоемкость по каждому виду ресурса 
:
Этап IV. На данном этапе выясним, на каких интервалах условие (4) не выполняется.
Определим
Целочисленная функция D представляет собой функцию качества при достижении допустимой области. Если значение D, полученное в новой точке, меньше, чем в предыдущей, значит, шаг является подходящим.
При D > 0 переходим к этапу VIII, поскольку допустимая область уже достигнута; если же D = 0, то переходим к вычислению функции качества (5), так как найденная точка находится внутри допустимой области.
Этап V. В функционале (5) jk(l) – функция штрафа за невыполнение условия:
, 
(6)
Это условие устанавливает некоторые допуски D1 и D2 для наличного ресурса l-го вида в произвольный момент.
Функция jk(l) определяется по формуле:
,
где
ti – моменты времени, в которые происходит
изменение потребного количества ресурса (ti = tн(i, j) или
ti = tн(i, j) + t(i, j)); 
– суммарное количество l-го вида ресурса, требуемого в момент
времени ti; 
сумма по тем ti, в которых происходит нарушение условия
(6) справа (перегрузка); 
и 
– коэффициенты штрафа за недогрузку и
перегрузку, соответственно, Il – число моментов ti на k-м интервале – τk.
Запоминаем значение F0 = F(T0) и переходим этапу VI. Если h ≥ 1 (h – номер шага поиска), то переходим к этапу Х.
Этап VI. На данном этапе моделируется М-мерный единичный случайный вектор 
. Данный вектор является равномерно
распределенным по всем направлениям фазового пространства. Обозначим координату
этого вектора как x(i, j), она соответствует работе (i, j).
Этап VII. Определим переход из точки Tη в точку Tη + 1 по формулам:
Для осуществления возврата в точку Тη необходимо вычислить величины
которые хранятся в памяти до следующего шага. Переходим к этапу III.
Этап VIII. Функция D вычисляется в первый раз в начале поиска или же после вычисления функции качества (5) (алгоритм работал в допустимой зоне). В этом случае, когда D вычислена впервые, присваиваем D0 значение D (D0 = D) и переходим к этапу VI. Иначе рассчитываем новую величину шага по следующей формуле:
(7)
Здесь У(Δ) – число удачных подряд шагов, δ(Δ) – целое, заранее известное число, определяющее количество удачных подряд шагов для увеличения величины шага, α(Δ) – коэффициент увеличения шага, α(Δ) > 1; Н(Δ) – число неудачных подряд шагов, χ(δ) – целое, заранее известное число, которое определяет число неудачных шагов для уменьшения шага, β(Δ) – коэффициент уменьшения шага, β(Δ) > 1; ε(Δ) – заданная точность, делать шаг меньше которой не имеет смысла; целое число r(Δ) определяет, сколько раз шаг уменьшался до заданной точности, если r(Δ) = l(Δ), которое задается заранее, то поиск прекращается, и точка Th принимается за оптимальную.
В случае, когда был получен удачный шаг (D < D0), значение Н(Δ) необходимо обнулить и перейти к этапу VI; иначе, когда шаг получен неудачный (D ³ D0), необходимо обнулить У(Δ) и перейти к этапу IX.
При попадании в допустимую область поиска (этап V) обнуляется как У(Δ), так и Н(Δ). Для того чтобы достичь наибольшей надежности поиска, необходимо обнулять и r(Δ).
Этап IX. Здесь происходят возврат в исходную точку по следующей формуле:
и переход на этап VI.
Этап X. После того как было получено новое значение функции качества F(Th), его необходимо сравнить с наилучшим значением, которые было занесено в память – F0. После этого формируется величина шага поиска в допустимой зоне.
В том случае, когда F(Th) > F0, считается, что шаг выбран удачно, и F0 необходимо изменить на значение F(Th); иначе шаг является неудачным, и F0 остается без изменения. В результате этого наилучшее значение F0 постоянно хранится в памяти.
Процедура формирования шага аналогична правилу (7):
где все параметры имеют тот же смысл, что и в (7).
При получении удачного шага переходим к этапу VI, иначе к этапу IX. При r(F) = l(F) в качестве оптимальной принимается точка (совокупность моментов начал всех операций задач в информационно-управляющей системе) tн(i, j), соответствующая F0, которая хранится в памяти вместе со значением T0.
Имея набор величин tн(i, j), соответствующих оптимальному технологическому процессу, и зная продолжительность всех работ – t(i, j), нетрудно рассчитать сроки окончания tо(i, j), и оптимальный план будет определен полностью.
Заключение
В статье предложены целочисленная модель и процедура формирования оптимального плана выполнения задач информационно-управляющей системы, реализующая метод случайного поиска с пересчетом с переменной величиной шага. Формируемый план задач информационно-управляющей системы представлен в виде сети. Предлагаемый подход позволяет получить оптимальный сетевой план задач информационно-управляющей системы в виде расписания начала времени выполнения задач системы, соответствующий минимальному времени выполнения всех задач информационно-управляющей системы и оптимальному использованию вычислительных ресурсов.
Рецензенты:Бронов С.А., д.т.н., профессор, руководитель научно-учебной лаборатории систем автоматизированного проектирования кафедры систем искусственного интеллекта Сибирского федерального университета, г. Красноярск;
Ченцов С.В., д.т.н., зав. кафедрой «Системы автоматики, автоматизированное управление и проектирование» Сибирского федерального университета, г. Красноярск.