Резерв времени и критический путь

1. узел с номером k принадлежит новому критическому пути,

2. если узел с номером j (j£k) принадлежит критическому пути, то номер предшествующего ему узла равен i(j),

3. начальный узел всегда имеет номер 0.

4. узел с номером l принадлежит новому критическому пути,

5. если узел с номером j (j³l) принадлежит критическому пути, то номер следующего за ним узла равен i*(j),

6. конечный узел всегда имеет номер n.

Пример 4.

Для всех дуг (работ) сети из примера 1 определите полный резерв времени, свободный резерв времени и независимый резерв времени.

Необходимо использовать результаты, полученные в примерах 2,3 и сведенные в таблицу 4.

Таблица 4

В таблицу 5 занесем значения резервов времени для всех работ. Анализ таблицы 5 подтверждает результат примера 2, что в данной сети критическим является путь

(0,2)-(2,3)-(3,4)-(4,6)-(6,7)-(7,8),

так как именно для этих работ полный резерв времени равен 0.

Таблица 5

Критический путь представляет собой взаимосвязанную по­следовательность работ и событий — от начального до завер­шающего. Задержка наступления любого события, принадлежащего критическому пути, приведет к задержке срока завершения всего проекта. Напротив, работы и события, не находящиеся на критическом пути, могут быть за­держаны на ненулевой промежуток времени без влияния на срок завершения всего проекта. Например, за­держка события 6 на 4 единицы времени относительно наиболее раннего возможного срока его наступления не по­влияет на срок завершения всего проекта и, более того, не повлияет на начало работы (5,6). Увеличение продолжительности выполнения работы (0,4) на 4 единицы времени приводит к появлению в сети еще одного критического пути

(0,4)-(4,6)-(6,7)-(7,8).

Если увеличить продолжительность работы (5,6) на величину ее полного резерва времени, то в сети появится новый критический путь, которому принадлежит работа (5,6). Найдем его, используя данные таблицы 4:

k=5, i(5)=3, i(3)=2, i(2)=0,

l=6, i*(6)=7, i*(7)=8.

Итак, новый критический путь проходит через узлы 0-2-3-5-6-7-8, и ему принадлежат работы (0,2)-(2,3)-(3,5)-(5,6)-(6,7)-(7,8).

5.5 Оптимизация плана комплексных работ

В предыдущих подразделах для анализа сети был рассмотрен метод критического пути (МКП), при реализации которого продолжительности работ предполагались заданными (фиксированными). Последующие возможные увеличения продолжительностей работ осуществлялись в пределах найденного с помощью МКП значения длины критического пути и без учета высвобождающихся при этом затрат. В этом разделе рассмотрим оптимизационные задачи, возникающие после применения МКП в случае необходимости изменения Tкр.

Предположим, что в сетевом графике продолжительность каждой работы (i,j) не фиксирована, а лишь известен интервал ее изменения [L_ij,U_ij,]. Обозначим продолжительность работы (i,j) переменной y_ij. Тогда, y_ijÎ[L_ij,U_ij,]. Изменение продолжительности работы либо требует дополнительных затрат, если имеется в виду ее более быстрое исполнение, либо приводит к уменьшению затрат, если наблюдается увеличение продолжительности. Будем считать, что зависимость затрат от продолжительности работ линейна, то есть затраты на выполнение работы (i,j) равны b_ij-a_ijy_ij, где b_ij³0, a_ij³0.

Очевидно, что затраты на выполнение всего проекта будут минимальны при y_ij=U_ij. Полагая y_ij=U_ij найдем длину критического пути T^вкр. Если нас не устраивает полученное значение времени исполнения проекта T^вкр, то можно попытаться его уменьшить. Для этого необходимо уменьшить, по меньшей мере, продолжительность критических работ, что потребует дополнительных затрат. Обозначим желаемую продолжительность исполнения проекта T₀. Пусть t_i- неизвестный нам момент наступления i-го события. При сделанных допущениях можно построить математическую модель, предназначенную для минимизации общей стоимости проекта, продолжительность исполнения которого не больше T₀. Математическая модель имеет вид

S (b_ij-a_ijy_ij)® min

(i,j)ÎS t_i,y_ij

t_i +y_ij £ t_j для всех (i,j)ÎS, (3)

t_n- t₀ £ T₀,

L_ij £ y_ij £ U_ij для всех (i,j)ÎS,

где S есть множество всех дуг сети.

Задача (3) позволяет найти оптимальные значения продолжительностей работ y_ij при заданных продолжительности проекта T₀, отношениях предшествования, верхних и нижних пределах продолжительности каждой работы.

Задача линейного программирования (3) эквивалентна задаче (4)

S a_ijy_ij® max

(i,j)ÎS t_i,y_ij

t_i -t_j+y_ij £ 0 для всех (i,j)ÎS, (4)

-t₀ +t_n £ T₀,

L_ij £ y_ij £ U_ij для всех (i,j)ÎS.

Пусть T^пкр есть длина предкритического пути (пути, ближайшего по своей длине к критическому, но меньшего его). Если T₀³T^пкр, то значение T₀ может быть получено вследствие уменьшения продолжительности только тех работ, которые принадлежат критическому пути.

Этот результат позволяет в ситуации, когда T₀>T^пкр, рассматривать вместо задачи (4) более простую задачу (5)

S a_ijy_ij® max

(i,j)ÎКр t_i,y_ij

t_i -t_j+y_ij£0 для всех (i,j)ÎКр, (5)

-t₀+t_n £T₀,

L_ij £ y_ij £ U_ij для всех (i,j)ÎКр, где Кр – множество дуг, принадлежащих критическим путям.

Если критический путь единственен, то задачу (5) можно упростить. Для этого перенумеруем работы, лежащие на критическом пути, 1,2,…,k. Обозначим продолжительности этих работ x_i для i=1,2,…,k. Величины a_ij, отвечающие критическим работам, назовем c_i.

Тогда задачу (5) можно переписать в виде непрерывной задачи о ранце с двухсторонними ограничениями на переменные.

k

S c_ix_i® max

i=1 x_i

k

S x_i £ T₀ (6)

i=1

L_i £ x_i £ U_i для i=1,2,…,k.

Здесь L_i,U_i (i=1,2,…,k) - это значения L_ij,U_ij , соответствующие критическим работам. Для задачи (6) существует простой метод решения.

Алгоритм решения задачи (6).

1. Упорядочим критические работы в порядке убывания значений c_i: i₁,i₂,…,i_k .

2. Полагаем T₀=T₀ -å L_i , j=1, i=1

3. Вычисляем z=min { Ui_j-Li_j,T₀ }, xi_j =Li_j +z. Присваиваем T₀=T₀-z.

4. Если j< k, то увеличиваем j на 1 и переходим к шагу 3.

5. Работа алгоритма завершена.

Пример 5.

Для сетевого графика из примера 1 найти оптимальные значения сроков наступления событий t_i и продолжительностей работ y_ij при заданных продолжительности проекта T₀ =33, отношениях предшествования, определенных в примере 1, верхних и нижних пределах продолжительности каждой работы, заданных в таблице 6.

Таблица 6

Полагаем y_ij=U_ij, и при этих значениях продолжительностей работ методом критического пути проводим анализ сети (см. пример 2). Величина критического пути равна T^вкр =36. Величина предкритического пути равна T^пкр =32. Это означает, что T₀ >T^пкр, и уменьшить время исполнения проекта можно за счет сокращения продолжительности работ, лежащих на критическом пути. Для этого достаточно решить задачу (6), которая в данном случае имеет вид:

3x₁ +6x₂ +0x₃+4x₄ +2x₅ +x₆ ® max

x₁ +x₂ +x₃+x₄ +x₅ +x₆ £33,

4£x₁ £6,

4£x₂ £7,

0£x₃ £0,

8£x₄ £10,

1£x₅ £4,

7£x₆ £9.

Переменные x_i обозначают продолжительность работ, принадлежащих критическому пути. При этом переменная x₃ соответствует фиктивной работе, и поэтому x₃ =0 (далее эту переменную не рассматриваем). Упорядочим переменные в соответствии с убыванием коэффициентов целевой функции {2,4,1,5,6}.

Полагаем T₀=33-(4+4+0+8+1+7)=9.

Тогда, x₂ =4+min{7-4,9}=7, уменьшаем T₀ =9-3=6,

x₄ =8+min{10-8,6}=10, уменьшаем T₀ =6 –2=4,

x₁ =4+min{6-4,4}=6, T₀ =4-2=2,

x₅ =1+min{4-1,2}=3, T₀ =2-2=0,

x₆ =7+min{9-7,0}=7, T₀ =0.

Результаты этого примера приведены в таблице 7. Звездочкой в таблице 7 помечены величины, соответствующие критическим работам и определяемые значением x_i.

Таблица 7

Пример 6.

Для сетевого графика, изображенного на рис. 4, найти оптимальные значения продолжительностей работ y_ij при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и продолжительности проекта T₀ =15.

Рисунок 4.

Таблица 8

Полагая y_ij=L_ij, находим T^нкр. При заданных значениях продолжительностей работ T^нкр=11. Так как T₀ >T^нкр, то задача разрешима. При y_ij= U_ij, величины критического и предкритического путей равны T^вкр =20 и T^пкр =18 соответственно. Это означает, что T₀<T^пкр и нельзя уменьшить время исполнения проекта только за счет сокращения продолжительности работ, лежащих на критическом пути. Таким образом, для определения продолжительности работ необходимо решить задачу (5), которая для данного примера при t₀=0 имеет вид:

y_0,1+8y_0,2+6y_1,2+7y_1,3+5y_2,3® max

y_0,1-t₁ £0

y_0,2-t₂ £0

y_1,2+t₁-t₂£0 (7)

y_1,3+t₁-t₃£0

y_2,3+t₁-t₃£0

t₃£15

2£y_0,1£8

5£y_0,2£10

1£y_1,2£4

4£y_1,3£8

6£y_2,3£8.

Сформулированная задача имеет слишком большую для ручного счета размерность (число ограничений m=16, число переменных n=8, а после приведения задачи к каноническому виду возрастет до n=29). Поэтому для решения задачи рекомендуем воспользоваться программой SIMPLEX, разработанной на кафедре исследования операций и предназначенной для решения задач линейного программирования.

До сих пор мы рассматривали оптимизационные модели, в которых ограничивающим фактором являлась продолжительность проекта T₀. В тех случаях, когда таким фактором является стоимость выполнения проекта C₀, можно сформулировать следующую оптимизационную задачу:

Tкр=t_n-t₀ ® min

t_i,y_ij

t_i - t_j +y_ij£0 для всех (i,j)ÎS,

(8)

S (b_ij-a_ijy_ij) £ C₀

(i,j)ÎS

L_ij £ y_ij £ U_ij для всех (i,j)ÎS.

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

Пусть С^н – затраты на выполнение проекта при y_ij=U_ij. Задача (8) разрешима тогда и только тогда, когда С ₀³C^н.

Задача (8) эквивалентна задаче линейного программирования (9):

Tкр=t_n-t₀ ® min

t_i,y_ij

t_i +y_ij £t_j для всех (i,j)ÎS,

(9)

S a_ijy_ij ³ D₀, где D₀= S b_ij -C₀,

(i,j)ÎS (i,j)ÎS

L_ij £ y_ij £ U_ij для всех (i,j)ÎS.

Задачу (9) как и задачу (4) можно решить симплекс-методом. Для этого можно воспользоваться программой SIMPLEX.

Пример 6.

Для сетевого графика изображенного на рис. 2 найти оптимальные значения продолжительностей работ y_ij, минимизирующих время выполнения проекта в целом при заданных в таблице 8 отношениях предшествования, верхних и нижних пределах продолжительности каждой работы и D₀ =201.

Задача (9) для данного примера при t₀=0 имеет вид:

t₃® min

y_0,1-t₁ £0

y_0,2-t₂ £0

y_1,2+t₁-t₂£0

y_1,3+t₁-t₃£0 (10)

y_2,3+t₁-t₃£0

y_0,1+8y_0,2+6y_1,2+7y_1,3+5y_2,3³201

2£y_0,1£8

5£y_0,2£10

1£y_1,2£4

4£y_1,3£8

6£y_2,3£8.

В результате работы программы было получено следующее оптимальное решение y_0,1=6, y_0,2=10, y_1,2=4, y_1,3=8, y_2,3=7, t ₁=6, t₂=10, Tкр=t ₃=17.