You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
67 lines
1.6 KiB
67 lines
1.6 KiB
/* CPP, Critical Path Problem */
|
|
|
|
/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
|
|
|
|
/* Note: Reduced costs of auxiliary variables phi[j,k] (see below)
|
|
can be only zero or one. The critical path is defined by the
|
|
constraints, whose reduced cost is one. */
|
|
|
|
set J;
|
|
/* set of jobs (activities) */
|
|
|
|
set P{j in J}, in J, default {};
|
|
/* P[j] is a subset of jobs that immediately precede job j */
|
|
|
|
param t{j in J}, >= 0;
|
|
/* duration required to perform job j */
|
|
|
|
var x{j in J}, >= 0;
|
|
/* starting time of job j */
|
|
|
|
s.t. phi{j in J, k in P[j]}: x[j] >= x[k] + t[k];
|
|
/* job j can start only after all immediately preceding jobs have been
|
|
completely performed */
|
|
|
|
var z;
|
|
/* project makespan */
|
|
|
|
s.t. fin{j in J}: z >= x[j] + t[j];
|
|
/* which is the maximum of the completion times of all the jobs */
|
|
|
|
minimize obj: z;
|
|
/* the objective is make z as small as possible */
|
|
|
|
data;
|
|
|
|
/* The optimal solution is 46 */
|
|
|
|
param : J : t :=
|
|
A 3 /* Excavate */
|
|
B 4 /* Lay foundation */
|
|
C 3 /* Rough plumbing */
|
|
D 10 /* Frame */
|
|
E 8 /* Finish exterior */
|
|
F 4 /* Install HVAC */
|
|
G 6 /* Rough electric */
|
|
H 8 /* Sheet rock */
|
|
I 5 /* Install cabinets */
|
|
J 5 /* Paint */
|
|
K 4 /* Final plumbing */
|
|
L 2 /* Final electric */
|
|
M 4 /* Install flooring */
|
|
;
|
|
|
|
set P[B] := A;
|
|
set P[C] := B;
|
|
set P[D] := B;
|
|
set P[E] := D;
|
|
set P[F] := D;
|
|
set P[G] := D;
|
|
set P[H] := C E F G;
|
|
set P[I] := H;
|
|
set P[J] := H;
|
|
set P[K] := I;
|
|
set P[L] := J;
|
|
set P[M] := K L;
|
|
|
|
end;
|