This notebook implements the solution to Question 4 on the Fall 2017 final exam.

from pyomo.environ import *
from pyomo.opt import *
opt = solvers.SolverFactory("glpk")

The following defines the problem data. Deps is a list of all the arcs in the dependency graph. The arcs starting from START do not need to be listed explicitly; (A,B) means T is a dictionary with the completion times of each task.

Deps = (('A','B'),
        ('A','F'),
        ('B','C'),
        ('C','D'),
        ('C','G'),
        ('D','FINISH'),
        ('E','C'),
        ('F','D'),
        ('G','FINISH'))

T = {'A':4,
     'B':1,
     'C':2,
     'D':5,
     'E':10,
     'F':4,
     'G':3}

A = list(T.keys())
N = A + ['FINISH']

model = ConcreteModel()
model.s = Var(N, within=NonNegativeReals)

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

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

model.cost = Objective(expr = model.s['FINISH']*1000 + 
                       (model.s['G'] + T['G'] - model.s['A'])*5000)

results = opt.solve(model)
model.s.get_values()

{'A': 5.0,
 'B': 9.0,
 'C': 10.0,
 'D': 13.0,
 'E': 0.0,
 'F': 9.0,
 'FINISH': 18.0,
 'G': 12.0}

model.cost.expr()

68000.0