Новый сетевой график

S
(is,js))	(1, 2)	(1, 3)	(2, 4)	(3, 4)	(3, 5)	(4, 5)	(5, 6)
τs

 

Задача о кратчайшем сроке выполнения проекта

Алгоритм Форда

Для каждого события (вершины) i=1,…,6 полагаем t_i = 0.

t’_{j s} = max {t_js, t_is+τ}.

Найти календарный план

t = (t₁, t₂, t₃, t₄, t₅, t₆) и λ(t) = t₆ - t₁ (кратчайший срок)

Шаг 1.

1. S =(1, 2): t’₂ = max {t₂, t₁ + τ₁ } = max {0, 0+3} = 3;

2. S =(1, 3): t’₃ = max {t₃, t₁ + τ₂ } = max {0, 0+5} = 5;

3. S =(2, 4): t’₄ = max {t₄, t₂ + τ₃ } = max {0, 3+7} = 10;

4. S =(3, 4): t’₃ = max {t₄, t₃ + τ₄ } = max {10, 5+0} = 10;

5. S =(3, 5): t’₅ = max {t₅, t₃ + τ₅ } = max {0, 5+4} = 9;

6. S = (4, 5): t’₅ = max {t₅, t₄ + τ₆ } = max {9, 10+6} = 16;

7. S = (5, 6): t’₆ = max {t₆, t₅ + τ₇ } = max {0, 16+3} = 19.

Шаг 2.

1. S =(1, 2): t’₂ = max {t₂, t₁ + 3 } = max {3, 0+3} = 3;

2. S =(1, 3): t’₃ = max {t₃, t₁ + 5 } = max {5, 0+5} = 5;

3. S =(2, 4): t’₄ = max {t₄, t₂ + τ₃ } = max {10, 3+7} = 10;

4. S =(3, 4): t’₃ = max {t₄, t₃ + τ₄ } = max {10, 5+0} = 10;

5. S =(3, 5): t’₅ = max {t₅, t₃ + τ₅ } = max {16, 5+4} = 16;

6. S = (4, 5): t’₅ = max {t₅, t₄ + τ₆ } = max {16, 10+6} = 16;

7. S = (5, 6): t’₆ = max {t₆, t₅ + τ₇ } = max {16, 16+3} = 19.

Конец работы алгоритма, т.к. ни одна из величин t_i не изменилась.

Итак, определили t_i - самые ранние сроки выполнения событий i =1,…,6 сетевого графика:

t = (0, 3, 5, 10, 16, 19) – календарный план и

λ(t) = t₆ - t₁ = 19 - минимальный срок выполнения проекта

Задача о нахождении наиболее поздних сроков наступлений событий