Consider a large-scale project’s planning stage. Hundreds of distinct actions must be completed by multiple separate organisations or firms in order for the project to be completed successfully. We’d like to finish the project as quickly as possible. This could be accomplished if all of the activities were finished at the same time. However, it is frequently impossible to commence one action before the completion of another. Buildings, for example, cannot be constructed until the forest cover over the Penny Bay area (where Disneyland is located) has been cleared. As a result, we’ll break down a project into a series of clearly defined activities. In addition, we need know how long each action is expected to take.
The following are some of the questions that the CPM/PERT analysis can answer. (a) When do you think we’ll be able to finish the entire project? (a) When it comes to an activity, when can we start doing it? (c) What are the bottleneck activities? These are actions that will cause the entire project to be delayed if they are not completed on time. (d) What is the latest time we can start an activity without causing the project to be delayed? For example, hiring and training a group of individuals to dress up as stuffed animals and dance on the street will take six months; Disneyland will open in December 2005. As a result, we won’t need to start hiring and training until the summer of 2005.
Table of Contents
Graphical modeling of Project Activities
Each activity is conveniently represented as an edge in traditional CPM/PERT graph modelling. The length of time it takes to construct the edge is indicated by its weight. Each node represents a milestone, which is the point in time when a specific activity is finished or initiated. The edges are directed, with the head of the edge colliding with the node that represents the activity’s completion milestone.
A precedence connection is imposed by the constraint that one activity cannot begin before another has been completed. As a result, the arrows in our graph will show the order in which the tasks can be done (equally: the paths indicate the sequence in which milestones can be achieved).
The graph also depicts the milestones’ order of precedence. If activity u must be finished before moving on to activity v, an arrow from the milestone (complete u) to the milestone (complete v) is used to highlight this (begin v). However, there may be no real activity between these two events, in which case this edge will have a weight of 0; such edges are referred to as dummy edges because they just indicate a precedence rather than actual activity.
To represent a project using a PERT network correctly, we must first list all precedence relationships. It is sufficient to identify each activity’s direct predecessors.
Once we have the project plan data in a format like the one above, we can use the following way to express it as a directed graph.
(i) Create a node, s, to symbolise the project’s start. (ii) Create an edge incident from s for each activity that has no direct precursor. (iii) Other activities are added to extend the graph based on the list of immediate predecessors; where there are two activities with some of their direct predecessors being the same but others not, a dummy activity is introduced to indicate the precedence restriction.
(iv) Finally, all activities that do not have a successor are linked to a common node that represents the project’s completion.
The graph for our hydropower plant project is now being built. The activity names in lower case letters are used to denote the edges in the graph. Each node symbolises the conclusion of the activity or activities illustrated by the edges incident to it, as well as the moment in time at which we might begin any action whose corresponding edge is incident from this node. The duration of the activity it depicts is represented by the weight of the edge. The dashed lines are the dummy edges, which have no name and are weighted at zero. The precedence restrictions are depicted using them.
We start at the start node and calculate the earliest possible start time for each subsequent activity. Without a doubt, the earliest start time at node s = 0. Any edge (activity) incident from this node can be traversed in the same amount of time as its weight. This indicates how long the activity will take to complete. The earliest start time of each activity that begins from this node is the maximum completion time owing to each edge incident on this node. For all precedence requirements to be satisfied, this is a necessary and sufficient condition.
We start the backward pass at the finish node (in our case, node Q). The goal is to address the following question: given the earliest completion deadline for the total project, when can we start a given activity without causing the project to be delayed?We won’t be able to finish the project in less than 68.8 weeks. The final activity is q, which takes 1.1 weeks and cannot begin until all of the other activities have been completed. As a result, if q is specified after 68.8 – 1.1 = 67.7 weeks, the project will be postponed. We place this limit, 67.7, in the square bracket adjacent to node M because the start of activity q is at node M.
Using this logic, we determine the latest permissible start time for each node. Figure 37b depicts the lone instance in which we must pay attention to this process. Node L indicates that action l, which has an 18.4-week length, must be completed by 59.7. As a result, it must start no later than 59.7 – 18.4 = 41.3 weeks. We can observe that the latest start time for activity k is 64.4 – 24.8 = 39.6 using the same approach. So, for event J, which of these two figures, 41.3 or 39.6, is correct? Clearly, we must choose the lower of the two figures, since if we multiply the most recent time at node J by 41.3.
Furthermore, we define a crucial path as any path from start to end with no slack time at any point along the way. It’s worth noting that a graph can contain multiple critical paths.
The critical activities are the actions that take place along any critical path. The procedure is also known as the Critical Path Method because of these terms. We can now respond to the questions posed at the outset:
(a) When do you think we’ll be able to finish the entire project?As computed by the forward pass, this is the moment we arrive at the final event (in our example, node Q).
(b) When it comes to an activity, when can we start doing it? After executing the forward pass, this is the time given by the number at the node corresponding to the commencement of the activity in the PERT graph.
(c) What are the bottleneck activities?The bottleneck is the critical activities.activities.
(d) What is the latest time we can start an activity without causing the project to be delayed?This is the result of the backward calculation.
This is the result of the backward pass calculation (the second number in the square brackets next to the event of interest).
CPM/PERT are sometimes less beneficial in practise than they are in principle for two reasons.
(a) Estimating exact time for any activity is generally challenging. As a result, most recent PERT techniques assign three time values to each activity: the best case, expected time, and worst case time. The worst case, best case, and expected length of each task are then used to create a probabilistic model. However, such projections are based on a number of assumptions, many of which may or may not be accurate in practise.
(b) The second issue is that while creating PERT graphs, we solely take into account task precedence relationships. In real-world enterprises, however, numerous tasks may share some physical resources (e.g. cranes may be used in different tasks during the project). If two or more jobs demand the same resource, they may not be able to be completed at the same time. PERT does not account for this type of limitation. To think about such scenarios, we’ll need a different kind of problem model. Resource constrained scheduling is a subfield of IELM that studies such models. It is possible to create LP formulations of such models on occasion.