La théorie des graphes

 Un graphe est une représentation symbolique d’un

réseau. Il s’agit d’une abstraction de la réalité de
sorte à permettre sa modélisation.
 Un réseau peut être représenté sous forme de graphe.
Un graphe G consiste en un ensemble de noeuds v et
d’arcs e. Par suite, G=(v,e).
 Un sommet v (nœud ) est un point d’extrémité ou un
point d’intersection d’un graphe .
 Un arc e est un lien entre deux sommets. Un arc
possède une direction souvent symbolisée par une
flèche.

Recherche Opérationnelle 1
 La théorie des graphes

 Ce graphe se définit de
façon suivante:
G = (v,e)
v = (1,2,3,4,5)
e = (1,2), (1,3), (2,2),
(2,5), (4,2), (4,3), (4,5)

On appelle un sous-graphe d'un graphe un graphe dont on a enlevé des

sommets.

Recherche Opérationnelle 2
 la théorie des graphes

 Une arête est un groupe de deux sommets tels qu’un

sommet fait partie de l’ensemble des correspondants de
l’autre sommet.

Ce graphe comporte 5 arcs

[(1,2), (2,1),(2,3), (4,3), (4,4)]
et 3 arêtes [(1-2), (2-3), (3-4)].

Recherche Opérationnelle 3
 la théorie des graphes

 L’établissement de chemins est une étape fondamentale dans la

mesure d’accessibilité et de flux de trafic au sein d’un réseau.
 Un chemin eulérien est un chemin simple qui passe une fois et
une seule par chaque arc.
 Un chemin hamiltonien est un chemin qui passe une fois et une
seule par chaque sommet.
 Une chaîne est une suite d’arcs telle que chaque arc de la
suite a une extrémité en commun avec l’arc précedent. La
direction n’a pas d’importance.

Recherche Opérationnelle 4
 la théorie des graphes
 Un circuit est un chemin fini et fermé dont l’extrémité
terminale du dernier arc coïncide avec l’extrémité
initiale du premier.

 Un cycle est une chaîne dont le sommet initial et

terminal coïncide et qui n’emprunte pas le même arc
constitue un cycle.

 Il convient de distinguer deux grands types de graphes

: les graphes orientés et ceux qui ne le sont pas (les
graphes non orientées).
Recherche Opérationnelle 5
 Le Problème
d’affectation

Recherche Opérationnelle 6
Le ProbLème d’affectation

 Il s'agit d'affecter :
- des famille de produits à des zones de stock,
- des commerciaux à des secteurs,
- des ouvriers sur des machines,
- des projets a des étudiants
- etc…

Recherche Opérationnelle 7
 Problème d’affectation
La méthode hongroise
( algorithme de KHUN)

 L’algorithme de résolution du problème d’affectation

fut crée par Harold KUHN en 1955. Il est utilisé
pour minimiser un cout ou maximiser une
satisfaction suite à différentes affectations .

Recherche Opérationnelle 8
 ProbLème d’affectation
La méthode hongroise

 Application :
• Les coûts de fabrication des ouvriers sur les diverses
machines sont donnés par le tableau ci-dessous.
• Chercher la meilleure affectation de manière à rendre le coût
de fabrication minimal

Recherche Opérationnelle 9
 Problème d’affectation
La méthode hongroise
 Etape 1: Obtention des zéros
Créer une nouvelle matrice des coûts en choisissant le
coût minimal dans chaque colonne et en le soustrayant
de chaque coût dans la colonne ( Idem pour les lignes ).

Recherche Opérationnelle 10
 Problème d’affectation
La méthode hongroise

 Etape 2:Recherche d’une solution optimale

- On cherche la ligne ou des lignes comptant le

moins de zéro.
- On encadre un des zéros de cette ligne, puis on
barre les zéros qui se trouvent sur la même ligne et
dans la même colonne que les zéros encadrés.
- On répète le processus pour les lignes restantes.
Un zéro encadré par ligne ⇒ Solution optimale

Recherche Opérationnelle 11
 Problème d’affectation
La méthode hongroise

 La ligne 4 ne contient pas un zéro encadré donc on va

appliquer l’étape 3 et 4 de l’algorithme.

Recherche Opérationnelle 12
 Problème d’affectation
La méthode hongroise
 Etape 3: Recherche des rangées en nombre minimal
contenant tous les zéros (procédure de marquage):
a. On marque d’une croix toute ligne ne contenant aucun
zéro encadré.
b. On marque toute colonne qui a un zéro barré sur une ou
plusieurs lignes marquées.
c. On marque toute ligne qui a un zéro encadré sur une ou
plusieurs colonnes marquées.
d. On répète b) et c) jusqu’à ce qu’il n’y ait plus de colonne
ou de ligne à marquer.
On trace un trait sur toute colonne marquée.
On trace un trait sur toute ligne non marquée.
Recherche Opérationnelle 13
 Problème d’affectation
La méthode hongroise

Recherche Opérationnelle 14
 Problème d’affectation
La méthode hongroise

 Etape 4: Déplacement de certains zéros:

-Tableau partiel : éléments traversés par aucun trait.
- Le plus petit élément du tableau partiel est ajouté aux
éléments rayés deux fois et retranché des éléments du
tableau.
- Retour à la phase 2.

Recherche Opérationnelle 15
 Problème d’affectation
La méthode hongroise

 Le plus petit élément est 2, ainsi on aura le tableau ci-

dessous:

Recherche Opérationnelle 16
 Problème d’affectation
La méthode hongroise

Recherche Opérationnelle 17
Problème d’affectation
La méthode hongroise

Recherche Opérationnelle 18
 Le Problème Du
FLOT MAXIMAL

Recherche Opérationnelle 19
 Le Problème Du FLOT MAXIMAL
 Le problème des flots dans les réseaux concerne la circulation de matière sur
les arcs d’un graphe. Parmi les nombreuses applications qui relèvent de ce
problème, on trouve:

o les réseaux de transport de marchandises (urbains, ferroviaires ou

aériens) de différents points distributeurs à différents points
consommateurs ;

o l’écoulement de liquides à l’intérieur de tuyaux ;

o le courant dans les réseaux électriques ;

o l’informatique à travers les réseaux de communication ;

o etc.

Recherche Opérationnelle 20
 Flots dans les réseaux
PROBLEME DU FLOT MAXIMUM

Objectif : Faire transiter la plus grande quantité

(informations, marchandises, personnes) d’une source
vers une destination au sein d’un réseau.

Un réseau avec capacités R = (X,U,C) d’ordre n est un

graphe orienté asymétrique* valué dans lequel :
 -1(x1) = Ø x1 est le sommet entrée (source)
 (xn) = Ø xn est le sommet sortie (destination)

*  (xi,xj)  U  (xj,xi)  U (arc à sens unique)

Notation :  (xi,xj)  U : C(xi,xj) = Cij capacité de l’arc
(xi,xj)
Exemple de réseau avec capacités

b
[3]
[7]

[5]
Entrée a [4] d e Sortie
[2]
[5]
[2]

c
 Définition du flot réalisable

Un flot F sur un réseau avec capacités R = (X,U,C) est

une valuation de l’ensemble des arcs U. Le flot correspond
à la quantité qui transite sur le réseau.
Notation :  (xi,xj)  U : F(xi,xj) = Fij flot sur l’arc (xi,xj)

Un flot F sur R = (X,U,C) est réalisable s’il satisfait les

contraintes de :
1. Capacité des arcs
Le flot sur un arc ne dépasse pas la capacité de cet
arc.
2. Conservation du flux (loi de Kirchhoff)
La somme des flots entrant dans un sommet est égale
à la somme des flots sortant de ce sommet.
 Définition du flot maximal

La valeur d’un flot F sur R = (X,U,C)

correspond à la quantité totale qui transite
sur le réseau. La valeur du flot correspond à
la somme des flots sortant de l’entrée qui
est égale à la somme des flots convergeant
vers la sortie (conservation du flux).
Un flot F sur R = (X,U,C) est maximal si F
est un flot réalisable qui maximise la valeur
du flot.
 Determination du flot maximal

 Connaissant les capacités des arcs d'un

réseau de transport, le problème du flot
maximum consiste à trouver quelle est la
quantité maximum de flot qui peut circuler
de la source à la destination. L'algorithme le
plus connu pour résoudre ce problème est
celui de Ford-Fulkerson. Nous verrons
l’approche par cette méthode qui consiste à
construire un graphe "d'écart" dans lequel
on recherche un chemin.
 Construction du graphe d’écart

Un arc (xi,xj) du réseau R = (X,U,C) est saturé par le flot F si :

Fij = Cij (capacité maximale atteinte)
Un arc (xi,xj) du réseau R = (X,U,C) est antisaturé par F si :
Fij = 0 (flot inexistant)

A partir du réseau R = (X,U,C) et d’un flot F, on peut construire le

graphe d’écart G = (X,F(U),E) qui traduit les augmentations ou
diminutions possibles du flot F dans le réseau.
 (xi,xj)  U :
Si Fij < Cij (non saturé) alors (xi,xj)  F(U) , Eij = Cij-Fij (augmentation)
Si Fij > 0 (non antisaturé) alors (xj,xi)  F(U) , Eji = Fij (diminution)
 Exemple de graphe d’écart
b b
3 [3] 2
5 [7] 3
5
a 2 [4] d a 2 2 d
1
4 [5] 2 [2] 4 2

c c

Réseau R = (X,U,C) Graphe d’écart G = (X,F(U),E)

 Construction d’un flot maximal

Algorithme de Ford-Fulkerson
Initialisation du flot F : Fij = 0 (arcs antisaturés)
Fin = FAUX
Tant que NON Fin
Construction du graphe d’écart G = (X,F(U),E)
Recherche d’un chemin C dans G depuis l’entrée vers la
sortie
Si C existe Alors
Calcul de l’augmentation
Affectation de l’augmentation
Sinon
Fin = VRAI
 ALGORITHME DE FORD-FULKERSON,
GRAPHE D'ECART

 On part d'un flot compatible. Ensuite, on construit un graphe d'écart à

partir de ce flot. Ce graphe d'écart représente les modifications de flot
possibles sur chaque arc. Sur ce graphe, les nœuds ont exactement la
même signification que dans le réseau de transport.
 Par contre, un arc indiquera de combien il est possible d'augmenter le
flot entre deux nœuds. Ainsi,

 pour un arc u = (x;y), on créera dans le graphe d'écart:

un arc de x à y de capacité c'((x;y)) = c(u) - f(u) si c(u) > f(u),
un arc de y à x de capacité c'((y;x)) = f(u) si f(u)> 0.

 Ensuite, dans ce graphe d'écart, on cherchera un chemin de l’entrée à

la sortie. Si on n'en trouve pas, le problème est résolu. Sinon, on
augmente le flot sur ce chemin. Le flot sera augmenté de la plus petite
capacité des arcs du chemin. Autrement dit, le chemin C sera
augmenté de:
min{c'(u) | u étant sur le chemin C}
Exemple : réseau et graphe
d’écart correspondant
 Augmentation du flot

 (A,B,C,D,F,G) est un chemin pour aller de A à G.

On peut augmenter le flot de:
 2 entre A et B, 3 entre B et C,1 entre C et D,4
entre D et F, 2 entre F et G.
 On augmentera donc le flot de 1 sur ce chemin, ce
qui signifie:
 augmenter de 1 entre A et B, réduire de 1 entre C
et B, augmenter de 1 entre C et D, augmenter de
1 entre D et F, augmenter de 1 entre F et G.
 Flot dans un réseau de transport

 On veut acheminer un produit à partir de 3

entrepôts (1,2,3) vers 4 clients (a,b,c,d)
 Quantités en stock : 45, 25, 25
 Demande des clients : 30,10, 20, 30
 Limitations en matière de transport d’un entrepôt à
un client a

1
a b c d b
E [0,25]
1 10 15 - 20 2 S

2 20 5 5 - c
3
3 - - 10 10
d
 Exemple de flot
a

b
[0,25], 25
E 2 S

Valeur du flot = 80
d

Ce flot est un flot complet, c-à-d, tout chemin de

E à S comporte au moins un arc saturé
 Détermination d’un flot maximum
 Principe de l’algorithme de Ford-Fulkerson
1. Construire un flot complet
2. Améliorer itérativement ce flot pour le maximiser

1. Construire un flot complet

 Examiner tous les chemins de E à S de façon
systématique
 Pour chaque chemin faire passer un flot égal à la
capacité résiduelle minimale de ce chemin
P.S
o Un flot complet n’est pas forcément maximum.
o Un flot maximum est forcément complet
 a

b
S [25,25] 2 T

c
Un flot complet 3

d
25
10 a
Graphe d’écart
15
1
10 5 5
10
35 5 b
10
25 5 5
S 2 T
5
5 c
15
10
20 20
3 30
10
d
Détermination d’un flot maximum

Améliorer itérativement ce flot

 Théorème : Un flot  compatible est
maximal ssi il n’existe pas de chemin de
E à S dans Ge().
 Principe de l’amélioration
 Chercher un chemin  de E à S dans Ge()
 Soit  la plus petite capacité de 
 Pour j+ de , augmenter j de 
 Pour j- de , diminuer j de 
Détermination d’un flot maximum

25
10 30
a

5 10 5 20 15 5 0 0 5
10 1

35 40 10 5
b
0 10
25 5 5
S 2 5 T
5
5 c
15
10
20 20
3 30
10
d

Valeur du flot = 85
Capacité minimale  = 5
 a

b
[25,25]
S 2 T

Un flot complet
d

30
10 a
Graphe d’écart 20
5 1

40 5 10 b
10
25 0 5
S 2 T
5
5 c
15
10
20 20
3 30
10
PLUS DE CHEMIN entre S et T d
 Le Problème Du
chemin optimal

Recherche Opérationnelle 39
 Dijkstra’s algorithm

notation:
 c(x,y): link cost from node
 computes least cost paths x to y; = ∞ if not direct
from one node (‘source”) neighbors
to all other nodes  D(v): current value of cost
 gives forwarding table for of path from source to
that node destination v
 iterative: after k iterations,  p(v): predecessor node
along path from source to
know least cost path to k v
destinations  N': set of nodes whose
least cost path definitively
known
Dijkstra’s algorithm
1 Initialization:
2 N' = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
7
8 Loop
9 find w not in N' such that D(w) is a minimum
10 add w to N'
11 update D(v) for all v adjacent to w and not in N' :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N'
 Dijkstra’s algorithm: example

D(v) D(w) D(x) D(y) D(z)

Step N' p(v) p(w) p(x) p(y) p(z)
0 u 7,u 3,u 5,u ∞ ∞
1 uw 6,w 5,u 11,w ∞
2 uwx 6,w 11,w 14,x
uwxv x
3 10,v 14,x
9
4 uwxvy 12,y
5 uwxvyz 5 7
4
8
note: u 3 w y z
 construct shortest path tree by 2
tracing predecessor nodes 3
7 4
v
 Dijkstra’s algorithm: Another
example

Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z)

0 u 2,u 5,u 1,u ∞ ∞
1 ux 2,u 4,x 2,x ∞
2 uxy 2,u 3,y 4,y
3 uxyv 3,y 4,y
4 uxyvw 4,y
5 uxyvwz

5 resulting shortest-path tree from u:

v 3 w v w
2 5
u u z
2 1 z
3
1 x y
x y 2
1
 Bellman-Ford algorithm

Bellman-Ford equation (dynamic programming)

let
dx(y) := cost of least-cost path from x to y
then
dx(y) = minv {c(x,v) + dv(y) }

cost from neighbor v to destination y

cost to neighbor v

min taken over all neighbors v of x

 Bellman-Ford example

5
clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
v 3 w
2 5
u 2 z
1
3
1
x y 2
B-F equation says:
1
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
1 + 3,
5 + 3} = 4
 Distance vector algorithm

 Dx(y) = estimate of least cost from x to y

 x maintains distance vector Dx = [Dx(y): y є N ]
 node x:
 knows cost to each neighbor v: c(x,v)
 maintains its neighbors’ distance vectors. For
each neighbor v, x maintains
Dv = [Dv(y): y є N ]
 Distance vector algorithm
key idea:
 from time-to-time, each node sends its
own distance vector estimate to
neighbors
 when x receives new DV estimate from
neighbor, it updates its own DV using
B-F equation:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N
 under minor, natural conditions, the estimate Dx(y)
converge to the actual least cost dx(y)
 Dx(z) = min{c(x,y) +
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to cost to
table x y z x y z
x 0 2 7 x 0 2 3

from
from

y ∞∞ ∞ y 2 0 1
z ∞∞ ∞ z 7 1 0

node y cost to
table x y z y
2 1
x ∞ ∞ ∞
x z
from

y 2 0 1 7
z ∞∞ ∞

node z cost to
table x y z
x ∞∞ ∞
from

y ∞∞ ∞
z 7 1 0
time
 Dx(z) = min{c(x,y) +
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}
= min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x cost to cost to cost to
table x y z x y z x y z
x 0 2 7 x 0 2 3 x 0 2 3

from
from

y ∞∞ ∞ y 2 0 1

from
y 2 0 1
z ∞∞ ∞ z 7 1 0 z 3 1 0
node y cost to cost to cost to
table x y z x y z x y z y
2 1
x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z
from

from

y 2 0 1 y 2 0 1

from
y 2 0 1 7
z ∞∞ ∞ z 7 1 0 z 3 1 0

node z cost to cost to cost to

table x y z x y z x y z

x ∞∞ ∞ x 0 2 7 x 0 2 3
from

from

y 2 0 1 y 2 0 1
from

y ∞∞ ∞
z 7 1 0 z 3 1 0 z 3 1 0
time
 Why Distance Vector Works

San
2 Hops
1 Hop
From SJ
Jose
3 Hops From SJ
From SJ

Hop-1 nodes
calculate current
(next hop, dist), &
send to neighbors
Accurate info about SJ
ripples across network,
Shortest Path Converges
Iteration Node 1 Node 2 Node 3 Node 4 Node 5

Initial (-1, ) (-1, ) (-1, ) (-1, ) (-1, )

1
2
3

Table entry Table entry

@ node 1 @ node 3
for dest SJ for dest SJ

2 3
1 1 San
5 2

4
Jose
3 1 3 6

2
2 5
4
Iteration Node 1 Node 2 Node 3 Node 4 Node 5

Initial (-1, ) (-1, ) (-1, ) (-1, ) (-1, )

1 (-1, ) (-1, ) (6,1) (-1, ) (6,2)
2
3

D3=D6+1
n3=6
D6=0
2 3 1
1 1
5 2
0
4 San
3 6
1 3
Jose
2 5 2
4
2
D5=D6+2 D6=0
n5=6
Iteration Node 1 Node 2 Node 3 Node 4 Node 5

Initial (-1, ) (-1, ) (-1, ) (-1, ) (-1, )

1 (-1, ) (-1, ) (6, 1) (-1, ) (6,2)
2 (3,3) (5,6) (6, 1) (3,3) (6,2)
3

3 1
2 3
1 1
5 2
3 0
4 San
3 6
1 3
Jose
2 2
5
4
6 2
Iteration Node 1 Node 2 Node 3 Node 4 Node 5

Initial (-1, ) (-1, ) (-1, ) (-1, ) (-1, )

1 (-1, ) (-1, ) (6, 1) (-1, ) (6,2)
2 (3,3) (5,6) (6, 1) (3,3) (6,2)
3 (3,3) (4,4) (6, 1) (3,3) (6,2)

1
3 2 3
1 1
5 2
3 0
4 San
3 6
1 3
Jose
2
2 5
4
6 4 2
 Le Problème
d’ordonnancement
Project Planning and scheduling
CPM / PERT
Recherche Opérationnelle 55
 Project Planning

 Be able to: develop precedence relationship

diagram which shows sequential relationship
of project activities.
 Determine the project’s time
 Determine the critical path in the project.

56
 Gantt Chart

 Popular tool for project scheduling

 Graph with bar representing time for each task
 Provides visual display of project schedule
 Also shows slack for activities
 Slack = amount of time activity can be delayed
without delaying project.

57
 A Gantt Chart example
Month
0  2  4  6  8  10
Activity

Design house and

obtain financing

Lay foundation

Order and receive

materials

Build house

Select paint

Select carpet

Finish work
    
1 3 5 7 9 58
 CPM/PERT

 Critical Path Method (CPM)

 Deterministic task times
 Activity-On-Arrow graph construction (AOA)

 Project Evaluation & Review Technique

(PERT)
 Multiple task time estimates (probabilistic)
 Activity-On-Node graph construction (AON)

59
 Graph Construction

 In AON, nodes represent activities & arrows

show precedence relationships.

 In AOA, arrows represent activities & nodes are

events for points in time.
 An event is the completion or beginning of an
activity.
 A dummy shows precedence for two activities with
same start & end nodes

60
 Graph Construction Example

Consider the following table which describes the

activities to be done to build a house and its sequence.

Activity predecessors Duration

A Design house and obtain financing - 3
B Lay foundation A 2
C Order and receive materials A 1
D Build house B,C 3
E Select paint B,C 1
F Select carpet E 1
G Finish work D,F 1
61
 Concurrent Activities

3
Lay foundation
Lay Dummy
foundation
2 3
2 4

Order material
Order material
Incorrect Correct
precedence precedence
relationship relationship

62
 Project graph For A House

3
Lay foundation Dummy
0
2 Build Finish
3 1 house work
1 2 4 6 7
3 1
Design house Order and 1
and obtain receive materials Select 1 Select
financing paint carpet
5

63
 Critical Path

 A path is a sequence of connected activities

running from the start to the end node in a
graph.

 The critical path is the path with the longest

duration in the graph.

 A project cannot be completed in less than the

time of the critical path (under normal
circumstances).

64
 All Possible Paths
3
Lay foundation Dummy
0
2 Build Finish
3 1 house work
1 2 4 6 7
3 1
Design house Order and 1
and obtain receive materials Select 1 Select
financing paint carpet
5
path1: 1-2-3-4-6-7
3 + 2 + 0 + 3 + 1 = 9 months; the critical path
path2: 1-2-3-4-5-6-7
3 + 2 + 0 + 1 + 1 + 1 = 8 months
path3: 1-2-4-6-7
3 + 1 + 3 + 1 = 8 months
path4: 1-2-4-5-6-7
3 + 1 + 1 + 1 + 1 = 7 months 65
 Early Times

 ES (Early Start) - Earliest time activity can start

 Forward pass starts at beginning of the graph to
determine ES times

 EF (Early Finish) = ES + activity time

 ESij = maximum (EFi) i1
 max (EFi) = max(EFi1i, EFi2i, EFi3i)
 EFij = ESij + tij i2
i
j
i3
66
 Computing Early Times
(House building example)
3
Lay foundation Dummy
0
2 Build Finish
3 1 house work
1 2 4 6 7
3 1
Design house Order and 1
and obtain receive materials Select 1
financing paint
5

ES12 = 0
EF12 = ES12 + t12 = 0 + 3 = 3 months
ES23 = max (EF2) = 3 months
ES46 = max (EF4) = max (5,4) = 5 months
EF46 = ES46 + t46 = 5 + 3 = 8 months
EF67 =9 months, the project duration
67
 Late Times

 LS (Late Start) - Latest time activity can start

without delaying the project
 Backward pass starts at end of the graph to
determine LS times
 LF (Late Finish) - Latest time activity can be
completed without delaying the project
j1
 LSij = LFij - tij
 LFij = minimum (LSj) i j j2
 min(LSj) = min(LSjj1, LSjj2, LSjj3)
j3
68
 Computing Late Times

The LF of the project is the EF of the last activity.

3
Lay foundation Dummy
0
2 Build Finish
3 1 house work
1 2 4 6 7
3 1
Design house Order and 1
and obtain receive materials Select 1
financing paint
5
 LF67 = 9 months
 LS67 = LF67 - t67 = 9 - 1 = 8 months
 LF56 = minimum (LS6) = 8 months
 LS56 = LF56 - t56 = 8 - 1 = 7 months
 LF24 = minimum (LS4) = min(5, 6) = 5 months
 LS24 = LF24 - t24 = 5 - 1 = 4 months 69
 Project cost analysis

ES=5, EF=5
ES=3, EF=5 3
LS=5, LF=5
LS=3, LF=5 0 ES=8, EF=9
ES=5, EF=8
2
3 1 LS=8, LF=9
LS=5, LF=8 7
1 2 4 6
ES=0, EF=3 ES=3, EF=4 3 1
1
LS=0, LF=3 LS=4, LF=5 1 ES=6, EF=7
ES=5, EF=6
LS=7, LF=8
LS=6, LF=7 5

70
 Activity Slack

 Slack is defined as the LS-ES or LF-EF

 Activities on critical path have ES = LS & EF =
LF (slack is 0)

 Activities not on critical path have slack

 Sij = LSij - ESij
 Sij = LFij - EFij

S24 = LS24 - ES24 = 4 - 3 = 1 month

71
 Free slack of an activity

 This is the maximum possible delay of an

activity which does not affect its immediate
successors.
 This is evaluated as: FSij = ESj – EFij

72
 Activity Slack Data
ES=5, EF=5
ES=3, EF=5 3
LS=5, LF=5
LS=3, LF=5 0 ES=8, EF=9
ES=5, EF=8
2
3 1 LS=8, LF=9
LS=5, LF=8 7
1 2 4 6
ES=0, EF=3 ES=3, EF=4 3 1
1
LS=0, LF=3 LS=4, LF=5 1 ES=6, EF=7
ES=5, EF=6
LS=7, LF=8
LS=6, LF=7 5
Activity ES LS EF LF Slack (S) Free slack
1-2* 0 0 3 3 0 0
2-3 3 3 5 5 0 0
2-4 3 4 4 5 1 1
3-4* 5 5 5 5 0 0
4-5 5 6 6 7 1 0
4-6* 5 5 8 8 0 0
5-6 6 7 7 8 1 1
6-7* 8 8 9 9 0 0
73
* Critical path
 Slack on Gantt Chart
0 2 4 6 8 10
• Activity

• Design house and

• obtain financing

• Lay foundation

• Order and receive

• materials

• Build house

• Select paint

• Select carpet

• Finish work

1 3 5 7 9
Recherche Opérationnelle 74
 AON example: Beans on Toast

Prepare Beans Prepare Toast Combine

Open Can Slice bread

Place Beans in saucepan Place bread in toaster

Place Saucepan on stove Depress toaster button

Light stove Remove toast from toaster

Stir beans till warm Butter the toast

 CPM: Two conventions
Heat Beans
Can Beans
Open Can Open Ready Beans onto toast

Beans
Start on Toast
AOA Ready

Bread Toast Dummy

Slice bread cut Ready
Toast Bread

Open Can Heat Beans

AON Start
Beans onto
toast
End

Slice bread Toast bread

 Finding the critical path

Open Can Heat Beans

T: T:
ES: EF: ES: EF: Beans onto toast
LS: LF: T:
LS: LF:
End
Start ES: EF:
Slice bread Toast bread LS: LF:
T: T:
ES: EF: ES: EF:
LS: LF: LS: LF:

Add notation: “T” = time, “ES” = Earliest Start, “EF” = Earliest Finish
“LS” = Latest Start, “LF” = Latest Finish
 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES: EF: ES: EF: Beans onto toast
LS: LF: T: 1:00
LS: LF:
End
Start ES: EF:
Slice bread Toast bread LS: LF:
T:1:00 T:3:00
ES: EF: ES: EF:
LS: LF: LS: LF:

Fill in the times.

 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES: EF: Beans onto toast
LS: LF: T: 1:00
LS: LF:
End
Start ES: EF:
Slice bread Toast bread LS: LF:
T:1:00 T:3:00
ES: 0 EF:1 ES: EF:
LS: LF: LS: LF:

ES for the first activity is zero, EF is ES + T

 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES:1 EF:6 Beans onto toast
LS: LF: T: 1:00
LS: LF:
End
Start ES:6 EF:7
Slice bread Toast bread LS: LF:
T:1:00 T:3:00
ES: 0 EF:1 ES:1 EF:4
LS: LF: LS: LF:

For subsequent activities, ES is max(EF of all upstream activities), EF is ES + T

 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES:1 EF:6 Beans onto toast
LS: LF: T: 1:00
LS: LF:
End
Start ES:6 EF:7
Slice bread Toast bread LS: LF:
T:1:00 T:3:00
ES: 0 EF:1 ES:1 EF:4
LS: LF: LS: LF:

For subsequent activities, ES is max(EF of all upstream activities), EF is ES + T

 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES:1 EF:6 Beans onto toast
LS: LF: T: 1:00
LS: LF:
End
Start ES:6 EF:7
Slice bread Toast bread LS: LF:7
T:1:00 T:3:00
ES: 0 EF:1 ES:1 EF:4
LS: LF: LS: LF:

The earliest finish of the final activity is also the latest acceptable finish for the
final activity, assuming we don’t want the project completion to be delayed.
 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES:1 EF:6 Beans onto toast
LS:1 LF:6 T: 1:00
LS:0 LF:1
End
Start ES:6 EF:7
Slice bread Toast bread LS:6 LF:7
T:1:00 T:3:00
ES: 0 EF:1 ES:1 EF:4
LS: 2 LF: 3 LS:3 LF: 6

Then we do a second, backwards, pass through the network, where for each node,
LF is min(LS of all downstream nodes) and LS is LF - T
 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES:1 EF:6 Beans onto toast
LS:1 LF:6 T: 1:00
LS:0 LF:1
End
Start ES:6 EF:7
Slice bread Toast bread LS:6 LF:7
T:1:00 T:3:00
ES: 0 EF:1 ES:1 EF:4
LS: 2 LF: 3 LS:3 LF: 6

Slack = 2 Slack = 2

The difference between EF and LF for a node is the slack for that activity
 Finding the critical path

Open Can Heat Beans

T: 1:00 T: 5:00
ES:0 EF:1 ES:1 EF:6 Beans onto toast
LS:1 LF:6 T: 1:00
LS:0 LF:1
End
Start ES:6 EF:7
Slice bread Toast bread LS:6 LF:7
T:1:00 T:3:00
ES: 0 EF:1 ES:1 EF:4
LS: 2 LF: 3 LS:3 LF: 6

Slack = 2 Slack = 2

Activities with no slack are on the critical path

 Crashing a Project

Crashing an activity means spending more money in order to get

it done faster. It’s obviously a waste of money to crash any
activity that has slack.
Crash cost – normal cost
Crash cost/ unit time =
Normal Time – Crash Time

2. Find minimum crash cost/unit time on the critical path

3. Reduce time as much as possible

4. Repeat
 PERT: Probabilistic Time Estimates

 Reflect uncertainty of activity times

 Beta distribution is used in PERT

Mean (expected time): t = a + 4m + b

6
Variance: s 2 = b - a2
( 6
)
where,

a = optimistic estimate
m = most likely time estimate
b = pessimistic time estimate
87
 Example Beta Distributions
P (time)

P (time)
m t b a t m b
a
P (time)

a m=t b
88
 PERT Example
Equipment testing
and modification
2 6
Final
Equipment Dummy debugging
installation

System
Training
1 3 5 8 9
System Manual System
development Testing changeover
System
Testing
Job Dummy
Position training
recruiting

Orientation
4 7
89
 Activity Information
Time estimates (wks) Mean Time Variance
Activity a m b t s2
1-2 6 8 10 8 .44
1-3 3 6 9 6 1.00
1-4 1 3 5 3 .44
2-5 0 0 0 0 .00
2-6 2 4 12 5 2.78
3-5 2 3 4 3 .11
4-5 3 4 5 4 .11
4-7 2 2 2 2 .00
5-8 3 7 11 7 1.78
5-7 2 4 6 4 .44
7-8 0 0 0 0 .00
6-9 1 4 7 4 1.00
8-9 1 10 13 9 4.00
90
 PERT Example
Equipment testing
and modification
2 6
5
Final
Equipment Dummy debugging
installation 0 4
8
System
6 3 Training 9
1 3 5 8 9
System Manual 7 System
development Testing changeover
System
Testing
Job 4 0 Dummy
Position 3 4
training
recruiting

Orientation
4 7
2
91
 Early And Late Times
Activity t s2 ES EF LS LF S

1-2 8 0.44 0 8 1 9 1
1-3 6 1.00 0 6 0 6 0
1-4 3 0.44 0 3 2 5 2
2-5 0 0.00 8 8 9 9 1
2-6 5 2.78 8 13 16 21 8
3-5 3 0.11 6 9 6 9 0
4-5 4 0.11 3 7 5 9 2
4-7 2 0.00 3 5 14 16 11
5-8 7 1.78 9 16 9 16 0
5-7 4 0.44 9 13 12 16 3
7-8 0 0.00 13 13 16 16 3
6-9 4 1.00 13 17 21 25 8
8-9 9 4.00 16 25 16 25 0 92
 Graph With Times
ES=8, EF=13
( LS=16 LF=21 )
ES=0, EF=8 2 5
6
ES=13, EF=17
( LS=1, LF=9 ) ES=8, EF=8 ( LS=21 LF=25 )
8
0
( LS=9, LF=9 ) 4

ES=0, EF=6 ES=9, EF=16

( LS=0, LF=6 ) 3 ( LS=9, LF=16 ) 9
1 3 5 8 9
6 ES=6, EF=9 7 ES=16, EF=25
( LS=6, LF=9 ) ES=9, EF=13
( LS=16 LF=25 )
ES=0, EF=3 4 ( LS=12, LF=16 ) 0
3 ( LS=2, LF=5 ) ES=3, EF=7 4
ES=13, EF=13
( LS=16 LF=16 )
( LS=5, LF=9 )
2
4 ES=3, EF=5
7
( LS=14, LF=16 ) 93
Project Variance

Project variance is the sum of the

variances along the critical path

s2 = s2 13 + s2 35 + s2 58 + s2 89

= 1.00 +0.11 + 1.78 + 4.00

= 6.89 weeks

94
 Probabilistic Analysis

Determine the probability that a project is completed

(project completion time is )
within a specified period of time
where x-m
Z = s
m = tp = project mean time
s = project standard deviation
x = project time (random variable)
Z = number of standard deviations of x from
the mean (standardized random variable) 

95
Normal Distribution Of Project Time

X ~ N (m ,s 2 ) Probability

xm
z
s
Zs

m = tp x Time

96
Standard Normal Distribution Of
transformed Project Time

Probability
Z ~ N (0,1 )

m =0 z Time

97
 Probabilistic Analysis Example

What is the probability that the project is

completed within 30 weeks?
P(X 30) = ?
s2 = 6.89 weeks
s = 6.89 = 2.62 weeks
Z = x - m =30 - 25 = 1.91
s 2.62
P(Z  1.91) = ?

98
 Determining Probability
From Z Value

Z 0.00 0.01 .. 04 … 0.09

.. .. ..
1.1
. 0.3643
. 0.3665
. 0.3729
1.9 0.4713 +0.4719 … 0.4767
P( x < 30 weeks) = 0.50+ 04719

= 0.9719

m = 25 x = 30 Time (weeks)

99
 Probabilistic Analysis Example

What is the probability that the project will

be completed within 22 weeks?
22 - 25 = -3
Z= = -1.14
2.62 2.62

P(Z< -1.14) = 0.1271

x = 22 m = 25 x=28 Time (weeks)

P( x< 22 weeks) = 0.1271

100