Сокращение времени завершения проекта, как правило, связано с привлечением дополнительных средств (количество рабочих, сверхурочное время). Рассмотрим два примера постановки задачи оптимизации проекта по времени с привлечением дополнительных средств.
Постановка задачи 1. Для сокращения времени выполнения проекта выделяется некоторая сумма дополнительных средств B. Задан сетевой график выполнения проекта, где Е — множество событий, а e — множество работ. Продолжительность каждой работы равна tij. Известно, что вложение дополнительных средств xij в работу (i, j) сокращает время ее выполнения от tij до t'ij, причем эта зависимость выражается как
(fij — известные функции).
Для каждой работы существует минимально возможное время ее выполнения dij.
Требуется определить время начала Јнij и окончания t°ij выполнения работ, а также количество дополнительных средств xij, которые необходимо вложить в работы (i, j), чтобы общее время выполнения проекта было минимальным, сумма вложенных дополнительных средств не превышала величины B, время выполнения каждой работы было не меньше минимально возможного времени dij.
|
|
Математически условия задачи можно записать следующим образом:
Ограничение (2) определяет сумму вложенных дополнительных средств: она не должна превышать величины B. Ограничения (3) показывают, что продолжительность каждой работы должна быть не менее минимально возможной ее продолжительности. Ограничения-равенства (4) показывают зависимость продолжительности каждой работы от вложенных в нее дополнительных средств. Ограничения (5) обеспечивают выполнение условий предшествования работ в соответствии с топологией сети: время начала выполнения каждой работы должно быть не меньше времени окончания непосредственно предшествующих ей работ. (6) — условие неотрицательности.
Если в последнее событие сети п входят сразу несколько работ, то необходимо добавить фиктивную работу (n, n+1), время выполнения которой равно нулю (ton,n+1-tнn,n+1=0 добавить в ограничение (4)). Тогда целевая функция запишется так
tкр=ton,n+1(min)
Постановка задачи 2. Пусть задан срок выполнения проекта to, а расчетное tкр > to. В этом случае оптимизация комплекса работ сводится к сокращению продолжительности критического пути. Задача заключается в определении величины дополнительных вложений xij в отдельные работы проекта, с тем чтобы общий срок его выполнения не превышал заданной величины to, а суммарный расход дополнительных средств был минимальным. Время выполнения каждой работы должно быть не меньше минимально возможного времени dij.
Математическая запись этой задачи:
|
|
Смысл ограничений аналогичен соответствующим ограничениям постановки задачи 1 (1) — (6).
Приведенные постановки задачи относятся к классу задач математического программирования и могут быть решены известными методами в зависимости от вида функций fij (хij). Если предположить, что продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением
где kij — технологические коэффициенты использования дополнительных средств, то будем иметь задачу линейного программирования.