Td ordonnancement dut informatique mathematiques Théori

Théorie des graphes : Td ordonnancement dut informatique mathematiques

Télécharger PDF

Exercice 1

Parmi les tâches A_i (i ∈ {1; 2; ...; n}) qui constituent un projet, on en considère deux distinctes : A_k et A_j, de durées respectives d_k et d_j ; leurs dates de début d’exécution sont notées respectivement t_k et t_j. Traduire les contraintes suivantes :

1. A_j commence au plus tôt un temps d après le début de A_k.

• Inégalité : t_j ≥ t_k + d

• Arc : A_k → A_j avec une valuation de d.

2. A_j commence au plus tôt un temps d après l’achèvement de A_k.

• Inégalité : t_j ≥ t_k + d_k + d

• Arc : A_k → A_j avec une valuation de d_k + d.

3. A_j commence au plus tôt lorsque la fraction f de la durée de A_k s’est écoulée.

• Inégalité : t_j ≥ t_k + f × d_k

• Arc : A_k → A_j avec une valuation de f × d_k.

4. A_j commence au plus tard un temps d après le début de A_k.

• Inégalité : t_j ≤ t_k + d

• Arc : A_j → A_k avec une valuation de d.

5. A_j doit débuter au plus tôt un temps d₁ après le début de A_k et au plus tard un temps d₂ après le début de A_k (d₁ ≤ d₂).

• Inégalités : t_j ≥ t_k + d₁ et t_j ≤ t_k + d₂

• Arcs : A_k → A_j avec une valuation de d₁, et A_j → A_k avec une valuation de d₂.

6. A_j doit commencer dès l’achèvement de A_k.

• Inégalité : t_j = t_k + d_k

• Arc : A_k → A_j avec une valuation de d_k.

7. A_j commence au plus tôt à la date T et au plus tard à la date T' (T ≤ T').

• Inégalités : t_j ≥ T et t_j ≤ T'

• Arcs : T → A_j avec une valuation de 0, et A_j → T' avec une valuation de 0.

Exercice 2

On considère deux projets composés de 5 tâches (S_i) pour i = 1,...,5, plus deux tâches fictives, S₀ et S_f, de début et de fin de projet. Ces projets sont représentés par des graphes potentiel-tâches et on note t_i le début de la tâche S_i (et t₀ = 0).

1. Projet 1

Graphe : S₀ → S₁ (0), S₁ → S₂ (3), S₂ → S₃ (2), S₃ → S₄ (2), S₃ → S₅ (4), S₄ → S_f (1), S₅ → S_f (2), S₂ → S_f (6).

(a) Lequel des ordonnancements suivants n’est pas compatible avec ce graphe ?

Ordonnancement 1 : t₁ = 0, t₂ = 3, t₃ = 5, t₅ = 9, t₄ = 11

Ordonnancement 2 : t₁ = 0, t₂ = 3, t₃ = 6, t₅ = 10, t₄ = 11

(b) Calculer l’ordonnancement au plus tôt du projet et sa durée minimale T₁.

• t₁ = 0 (début du projet)

• t₂ = t₁ + 3 = 3

• t₃ = t₂ + 2 = 5

• t₄ = t₃ + 2 = 7 (mais doit attendre t₅ = 9, donc t₄ = 9)

• t₅ = t₃ + 4 = 9

• T₁ = max(t₄ + 1, t₅ + 2) = max(10, 11) = 11

(c) Donner l’ordonnancement au plus tard pour terminer le projet en 10 jours.

• T_f = 10 (fin du projet)

• t_f = T_f

• t₅ = T_f - 2 = 8

• t₄ = T_f - 1 = 9

• t₃ = min(t₄ - 2, t₅ - 4) = min(7, 4) = 4

• t₂ = t₃ - 2 = 2

• t₁ = t₂ - 3 = -1 (doit être au plus tard à 0, donc t₁ = 0)

FAQ

Qu’est-ce qu’un graphe potentiel-tâches ?

Un graphe potentiel-tâches est un modèle utilisé en ordonnancement de projet pour représenter les dépendances entre tâches et leurs durées.

Comment calculer l’ordonnancement au plus tôt ?

L’ordonnancement au plus tôt se calcule en partant de la tâche initiale et en ajoutant les durées des arcs pour déterminer les dates de début possibles.

Qu’est-ce qu’une tâche fictive dans un graphe potentiel-tâches ?

Une tâche fictive est une tâche sans durée (d_i = 0) utilisée pour représenter le début ou la fin d’un projet.

Td ordonnancement dut informatique mathematiques Théori

Exercice 1

1. Aj commence au plus tôt un temps d après le début de Ak.

2. Aj commence au plus tôt un temps d après l’achèvement de Ak.

3. Aj commence au plus tôt lorsque la fraction f de la durée de Ak s’est écoulée.

4. Aj commence au plus tard un temps d après le début de Ak.

5. Aj doit débuter au plus tôt un temps d1 après le début de Ak et au plus tard un temps d2 après le début de Ak (d1 ≤ d2).

6. Aj doit commencer dès l’achèvement de Ak.

7. Aj commence au plus tôt à la date T et au plus tard à la date T' (T ≤ T').