Оптимизация проекта по времени

Оптимизация проекта по времени сводится к сокращению продолжительности критического пути за счет привлечения дополнительных средств (количество рабочих, сверхурочное время). Эта задача возникает, когда критическое время выполнения комплекса операций превышает заданный срок .

Рассмотрим два примера постановки задачи оптимизации проекта по времени с привлечением дополнительных средств.

Постановка задачи 1. Задан сетевой график выполнения проекта, где Е – множество событий, а – множество работ. Продолжительность каждой работы равна . Известно, что вложение дополнительных средств в работу (i, j)сокращает время ее выполнения от до ,причем эта зависимость выражается как ( – известные функции). Для каждой работы существует минимально возможное время ее выполнения , таким образом, сокращение продолжительности работы не беспредельно.

Требуется определить количество дополнительных вложений средств в отдельные работы проекта, а также время начала и окончания выполнения работ, чтобы проект был выполнен в заданный срок , время выполнения каждой работы было не меньше минимально возможного времени , и сумма вложенных дополнительных средств была минимальной.

Математическая запись этой задачи представлена в таблице 1.

Постановка задачи 2 аналогична постановке задачи 1, с тем отличием, что срок выполнения проекта сокращается на сколько это возможно за счет вложения суммы дополнительных средств , не превышающей величины B.

Требуется определить количество дополнительных средств ,которые необходимо вложить в отдельные работы (i, j) проекта, а также время начала и окончания выполнения работ, чтобы проект был выполнен в заданный срок , время выполнения каждой работы было не меньше минимально возможного времени , и сумма вложенных дополнительных средств была минимальной и не превышала величины B.

Математически условия задачи можно записать так, как показано в таблице 1.

Таблица 1

Постановка задачи 1	Постановка задачи 2
Целевая функция минимизации суммы вложенных дополнительных средств	Целевая функция минимизации общего времени выполнения проекта
Ограничение по времени окончания проекта (должно быть не больше заданного ):	Ограничение по сумме вложенных дополнительных средств, которая не должна превышать величины B
Ограничение по продолжительности каждой работы (продолжительность должна быть не менее минимально возможной ее продолжительности ):
Ограничения-равенства, показывающие зависимость продолжительности каждой работы от вложенных в нее дополнительных средств:
Ограничения, обеспечивающие выполнение условий предшествования работ: время начала выполнения каждой работы должно быть не меньше времени окончания предшествующих ей работ:
Условие неотрицательности искомых величин:

Приведенные постановки задачи относятся к классу задач математического программирования и могут быть решены известными методами в зависимости от вида функций . Если предположить, что продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением

где – технологические коэффициенты использования дополнительных средств, то будем иметь задачу линейного программирования.

Если в последнее событие сети п входят сразу несколько работ, то на сетевой график необходимо добавить фиктивную работу (n, n +1), время выполнения которой равно нулю. К ограничениям-равенствам, показывающим зависимость продолжительности каждой работы от вложенных в нее дополнительных средств, добавится ограничение . Целевая функция запишется так: .

Пример 1. Для сокращения срока реализации проекта, представленного сетевым графиком (рисунок 1), заказчик выделил дополнительные средства. Продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением . Известно, что k _l2 = 0,1; k ₁₃ = 0,2; k ₂₃ = 0,5; k ₂₄ = 0,3; k ₃₅ = 0,6; k ₄₅ = 0,1.Над каждой работой поставлена ее продолжительность и минимально возможное время выполнения d_ij.

Рисунок 1

Требуется оптимизировать сетевой график по времени, то есть найти такие , , , чтобы:

а) время выполнения всего проекта не превышало 24 ед.;

б) продолжительность выполнения каждой работы была не меньше заданной величины ;

в) суммарный расход дополнительных средств был минимальным.

Запишем условие задачи на листе Excel и решим ее (рисунки 2-4).

Рисунок 2

Рисунок 3

Рисунок 4

Пример 2. Для сокращения срока реализации проекта, представленного сетевым графиком (рисунок 4), заказчик выделил 14 ед. дополнительных средств. Продолжительность выполнения работ линейно зависит от дополнительно вложенных средств и выражается соотношением . Известно, что k _l2 = 0,1; k ₁₃ = 0,2; k ₂₃ = 0,5; k ₂₄ = 0,3; k ₃₅ = 0,6; k ₄₅ = 0,1.Над каждой работой поставлена ее продолжительность и минимально возможное время выполнения d_ij.

Рисунок 4

Требуется оптимизировать сетевой график по времени, то есть найти такие , , , чтобы:

а) время выполнения всего проекта было минимальным;

б) продолжительность выполнения каждой работы была не меньше заданной величины ;

в) сумма дополнительно вложенных средств не превышала 14 ед.

Запишем условие задачи на листе Excel и решим ее (рисунки 2-4).

Рисунок 5

Рисунок 6

Рисунок 6

Таким образом, при дополнительном вложении 14 ед. комплекс работ может быть выполнен за 30 ед. времени. При этом средства распределятся следующим образом: 4 ед. в работу (2, 3) и 10 ед. в работу (3, 5) (Рис.4).