Building a house (Harvard Business Review, 1963)

Several tasks must be completed in order to build our house. Each task has a duration, tasks may be worked on simultaneously, but there is also a precedence relation. Some tasks can only be started once other tasks have been completed. The following table shows each task, it's duration, and the tasks that must be completed before it starts. How fast can the house be built? alt text

Problem Data

In [1]:
# this array stores the task names (:a, :b, ..., :x)
tasks = []
for i = 'a':'x'
    push!(tasks, Symbol(i))    # string(sym) converts back to a string, i.e. string(:hello) returns "hello"
end

# this dictionary stores the project durations
dur = [0, 4, 2, 4, 6, 1, 2, 3, 2, 4, 10, 3, 1, 2, 3, 2, 1, 1, 2, 3, 1, 2, 5, 0]
duration = Dict(zip(tasks,dur))

# this dictionary stores the projects that a given project depends on (ancestors)
pre = ( [], [:a], [:b], [:c], [:d], [:c], [:f], [:f], [:d], [:d,:g], [:i,:j,:h], [:k],
    [:l], [:l], [:l], [:e], [:p], [:c], [:o,:t], [:m,:n], [:t], [:q,:r], [:v], [:s,:u,:w])
pred = Dict(zip(tasks,pre));

Problem Model

In [3]:
using JuMP,Clp
m = Model(solver=ClpSolver())

@variable(m, tstart[tasks])

# one-line implementation of the constraints:
# @constraint(m, link[i in tasks, j in pred[i]], tstart[i] >= tstart[j] + duration[j])

for i in tasks
    for j in pred[i]
        @constraint(m, tstart[i] >= tstart[j] + duration[j])
    end
end
@constraint(m, tstart[:a] == 0)
@objective(m, Min, tstart[:x] + duration[:x])     # total duration is start time of last task + duration of last task.

solve(m)
println(getvalue(tstart))
println("minimum duration: ", getobjectivevalue(m))
tstart: 1 dimensions:
[a] = -0.0
[b] = -0.0
[c] = 4.0
[d] = 6.0
[e] = 10.0
[f] = 6.0
[g] = 8.0
[h] = 11.0
[i] = 12.0
[j] = 10.0
[k] = 14.0
[l] = 24.0
[m] = 28.0
[n] = 27.0
[o] = 29.0
[p] = 16.0
[q] = 18.0
[r] = 18.0
[s] = 32.0
[t] = 29.0
[u] = 33.0
[v] = 19.0
[w] = 29.0
[x] = 34.0
minimum duration: 34.0
In [ ]: