PERT method

see the course in PDF

Like the Gantt chart, the PERT method makes it possible to evaluate the duration of completion of a complex project and to detect the parts of this project that do not bear any delay.

The task information are summarized in a timeline like the following example:

 task predecessor time A – 6 B – 5 C A 4 D B 6 E C 5 F A, D 6 G E, F 4

Step 1: Building the graph from the timeline

• Determination of the levels of the tasks:

Level 0 will be assigned to tasks that do not have a previous task.

Level 1 will be assigned to tasks whose previous tasks are level 0.

This will determine the level of each task: the tasks at level k + 1 will be the tasks whose previous tasks are of lower level with at least one task of level k among them.

We will build the graph by tracing the tasks by increasing level.

• Beginning, finishing, convergent tasks:

Before starting the construction of the graph, it will often be useful to detect so-called starting, finishing or convergent tasks.

The starting tasks are the tasks without previous task, they start from the vertex 1 of the graph.
The finishing tasks are the tasks that are not anterior task, they arrive at the terminal vertex of the graph.
Convergent tasks are tasks that are always encountered together (ie never one without the other) in the Prior Tasks column; in the graph, they will have the same terminal vertex. The edge between 2 and 5 is called a fictional task and is always of zero weight. Its purpose is to model the fact that task A must be completed to start task F. The edge between 1 and 2 means that task A starts in state 1 and ends in state 2.

Step 2: Determine dates and margins

Once the graph is built, we will determine the dates at the earliest and at the latest for the different vertices and the free and total margins for the tasks.

• Dates at the earliest:
For a vertex, the earliest date (noted t) represents the minimum time required to reach that summit. It will be determined step by step, in ascending order of vertex, from the entry of the graph, thanks to Ford’s search algorithm of the longest path.

t1 = 0 and tj = Max ( ti + dij ) for all i predecessor of j and dij = time between i and j.
In our example, t1 = 0, t2 = 0+6 = 6, t3 = 0+5 = 5, t4 = 6+4 = 10, t5 = max ( 6+0 , 5+6 ) = 11, t6 = max ( 11+6 , 10+5 ) = 17, t7 = 17+4 = 21.

The earliest date of the output of the graph represents the minimum duration achievable for the entire project (in our example, t7= 21).

• Dates at the latest:
For a vertex, the date at the latest (noted T) concretely represents the date on which this state must be reached if one does not want to increase the total duration of the project. It will be determined analogously to t, but in descending order of vertex, from the output of the graph to the input.

Tn = tn = Total time and Ti = Min ( Tj – dij ) for all j predecessor of i.
In our example, T7 = 21, T6 = 21 – 4 = 17, T5 = 17 – 6 = 11, T4 = 17 – 5 = 12, T3 = 11 – 6 = 5, T2 = min ( 11-0 , 12-4 ) = 8, T1 = min ( 8-6 , 5-5 ) = 0.
We always have t1 = T1 = 0 and t inferior or equal to T for each vertex. We call T-t the margin for every vertex.

• Margin of task:
The free margin of a task represents the maximum possible delay of a task without delaying the start of the following tasks, note ML. The total margin of a task represents the maximum possible delay for carrying out a task without delaying the whole project, it will be noted MT: MLij = tj – ti – dij et MTij = Tj – ti – dij.

Given the calculation mode, the margins are always positive or zero and the free margin of a task will always be less than or equal to its total margin.

It is called critical, a task whose total margin is zero. A critical task must not be delayed if we do not want to increase the total duration of the project.

If the duration of a non-critical task increases, part of this increase will be absorbed by the margin of the task, only the surplus will affect the duration of the project. Aside

Vertices can contain multiple pieces of information at the same time: Publicités