Орграф без контуров с неотрицательными
Календарное (сетевое) планирование
Сетевая модель:
вершины – события (завершение одних видов работ и начало других видов работ – выходящих из вершин);
дуги – работы
орграф без контуров с неотрицательными
весами вершин или дуг
|  … ð  контур
простой путь
 … ð  цикл
|
Проект –совокупность частично упорядоченных работ, направленных на достижение некоторой цели.
Пример: проект из 6 работ и их длительности.
Найти:
1) Диаграмму Ганта;
2) Правильную нумерацию;
3) Кратчайший срок и кратчайший путь.
| Работа | Предшествование | Длительность |
| A | - | |
| B | - | |
| C | A | |
| D | B,C | |
| E | B | |
| F | E,D |
Диаграмма Ганта
Например, работа D – критическая (её задержка приведёт к задержке всего проекта)
Сеть «работы - дуги»
| S | |||||||
| (is,js)) | (1,2) | (1,6) | (2,3) | (3,4) | (4,5) | (6,4) | (6,3) |
| τs |
Вычисление параметров сети
Опр. Рангом Ri события (вершины) i называется максимальное число дуг в пути из входной 1 в вершину i. Ранги событий находят по рекурсивной формуле: Rk(j)= … k(j) – концевая вершина;Алгоритм Форда
Шаг 1. Последовательностно просматриваем дуги (работы) и пересчитываем ранги их концевых вершин: S = 1 ð (1, 2): R2 = max {R2, R1 +1} = max {0, 0+1} = 1; S = 2 ð (1, 6): R6 = max {R6, R1 +1} = max {0, 0+1} = 1;Был сетевой график
Введём правильную нумерацию:
Ø Входу (вершине нулевого ранга) ð 1;
Ø Вершинам ранга 1 (вершинам 2,6) ð номера 2 и 3 соответственно;
Ø Вершинам ранга 2 (вершине 3) ð номер 4;
Ø Вершинам ранга 3 (вершине 4) ð номер 5;
Ø Вершинам ранга 4 (вершине 5) ð номер 6.