Construction Planning, Schedule and Control
Lecture 12 – Schedule Compression – Simplex Method – Example
Dr. Muhammad Abdullah
Department of Civil Engineering
National University of Computer and Emerging Sciences, Lahore
Crashing as a Linear Programming Problem
Let’s formulate this crashing example as
a linear programming problem
2
Crashing as a Linear Programming Problem
Restatement of the problem: Let Z be the total
cost of crashing activities. The problem then is to
minimize Z, subject to the constraint that project
duration must be less than or equal to the time
desired by the project manager.
3
Crashing as a Linear Programming Problem
• The natural decision variables are xj = reduction in the
duration of activity j due to crashing this activity, for j = A,
B . . . , N.
4
Crashing as a Linear Programming Problem
• By using the last column of the Table, the objective function to
be minimized then is Z = 100,000xA + 50,000xB + … + 60,000xN.
5
Crashing as a Linear Programming Problem
• Each of the 14 decision variables on the right-hand side
needs to be restricted to nonnegative values that do not
exceed the maximum given in the next-to-last column of
the Table.
6
Crashing as a Linear Programming Problem
• To impose the constraint that project duration must be
less than or equal to the desired value (40 weeks), let
yFINISH = project duration, i.e., the time at which the FINISH node in
the project network is reached.
• The constraint then is
yFINISH ≤ 40.
7
Crashing as a Linear Programming Problem
• To help the linear programming model assign the
appropriate value to yFINISH, given the values of xA, xB, . . . ,
xN, it is convenient to introduce into the model the
following additional variables.
yj = start time of activity j (for j = B, C, . . . , N), given the values of xA,
xB, . . . , xN.
• (No such variable is needed for activity A, since an activity
that begins the project is automatically assigned a value
of 0.)
8
Crashing as a Linear Programming Problem
• The start time of each activity (including FINISH) is directly
related to the start time and duration of each of its
immediate predecessors as summarized below.
• For each activity (B, C, . . . , N, FINISH) and each of its immediate
predecessors,
• Start time of this activity ≥ (start time + duration) for this immediate
predecessor.
• Furthermore, by using the normal times from the Table, the
duration of each activity is given by the following formula:
• Duration of activity j = its normal time - xj
9
Crashing as a Linear Programming Problem
• To illustrate these relationships,
consider activity F in the project
network
• Immediate predecessor of activity F:
Activity E, which has duration = 4 - xE
• Relationship between these activities:
yF ≥ yE + 4 - xE
• Thus, activity F cannot start until activity
E starts and then completes its duration
of 4 - xE
10
Crashing as a Linear Programming Problem
• Now consider activity J, which has two
immediate predecessors.
• Immediate predecessors of activity J:
Activity F, which has duration = 5 - xF
Activity I, which has duration = 7 - xI
• Relationships between these activities:
yJ = yF + 5 - xF
yJ = yI + 7 - xI
• These inequalities together say that
activity j cannot start until both of its
predecessors finish.
11
Crashing as a Linear Programming Problem
• By including these relationships for all the activities as
constraints, we obtain the complete linear programming
model given below.
• Minimize Z = 100,000xA + 50,000xB + … + 60,000xN
• subject to the following constraints:
• Maximum reduction constraints
• Nonnegativity constraints
• Start-time constraints
• Project duration constraint
12
Crashing as a Linear Programming Problem
Maximum reduction constraints
• xA ≤ 1, xB ≤ 2, . . . , xN ≤ 3
13
Crashing as a Linear Programming Problem
Nonnegativity constraints
• xA ≥ 0, xB ≥ 0, . . . , xN ≥ 0
• yB ≥ 0, yC ≥ 0, . . . , yN ≥ 0, yFINISH ≥ 0.
14
Crashing as a Linear Programming Problem
Start-time constraints
• Except for activity A (which starts the project), there is one such constraint for
each activity with a single immediate predecessor (activities B, C, D, E, F, G, I, K,
L, M) and two constraints for each activity with two immediate predecessors
(activities H, J, N, FINISH), as listed below.
• In general, the number of start-time constraints for an activity equals its
number of immediate predecessors since each immediate predecessor
contributes one start-time constraint.
15
Crashing as a Linear Programming Problem
Project duration constraint
• yFINISH ≤ 40
16
Solution
17
Crashing as a Linear Programming Problem
Maximum reduction constraints
• xA ≤ 1, xB ≤ 2, xC ≤ 3, xD ≤ 2, xE ≤ 1, xF ≤ 2, xG ≤ 3, xH ≤ 3, xI ≤ 2, xJ ≤
2, xK ≤ 1, xL ≤ 2, xM ≤ 1, xN ≤ 3
18
Crashing as a Linear Programming Problem
Nonnegativity constraints
• xA ≥ 0, xB ≥ 0, . . . , xN ≥ 0
• yB ≥ 0, yC ≥ 0, . . . , yN ≥ 0, yFINISH ≥ 0.
19
Crashing as a Linear Programming Problem
Start-time constraints
One immediate predecessor Two immediate predecessors
• yB ≥ 0 + 2 – xA • yH ≥ yG + 7 – xG
• yC ≥ yB + 4 – xB • yH ≥ yE + 4 – xE
• yD ≥ yC + 10 – xC
• yJ ≥ y F + 5 – xF
• yE ≥ yC + 6 – xC
• yJ ≥ y I + 7 – xI
• yF ≥ yE + 4 – xE
• yN ≥ yK + 4 – xK
• yG ≥ yD + 6 – xD
• yN ≥ yL + 5 – xL
• yI ≥ yC + 10 – xC
• yK ≥ yJ + 8 – xJ • yFINISH ≥ yM + 2 – xM
• yL ≥ yJ + 8 – xJ • yFINISH ≥ yN + 6 – xN
• yM ≥ yH + 9 – xH
20
Crashing as a Linear Programming Problem
Project duration constraint
• yFINISH ≤ 40
21
Crashing as a Linear Programming Problem
Project duration constraint
• Minimize Z = 100,000xA + 50,000xB + 80,000xC + 40,000xD +
160,000xE + 40,000xF + 40,000xG + 60,000xH + 30,000xI + 30,000xJ
+ 40,000xK + 50,000xL + 100,000xM + 60,000xN
22
Solving the Problem Using an
Online Tool
23
Solving the Problem Using an Online Tool
• Rearrange the equations as follows:
• Minimize p = 100000x1 + 50000x2 + 80000x3 + 40000x4 + 160000x5 + 40000x6 + 40000x7 +
60000x8 + 30000x9 + 30000x10 + 40000x11 + 50000x12 + 100000x13 + 60000x14 + 0x15 + 0x16 +
0x17 + 0x18 + 0x19 + 0x20 + 0x21 + 0x22 + 0x23 + 0x24 + 0x25 + 0x26 + 0x27 + 0x28 + 0x29
• subject to x1 + x16 >= 2 x1 <= 1
x2 - x16 + x17 >= 4 x2 <= 2
x3 - x17 + x18 >= 10 x3 <= 3
x3 - x17 + x19 >= 10 x4 <= 2
x5 - x19 + x20 >= 4 x5 <= 1
x4 - x18 + x21 >= 6 x6 <= 2
x3 - x17 + x23 >= 10 x7 <= 3
x10 - x24 + x25 >= 8 x8 <= 3
x10 - x24 + x26 >= 8 x9 <= 2
x8 - x22 + x27 >= 9 x10 <= 2
x5 - x19 + x22 >= 4 x11<= 1
x7 - x21 + x22 >= 7 x12 <= 2
x6 - x20 + x24 >= 5 x13 <= 1
x9 - x23 + x24 >= 7 x14 <= 3
x11 - x25 + x28 >= 4 x29 <= 40
x12 - x26 + x28 >= 5
x13 - x27 + x29 >= 2
x14 - x28 + x29 >= 6
24
Solving the Problem Using an Online Tool
• Solve it using any of the following tools:
• [Link]
• [Link]
• [Link]
25
Thanks
26