Как определить, какие элементы находятся на критическом пути в GAMS?

Это мой текущий код в GAMS. Да, я знаю, что это может быть более кратким, но потерпите меня здесь:

set activity /a*q/;

parameter duration (activity) "in days"
/a 15, b 4, c 5, d 10, e 4, f 15, g 15, h 5, i 5, j 10, k 4, l 3, m 4, n 20, o 5,
p 2, q 2/;

alias (activity, x, y);

set prec(x,y) "Precedence Order"

/A.(B,C,D)
(B,C,D).E
E.(F,G,H)
F.N
G.(K,I) 
H.I
K.M
I.J
J.L
L.M
M.N
N.O
O.P
P.Q/            ;

Free Variable
T Completion Time; 

Nonnegative Variables
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q;

equations
t_A, t_B, t_C, t_D, t_E, t_F, t_G, t_H, t_I, t_J, t_K, t_L, t_M, t_N, t_O, t_P,
t_Q, s_AB, s_AC, s_AD, s_BE, s_CE, s_DE, s_EF, s_EG, s_EH, s_FN, s_GK, s_GI,
s_HI, s_KM, s_IJ, s_JL, s_LM, s_MN, s_NO, s_OP, s_PQ;

t_A.. T =G= A + 15;
t_B.. T =G= B + 4;
t_C.. T =G= C + 5;
t_D.. T =G= D + 10;
t_E.. T =G= E + 4;
t_F.. T =G= F + 15;
t_G.. T =G= G + 15;
t_H.. T =G= H + 5;
t_I.. T =G= I + 5;
t_J.. T =G= J + 10;
t_K.. T =G= K + 4;
t_L.. T =G= L + 3;
t_M.. T =G= M + 4;
t_N.. T =G= N + 20;
t_O.. T =G= O + 5;
t_P.. T =G= P + 2;
t_Q.. T =G= Q + 10;

s_AB.. A + 15 =L= B;
s_AC.. A + 15 =L= C;
s_AD.. A + 15 =L= D;
s_BE.. B + 4 =L= E;
s_CE.. C + 5 =L= E;
s_DE.. D + 10 =L= E;
s_EF.. E + 4 =L= F;
s_EG.. E + 4 =L= G;
s_EH.. E + 4 =L= H;
s_FN.. F + 15 =L= N;
s_GK.. G + 15 =L= K;
s_GI.. G + 15 =L= I;
s_HI.. H + 5 =L= I;
s_KM.. K + 4 =L= M;
s_IJ.. I + 5 =L= J;
s_JL.. J + 10 =L= L;
s_LM.. L + 3 =L= M;
s_MN.. M + 4 =L= N;
s_NO.. N + 20 =L= O;
s_OP.. O + 5 =L= P;
s_PQ.. P + 2 =L= Q;

model thesis /all/;
solve thesis using lp minimizing t;
display t.l;

Этот код дает мне массу деталей, например, в какие дни я должен начинать каждое действие. Однако он не говорит мне (насколько я понимаю), какие действия находятся на критическом пути. Как я могу определить это с помощью GAMS?


linear-programming gams-math
person Priya Bansal    schedule 17.09.2015    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Зависимость находится на критическом пути, если маргинал уравнения зависимости (s_AB и т. д. в вашей формулировке) равен -1. Вы можете проверить это в файле листинга (.lst) или с помощью кода ниже:

set activity /a*q/;

parameter duration (activity) "in days"
/a 15, b 4, c 5, d 10, e 4, f 15, g 15, h 5, i 5, j 10, k 4, l 3, m 4, n 20, o 5,
p 2, q 2/;

alias (activity, x, y);

set prec(x,y) "dependency Order"

/A.(B,C,D)
(B,C,D).E
E.(F,G,H)
F.N
G.(K,I) 
H.I
K.M
I.J
J.L
L.M
M.N
N.O
O.P
P.Q/;

Free Variable
T Completion Time; 

Nonnegative Variables
start(x);

equations
t_bound(x)
dependency(x,y);

t_bound(x).. T =G= start(x) + duration(x);

dependency(x,y)$prec(x,y).. start(x) + duration(x) =l= start(y);

model thesis /all/;
solve thesis using lp minimizing t;

set criticalpath(x,y);
criticalpath(x,y) = 1$(dependency.M(x,y) < 0);

display t.l, criticalpath;
person jebob    schedule 08.08.2017

arrow_upward
-1
arrow_downward

Насколько я понял, это проблема планирования проекта без ограничений по ресурсам.

В этом случае действия со временем начала, равным самому раннему времени начала, и временем окончания, равным самому позднему времени окончания, находятся на критическом пути.

Другими словами, критически важные действия не имеют люфта.

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

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

надеюсь это поможет.

person m3d    schedule 22.06.2017