Смекни!
smekni.com

Сетевые графики (стр. 2 из 3)

n 1 2 3 4 5 6 7 8 9 10 11
РНАЧ(v) 0 0 5 35 35 50 55 65 68 65 71
РВЫП(v) 0 5 35 50 47 55 65 68 71 68 71

Получили, что минимальное время, требуемое для выполнения проекта равно Т=РВЫП(11), Т=71. Теперь найдем посредством алгоритма 2 значение времени наиболее позднего начала и выполнения работ. Работу алгоритма изложим в виде последовательности выполняемых шагов.

Шаг n Действия выполняемые шагом
1 Объявление значений ПВЫП(v), vÎV равным Т. Текущая вершина vk=11.
2 ПНАЧ(11)=ПВЫП(11)-t(11) {ПНАЧ(11) стало равным 71}.
3 ПВЫП(9)=МИН{ПВЫП(9),ПНАЧ(11)}{ПВЫП(9) стало равным 71} ПВЫП(10)=МИН{ПВЫП(10),ПНАЧ(11)}{ПВЫП(10) стало равным 71}
4 Текущая вершина vk=10.
5 Переход в Шаг 2.
2 ПНАЧ(10)=ПВЫП(10)-t(10) {ПНАЧ(10) стало равным 68}
3 ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(10)}{ПВЫП(7) стало равным 68}
4 Текущая вершина vk=9.
5 Переход в Шаг 2.
2 ПНАЧ(9)=ПВЫП(9)-t(9) {ПНАЧ(9) стало равным 68}
3 ПВЫП(8)=МИН{ПВЫП(8),ПНАЧ(9)}{ПВЫП(8) стало равным 68}
4 Текущая вершина vk=8.
5 Переход в Шаг 2.
2 ПНАЧ(8)=ПВЫП(8)-t(8) {ПНАЧ(8) стало равным 65}
3 ПВЫП(7)=МИН{ПВЫП(7),ПНАЧ(8)}{ПВЫП(7) стало равным 65}
4 Текущая вершина vk=7.
5 Переход в Шаг 2.
2 ПНАЧ(7)=ПВЫП(7)-t(7) {ПНАЧ(7) стало равным 55}
3 ПВЫП(5)=МИН{ПВЫП(5),ПНАЧ(7)}{ПВЫП(5) стало равным 55} ПВЫП(6)=МИН{ПВЫП(6),ПНАЧ(7)}{ПВЫП(6) стало равным 55}
4 Текущая вершина vk=6.
5 Переход в Шаг 2.
2 ПНАЧ(6)=ПВЫП(6)-t(6) {ПНАЧ(6) стало равным 50}
3 ПВЫП(4)=МИН{ПВЫП(4),ПНАЧ(6)}{ПВЫП(5) стало равным 50}
4 Текущая вершина vk=5.
5 Переход в Шаг 2.
2 ПНАЧ(5)=ПВЫП(5)-t(5) {ПНАЧ(5) стало равным 43}
3 ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(5)}{ПВЫП(3) стало равным 43}
4 Текущая вершина vk=4.
5 Переход в Шаг 2.
2 ПНАЧ(4)=ПВЫП(4)-t(4) {ПНАЧ(4) стало равным 35}
3 ПВЫП(3)=МИН{ПВЫП(3),ПНАЧ(4)}{ПВЫП(3) стало равным 35}
4 Текущая вершина vk=3.
5 Переход в шаг 2.
2 ПНАЧ(3)=ПВЫП(3)-t(3) {ПНАЧ(3) стало равным 5}
3 ПВЫП(2)=МИН{ПВЫП(2),ПНАЧ(3)}{ПВЫП(2) стало равным 5}
4 Текущая вершина vk=2.
5 Переход в Шаг 2.
2 ПНАЧ(2)=ПВЫП(2)-t(2) {ПНАЧ(2) стало равным 0}
3 ПВЫП(1)=МИН{ПВЫП(1),ПНАЧ(2)}{ПВЫП(1) стало равным 0}
4 Текущая вершина vk=1.
5 Переход в Шаг 2.
2 ПНАЧ(1)=ПВЫП(1)-t(1) {ПНАЧ(1) стало равным 0}
3 Переход в Шаг 4.
4 Переход в Шаг 6.
6 Конец работы алгоритма, выдача значений времени наиболее позднего начала и выполнения работ.

Дадим таблицу результатов работы алгоритма с результатами предыдущего алгоритма и сосчитаем резерв времени для каждой работы по формуле PE3EPB(v)=ПНАЧ(v)-PHAЧ(v) или РЕЗЕРВ(v)=ПВЫП(v)-РВЫП(v).

Работы РНАЧ РВЫП ПНАЧ ПВЫП Резерв
1 0 0 0 0 0
2 0 5 0 5 0
3 5 35 5 35 0
4 35 50 35 50 0
5 35 47 43 55 8
6 50 55 50 55 0
7 55 65 55 65 0
8 65 68 65 68 0
9 68 71 68 71 0
10 65 68 68 71 3
11 71 71 71 71 0

Из таблицы видно, что критическими работами являются 1, 2, 3, 4, 6, 7, 8, 9, 11, которые и образуют в сети G критический путь. Расчеты выполнены при Т=71.

Пример 2: Проект склада сажи и других материалов в помещение производственного цеха.

n Наименование работы Предшеству-ющие работы Время вы-полнения t(vk)
1. Начало проекта (фиктивн. работа) Нет 0
2. Монтаж металлоконструкций нижней обвязки каркаса 1 5
3. Устройство бетона под стойки 2 3
4. Монтаж стоек 3 10
5. Монтаж опорных столиков 4 5
6. Монтаж балок 2 7
7. Монтаж металлоконструкций ворот 6 7
8. Обшивка стен и кровли волнистым листом 6 12
9. Монтаж козлового крана 7 5
10. Устройство асфальтобетонных покрытий 8 5
11. Конец проекта (фиктивн. работа) 5,9,10 0

Рис 2. Проект склада сажи и других материалов в помещение производственного цеха.

Найдем значения наиболее раннего начала и выполнения работ проекта посредством алгоритма 1. Работу алгоритма изложим в виде последовательности выполняемых шагов.

Шаг n Действия выполняемые шагом
1 Объявление значений РНАЧ(v) и РВЫП(v), vÎV равным нулю. Текущая вершина vk=1.
2 Вершин предшествующей первой нет. Значение РНАЧ(1)=РВЫП(1)+t(1).
3 Текущая вершина vk=2.
4 Переход в Шаг 2.
2 РНАЧ(2)=МАКС{РВЫП(1),РНАЧ(2)} {РНАЧ(2) стало равным 0} РВЫП(2)=РНАЧ(2)+t(2) {РВЫП(2) стало равным 5}.
3 Текущая вершина vk=3.
4 Переход в Шаг 2.
2 РНАЧ(3)=МАКС{РВЫП(2),РНАЧ(3)} {РНАЧ(3) стало равным 5} РВЫП(3)=РНАЧ(3)+t(3) {РВЫП(3) стало равным 8}.
3 Текущая вершина vk=4.
4 Переход в Шаг 2.
2 РНАЧ(4)=МАКС{РВЫП(3),РНАЧ(4)} {РНАЧ(4) стало равным 8} РВЫП(4)=РНАЧ(4)+t(4) {РВЫП(4) стало равным 18}.
3 Текущая вершина vk=5.
4 Переход в Шаг 2.
2 РНАЧ(5)=МАКС{РВЫП(4),РНАЧ(5)} {РНАЧ(5) стало равным 18} РВЫП(5)=РНАЧ(5)+t(5) {РВЫП(5) стало равным 23}.
3 Текущая вершина vk=6.
4 Переход в Шаг 2.
2 РНАЧ(6)={РВЫП(2),РНАЧ(6)} {РНАЧ(6) стало равным 5} РВЫП(6)=РНАЧ(6)+t(6) {РВЫП(6) стало равным 12}.
3 Текущая вершина vk=7.
4 Переход в Шаг 2.
2 РНАЧ(7)=МАКС{РВЫП(6),РНАЧ(7)} {РНАЧ(7) стало равным 12} РВЫП(7)=РНАЧ(7)+t(7) {РВЫП(7) стало равным 19}.
3 Текущая вершина vk=8.
4 Переход в Шаг 2.
2 РНАЧ(8)=МАКС{РВЫП(6),РНАЧ(8)} {РНАЧ(8) стало равным 12} РВЫП(8)=РНАЧ(8)+t(8) {РВЫП(8) стало равным 24}.
3 Текущая вершина vk=9.
4 Переход в Шаг 2.
2 РНАЧ(9)=МАКС{РВЫП(7),РНАЧ(9)} {РНАЧ(9) стало равным 19} РВЫП(9)=РНАЧ(9)+t(9) {РВЫП(9) стало равным 24}.
3 Текущая вершина vk=10.
4 Переход в Шаг 2.
2 РНАЧ(10)=МАКС{РВЫП(8),РНАЧ(10)} {РНАЧ(10) стало равным 24} РВЫП(10)=РНАЧ(10)+t(10) {РВЫП(10) стало равным 29}.
3 Текущая вершина vk=11.
4 Переход в Шаг 2.
2 РНАЧ(11)=МАКС{РВЫП(9),РНАЧ(11)} {РНАЧ(11) стало равным 24} РНАЧ(11)=МАКС{РВЫП(10),РНАЧ(10)}{РНАЧ(11) стало равным 29} РВЫП(11)=РНАЧ(11)+t(11) {РВЫП(11) стало равным 29}.
3 Переход в Шаг 5.
5 Конец работы алгоритма, выдача значений наиболее раннего начала и выполнения работ.

Таблица результатов работы алгоритма.