1.1. Постановка задачи календарного планирования
Проект обычно представляют как некоторое множество операций (комплекс операций).
Операция это процесс, требующий затрат времени и ресурсов. Для формального описания операции необходимо задать ее объем W и зависимость скорости (интенсивности) операции от количества ресурсов, ее выполняющих. Будем обозначать эту зависимостьw = f(u(t)),
где u(t) - вектор ресурсов в операции в момент t.
Пусть ^ - момент начала операции, a t0 - момент ее окончания. Тогда объем операции удовлетворяет условию
W = J f [u(t)] dt.
Как правило, ресурсы участвуют в операции в определенных соотношениях, называемых набором ресурсов. Набор ресурсов можно представить в виде
Uj = Pj v, j = 1,m,
где m - количество видов ресурсов, v - интенсивность набора, Pj, - количество ресурса j-го вида на единицу мощности набора.
В качестве величины интенсивности набора, как правило. берется вид ресурса, который является основным (определяющим). Например, количество людей, выполняющих работу, определяет требуемое количество материалов, инструмента, рабочей одежды и т.д. Для определяющего ресурса, очевидно, b = 1. Ограничение на ресурсы теперь можно записать в следующем виде:
(t)< Nj (t), j=1,m
i=1
где n - число операций комплекса, Nj(t) - количество ресурсов j-го вида в момент t.
Ограничения на ресурсы часто связаны с ограниченностью финансов. Если обозначить cj- стоимость единицы ресурсов j-го вида в единицу времени, a S(t) - объем финансирования в момент t, то ограничения, связанные с финансированием, принимают вид
n m
jjcj (t)< Sj (t).
i=1 j=1
Это ограничения типа мощности. Если ограничены средства, выделенные на проект, то получаем ограничения типа затрат:
j^Si где m ю Si = j cj J vi (t) dt. m tio vi j=! tin Наконец, если задан график Q(t) поступления ресурсов на проект (график финансирования проекта), то получаем следующие ограничения на ресурсы: n m t jjcjbj vi (t) dt< Q(t). i=1 j=1 0 Задача оптимального распределения ресурсов (задача календарного планирования) заключается в определении распределения ресурсов v(t)={vi(t)} такого, что все операции комплекса выполнены за минимальное время (задача оптимальною быстродействия), либо потери, связанные с задержкой времени реализации комплекса или ряда его операций, минимальны (минимизация упущенной выгоды). n Ф = X qi (ti - di), ti > di, 1=1 где di - желательный срок завершения i-й операции, qi - потери в единицу времени при завершении операции позже di. Заметим, что и настоящее время в условиях дефицита финансовых средств. насыщенности рынка и материальных, и трудовых ресурсов. ограничивающим фактором являются финансовые ресурсы. Это позволяет рассматривать задачи календарного планирования, как задачи распределения ресурсов одного вида (финансовых ресурсов). Такой подход тем более обоснован, поскольку он позволяет сконцентрировать внимание именно на особенностях решения задач календарного планирования на основе агрегирования. Поэтому в дальнейшем, если это не оговорено особо, будем считать, что все операции выполняются ресурсами одного вида (финансовыми ресурсами). Будем обозначать далее m u(t) = X cjPijvi (t) j=1 количество финансовых ресурсов на i-ой операции в момент t и, соответственно, f,(u) - скорость i-ой операции в зависимости от количества ресурсов.
i=1