|
1 /* CPP, Critical Path Problem */ |
|
2 |
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
|
4 |
|
5 /* Note: Reduced costs of auxiliary variables phi[j,k] (see below) |
|
6 can be only zero or one. The critical path is defined by the |
|
7 constraints, whose reduced cost is one. */ |
|
8 |
|
9 set J; |
|
10 /* set of jobs (activities) */ |
|
11 |
|
12 set P{j in J}, in J, default {}; |
|
13 /* P[j] is a subset of jobs that immediately precede job j */ |
|
14 |
|
15 param t{j in J}, >= 0; |
|
16 /* duration required to perform job j */ |
|
17 |
|
18 var x{j in J}, >= 0; |
|
19 /* starting time of job j */ |
|
20 |
|
21 s.t. phi{j in J, k in P[j]}: x[j] >= x[k] + t[k]; |
|
22 /* job j can start only after all immediately preceding jobs have been |
|
23 completely performed */ |
|
24 |
|
25 var z; |
|
26 /* project makespan */ |
|
27 |
|
28 s.t. fin{j in J}: z >= x[j] + t[j]; |
|
29 /* which is the maximum of the completion times of all the jobs */ |
|
30 |
|
31 minimize obj: z; |
|
32 /* the objective is make z as small as possible */ |
|
33 |
|
34 data; |
|
35 |
|
36 /* The optimal solution is 46 */ |
|
37 |
|
38 param : J : t := |
|
39 A 3 /* Excavate */ |
|
40 B 4 /* Lay foundation */ |
|
41 C 3 /* Rough plumbing */ |
|
42 D 10 /* Frame */ |
|
43 E 8 /* Finish exterior */ |
|
44 F 4 /* Install HVAC */ |
|
45 G 6 /* Rough electric */ |
|
46 H 8 /* Sheet rock */ |
|
47 I 5 /* Install cabinets */ |
|
48 J 5 /* Paint */ |
|
49 K 4 /* Final plumbing */ |
|
50 L 2 /* Final electric */ |
|
51 M 4 /* Install flooring */ |
|
52 ; |
|
53 |
|
54 set P[B] := A; |
|
55 set P[C] := B; |
|
56 set P[D] := B; |
|
57 set P[E] := D; |
|
58 set P[F] := D; |
|
59 set P[G] := D; |
|
60 set P[H] := C E F G; |
|
61 set P[I] := H; |
|
62 set P[J] := H; |
|
63 set P[K] := I; |
|
64 set P[L] := J; |
|
65 set P[M] := K L; |
|
66 |
|
67 end; |