CHAPTER FIVE

NETWORK MODELING
 NETWORKS

• Network
• A set of nodes and connecting arcs or branches. Can be useful in
representing various systems, such as distribution systems, production
systems, and transportation systems.
• Network models are an important approach for problem solving because:
• They can be used to model a wide range of problems.
• They are relatively simple to work with
• They provide a visual portrayal of a problem.
Network Models Are:

Basic Network Applications

 Shortest Path Problem
 Minimal Spanning Tree
 Maximum Flow Problem

Project Management
 Critical Path Method (CPM)
 Program Evaluation Review Technique (PERT)
A SIMPLE NETWORK DIAGRAM
 NETWORK DIAGRAMS

• Activity-on-Node (AON):
• Uses nodes to represent the activity
• Uses arrows to represent precedence relationships
 SHORTEST- ROUTE PROBLEM

• The shortest route problem determines the shortest route

between a source and destination.
• In order to determine the shortest time, distance, or cost
from an origin to a destination through a network.
EXAMPLE
EXAMPLESHORTEST
SHORTESTROUT
ROUT

Labeling Procedure
A label is developed for each node. The labels
consist of two numbers separated by a
comma: The first number refers to the
distance from Node 1 to the labeled node
along a certain path, while the second
number refers to the node that immediately
precedes this node along that path.
EXAMPLE
EXAMPLE8-1
8-1(CONT’D)
(CONT’D)
EXAMPLE
EXAMPLE8-1
8-1(CONT’D)
(CONT’D)
FIGURE 8–2 NETWORK FOR TRI-STATE SHIPPING COMPANY
SHORTEST-ROUTE
PROBLEM
 FIGURE 8–3 NETWORK FOR OIL PIPELINE PROBLEM

Note: Arc lengths are not precisely proportional to the distances shown on the arcs.
 MINIMAL SPANNING TREE

• It deals with linking the nodes of network, directly or indirectly,

using shortest length of connecting branches.
• The typical application occurs in construction of paved roads that
link several towns.
• In order to determining the minimum distance (cost, time) needed to
connect a set of locations into a single system.
EXAMPLE
EXAMPLE8-3
8-3
EXAMPLE
EXAMPLE8-3
8-3(CONT’D)
(CONT’D)
EXAMPLE
EXAMPLE8-3
8-3(CONT’D)
(CONT’D)
 MAXIMAL FLOW ALGORITHM

• In a maximal flow problem, we seek to find the maximum volume of flow from a source node to
terminal sink node in a capacitated network.

• Maximum flow algorithm is straightforward.

 HOW IT WORKS

• In maximum flow algorithm, we determine if there is any path from source to sink that can carry
flow.

• If there is , the flow is augmented as much as possible along this path; and residual capacities of
the arc used on the path are reduced accordingly.
STEPS OF MAXIMUM FLOW ALGORITHM

• Step1: find path from the source to the sink that has positive
residual capacities. If no path have positive, STOP; the maximum
flow have been found
• Step2: Find the minimum residual capacity of the arc on the path
( call it K) and augment the flow on each involved arc by K
• Step3: Adjust the residual capacities of arcs on the path by
decreasing the residual capacities in direction of flow by K; and
increasing the residual capacities in the direction opposite the flow
by K;
GO TO STEP 1
EXAMPLE A FLOW NETWORK
FIGURE 8–5 UPDATED FLOW NETWORK
FIGURE 8–6 SECOND REVISION OF THE NETWORK
FIGURE 8–7 THIRD REVISION OF FLOW NETWORK
FIGURE 8–8 FINAL SOLUTION FOR FLOW NETWORK EXAMPLE
FIGURE 8–9 FLOW NETWORK FOR DEMONSTRATION OF REVERSE FLOW
FIGURE 8–10 FLOW NETWORK FOR DEMONSTRATION OF REVERSE FLOW
FIGURE 8–11 REVISED FLOW NETWORK
NETWORK PLANNING TECHNIQUES
PROJECT MANAGEMENT
• Program Evaluation & Review Technique (PERT):
• Developed to manage the Polaris missile project
• Many tasks pushed the boundaries of science & engineering (tasks’
duration = probabilistic)

• Critical Path Method (CPM):

• Developed to coordinate maintenance projects in the chemical
industry
• A complex undertaking, but individual tasks are routine (tasks’
duration = deterministic)
 BOTH PERT AND CPM

• Graphically display the precedence relationships & sequence of

activities
• Estimate the project’s duration
• Identify critical activities that cannot be delayed without delaying the
project
• Estimate the amount of slack associated with non-critical activities
 CLASSIFICATION OF ACTIVITIES

• Predecessor activity: Activities that must be completed immediately prior

to the start of another activity are called predecessor activities.

• Successor activity : activities that cannot be started until one or more of

other activities are completed but immediately succeed them are called
successor activities.

• Concurrent activities: activities that can be accomplished together are

known as concurrent activities.

• Dummy activity: An activity which does not consume any resource but
merely depicts the dependence of one activity on other is called dummy
activity. It is introduced in a network when two or more parallel activities
have the same start and finish nodes.
 NETWORK DIAGRAMS

• Once again look Activity-on-Node (AON):

• Uses nodes to represent the activity
• Uses arrows to represent precedence relationships
 Step 1-define The Project: Cables By US Is Bringing A New
Product On Line To Be Manufactured In Their Current Facility In
Existing Space. The Owners Have Identified 11 Activities And
Their Precedence Relationships. Develop An AON For The Project.

Immediate Duration
Activity Description
Predecessor (weeks)
A Develop product specifications None 4
B Design manufacturing process A 6
C Source & purchase materials A 3
D Source & purchase tooling & equipment B 6
E Receive & install tooling & equipment D 14
F Receive materials C 5
G Pilot production run E&F 2
H Evaluate product design G 2
I Evaluate process performance G 3
J Write documentation report H&I 4
K Transition to manufacturing J 2
STEP 2- DIAGRAM THE NETWORK FOR
CABLES BY US
STEP 3 (A)- ADD DETERMINISTIC TIME
ESTIMATES AND CONNECTED PATHS
STEP 3 (A) (CON’T): CALCULATE THE
PROJECT COMPLETION TIMES
Paths Path duration
ABDEGHJK 40
ABDEGIJK 41
ACFGHJK 22
ACFGIJK 23
• The longest path (ABDEGIJK) limits the project’s
duration (project cannot finish in less time than its
longest path)
• ABDEGIJK is the project’s critical path
 SOME NETWORK DEFINITIONS

• All activities on the critical path have zero slack

• Slack defines how long non-critical activities can be delayed
without delaying the project
• Slack = the activity’s late finish minus its early finish (or its late
start minus its early start)
• Earliest Start (ES) = the earliest finish of the immediately
preceding activity
• Earliest Finish (EF) = is the ES plus the activity time
• Latest Start (LS) and Latest Finish (LF) = the latest an activity can
start (LS) or finish (LF) without delaying the project completion
ES, EF NETWORK
LS, LF NETWORK
 CALCULATING SLACK
Late Early Slack
Activity
Finish Finish (weeks)
A 4 4 0
B 10 10 0
C 25 7 18
D 16 16 0
E 30 30 0
F 30 12 18
G 32 32 0
H 35 34 1
I 35 35 0
J 39 39 0
K 41 41 0
 REVISITING CABLES BY US USING
PROBABILISTIC TIME ESTIMATES
Optimistic Most likely Pessimistic
Activity Description
time time time
A Develop product specifications 2 4 6
B Design manufacturing process 3 7 10
C Source & purchase materials 2 3 5
D Source & purchase tooling & equipment 4 7 9
E Receive & install tooling & equipment 12 16 20
F Receive materials 2 5 8
G Pilot production run 2 2 2
H Evaluate product design 2 3 4
I Evaluate process performance 2 3 5
J Write documentation report 2 4 6
K Transition to manufacturing 2 2 2
 USING BETA PROBABILITY DISTRIBUTION TO
CALCULATE EXPECTED TIME DURATIONS
• A typical beta distribution is shown below, note that it has definite end points
• The expected time for finishing each activity is a weighted average

optimistic  4most likely   pessimisti c

Exp. time 
6
CALCULATING EXPECTED TASK
TIMES
optimistic  4most likely   pessimisti c
Expected time 
6
Optimistic Most likely Pessimistic Expected
Activity
time time time time
A 2 4 6 4
B 3 7 10 6.83
C 2 3 5 3.17
D 4 7 9 6.83
E 12 16 20 16
F 2 5 8 5
G 2 2 2 2
H 2 3 4 3
I 2 3 5 3.17
J 2 4 6 4
K 2 2 2 2
NETWORK DIAGRAM WITH EXPECTED
ACTIVITY TIMES
ESTIMATED PATH DURATIONS THROUGH
THE NETWORK

Activities on paths Expected duration

ABDEGHJK 44.66
ABDEGIJK 44.83
ACFGHJK 23.17
ACFGIJK 23.34

• ABDEGIJK is the expected critical path & the

project has an expected duration of 44.83 weeks
ADDING ES AND EF TO NETWORK
 GANTT CHART SHOWING EACH ACTIVITY
FINISHED AT THE EARLIEST POSSIBLE START
DATE
ADDING LS AND LF TO NETWORK
 GANTT CHART SHOWING THE LATEST
POSSIBLE START TIMES IF THE PROJECT IS TO
BE COMPLETED IN 44.83 WEEKS
 ESTIMATING THE PROBABILITY OF
COMPLETION DATES

• Using probabilistic time estimates offers the advantage of predicting the probability of project
completion dates
• We have already calculated the expected time for each activity by making three time estimates
• Now we need to calculate the variance for each activity
• The variance of the beta probability distribution is:

• variance for individual estimate ……. ( p  o) 2

σ  2

62
• Variance for the path ------------
 ( P  O)
2

σ2 
62
 PROJECT ACTIVITY VARIANCE
Activity Optimistic Most Likely Pessimistic Variance
A 2 4 6 0.44
B 3 7 10 1.36
C 2 3 5 0.25
D 4 7 9 0.69
E 12 16 20 1.78
F 2 5 8 1.00
G 2 2 2 0.00
H 2 3 4 0.11
I 2 3 5 0.25
J 2 4 6 0.44
K 2 2 2 0.00
 VARIANCES OF EACH PATH
THROUGH THE NETWORK
Path Activities on Path Variance
Number Path (weeks)
1 A,B,D,E,G,H,J,k 4.82

2 A,B,D,E,G,I,J,K 4.96

3 A,C,F,G,H,J,K 2.24

4 A,C,F,G,I,J,K 2.38
 CALCULATING THE PROBABILITY OF
COMPLETING THE PROJECT IN LESS THAN A
SPECIFIED TIME
• When you know:
• The expected completion time
• Its variance
• You can calculate the probability of completing the project in “X” weeks with
the following formula:

specified time  path expected time  DT  EFP 

z   
path standard time  σP 2

Where DT = the specified completion date
EFPath = the expected completion time of the path
σPath  variance of path
2
 EXAMPLE: CALCULATING THE PROBABILITY
OF FINISHING THE PROJECT IN 48 WEEKS
• Use the z values in Appendix B to determine probabilities
• e.g. probability for path 1 is
 48 weeks  44.66 weeks 
z     1.52
 4.82 

Path Activities on Path Path Variance z-value Probability of

Number (weeks) Completion
1 A,B,D,E,G,H,J,k 4.82 1.5216 0.9357
2 A,B,D,E,G,I,J,K 4.96 1.4215 0.9222
3 A,C,F,G,H,J,K 2.24 16.5898 1.000

4 A,C,F,G,I,J,K 2.38 15.9847 1.000

 REDUCING PROJECT COMPLETION TIME

• Project completion times may need to be shortened

because:
• Different deadlines
• Penalty clauses
• Need to put resources on a new project
• Promised completion dates
• Reduced project completion time is “crashing”
 REDUCING PROJECT COMPLETION TIME –
CON’T
• Crashing a project needs to balance
• Shorten a project duration
• Cost to shorten the project duration
• Crashing a project requires you to know
• Crash time of each activity
• Crash cost of each activity
Crash cost/duration = (crash cost-normal cost)/(normal time – crash
time)
 REDUCING THE TIME OF A PROJECT
(CRASHING)

Activity Normal Normal Crash Crash Max. weeks Reduce cost

Time (wk) Cost ($) Time Cost ($) of reduction per week
A 4 8,000 3 11,000 1 3,000
B 6 30,000 5 35,000 1 5,000
C 3 6,000 3 6,000 0 0
D 6 24,000 4 28,000 2 2,000
E 14 60,000 12 72,000 2 6,000
F 5 5,000 4 6,500 1 1500
G 2 6,000 2 6,000 0 0
H 2 4,000 2 4,000 0 0
I 3 4,000 2 5,000 1 1,000
J 4 4,000 2 6,400 2 1,200
K 2 5,000 2 5,000 0 0
CRASHING EXAMPLE: SUPPOSE THE CABLES BY US
PROJECT MANAGER WANTS TO REDUCE THE NEW
PRODUCT PROJECT FROM 41 TO 36 WEEKS.
• Crashing Costs are considered to be linear
• Look to crash activities on the critical path
• Crash the least expensive activities on the critical path first (based
on cost per week)
• Crash activity I from 3 weeks to 2 weeks $1000
• Crash activity J from 4 weeks to 2 weeks $2400
• Crash activity D from 6 weeks to 4 weeks $4000
• Recommend Crash Cost $7400

• Question: Will crashing 5 weeks return more in benefits than it

costs?
CRASHED NETWORK DIAGRAM
 THE CRITICAL CHAIN APPROACH
• The Critical Chain Approach focuses on project due dates rather than on individual
activities and the following realities:
• Project time estimates are uncertain so we add safety time
• Multi-levels of organization may add additional time to be “safe”
• Individual activity buffers may be wasted on lower-priority activities
• A better approach is to place the project safety buffer at the end

Original critical path

Activity A Activity B Activity C Activity D Activity E

Critical path with project buffer

Activity A Activity B Activity C Activity D Activity Project Buffer
E
 ADDING FEEDER BUFFERS TO CRITICAL
CHAINS

• The theory of constraints, the basis for critical chains, focuses on keeping
bottlenecks busy.
• Time buffers can be put between bottlenecks in the critical path
• These feeder buffers protect the critical path from delays in non-critical paths
PROJECT MANAGEMENT WITHIN OM: HOW
IT ALL FITS TOGETHER
• Project management techniques provide a structure for the
project manager to track the progress of different activities
required to complete the project. Particular concern is given
to critical path (the longest connected path through the
project network) activities.
• Any delay to a critical path activity affects the project
completion time. These techniques indicate the expected
completion time and cost of a project. The project manager
reviews this information to ensure that adequate resources
exist and that the expected completion time is reasonable.
 PROJECT MANAGEMENT OM ACROSS THE
ORGANIZATION
• Accounting uses project management (PM) information to provide a
time line for major expenditures
• Marketing use PM information to monitor the progress to provide
updates to the customer
• Information systems develop and maintain software that supports
projects
• Operations use PM to information to monitor activity progress both
on and off critical path to manage resource requirements