Задачи распределения ресурса на сетях
удобно рассматривать, изображая операции вершинами сети, а зависимости - дугами (представления «операции-дуги, события-вершины» и «зависимо-сти-дуги, операции-вершины» эквивалентны [10]). Пунктиром могут быть отражены ресурсные зависимости - когда для выполнения одних и тех же операций должны быть использованы одни и те же ресурсы. Примером могут являться сети, изображенные на рисунках 6 и 7. Полным резервом операции (i; J) называется величина AiJ- = t^ - tj , где tп - поздний срок начала (окончания) операции, а t]' - ранний срок начала (окончания) операции.11
![Рис. 7. Представление «операции-вершины» для сети рисунка 6]()
Рис. 7. Представление «операции-вершины» для сети рисунка 6
Для определения оптимального распределения ресурса необ-ходимо найти критические пути для каждого из вариантов распределения ресурса и сравнить длины этих путей (в сети, приведенной на рисунке 7, существует общий для операций «0-1» и «0-2» ресурс; потенциалы вершин, соответствующие различным способам использования этого ресурса - сначала выполняется операция «01», затем «0-2» и наоборот, приведены на рисунке 7 соответственно в квадратных скобках и без скобок).
Универсальных эффективных точных методов решения задач распределения ресурсов на сетях не существует. В качестве частного случая, для которого существует простой алгоритм, приведем следующий пример.
В сети, изображенной на рисунке 8, для трех операций известны поздние времена окончания ti. Требуется определить очередность выполнения этих трех операций при условии, что все операции выполняются одной единицей ресурса и поэтому не могут выполняться одновременно.
![Рис.<div class=]()
8. Пример распределения ресурса" />
Рис. 8. Пример распределения ресурса
Легко показать, что в рассматриваемом примере оптимально выполнять первой операцию с минимальным ti.
Если для выполнения проекта выделено ограниченное количество ресурса, то возникает задача наилучшего его использования. Обозначим wi - объем i-ой операции, /-(у,) - скорость ее выполнения в зависимости от количества ресурса vПредположим, что /(•) - непрерывная справа неубывающая функция, причем /(0) = 0. Если vi(t) - количество ресурса на i-ой операции в момент времени
t, то момент ti ее окончания определяется как минимальное время, удовлетворяющее уравнению:
ti
\ / (V (t ))dt = w,-.
0
Если количество ресурса, используемое при выполнении некоторой операции, не изменяется во времени, то говорят, что она выполняется с постоянной интенсивностью. Тогда продолжительность операции определяется выражением
ti(Vi) = wi //(v).
В настоящее время общих алгоритмов поиска распределения ограниченных ресурсов между операциями, минимизирующего время завершения проекта, не существует. Поэтому рассмотрим несколько частных случаев.
Пусть все операции независимы и выполняются ресурсом одного вида, количество которого равно R, а /(V,) - непрерывные строго монотонные вогнутые функции. Тогда существует оптимальное решение, в котором каждая операция выполняется с постоянной интенсивностью и все операции заканчиваются одновременно в момент времени T, определяемый как минимальное время, удовлетворяющее следующему неравенству:
n w
Z /"Чw) ? R,
i=1 T
где /_1Q - функция, обратная функции/(•), i = 1,n [7, 10].
Эвристические алгоритмы определения оптимального распределения ресурса для ряда случаев «невогнутых» функций интенсивности рассматриваются в [1-4].
Обширный класс задач КСПУ составляют задачи агрегирования - представления комплекса операций (проекта) в виде одной операции и исследования свойств таких представлений, для которых оптимизация в рамках агрегированного описания дает решение, оптимальное для исходного (детального) описания. Основные подходы к постановке и решению задач агрегирования рассматри-ваются в [1, 2, 10, 16].
