Consider the (simplified) list of activities and predecessors that are involved in building a house (Table). Immediate Duration Activity Description Predecessors (Days) A Build foundation — 5 B Build...

Solution
Consider the (simplified) list of activities and predecessors that are involved in building a house, as listed in Table 1.
    Activity
    Description
    Predecessors
    Duration (days)
    Activity A
    Build foundation
    —
    5
    Activity B
    Build walls and ceilings
    A
    8
    Activity C
    Build roof
    B
    10
    Activity D
    Do electrical wiring
    B
    5
    Activity E
    Put in windows
    B
    4
    Activity F
    Put on siding
    E
    6
    Activity G
    Paint house
    C, F
    3
Table 1: House-Building Activities
a. Draw a project network and use LP to find the critical path and the minimum number of days needed to build the house.
Here is one possible network diagram (an activity-on-arc diagram). The arrows (arcs) represent activities; the balls (nodes) have been numbered for ease of discussion:
1
0
Start
4
3
2
A
5
B
8
C
10
E
4
D
5
G
3
F
6
5
End
Managerial Formulation
Decision Variables
We are trying to decide when to begin and end each of the activities.
Objective
Minimize the total time to complete the project.
Constraints
Each activity has a fixed duration.
There are precedence relationships among the activities.
We cannot go backwards in time.
Mathematical Formulation
This is an example of a type of project-scheduling problem that can be solved with the Critical Path Method (CPM). These problems can be solved by hand, or with any of a large number of project management software packages. They can also be solved using linear programming, as is demonstrated here.
Decision Variables
Define the nodes to be discrete events. In other words, they occur at one exact point in time. Our decision variables will be these points in time.
Define ti to be the time at which node i occurs, and at which time all activities preceding node i have been completed.
Define t0 to be zero.
Objective
Minimize t5.
Constraints
There is really one basic type of constraint. For each activity x, let the time of its starting node be represented by tjx and the time of its ending node be represented by tkx. Let the duration of activity x be represented as dx.
For every activity x,
x
jx
kx
d
t
t
³
-
For every node i,
0
³
i
t

Solution Methodology
Here’s the spreadsheet...