University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
Tutorial 5
Exercice 1 : (Checking if a scheduling plan is valid )
Scheduling in graph theory is the process of finding an optimal sequence and timing for a set
of interdependent tasks, modeled as nodes and edges in a directed graph, to achieve specific
objectives under given constraints. (Tasks as nodes, dependencies as directed edges).
Let consider a graph with the following Dependency list:
A→B
B→C
C→D
D→A
Question: Is this scheduling valid? justify?
Exercice 2 : (MPM diagram)
Given the table below,
1. Draw the MPM diagram.
2. Determine the critical path and total project duration.
3. Calculate the slack (float) for each task.
Task duration predecessors
A 15 -------
B 20 -------
C 10 A
D 10 B
E 30 C-D
Exercice 3 : (PERT diagram)
Given the following Tasks with duration and dependencies: A (5), B (2, after A), C (4, after A), D
(6, after B), E (3, after B,C), F (4, after C), G (5, after D,E), H (2, after F,G).
1. Draw the PERT diagram.
2. Determine the critical path and total project duration.
3. Calculate the slack (float) for each task.
p. 1
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
Exercice 1 solution:
No — it contains a cycle (A → B → C → D → A). Scheduling requires a Directed Acyclic Graph (DAG).
Exercice 2 : (MPM diagram)
1. Draw the MPM diagram. (the process of creating MPM diagram is explained in course
5)
We first calculate the earliest starts ES from START to END (by addition), we set the
maximum time if necessary.
Earliest Start ES Latest Start LS
15
0 15 10 30
0 0 A C E
START 10 30
20
0 20 60
B D END
Then we calculate the Latest Starts from END to START (by substraction)
2. Determine the critical path and total project duration: the critical path is set in red, we
select only nodes with Earliest Start = Latest Start, so the critical path is (start-B-D-E-
end), total project duration is 60.
p. 2
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
3. Calculate the slack (float) for each task.
Slack=LS-ES
Slack (A)=5-0=5
Slack (B)=0-0=0
Slack (C)=20-15=5
Slack (D)=20-20=0
Slack (E)=30-30=0
Exercice 3 : (PERT diagram)
Given the following Tasks with duration (in days) and dependencies: A (5), B (2, after A), C (4,
after A), D (6, after B), E (3, after B,C), F (4, after C), G (5, after D,E), H (2, after F,G).
1. Draw the PERT diagram.
2. Determine the critical path and total project duration.
3. Calculate the slack (float) for each task.
We start by a node with Earliest Start ES =0
START
The Task A has 5 days duration, so 0+5=5
0 A(5) 5
START
The Task B has 2 days duration, so 5+2=7, and task C has 4 days duration, so 5+4=9
7
B(2)
0 A(5) 5
START
9
C(4)
p. 3
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
The task D has a duration of 6 days so 7+6=13
D(6) 13
7
B(2)
0
5
A(5)
START
C(4)
Task E has a 3 days duration after B and C, so the earliest star for the task E is maximum (7+3,
9+3)=12
7 13
B(2)
D(6)
0
A(5) E’(0)
5
START
9
E(3) 12
C(4)
p. 4
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
the task F has 4 days duration after C so ES=9+4=13
7 13
B(2)
D(6)
0
A(5) E’(0)
5
START
9
12
C(4) E(3)
F(4)
13
p. 5
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
The task G has 5 days duration after D, E
7 13
B(2)
D(6)
0
A(5) E’(0) G’(0)
5 )
START
9
E(3) 12
C(4)
G(5)
F(4)
13 18
Maximum(13+5, 12+5)=18
p. 6
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
The task H has 2 days duration after F and G so the earliest Start = minimum(13+2,18+2)=20
7 13
B(2)
D(6)
0
A(5) E’(0) G’(0)
5 )
START
9
E(3) 12
C(4)
G(5)
F(4)
18 18
H’(0)
H(2)
20
The total project duration is 20 days
p. 7
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
Now we calculate the Latest Start from the END to the START, by doing substraction and keeping
minimum if necessary.
7 7 13 13
B(2)
D(6)
0 0
F(4) 0 0
5 5 E’(0)
A(5) G’(0))
START 0
0 9 10 13
E(3) 12
C(4)
1
1
G(5)
F(4)
13 18 18 18
5
H’(0)
0
H(2)
20 20
We put the latest Start = the earliest start =20 to the final node H, so the slack =0
We then calculate the Latest Start for G, 20-2=18
We then calculate the Latest Start for F, 20-2=18
We then calculate the Latest Start for E, 18-5=13
We then calculate the Latest Start for D, 18-5=13
p. 8
University Abdelhamid Mehri Constantine 2
NTIC FACULTY 2nd year common core
We then calculate the Latest Start for B, minimum (13-6,13-3)=7
We then calculate the Latest Start for C, minimum (18-4,13-3)=10
We then calculate the Latest Start for A, minimum (7-2,10-4)=5
We then calculate the Latest Start for the START node, 5-5=0
The slack is then calculated as being LS-ES for all nodes (in green)
The critical path is composed of all the nodes whose slack=0.
So the critical path here is
ABDGH
We can enhance the drawing by combining nodes like below:
7 7
B(2)
0
0 0 D(6)
5 5 E’(0)
A(5)
START
0 9 10
0 13 13
C(4) E(3)
G(5)
F(4)
13 18
0
H(2)
20 20
p. 9
