This file shows how to solve the CMP project crashing problem for the Tinker Construction Company from Hillier and Lieberman, Section 9.8 exercises.

In [1]:
from pyomo.environ import *
from pyomo.opt import *
opt = solvers.SolverFactory("glpk")

In the following, we define the raw data for this problem. Deps encodes the arcs of the dependency graph, and ActivityData encodes the following data for each activity: Duration without crashing, duration with maximal crashing, cost without crashing, cost with maximal crashing.

In [2]:
Deps = (('A','C'),
        ('B','D'),
        ('C','Finish'),
        ('D','Finish'))

ActivityData = {'A':(8,5,25,40),
                'B':(9,7,20,30),
                'C':(6,4,16,24),
                'D':(7,4,27,45)}

total_time = 12

From the raw data, we extract the following data needed in the model: A is the list of all activities, N is the list of all nodes (except for the starting node which does not feature explicitly in the model), T is the dictionary of regular completion times for each activity, U is the dictionary of upper bounds on the time that can be saved by crashing, and C is the additional cost of crashing per time saved.

In [3]:
A = list(ActivityData.keys())
N = A + ['Finish']

C = {}
T = {}
U = {}
for a in A:
    T[a] = ActivityData[a][0]
    U[a] = T[a] - ActivityData[a][1]
    C[a] = (ActivityData[a][3]-ActivityData[a][2])/U[a]

The decision variables are x, the time saved by crashing on each activity, and s, the starting time of each activity.

In [4]:
model = ConcreteModel()
model.x = Var(A, within=NonNegativeReals)
model.s = Var(N, within=NonNegativeReals)

Now the model: Minimize $$ \sum_{i \in A} x_i \, C_i $$ subject to $x_i \leq U_i$ for $i \in A$, $t_{\text{Finish}} \leq 12$, and $$ s_i + T_i - x_i \leq s_j $$ whenever activity $j$ depends on activity $i$.

In [5]:
def crash_time_rule(model, n):
    return model.x[n] <= U[n]
    
model.c = Constraint(A, rule=crash_time_rule)

def dep_rule(model, i, j):
    return model.s[i] + T[i] - model.x[i] <= model.s[j]

model.d = Constraint(Deps, rule=dep_rule)

model.finish = Constraint(expr = model.s['Finish'] <= total_time)

model.cost = Objective(expr = sum(model.x[i]*C[i] for i in A), sense=minimize)

Now we solve and output the crashing time on each activity:

In [6]:
model.dual = Suffix(direction=Suffix.IMPORT)
results = opt.solve(model)
model.x.get_values()
Out[6]:
{'A': 0.0, 'B': 2.0, 'C': 2.0, 'D': 2.0}

And the starting time of each activity:

In [7]:
model.s.get_values()
Out[7]:
{'A': 0.0, 'B': 0.0, 'C': 8.0, 'D': 7.0, 'Finish': 12.0}

These are the shadow prices of each activity. In this example, they can be interpreted as the increase in total cost for each unit of decrease of the regular completion time. (The shadow prices come out negative, i.e., the total cost in fact decreases as each activity takes less time.)

In [8]:
for i in Deps:
    print (i, model.dual[model.d[i]])

('A', 'C') -5.0
('B', 'D') -6.0
('C', 'Finish') -5.0
('D', 'Finish') -6.0

And these are the duals of the maximal crashing time. A non-zero value indicates that this activity is maximally crashed.

In [9]:
for i in A:
    print (i, model.dual[model.c[i]]) 

C -1.0
D 0.0
B -1.0
A 0.0