Question

Consider the following activity-on-arc project network, where the 12 arcs (arrows) represent the 12 activities (tasks) that must be performed to complete the project and the network displays the order in which the activities need to be performed. The number next to each arc (arrow) is the time required for the corresponding activity. Consider the problem of finding the longest path (the largest total time) through this network from start (node 1) to finish (node 9), since the longest path is the critical path.

(a) Formulate the network flow model for the corresponding diagram.

(b) What is the logical resoning behind the fact that the longest path in a network is chosen to be the critical path.

Answer 1

Decision variable:

Xij­ = 1, the arc from node i to node j is chosen in the optimal (longest) path otherwise Xij­ = 0

Objective Function:

Maximize the total time required from node 1 to node 9:

Max. Z = ∑(cij)(Xij)

Where, cij = time taken by arc (activity) from ith node and jth node
MAx Z. = 5X12 + 3X13 + 3X35 + 2X25 + 4X24 + 4X47 + 1X46 + 2X58 + 6X57 + 6X57 + 5X69 + 4X79 + 7X89

Constraint:

For longest route problem, following constraint are to be satisfied,

For origin Node 1, outgoing arc is equal to 1,

X12 + X13 = 1

For intermediate nodes,

Arc in = arc out

For node 2: X12 = X25 + X24 or X12 – X25 - X24 = 0  

For node 3: X13 = X35 or X13 – X35 = 0

For node 4: X24 = X46 + X47 or X24 – X46 – X47 = 0

For node 5: X25 + X35 = X57 + X58 or X25 + X35 - X57 - X58 = 0

For node 6: X46 = X69 or X46 – X69 = 0

For node 7: X57 + X47 = X79 or X57 + X47 – X79 = 0

For node 8: X58 = X89 or X58 – X89 = 0

For destination node:

Arc in = 1

For node 9, X69 + X79 + X89 = 1