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