There are two origins of the critical path method: the PERT method (Program Evaluation and Review Technique) developed by the United States Navy in 1957, to control the execution times of the various activities that make up space projects, due to the need to complete each of them within the available time intervals. It was originally used by the Polaris project time control and is currently used throughout the space program. The CPM method (Critical Path Method), the second origin of the current method, was also developed in 1957 in the United States of America, by an operations research center for the firm Dupont and Remington Rand,looking for the control and optimization of operating costs through adequate planning of the project's component activities.
Both methods provided the administrative elements necessary to form the current critical path method, using
control of execution times and operating costs, to seek that the total project is executed in the shortest time and at the lowest possible cost.
- Applications
The field of action of this method is very wide, given its great flexibility and adaptability to any large or small project. To obtain the best results, it should be applied to projects that have the following characteristics:
- That the project is unique, non-repetitive, in some parts or in its entirety. That all or part of the project must be executed, in a minimum time, without variations, that is, in critical time. That the cost of lowest possible operation within an available time.
Within the scope of application, the method has been used for the planning and control of various activities, such as construction of dams, opening of roads, paving, construction of houses and buildings, repair of ships, market research, settlement movements, regional economic studies, audits, university career planning, distribution of operating rooms times, factory extensions, planning of itineraries for collections, sales plans, population censuses, etc.
- Project planning and control with PERT-CPM
Good management of large-scale projects requires careful planning, scheduling, and coordination of many interrelated activities. In the early 1950s, formal procedures based on the use of networks and networking techniques were developed to assist in these tasks. Among the most outstanding procedures are PERT (program evaluation and review technique) and CPM (critical path method). Although PERT-type systems were originally applied to evaluate the schedule of a research and development project, they are also used to monitor the progress of other special types of projects. Examples include building programs, computer programming, preparing proposals and budgets,In planning maintenance and installing computer systems, this type of technique has been applied even to film production, political campaigns, and complex surgical operations.
The goal of PERT-like systems is to aid planning and control, so it doesn't involve much direct optimization. Sometimes the primary objective is to determine the probability of meeting specific delivery dates. It also identifies those activities that are more likely to become bottlenecks and points out, therefore, at which points the greatest effort should be made to avoid delays. A third objective is to evaluate the effect of program changes. For example, the effect of a possible change in resource allocation can be assessed from less critical activities to those identified as having bottlenecks. Another important application is the evaluation of the effect of deviating from schedule.
All PERT-type systems use a project network to graphically visualize the interrelationship between their elements. This representation of a project plan shows all the relationships of origin, regarding the order in which the activities should be carried out. In Fig. 1 these characteristics are shown for the initial project network for the construction of a house. This network indicates that the excavation should be done before laying the foundation and then the foundation should be completed before laying the walls. Once the walls are raised, three activities can be carried out in parallel. Following the network forward you see the order of subsequent tasks.
In PERT terminology, each arc of the network represents an activity, that is, one of the tasks required by the project, each node represents an event that is generally defined by the moment when all the activities that arrive at the end are completed. that node, The arrowheads indicate the sequence in which3 each of these events should occur. What's more, an event must precede the initiation of the activities that reach that node. The arrowheads indicate the sequence in which each of these events should occur. What's more, an event must precede the initiation of the activities that come out of that node. (In reality, successive stages of a project can often overlap, so the network may represent an idealized approximation of a project plan.)
The node towards which all activities are directed is the event that corresponds to the completion from its conception, or, if the project has already started, the plan for its completion. In the latter case, each node of the network without arriving arcs represents the event of continuing an activity in progress or the event of starting a new activity that can start at any time.
Each arch plays a double role, that of representing an activity and that of helping to represent the relationships of origin between the different activities. Sometimes an arc is needed to define provenance relationships even when there is no actual activity to represent. In this case, a fictitious activity is introduced that requires zero time, where the arc representing this fictitious activity is shown as a dotted arrow indicating that provenance relationship. For example, consider arc 5 ® 8 representing a fictitious activity in Fig. 1; the sole purpose of this arc is to indicate that the pipe placement must be complete before the exteriors can be started.
A common rule to build this type of network is that two nodes cannot be directly connected by more than one arc. Dummy activities can also be used to avoid violating this rule when you have two or more concurrent activities; This is illustrated in Fig. 1 with arch 11® 12. The sole purpose of this arch is to indicate that the flooring installation must be completed before installing interior trim without having two arches from node 9 to node 12.
Once the network of a project has been developed, the next step is to estimate the time required for each activity. These estimates for the house construction example in Figure 1. are shown in Figure 2 with the darkest numbers (in units of work days) appearing next to the arcs. These times are used to calculate two basic quantities for each event, namely its nearest time and its furthest time.
The closest time to an event is the (estimated) time in which the event will occur if the activities that follow it start as soon as possible.
The closest times are obtained by making a forward pass through the network, starting with the initial events and working forward in time, until the final events, for each event a calculation of the time in which each will occur is made. one, if each immediate proceeding event occurs in its closest time and each intervening activity consumes exactly its estimated time. The initiation of the project must be labeled with time 0. This process is shown in table 1. for the example considered in figures 1 and 2. the closest times that were obtained are recorded in figure 2, with the first of the two numbers given for each node.
The earliest time for an event is the last (estimated) time that it can occur without delaying the completion of the project beyond its closest time.
Table 1. Calculation of the nearest times for the example of the construction of a house.
| Event | Immediate event
Previous |
Time time
more + of the next activity |
Weather
= maximum plus next |
| one | ___ | ___ | 0 |
| two | one | 0 + 2 | two |
| 3 | two | 2 + 4 | 6 |
| 4 | 3 | 6 + 10 | 16 |
| 5 | 4 | 16 + 4 | twenty |
| 6 | 4 | 16 + 6 | 22 |
| 7 | 4 | 16 + 7 | 25 |
| 5 | 20 + 5 | ||
| 8 | 5 | 20 + 0 | 29 |
| 6 | 22 + 7 | ||
| 9 | 7 | 25 + 8 | 33 |
| 10 | 8 | 29 + 9 | 38 |
| eleven | 9 | 33 + 4 | 37 |
| 12 | 9 | 33 + 5 | 38 |
| eleven | 37 + 0 | ||
| 13 | 10 | 38 + 2 | 44 |
In this case the furthest times are obtained successively for the events by making a pass back through the network, starting with the final events and working backward in time to the initial ones. For each event he calculated the final time in which an event can occur so that those that follow occur at its furthest time, if each activity involved consumes exactly its estimated time. This process is illustrated in Table 2, where 44 days is the closest time and the furthest time for completion of the house construction project. The earliest times for the completion of the house construction project. The most distant times that were obtained are also found in figure 2 as the second number that is given for each node.
Let the activity (i, j) be the activity that goes from event i to event j in the project network.
The slack for an event is the difference between its earliest time and its closest time.
The slack for an activity (i, j) is the difference between and.
Thus, if everything else is assumed to be running on time, the slack for an event indicates how much delay can be tolerated to get to that event without delaying the completion of the project, and the slack for an activity indicates the same for a delay in the termination of that activity. Table 3 shows the calculations of these clearances for the project of the construction of a house.
A critical path of a project is a path whose activities have zero slack. (All activities and events that have zero slack must be on a critical path, but not others.)
Table 2. Calculation of the furthest times for the example of building a house
|
Event |
Immediate event
Previous |
Time time
more - of the distant activity |
Weather
= minimum plus next |
| 13 | __ | ___ | 44 |
| 12 | 13 | 44-6 | 38 |
| eleven | 12 | 38-0 | 38 |
| 10 | 13 | 44-2 | 42 |
| 9 | 12 | 38-5 | 33 |
| eleven | 38-4 | ||
| 8 | 10 | 42-9 | 33 |
| 7 | 9 | 33-8 | 25 |
| 6 | 8 | 33-7 | 26 |
| 5 | 8 | 33-0 | twenty |
| 7 | 25-5 | ||
| 4 | 7 | 25-7 | 16 |
| 6 | 26-6 | ||
| 5 | 20-4 | ||
| 3 | 4 | 16-10 | 6 |
| two | 3 | 6-4 | two |
| one | two | 2-2 | 0 |
Table 3. Calculation of the clearances for the example of the construction of a house.
| Event | Clearance | Exercise | Clearance | |||
| one
two 3 4 5 6 7 8 9 10 eleven 12 13 |
0 - 0 = 0
2 - 2 = 0 6 - 6 = 0 16 - 16 = 0 20 - 20 = 0 26 - 22 = 4 25 - 25 = 0 33 - 29 = 4 33 - 33 = 0 42 - 38 = 4 38 - 37 = 1 38 - 38 = 0 44 - 44 = 0 |
(1,2)
(2.3) (3,4) (4.5) (4.6) (4.7) (5.7) (6.8) (7.9) (8.10) (9.11) (9.12) (10.13) (12.13) |
2 - (0 + 2) = 0
6 - (2 + 4) = 0 16 - (6 + 10) = 0 20 - (16 + 4) = 0 26 - (16 + 6) = 4 25 - (16 + 7) = 2 25 - (20 + 5) = 0 33 - (22 + 7) = 4 33 - (25 + 8) = 0 42 - (29 + 9) = 4 38 - (33 + 4) = 1 38 - (33 + 5) = 0 44 - (38 + 2) = 4 44 - (38 + 6) = 0 |
If the activities that have zero slack are verified in table 3, it is observed that the example of the construction of a house has a critical path, 1 ® 2 ® 3 ® 4 ® 5 ® 6 ® 7 ® 9 ® 12 ® 13, as shown in figure 2 with the darker arrows. This sequence of critical activities must be kept strictly on time if delays in project completion are to be avoided. Other projects may have more than one critical path; For example, note what would happen in figure 2 if the estimated time of the activity (4,6) were changed from 6 to 19.
It is interesting to observe in table 3 that while all the events on the critical path (including 4 and 7) necessarily have zero slack, this is not the case for activity (4, 7), since its estimated time is less than the sum of the estimated times for activities (4, 5) and (5, 7). Consequently, these latter activities are on the critical path, but activity (4, 7) is not.
This information on the nearest and furthest times, clearances and the critical path, is invaluable to the project manager. Among other things, it allows you to investigate the effect of possible planning improvements to determine where a special effort should be made to stay and assess the impact of delays.
PERT
graphs The PERT graph is an original graph of unmeasured networks that contains the data of the activities represented by arrows that start from event i and end in event j.
In the upper part of the arrow the identification number is indicated, usually the event numbers (ij). The standard duration (t) of the activity appears within a rectangle at the bottom. In the upper half of the event the progressive number is noted, in the lower left quarter the last reading of the project and in the lower right quarter the first reading of the project.
This graph has the advantage of informing the earliest and latest start and end dates of each activity, without having to resort to the slack matrix.
Let's see how the factory expansion is presented by means of a PERT chart.
- Activities Network
Network is called the graphic representation of activities that show their events, sequences, interrelationships and the critical path. Not only is the method called critical path, but also the series of activities counted from the beginning of the project to its completion, which have no flexibility in their execution time, so any delay suffered by any of the activities in the series would cause a delay in the whole project.
From another point of view, critical path is the series of activities that indicates the total duration of the project. Each of the activities is represented by an arrow that begins at one event and ends at another.
An event is called the moment of initiation or termination of an activity. It is determined in a variable time between the earliest and the latest possible, of initiation or termination.
The events are also known by the names of nodes.
Event event
I j
The starting event is called i and the ending event is called j. The end event of an activity will be the start event of the next activity.
The arrows are not vectors, scalars, nor do they represent any measure. The shape of the arrows does not matter, since they will be drawn according to the needs and convenience of presentation of the network. They can be horizontal, vertical, ascending, descending, curved, straight, broken, etc.
In cases where there is a need to indicate that an activity has an interrelation or continuation with another, a dotted line, called a league, will be drawn between the two, which has a duration of zero.
The league can sometimes represent a waiting time to start the next activity
Several activities can end in an event or start from the same event.
(a) Incorrect, (b) Correct .
When building the network, the following should be avoided:
- Two activities that start from the same event and arrive at the same event. This produces confusion of time and continuity. The start event or the end event must be opened in two events and linked with a league.
- Split an activity from an intermediate part of another activity. Every activity must invariably begin at one event and end at another. When this case occurs, the base or initial activity is divided into events based on percentages and the secondary activities are derived from them.
(a) Incorrect; (b) Correct.
- Leave events loose when finishing the network. All of them must be related to the initial event or the final event.
(a) Incorrect; (b) correct
- PERT three estimate approach.
Until now it has been implicitly assumed that estimates can be obtained with reasonable accuracy of the time required for each project activity. In reality, there is often quite a bit of uncertainty about what these times will be; in fact it is a random variable that has a certain probability distribution. The original version of PERT takes this uncertainty into account by using three different types of estimates for the times of the activities, in order to obtain basic information about their probability distribution. This information for all time of the activities is used to estimate the probability of finishing the project on the scheduled date.
The three estimates used by PERT for each activity are a most likely estimate, an optimistic estimate, and a pessimistic estimate. The most probable estimate (denoted by m) tries to be the most realistic estimate of the time an activity can take. In statistical terms, it is an estimate of the mode (the highest point) of the probability distribution for the time of the activity. The optimistic estimate (denoted by a) tries to be the unlikely but possible time if all goes well; it is essentially an estimate of the lower bound of the probability distribution. Finally, the pessimistic estimate (denoted by b) is intended to be the unlikely but possible time if everything goes wrong. In statistical terms,it is essentially an estimate of the upper bound of the probability distribution. Figure 3 shows the ideal location of these three estimates with respect to the probability distribution.
Elapsed time
Figure 3. Probability distribution model for the times of activities in the approach of three PERT estimates: m = probable estimate, a = optimistic estimate and b = pessimistic estimate.
Two assumptions are made to convert m, a and b into estimates of the expected value (t e) and the variance (s 2) of the time required for the activity. One assumption is that s, the standard deviation (square root of the variance), is equal to one sixth of the range of reasonably possible time requirements; this is, is the desired estimate of the variance. The rationale for making this assumption is that the tails of many probability distributions (as in the normal distribution) are considered to be more or less three standard deviations from the mean, so that there is a spread of about six standard deviations between tails, for example, control charts commonly used for statistical quality control are constructed so that the dispersion between the control limits is estimated to be six standard deviations.
To obtain the estimate of the expected value (t e), an assumption about the shape of the probability distribution is also necessary, the distribution is assumed to be (at least approximately) a beta distribution. This type of distribution has the form shown in figure 3, which is reasonable for this purpose.
If the model illustrated in figure 3 is used, the expected value of the time of an activity is approximately
Note that the middle of the interval (a + b) / 2 lies between a and b so that t e is the weighted arithmetic mean of the mode and half of the interval, with a two-thirds weight for the mode. Although the assumption of a beta distribution is arbitrary, it serves the purpose of locating the expected value am, a and b in a way that appears to be reasonable.
After calculating the expected value and estimated variance for each of the activities, three additional assumptions (or approximations) are needed to calculate the probability of completing the project on time. One is that the times of the activities are statistically independent. A second is that the critical route (in terms of expected times) always requires a greater total time than any other route. This implies that the expected value and the variance, it is easy to find the probability that this normal random variable (project time) is less than the scheduled completion time.
- CPM method for trade-offs between time and cost
The original versions of CPM and PERT differ in two important respects. First, the CPM assumes that activity times are deterministic (that is, they can be predicted reliably without significant uncertainty), so it does not need the three estimates just described. Second, instead of giving prime importance to time (explicitly), CPM assigns equal importance to time and cost and highlights this by constructing a time-cost curve for each activity, with the one shown in Figure 4. This curve represents the relationship between the direct cost budgeted for the activity and its resulting duration time.
Figure 4. Time-cost curve for activity (i, j).
Usually the graph is based on two points: the normal and the intensive or break. The normal point gives the cost and the time necessary when the activity is carried out in the normal way, without incurring additional costs (overtime of labor, special equipment or materials to save time, etc.), To speed up the activity. On the contrary, the break point provides the time and cost necessary when the activity is carried out in an intensive or break way, that is, it is completely accelerated without regard to costs, in order to reduce its duration time as much as possible. can. As an approximation, it is then assumed that all intermediate trade-offs between time and costs are possible and that they lie on the line segment joining these two points. (Note the dark line segment in Fig. 4). So,the only estimates project staff have to obtain are cost and time for these two items.
The fundamental objective of the CPM is to determine the trade-off between time and cost that must be used in each activity to meet the project completion time that is scheduled at a minimum cost. One way to determine the
optimal combination of time and cost is to apply linear programming. To discover this, it is necessary to introduce new notation, part of which is summarized in figure 4. Let
D ij = normal time for activity (i, j)
CD ij = normal (direct) cost for activity (i, j)
d ij = break time for activity (i, j)
Cd ij = (direct) break cost for activity (i, j)
The decision variables for the problem are x ij where
x ij = duration of the activity (i, j)
Then there is a decision variable x ij for each activity, but there is none for the values of i and j that do not have a corresponding activity.
To express the direct cost of activity (i, j) as a (linear) function of X jj, denote the slope of the line that passes through the normal and break points for activity (i, j) by
Also define K ij as the intersection with the direct cost axis of this line, as shown in fig. 4, therefore,
direct cost of the activity (i, j) = K ij + S ij x ij,
consequently, total direct cost of the project =
where the sum is spread over all activities (i, j). Now the problem can be stated and formulated mathematically.
The problem: given a project completion time T (maximum), select the x jj that minimizes the total direct cost of the project.
Linear Programming Formulation. To take the project completion time into account in the linear programming formulation of the problem, one more variable is needed for each event. This additional variable is
yk = nearest (unknown) time for event k, which is a deterministic function of X ij.
Each yk is an auxiliary variable, that is, a variable that is introduced to the model because it is convenient in the formulation and that does not represent a decision. The simplex method treats auxiliary variables the same as normal decision variables (x ij).
To see how the yk's are introduced into the formulation, consider event 7 in Figure 1 By definition, its closest time is:
y 7 = max {y 4 + x 47, y 5 + x 57 },
In other words y 7 is the smallest quantity such that the following two restrictions hold:
y 4 + x 47 < y 7
y 5 + x 45 < y 7, so these two constraints can be incorporated directly into the linear programming formulation (after passing y 7 to the left side to get the appropriate form). Still further, we will see later why the optimal solution obtained with the simple method for the complete model will automatically make the value of y 7 be the smallest quantity that satisfies these restrictions, so no more are needed restrictions to incorporate the definition of y 7 into the model.
Within the process and incorporation of these restrictions for all events, each variable x ij will appear in exactly one restriction of this type, which can be expressed in the appropriate way as
To continue preparations to write the complete linear programming model, they are labeled
Event 1 = project start
Event n = project end,
thus
= 0
= completion time..
Note also that it is a fixed constant that can be eliminated from the objective function, so that minimizing the total direct cost for the project is equivalent to maximizing.Therefore, the linear programming problem is to find the (and corresponding) ones such that
Maximize
Hold it:
For all activities (i, j)
From a computational point of view, this model can be improved somewhat by substituting all for
throughout the model, so that the first set of functional constraints () is replaced by the non-negativity constraints
It is also convenient to introduce non-negativity restrictions for the rest of the variables:
although these variables were already forced to be non-negative when setting y 1 = 0, due to
restrictions and
An interesting property of an optimal solution for this model is that (under normal circumstances) every path in the network will be a critical path that requires a time T. The reason is that such a solution satisfies the constraints while avoiding the additional costs incurred to shorten the time of any trajectory.
The key to this formulation is the way in which the are introduced to the model by the constraints, in order to provide the closest times for the respective events (given the values of the in the current basic feasible solution). As the closest times have to be obtained in order, all of these are only necessary to finally obtain the correct value of (for the current values of the), thus reinforcing the restriction. However, getting the correct value requires that the value of each (even of) be the smallest amount that satisfies all the restrictions. Now a brief description will be made of why (under normal circumstances) this property holds for an optimal solution.
Consider a solution for the variables such that every path in the network is critical and requires a time T. If the values of las satisfy the previous property, then las are the closest true times with exactly and the complete solution for y satisfies all The restrictions. However, if some get a little bigger, this would create a chain reaction where some would have to get a little bigger to still satisfy the constraints etc., until ultimately they have to get a little bigger. and the restriction is violated. The only way to avoid this with a slightly larger one is to make the duration times of some activities (after event i) a little shorter, thereby increasing the cost. Thus,an optimal solution will prevent them from being larger than necessary to satisfy the constraints.
The problem, as stated here, assumes that a specific delivery date T (perhaps by contract) has been set for project completion. Some projects do not actually have a due date, in which case it is unclear what value to assign to T in the linear programming formulation. In these types of situations, the decision on T (which turns out to be the duration of the project in the optimal solution), in fact depends on which is the best trade-off between the total cost and the total time of the project.
The basic information needed to make this decision is how the minimum total direct cost changes when the value of T in the previous formulation changes, as shown in Figure 5. This information can be obtained when parametric linear programming is used to obtain the optimal solution as a function of T over the entire interval. There are even more efficient procedures to obtain this information that exploit the special structure of the problem.
Figure 5 provides a useful basis for the manager's decision-making on the value of T (and the corresponding optimal solution for) when the important effects of project duration (other than direct costs) are essentially intangible. Now, when these other effects that are basically financial (indirect costs), it is appropriate to combine the curve of the total direct cost of figure 5 with a curve of minimum total indirect cost (supervision, facilities, interest, contractual penalties) against t, as shown in figure 6. The sum of these curves will provide the curve of the minimum total cost of the project for different values of T. The optimal value of T will then be the one that minimizes this total cost curve.
- Choice between PERT and CPM
The choice between the three PERT estimates approach and the CPM time-cost trade-off method depends primarily on the type of project and management objectives. PERT is particularly appropriate when handling a lot of uncertainty when predicting activity times and when it is important to effectively control project scheduling; for example, most research and development projects fall into this category. On the other hand, CPM is very appropriate when activity times can be well predicted.
(perhaps based on experience) and when these times can be easily adjusted (for example, if brigade sizes are changed), as well as when it is important to plan an appropriate combination between project time and cost. The latter type is represented by many construction and maintenance projects.
Currently, the differences between the current versions of PERT and CPM are not as marked as described. Many versions of PERT allow a single estimate (the most likely) to be used for each activity, thus omitting the probabilistic investigation. A version called PERT / Cost also considers combinations of time and cost in a similar way to CPM.
- Differences Between PERT and CPM
The difference between PERT and CPM is the way in which time estimates are made. E1 PERT assumes that the time to perform each of the activities is a random variable described by a probability distribution. The CPM, on the other hand, infers that the times of the activities are known in a deterministic way and can be varied by changing the level of resources used.
The time distribution that PERT assumes for an activity is a beta distribution. The distribution for any activity is defined by three estimates:
- the most likely time estimate, m, the most optimistic time estimate, a; and the most pessimistic time estimate, b.
The shape of the distribution is shown in the following Figure. The most likely time is the time required to complete the activity under normal conditions. Optimistic and pessimistic times provide a measure of the uncertainty inherent in the activity, including equipment breakdowns, labor availability, material delays, and other factors.
With the defined distribution, the mean (expected) and standard deviation, respectively, of the activity time for the Z activity can be calculated using the approximation formulas.
The expected completion time of a project is the sum of all the expected times of the activities on the critical path. Similarly, assuming that the time distributions of the activities are independent (realistically, a strongly questionable assumption), the project variance is the sum of the variances of the activities on the critical path. These properties will be demonstrated later.
In CPM only an estimate of time is required. All calculations are made with the assumption that the uptime is known. As the project progresses, these estimates are used to monitor and monitor progress. If any delay occurs in the project, efforts are made to get the project back on schedule by changing the allocation of resources.
- Bibliography
- Frederick S. Hillier, Gerald J. Lieberman; Introduction to Operations Research, Fifth Edition, Edit. McGraw Hill, Mexico 1993.http: //www.gestiopolis.com
