Муравьиный алгоритм для построения однопроцессорного расписания с минимизацией пикового использования ресурса

Рассматривается задача построения однопроцессорного расписания с минимизацией пикового использования ресурса вычислителя. В качестве ресурса может выступать оперативная память. Набор заданий для планирования представлен в виде ориентированного ациклического графа, в каждой вершине которого указан объём занимаемого соответствующим заданием ресурса. Высвобождение ресурса, выделенного заданию, происходит по завершении последнего (согласно расписанию) непосредственного потомка этого задания в графе. Ограничением корректности на расписание является соблюдение частичного порядка, определённого графом заданий. Длительности заданий не рассматриваются. Приводится формальная постановка задачи. В качестве алгоритма для её решения предлагается муравьиный алгоритм, модифицированный так, что матрица феромона отражает желательность взаимного расположения (порядка) в расписании для любой пары заданий, а не только для пар соседних заданий. При построении расписания алгоритм для каждого задания выбирает его позицию в расписании, в отличие от известных муравьиных алгоритмов, которые строят расписание в порядке увеличения номеров позиций («слева направо») и для каждой очередной позиции выбирают задание. Выполнено экспериментальное исследование алгоритма на двух наборах заданий. Графы из первого набора построены так, чтобы априорно была известна оценка оптимального значения целевой функции. Графы из второго набора «слоистые», что соответствует структуре приложений по многостадийной обработке данных. В рамках каждого из наборов графы сформированы случайным образом, с соблюдением заданных параметров генерации и ограничений на структуру графа. Экспериментальное исследование показало высокую точность и стабильность предложенного муравьиного алгоритма. Табл. 1, ил. 12, библиогр. 17.