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

Исходные данные: t_i = 19, i=1,…,6.

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

Шаг 1.

1. S =(1, 2): t’₁ = min {t₁, t₂ - τ₁ } = min {19, 19-3} = 16;

2. S =(1, 3): t’₁ = min {t₁, t₃ - τ₂ } = min {16, 19-5} = 14;

3. S =(2, 4): t’₂ = min {t₂, t₄ - τ₃ } = min {19, 19-7} = 12;

4. S =(3, 4): t’₃ = min {t₃, t₄ - τ₄ } = min {19, 19-0} = 19;

5. S =(3, 5): t’₃ = min {t₃, t₅ - τ₅ } = min {19, 19-4} = 15;

6. S = (4, 5): t’₄ = min {t₄, t₅ - τ₆ } = min {19, 19-6} = 13;

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

Шаг 2.

1. S = (1, 2): t’₁ = min {t₁, t₂ - 3 } = min {14, 12-3} = 11;

2. S = (1, 3): t’₁ = min {t₁, t₃ - 5 } = min {9, 15-5} = 9;

3. S = (2, 4): t’₂ = min {t₂, t₄ -7 } = min {12, 13-7} = 6;

4. S = (3, 4): t’₃ = min {t₃, t₄ - 0 } = min {15, 13-0} = 13;

5. S = (3, 5): t’₃ = min {t₃, t₅ - 4 } = min {13, 16-4} = 12;

6. S = (4, 5): t’₄ = min {t₄, t₅ - 6 } = min {13, 16-6} = 10;

7. S = (5, 6): t’₅ = min {t₅, t₆ - 3 } = min {16, 19-3} = 16.

Шаг 3.

1. S = (1, 2): t’₁ = min {t₁, t₂ - 3 } = min {9, 6-3} = 3;

2. S = (1, 3): t’₁ = min {t₁, t₃ - 5 } = min {3, 12-5} = 3;

3. S = (2, 4): t’₂ = min {t₂, t₄ -7 } = min {6, 10-7} = 3;

4. S = (3, 4): t’₃ = min {t₃, t₄ - 0 } = min {12, 10-0} = 10;

5. S = (3, 5): t’₃ = min {t₃, t₅ - 4 } = min {10, 16-4} = 10;

6. S = (4, 5): t’₄ = min {t₄, t₅ - 6 } = min {10, 16-6} = 10;

7. S = (5, 6): t’₅ = min {t₅, t₆ - 3 } = min {16, 19-3} = 16.

Шаг 4.

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

2. S = (1, 3): t’₁ = min {t₁, t₃ - 5 } = min {0, 12-5} = 0;

3. S = (2, 4): t’₂ = min {t₂, t₄ -7 } = min {6, 10-7} = 3;

4. S = (3, 4): t’₃ = min {t₃, t₄ - 0 } = min {12, 10-0} = 10;

5. S = (3, 5): t’₃ = min {t₃, t₅ - 4 } = min {10, 16-4} = 10;

6. S = (4, 5): t’₄ = min {t₄, t₅ - 6 } = min {10, 16-6} = 10;

7. S = (5, 6): t’₅ = min {t₅, t₆ - 3 } = min {16, 19-3} = 16.

На шаге 5 получили те же результаты, что и на шаге 4 ð конец работы алгоритма.

Шаг 5.

0; 0; 3; 10; 10; 10; 16.

t = (0, 3, 10, 19, 16, 19) – наиболее поздние сроки

Запишем результаты в таблицу и вычислим некоторые параметры сетевой модели:

i
ti(р.с.)
ti(п.с.)
ρi

 

Где t_i(р.с.) – ранние сроки, t_i(п.с.) - поздние сроки, ρ_i – резервы.

1). Резервы времени:

ρ₁ = t_i(р.с.) - t_i(п.с.) = 0 – 0 = 0;

ρ₂ = t_i(р.с.) - t_i(п.с.) = 3 – 3 = 0;

ρ₃ = t_i(р.с.) - t_i(п.с.) = 10 – 5 = 5;

ρ₄ = t_i(р.с.) - t_i(п.с.) = 10 – 10 = 0;

ρ₅ = t_i(р.с.) - t_i(п.с.) =16 – 16 = 0;

ρ₆ = t_i(р.с.) - t_i(п.с.) = 19 – 19 = 0.

Критические события (те, у которых ρ_i = 0): 1, 2, 4, 5, 6.

2). Напряжённые работы(дуги):

Это те работы (дуги), для выполнения которых нет дополнительного резерва времени, т.е.

τ_s = t _js – t_is,

где (i_s, j_s) –дуга-работа; t_i –планируемые сроки выполнения i–ого события, i=1,…,m.

t = (t₁,…, t_m) – календарный план выполнения проекта

1: s = (1, 2): t₂ – t₁ = 3 – 0 = 3 = τ₁ ü

2: s = (1, 3): t₃ – t₁ = 5 – 0 = 5 = τ₂ ü

4: s = (3, 4): t₄ – t₃ = 10 – 5 = 5 ≠ τ₄

5: s = (3, 5): t₅ – t₃ = 16 – 5 = 11 ≠ τ₅ ü

6: s = (4, 5): t₅ – t₄ = 16 – 10 = 6 = τ₆ ü ð

Напряжённые дуги (работы): s = {1, 2, 6}.

2). Найдём критический путь

v Критический путь проходит по напряжённым дугам;

v Длина критического пути равна кратчайшему сроку выполнения проекта.

1 – 2 – 4 – 5 – 6

Длина критического пути равна

3+7+6+3 = 19.