Errors in Network Diagram

Looping : if an activity were represented as going back in time

B A C

Close loop produced endless cycle in computer programmes without a built-in routine for detection of identification of the cycle

Cycles A cycle is any path of jobs that leads back into itself. It represents logical error. It has to be removed before scheduling computation. A job list with cycles cannot be put in topological order.

Errors in Network Diagram

Dangling :No activity should end without being joined to maintain the continuity of the system. Such end events other then the end of the projects as a whole are called dangling events

B A C Dangling D Dummy

The CPM Diagram

Tasks are Arrows Events are Circles Critical Tasks are Thick Arrows Dummy Tasks are Dashed Arrows

Rules for Network Construction

1. Each activity is represented by one and only one arrow 2. Each activity must be identify by its starting and end node
Two activities should not be identified by the same completion events Activity must be represented by their symbol or corresponding order pair of starting and completion events

Nodes are numbered to identify an activity uniquely. 3. Between any pair of nodes, there should be one and only one activity 4. Arrow should be kept straight or not curved or bent. 5. The logical sequence between activities must follow following rules
- An event cannot occur until all the incoming activities into it have been

completed - An activity cannot start unless all the preceding activities on which it depends have been completed - Dummy activities should only be introduced if obviously necessary

Numbering the Events

Event number should be unique. Event numbering should be carried out on a sequential basis from left to right. The initial event which has all outgoing arrows with no incoming arrows is numbered 0 or 1 The head of an arrow should always bear a number higher than the one assigned at all tail of the arrow. Gaps should be left in the sequence of event numbering to accommodate subsequent inclusion of activities, if necessary.

Illustration - 1
A television is manufactured in six steps, labeled A through F. Because of its size and complexity, the television is produced one at a time. The production control manager thinks that network scheduling techniques might be useful in planning future production. He recorded the following information A is the first step and precedes B and C C precedes D and E. B follows D and precedes E. D, E is successor of F.

Activity on node diagram

A is the first step and precedes B and C (A < B, C) C precedes D and E. B follows D and precedes E. D, E is successor of F.

B A C

Activity on node diagram

A is the first step and precedes B and C C precedes D and E. (C < D, E) B follows D and precedes E. D, E is successor of F.

B A C

D E

Activity on node diagram

A is the first step and precedes B and C C precedes D and E. B follows D and precedes E. (D < B > E) D, E is successor of F.

B A C

D E

Activity on node diagram

A is the first step and precedes B and C C precedes D and E. B follows D and precedes E. D, E is successor of F. (F < D, E )

B A C

D F E

Illustration - 2
Construct the network diagram comprising activities B, C, , Q and N such that the following constraints are satisfies B < E, F; C < G, L; E, G < H; L, H < I; L < M; H < N; H < J; I,J < P; P < Q.
E B 1 C 4 2 F 3 G Q L 7 M 8 N 12 5 H 6 I J 9 10 P 11

Illustration - 3
Construct the network diagram comprising activities A, B, C > NONE; A< D B, C < E A< F C<G H < D, E, F D<I G < J, K H, J < L K<M I, L < N

Illustration - 3
Construct the network diagram comprising activities A, B, C > NONE; A< D 0 B, C < E H 11 D A< F I 2 5 7 C<G F N A H < D, E, F L D<I J 8 10 C 1 4 G G < J, K 6 K B M H, J < L 9 E K<M 3 I, L < N

Illustration - 4
Network analysis of a minor redesign of a product and its associated packaging. The key question is: How long will it take to complete this project ?

For clarity, this list is kept to a minimum by specifying only immediate relationships, that is relationships involving activities that "occur near to each other in time".

Practice Example
A social project manager is faced with a project with the following activities: Activity Description Social work team to live in village Social research team to do survey Analyse results of survey Establish mother & child health program Establish rural credit programme Carry out immunization of under fives Duration 5w 12w 5w 14w 15w 4w

Draw network diagram and show the critical path. Calculate project duration.

Practice problem
Activity Description 1-2 Social work team to live in village 1-3 3-4 2-4 3-5 4-5 Social research team to do survey Analyse results of survey Establish mother & child health program Establish rural credit programme Carry out immunization of under fives 4 5 3 Duration 5w 12w 5w 14w 15w 4w

2 1

CPM calculation
Path
A connected sequence of activities leading from the starting event to the ending event

Critical Path
The longest path (time); determines the project duration

Critical Activities
All of the activities that make up the critical path

Critical Path Analysis

The objective of critical path analysis is to estimate the total project duration
Total duration needed for the completion of the project The activities of the project as being critical or non-critical

An Activity in a network diagram is said to be critical is the delay in its start will further delay the project completion time.

Critical Path Analysis

The following terms shall be used in the critical path calculation

Ei = Earliest occurrence time of event i Lj = Latest occurrence time of event j Tij = duration of the activity (i, j)

Forward Pass
Earliest Start Time (ES) earliest time an activity can start ES = maximum EF of immediate predecessors Earliest finish time (EF) earliest time an activity can finish earliest start time plus activity time EF= ES + t

Backward Pass
LS= LF - t

Latest Start Time (LS)

Latest time an activity can start without delaying critical path time
Latest finish time (LF)

latest time an activity can be completed without delaying critical path time LS = minimum LS of immediate predecessors

CPM analysis
Draw the CPM network Analyze the paths through the network Determine the float for each activity Compute the activitys float float = LS - ES = LF - EF Float is the maximum amount of time that this activity can be delay in its completion before it becomes a critical activity, i.e., delays completion of the project Find the critical path is that the sequence of activities and events where there is no slack i.e.. Zero slack Longest path through a network Find the project duration is minimum project completion time

CPM Example:
CPM Network f, 15 a, 6 g, 17 i, 6 b, 8 d, 13 c, 5 e, 9 j, 12 h, 9

CPM Example
ES and EF Times
f, 15 g, 17 i, 6 h, 9

a, 6 0 6 b, 8 0 8 c, 5 0 5

d, 13

j, 12

e, 9

CPM Example
ES and EF Times
a, 6 0 6 b, 8 0 8 c, 5 0 5 d, 13 8 21 e, 9 5 14 j, 12 f, 15 6 21 g, 17 6 23 i, 6 h, 9

CPM Example
ES and EF Times
a, 6 0 6 b, 8 0 8 c, 5 0 5 d, 13 8 21 e, 9 5 14 j, 12 21 33 Projects EF = 33 f, 15 6 21 g, 17 6 23 i, 6 23 29 h, 9 21 30

CPM Example
LS and LF Times
a, 6 0 6 b, 8 0 8 c, 5 0 5 f, 15 6 21 g, 17 6 23 i, 6 23 29 27 33 h, 9 21 30 24 33

d, 13 8 21 e, 9 5 14

j, 12 21 33 21 33

CPM Example
LS and LF Times
f, 15 6 21 9 24 g, 17 6 23 10 27 d, 13 8 21 8 21 e, 9 5 14 12 21 h, 9 21 30 24 33

a, 6 0 6 3 9 b, 8 0 8 0 8 c, 5 0 5 7 12

i, 6 23 29 27 33

j, 12 21 33 21 33

CPM Example
Float
f, 15 3 6 21 9 24 g, 17 4 6 23 10 27 d, 13 8 21 0 8 21 e, 9 5 14 7 12 21 h, 9 3 21 30 24 33

a, 6 3 0 6 3 9 b, 8 0 0 8 0 8 c, 5 0 5 7 7 12

i, 6 23 29 4 27 33

j, 12 21 33 0 21 33

CPM Example
Critical Path
f, 15 g, 17 i, 6 b, 8 d, 13 c, 5 e, 9 j, 12 h, 9

a, 6

Critical Path Analysis

A critical path consists that set of dependent tasks (each dependent on the preceding one), which together take the longest time to complete. One way is to draw critical path tasks with a double line instead of a single line. The critical path for any given method may shift as the project progresses; this can happen when tasks are completed either behind or ahead of schedule, causing other tasks which may still be on schedule to fall on the new critical path

PERT
PERT is based on the assumption that an activitys duration follows a probability distribution instead of being a single value Three time estimates are required to compute the parameters of an activitys duration distribution: pessimistic time (tp ) - the time the activity would take if things did not go well most likely time (tm ) - the consensus best estimate of the activitys duration optimistic time (to ) - the time the activity would take if things did go well Mean (expected time): te =

tp + 4 tm + to
6
2

Variance: Vt =W2 =

tp - to
6

PERT analysis
Draw the network. Analyze the paths through the network and find the critical path. The length of the critical path is the mean of the project duration probability distribution which is assumed to be normal The standard deviation of the project duration probability distribution is computed by adding the variances of the critical activities (all of the activities that make up the critical path) and taking the square root of that sum Probability computations can now be made using the normal distribution table.

Probability computation
Determine probability that project is completed within specified time x-Q Z= W where Q = tp = project mean time W = project standard mean time x = (proposed ) specified time

PERT Example
Immed. Optimistic Most Likely Pessimistic Activity Predec. Time (Hr.) Time (Hr.) Time (Hr.) A -4 6 8 B -1 4.5 5 C A 3 3 3 D A 4 5 6 E A 0.5 1 1.5 F B,C 3 4 5 G B,C 1 1.5 5 H E,F 5 6 7 I E,F 2 5 8 J D,H 2.5 2.75 4.5 K G,I 3 5 7

PERT Example PERT Network

D

C B F G I K

PERT Example
Activity
A B C D E F G H I J K

Expected Time
6 4 3 5 1 4 2 6 5 3 5

Variance
4/9 4/9 0 1/9 1/36 1/9 4/9 1/9 1 1/9 4/9

PERT Example
Activity ES
A B C D E F G H I J K 0 0 6 6 6 9 9 13 13 19 18

EF
6 4 9 11 7 13 11 19 18 22 23

LS
0 5 6 15 12 9 16 14 13 20 18

LF
6 9 9 20 13 13 18 20 18 23 23

Slack
0 *critical 5 0* 9 6 0* 7 1 0* 1 0*

PERT Example Vpath = VA + VC + VF + VI + VK = 4/9 + 0 + 1/9 + 1 + 4/9 = 2 Wpath = 1.414 z = (22 - 23)/W!(22-23)/1.414 = -0.71 From the Standard Normal Distribution table: P(z < 0.71) = .5 + .2612 = .7612

We will use PERT/CPM Analysis to determine Task Secondary properties:

Tail Event and Head Event Earliest Start, Earliest Complete Latest Start, Latest Complete Critical / Non-Critical Status Total Float, Free Float Scheduled Start, Scheduled Complete Actual Staffing, Duration, and Variable Costs

We will then use Task Secondary Properties to generate Project Management Tools:
Gantt Chart (Project Schedule) Manpower Chart Expenditure Curves Project Completion (PC)

Generate Initial CPM Diagram

Must strictly enforce all prerequisite relationships. Number of events is initially unknown Critical path is initially unknown Iterative Process Try to minimize number of Dummy Tasks

CPM Hint #1

Add or remove events at your pleasure. Do not number events until last.

CPM Hint #2
The initial event is the Tail Event for all tasks which have empty prerequisite sets (Initial Tasks). The Final Event is the Head Event for all tasks which are not members of any prerequisite set (Final Tasks).

CPM Hint #3
Tasks which have identical prerequisite sets have the same Tail Event

CPM Hint #4
Starting with the Final Tasks, work backwards, enforcing the smallest prerequisite sets first. Use Dummy Tasks to enforce any prerequisites in large sets which have already been enforced in a smaller set.

Finish CPM Diagram

Remove all redundant Dummy Tasks Remove all redundant Events Number all remaining events Not really finished . . havent identified critical tasks yet.

Generate PERT Chart: Enter Data for Each Task

Task Symbol Tail Event Head Event Task Duration (TD)

Forward Pass: Determine Earliest Start (ES) and Earliest Complete (EC) for each Task
For all Initial Tasks, ES = 0 Once ES is Determined, EC equals ES plus TD. The ES for all tasks with tail [i] is equal to the largest value of EC for all tasks with head [i]. PC is the largest value of EC for all Final Tasks.

Backward Pass: Determine Latest Start (LS) and Latest Complete (LC) for each Task
For all Final Tasks, LC = PC Once LC is Determined, LS equals LC minus TD. The LC for all tasks with head [j], is equal to the smallest value of LS for all tasks with tail [j]. At least one Initial Task must have LS = 0; none may be negative.

Determine Total Float (TF): Allowable delay in start of task which will not delay Project Completion
For task with tail [i] and head [j], TF[i,j] = (LC[j] ES[i]) TD[i,j] ES[i] is earliest start for all tasks with tail [i]. LC[j] is latest complete for all tasks with head [j].

Determine Free Float (FF): Allowable delay in start of task which will not delay start of any other task.
For task with tail [i] and head [j], FF[i,j] = ES[j] - ES[i] - TD[i, j] = ES[j] - EC[i,j] If [j] is the final event, use PC for ES[j]

Determine Critical Path

All Tasks with zero Total Float are Critical. Any delay in these Tasks will delay Project Completion. Darken these Tasks to finish CPM Diagram.