Math Homewok needed for VFLORIDA
1
Week 14 Program Evaluation and Review Technique (PERT) and
Critical Path Method (CPM) Applications
Two simple, yet interesting and important applications of partial ordering relations are
the PERT and CPM techniques in job scheduling. The following description was taken
from googling PERT.
PERT is a method to analyze the involved tasks in completing a given project, especially
the time needed to complete each task, and identifying the minimum time needed to
complete the total project. PERT was developed primarily to simplify the planning and
scheduling of large and complex projects. It was developed for the U.S. Navy Special
Projects Office in 1957 to support the U.S. Navy's Polaris nuclear submarine project. [1]
It was able to incorporate uncertainty by making it possible to schedule a project while
not knowing precisely the details and durations of all the activities. It is more of an event-
oriented technique rather than start- and completion-oriented, and is used more in
projects where time, rather than cost, is the major factor. It is applied to very large-scale,
one-time, complex, non-routine infrastructure and Research and Development projects.
PERT is valuable to manage where multiple tasks are occurring simultaneously to reduce
redundancy
See exercise 66 in the text, section 9.6 for an example of the list of tasks needed to build
a house. Exercise 67 is also an interesting example. If we let A = {set of tasks given in
exercise 66} and define the relation R on A by : xRy iff task x precedes (is a prerequisite
task of) task y or task x = task y the Hasse diagram is as is given in the illustration in the
text.
The first step to scheduling a project is to determine the tasks that the project requires and
the order in which they must be completed. Many of the following examples are student
examples.
Note in the following examples read the diagrams from left to right.
Example 1.
The creation of a 3D video game Tasks
1. General brainstorming (game type, setting, etc) 2. Design and implement game engine 3. Design and implement graphics engine 4. Write story 5. Design the characters 6. Design the world 7. Create 3D models 8. Create character animations 9. Voice actor casting 10. Sound recording 11. Program levels, characters, sounds, etc into game 12. Packaging
2
1
13
9
5
7 8 10
8 12 14
18 19
Task Immediately Preceding Tasks Time required
1 1 Week
2 1 3 Months
3 1 2 Months
4 1 1 Month
5 4 2 Weeks
6 4 3 Weeks
7 5, 6 1 Month
8 7 2 Weeks
9 5 1 Week
10 9 2 Weeks
11 2, 3, 8, 10 1 Month
12 11 1 Week
Let T = { Task 1, Task 2, … , Task 11 } Define R on T by xRy iff x is needed for y or x = y
The Critical path seen in the figure above is 1, 4, 6, 7, 8, 11, 12. This is because the
sequence requires the most time to complete, which prevents the game from being finished.
One way that could decrease the critical path would be to design the characters and
levels as they are introduced during the story writing process. This would merge those three
tasks into one with a greatly reduced total time.
Task 1
1 Week
Task 2 12
Weeks
Task 3
8 Weeks
Task 4
4 Weeks
Task 5
2 Weeks
Task 6
3 Weeks
Task 7
4 Weeks
Task 8
2 Weeks
Task 9
1 Week
Task 10
2 Weeks
Task 11
4 Weeks
Task 12
1 Week
3
Finish Start
2
2
2
1
0
1
1
1
1 8
8
8 7
7
3
1
Example 2. The construction of a cottage requires the performance of certain tasks. The
following table 1 lists the various tasks with their priority relationship. The start task ( )
and finish task ( ) are added, is linked to task A and is linked to task K.
Table 1
Code Of Task Duration
(Weeks)
Prerequisite tasks
A Masonry 7 -
B Carpentry for roof 3 A
C Roof 1 B
D Sanitary and
electrical
installations
8 A
E Front 2 D, C
F Windows 1 D, C
G Garden 1 D, C
H Ceiling 3 F
J Painting 2 H
K Moving in 1 E, G, J
Let S be the set of all tasks and consider the partial order relation R defined on S
as follows: for all tasks x and y in S,
xRy x = y or x precedes y.
The minimum time required to finish this job is calculated using Project
Evaluation and Review Technique (PERT). The PERT diagram of the project is shown in
the figure 1.
Figure 1
A D
F J H
E K
G C B
4
Finish
0
8
7
3 1
2
1
2 8
2 1
8 1
1
1
(0)
(0) (21)
(7)
(7) (10)
(15)
(15)
(15)
(16) (18)
(20)
In this representation, the tasks are the vertices of the graph. The length of each
task is the duration of the corresponding task. The start and finish of a task are two stages
of the project. We can define an initial stage as start and a final stage as finish and a
certain number of intermediate stages. Each stage is defined by tasks already carried out.
In the beginning milestone of the project is start stage. The start followed by task
A which is carried out in 7 weeks. After finishing stage A, we have two options. We can
start task B and task D simultaneously. Task B takes 3 weeks to finish and task D takes 8
weeks to finish the job. Task B is immediately followed by task C, which takes one week
to carry out. The minimum time required to start task C is the total time required to finish
task B and A which is 10 weeks. Task C is followed by task E. to start task E, we have to
finish C and D. C is finished in 11 weeks, and D is finished in 15 weeks, so it is very
common that we cannot start task E before finishing task D which takes 15 weeks to
carry out. Same way, we can decide the earliest time to start each task, which is shown in
Table 2. below:
Table 2 Task Earliest Start Time
Start ( ) 0
A 0
B 7
C 10
D 7
E 15
F 15
G 15
H 16
J 18
K 20
Finish ( ) 21
The above analysis shows that at least 21 weeks is required to complete the
project. The minimum duration of the project will be the length of the longest path
between the initial stage and the finish stage. This is shown in with the darker line in the
figure 2.
Figure 2
A
B
D
F
E K
G C
H J
5
If we delay any work in this path, we delay in the project finish time. That means
delay in performing any of these tasks in the path cause delay in the time required to
finish the project, and for these reason, this path is known as critical path.
The tasks outside the critical path can be delayed by certain amount of time. For
example task E is not on critical path and it is followed by task K. If we delay E by 3
week than its earliest start time, then we can start the task K as per its earliest start time
because K must be started after finishing J which takes 20 weeks. We can finish task E in
20 weeks by delaying 3 weeks. In the opposition if we delay work on the critical path, we
delay the time to complete the project. For example 3 weeks delay in task J cause 3
weeks delay to start K, and K start after 3 weeks than its earliest start time and these
cause three week delay to complete the project. Now if we finish task J earlier by one
week then we can also reach task K earlier by one week and finish it off. And finally the
overall project is also finished one week before.
Example 3.
In order to construct a house, there are many jobs that need to be done at the same
time. Certain parts of the construction must be done before others can be started. We
can not start wiring the house if the walls have not been put up, and we can not put the
walls up till the foundation had been set. Before the foundation is set, you must choose a
good plot to dig the foundation hole. However, there are certain jobs which can be done
simultaneously. While you are wiring the outlets, you can have someone do the heating
and air conditioning ducts or can have the landscaper working on the outside layout. The
partial order diagram will allow one to see how long the whole process will take.
Below, we show each task that needs to be done, and the amount of time required for that
task. The amount of time is estimated.
1. Find Plot 2 days 2.
1 Excavate land 5 days
3. Dig for foundation 3 days 4. Lay concrete foundation 5 days 5. Exterior firework 2 days 6. Exterior electrical 2 days 7. Exterior gasline 5 days 8. Supports for walls/ceiling/floor/stairs 5 days 9. Siding/Roof 3 days 10. Windows 1 days 11. Interior wiring 2 days 12. Interior plumbing 2 days 13. Heating/AC ducts 2 days
6
14. Insulation 1 day 15. Dry wall 2 days 16. Landscaping 14 days 17. Painting 2 days 18. Light Fixtures/Switches 7 hours 19. Floor Ring 2 day 20. Doors/Cabinets 1 day 21. Clean-up 1 day
The next table shows what task precedes each task. This allows us to see what tasks can
be done at the same time. If one task does not depend on the other, then those two tasks
can be done at the same time.
Task Prerequisite tasks Time
1 0 2 days
2 1 5 days
3 2 3 days
4 3 5 days
5 1,2,3,4 2 days
6 1,2,3,4 2 days
7 1,2,3,4 2 days
8 4 5 days
9 8 3 day
10 8 1 day
11 8 2 days
12 8 2 days
13 8 2 days
14 10,11,12,13 1 day
15 14 2 days
16 8 14 days
17 15 2 days
18 17 7 hours
19 17 2 days
20 19 1 day
21 20 1 day
7
Partial Order formula: x R y task x = task y or task x precedes task y
We read the following Hasse diagram from left to right to find the minimum time for the
whole process of constructing the house.
Partial Order Diagram: Construction of a House
Critical Path Method(CPM): 1,2,3,4,816,21 which is 35 days
The critical path time can be reduced if we do certain tasks differently. The time
for landscaping right now is 14 days. But if more workers are used, then the time will be
less. If pre-fabricated materials are used, then it will take less time, because less people
are needed, and less time is used in making the material. Also depending on the design
of the house, the time can be reduced or even increased. If less rooms are needed by the
Task 1 2 Days
Task 2 5 Days
Task 3 3 Days
Task 4 5 Days
Task 6 2 Days
Task 7 2 Days
Task 8 5 Days
Task 5 2 Days
Task 12 2 Days
Task 11 2 Days
Task 10 1 Day
Task 13 2 Days
Task 16 14 Days
Task 9 3 Days
Task 14 1 Day
Task 15 2 Days
Task 17 2 Days
Task 18 7 Hours
Task 19 2 Days
Task 20 1 Day
Task 21 1 Day
8
family that is living there, then it will take less time, then designing at large size home
with many rooms, and closets inside each room.
What can also reduce the time is experience of the construction workers. If the
workers are new, then they will be a bit slower, and making more mistakes which
increases the time for each task.
Example 4.. Are the partial ordering diagrams complete? Can you fill in the missing
edges?
As an application of partial order relations, I have chosen to refurbish my younger
daughter’s bedroom. This is a project that I am actually in the middle of now, but I
decided to see how fast it would get done if I were commanding a number of
professionals. Let A={tasks}. We can define R on A by xRy iff {x=y or task x is a
prerequisite of task y}.
The job can be divided into several tasks:
1. Move all of my daughters things out.
2. Rip out doorjam from bedroom to bathroom (the bathroom is to become a
master bath).
3. Lower two electrical outlets, sheetrock holes (previous owners had a two
family with this room as a kitchen so two outlets are above where the counter used to be).
4. Frame doorway, install electrical outlet, send wires up into attic, and
sheetrock over doorway to bath.
5. Cut, sand, prepare, stain, and urethane baseboard (the old baseboard must
be destryed in taking out the door frame).
6. Attach the new outlet wires to junction box in the attic.
7 Tape, joint compound, sand, joint compound, and sand areas where new
sheetrock has been installed. Also same procedure on any cracks, etc.
8. Primer walls.
9. Install new baseboard.
10. Paint ceiling.
11. Install wall paper.
12. Clean and move furniture back in.
Some of these tasks can be done simultaneously, but most must wait for a
preceeding task to be complete. Table 1 demonstrates which task immediately precedes
another as well as the times required to complete each task.
9
Table 1.
Task Immediately Preceding Time
Task(s)
1 ½ Hour
2 1 1 Hour
3 1 4 Hours
4 2 3 Hours
5 4 6 Hours
6 4 1 Hour
7 3, 4 7 Hours
8 7 2 Hours
9 5 ½ Hour
10 8 1 Hour
11 9, 10 3 Hours
12 6, 11 ½ Hour
Table 2 displays the Hasse diagram for this relation, with the time to complete
each task included in each box.
Table 2.
To calculate the minimum time it would take to refurbish this room, we must add
the times in the diagram, adding the longest prerequisite time to the time in each box as
we go. Table 3 shows the results.
Task 6 1 Hour
Task 2 1 Hour
Task 4 3 Hours
Task 5 6 Hours
Task 9 ½ Hour
Task 11 3 Hours
Task 12 ½ Hour
Task 1 ½ Hour
Task 3 4 Hours
Task 8 2 Hours
Task 10 1 Hour
Task 7 7 Hours
10
Table 3.
As Table 3 shows, the minimum time it would take to complete the entire job is
18 hours. What is interesting to note is that this diagram has two critical paths. To get to
task 7, both tasks 3 and 4 have 4.5 hours of prerequisite time. So the longest path in
terms of time can go from tasks 1 to 2, 4, 7, 8, 10, 11, and 12 but can also go from tasks 1
to 3, 7,8, 10, 11, and 12. These are the two critical paths
If I wanted to speed up the process, I might put an extra person on joint
compound duty and/or painting. This would have to be experimented with since some of
the times posted include drying times. Also, if too many people are on the same job, they
may simply get in each other’s way and add to times instead of reducing them.
Example 5.
Software project scheduling problem
It is Call Center software that is able to route customer information to agents. It is used
by companies that have 1-800-XXX-XXX services. This project is made of server and
client.
Call Center server is a fault-tolerant scalable server that connects clients with multiple
customer contact sources, such as calls, emails, and web collaboration sessions. It enables
thin-client applications and provides a client interface library for support access through
C, C++, Java, or COM.
The Call Center Client Interface is not limited to providing application to manage
telephone/ voice initiated interactions. It provides a broad concept of an Agent and their
interaction with multiple sources, including CTI (Computer Telephony Interface), e-mail
and web collaboration servers.
18 4.5
17.5 4.5
4.5
11 4.5
4.5
10.5 4.5
Task 6 1 Hour
Task 1 ½ Hour
Task 2 1 Hour
Task 4 3 Hours
Task 5 6 Hours
Task 9 ½ Hour
Task 11 3 Hours
Task 12 ½ Hour
Task 3 4 Hours
Task 7 7 Hours
Task 8 2 Hours
Task 10 1 Hour
.5 4.5
4.5
4.5 4.5
11.5 4.5
13.5 4.5
14.5 4.5
1.5 4.5
5.5
11
The project can be broken into these tasks (Table 1) in order to finish it. The start task (S)
and finish task (E) are added, S is linked to task 1 and E is linked to task 12.
Table 1
Task Description Immediately
Preceding Tasks
Time Needed to
Perform Task
Start (S) Start Task None None
1 Architect overall project S 3 weeks
2 Design Server and its
Components
1 5 weeks
3 Design Client and its
Components
1 4 weeks
4 Design Common
Components
1 4 weeks
5 Implement server and its
components
2,7 30 weeks
6 Implement client and its
components
3,7 20 weeks
7 Implement common
components
4 10 weeks
8 Test server and fix bugs 5 5 weeks
9 Test client and fix bugs 6 3 weeks
10 Implement client interfaces
for different technologies
9 20 weeks
11 Test sever with different
client interfaces
8,10 8 weeks
12 Polish the software and
update documents and get it
ready for the customer
11 3 weeks
End (E) End Task 12 None
12
Figure 1
In figure 1, the tasks are the vertices of the graph. The length of each task is the duration
of the corresponding task. The start and finish tasks are two stages of the project. The
initial stage is the start stage and a final stage is the finish stage.
In the beginning of the project is start stage. The start stage followed by task (1) which is
carried out in 3 weeks. After finishing task (1), we have 3 options. We can start task (2),
task (3), and task (4) simultaneously. Task (2) takes 5 weeks to finish, task (3) takes 4
weeks to finish and task (4) takes 4 weeks to finish.
In order to start task (5), we have to finish task (7) and task (2). Task (2) finishes in 8
weeks and task (7) finishes in 17 weeks, so task (5) starts after finishing task (7), which is
after 17 weeks.
In order to start task (6), we have to finish task (7) and task (3). Task (3) finishes in 7
weeks and task (7) finishes in 17 weeks, so task (6) starts after finishing task (7), which is
after 17 weeks. Task (5) and task (6) can start simultaneously.
Task (8) starts right after task (5) ends, so it starts after 47 weeks and it finishes in 5
weeks.
Task (9) starts right after task (6) ends, so it starts after 37 weeks and it finishes in 3
weeks.
Task (10) starts right after task (9) ends, so it starts after 40 weeks and it finishes in 20
weeks.
Task (11) has to wait for task (8) and task (10) end. Task (8) finishes in 52 weeks and
task (10) finishes in 60 weeks. So task (11) has to start after task (10) finishes, which is in
60 weeks and it finishes in 8 weeks.
Start (S)
Task 2 (5)
Task 1 (3)
Task 5 (30)
Task 6 (20)
Task 3 (4)
Task 4 (4)
Task 8 (5)
Task 9 (3)
Task 7 (10)
Task 10 (20)
Task 11 (8)
Task 12 (3)
End (E)
13
Task (12) starts after task (11) ends. It starts in 68 weeks and it takes 3 weeks to finish.
Example 6.
My example PERT is based on a software development project – starting from business requirements definition through deployment – to build a “load & rebate” system for purchasing information. It assumes that the methodology being used calls for the completion of a users’ guide as well as user-training before the system can be deployed to the production environment. Task Table:
Task Preceding Task(s)
Task Description Duration
A Business Requirements 5 days
B A Technical Requirements 2 days
C A Functional Specification – Load Application 6 days
D A Functional Specification – Rebate Application 8 days
E B Develop Technical Foundation classes 10 days
F C, E Develop Load Application 15 days
G D, E Develop Rebate Application 20 days
H F Quality Assurance (QA) Testing – Load Application
7 days
I G Quality Assurance (QA) Testing – Rebate Application
10 days
J C, D Prepare User Guide 4 days
K J Prepare Training Material 6 days
L H, I, K Train Users 3 days
M H, I, L Deploy System to Production Environment 1 day
(a)
B A
C
D
E
F
G
J K
H
I
L
M ω α
Finish
5
20
5
5
6
6
2
10
10
4 6
7
7
10
3
1
8
15
0
8 10
Start
14
From the above graph we can determine the earliest start time of each task and tabulate the results in the table below. The earliest start time for a given task is the maximum of the sums of all preceding tasks.
Task Earliest Start Time
Start 0
A 0
B 5
C 5
D 5
E 7
F 11
G 17
H 26
I 37
J 13
K 17
L 47
M 50
Finish 51 The above table shows that the minimum time required to complete the tasks is 51 days. (b) Determining the minimum time required to complete all the tasks (above) also tells us that the critical path is 51 days long. The diagram below shows the critical path of my project (in red and bold). This tells us that the duration of tasks, that are on the critical path, directly affect the duration of the overall project (i.e. extending their duration will increase the project duration while reducing their duration may reduce the duration of the project).
(c) Clearly, any tasks that are on the “critical” path can result in a project delay if more time is taken that originally planned. Other tasks (that are not on the critical path) will have some element of tolerance to overruns, but only to a point (i.e. the point up until the duration of the tasks makes it a critical task).
B A
C
D
E
F
G
J K
H
I
L
M ω α
Finish
5
20
5
5
6
6
2
10
10
4 6
7
7
10
3
1
8
15
0
8 10
15
In my example, the development of the foundation classes and rebate application (tasks E and G respectively) makeup 30 days of programming. If two programmers were used instead of one, then it may be possible to reduce this duration to 7 days and 15 days – thereby reducing the overall project plan (critical path) by 8 days. The QA tasks (H and I) are also areas where project overruns could be introduced – for example, sloppy programming may result in more time to fix bugs and retest than originally expected.
Table 2
Task Earlier Start Time (weeks)
Start (S) 0
1 0
2 3
3 3
4 3
5 17
6 17
7 7
8 47
9 37
10 40
11 60
12 68
End (E) 71
The above analysis shows that at least 71 weeks is required to complete the project. The minimum duration of the project will be the length of the longest path between the start stage and the finish stage. If we delay any work in this path, we delay the whole project. That means if we delay any of the tasks then we cause a delay in the time required to finish the project. This path is known as critical path. Figure 2 shows the critical path with darker line.
Figure 2
Start (S)
Task 2 (5)
Task 1 (3)
Task 5 (30)
Task 6 (20)
Task 3 (4)
Task 4 (4)
Task 8 (5)
Task 9 (3)
Task 7 (10)
Task 10 (20)
Task 11 (8)
Task 12 (3)
End (E)
16
The tasks that are not in critical path can be delayed by certain amount of time. For example, if we delay task (8) by 4 weeks than its earliest start time, then we can start task (11) as per its earliest start time because task (11) must be started after finishing task (10) which takes 60 weeks. In the opposition, 4 weeks delay in task (10) causes 4 weeks delay to start task (11), and task (11) starts after 4 weeks than its earliest start time and these cause 3 weeks delay to complete the project. On the other hand, if we finish task (10) 4 weeks earlier then we can start task (11) earlier by 4 weeks and finally the overall project is also finished 4 weeks before.
Example 7. In your notes of week 12 Project Evaluation and Review Technique (PERT)
is explained. Make up a meaningful example illustrating this process. Explain all details.
Draw the graphs involved. You should use a reasonable number of tasks.
(a) Determine the minimum time needed to complete your set of tasks.
(b) Determine the Critical Path for your example. Explain what this gives you. Comment on your example. Which task(s) cause a delay in the project? How
would you fix the problem? Can you obtain more information out of your
example?
Project:
Title V Septic System Upgrade to my home
Tasks Prerequisites Weeks
A. send RFI to possible engineering firms, receive responses and select engineer
- 2
B. engineer arranges for digging of test holes, perk tests, and official oversight
A 3
C. engineer designs septic system and gets official plan approvals
B 8
D. send RFP to possible construction contractors (contractor & engineer must be independent by law), receive responses
and select constructor
C 2
E. constructor orders and receives settling tank and distribution box (preformed concrete)
D 1
F. constructor orders and receives leeching bed sand (truckloads)
D 1
G. constructor orders and receives leeching bed tubes (perforated plastic semi-cylinders)
D 3
H. constructor orders and receives piping and tank filter (PVC)
D 1
I. constructor excavates tank and distribution locations and connecting trenches
D 1/5
J. constructor installs distribution box and tank E, I 1/5
17
K. constructor installs piping and tank filter H, J 1/5
L. constructor excavates leeching field D 3/5
M. constructor installs and levels leeching bed sand to level needed for tubes
F, L 1/5
N. constructor installs leeching bed tubes G, M 1
O. constructor covers leeching bed tubes with sand, backfills and rough grades site
K, N 3/5
P. contractor gets official inspection and approval of system O 1
Q. send RFP to possible landscape contractors, receive responses and select landscaper
P 2
R. landscaper orders and receives loam (top soil) Q 2/5
S. landscaper finish grades site, installs loam, rakes, installs grass seed and mulch
R 1
PERT Chart with Critical Path in red (created with Geometers Sketchpad).
Project time from start to end is 24 weeks. The leeching bed tubes ordering (3 weeks) and
installing (1 week) are the gating items in the critical path. If we could find a tube
distributor that could deliver faster we could shorten the critical path, perhaps to one
week. The installation time of the tubes could be shortened if more than one skilled
worker was assigned to the task. In fact, five lines of tubes were installed so probably five
workers could have been used, shortening task N to 1/5 of a week. But there is no need to
reduce task N below 19.6-3+1-16.4-0.6=0.6=3/5 (because then two paths would have the
same overall task time), so only increase tube installers to three people.
3
8
2
1
2 1
3
1
1/5
1/5
1/5
1/5
1/5
3/5
1/5
1/5 1
1
3/5
3/5 1
2 2/5
1
0
A (2)
B (5) C (13)
D (15)
E (16)
F (16)
G (18)
H (16)
I (15.2)
J (16.2)
K (16.4)
L (15.6)
M (16.2)
N (19)
O (19.6) P (20.6)
Q (22.6) R (23)
Start
S (24)
End (24)
18