Теорема доказана

4.16. Сетевое планирование и потоки в сетях

Следующий класс задач на графах связан с сетями.

Сетевые графики работ

Пусть задано некоторое множество работ (например, постройка дома). Введём на этом множестве отношение предшествования: работа А может быть выполнена только после работы В (результат работы А используется В). Это есть отношение частичного порядка. Нарисуем для полученного упорядоченного множества диаграмму Хассе – ориентированный граф, в котором:

а) есть единственный источник и единственный сток;

б) нет циклов;

в) для любой вершины существует путь из начала в конец, проходящий через неё.

Следовательно, работы с точки зрения теории множеств представляются решёткой с нулём и единицей. Вершины орграфа называются событиями, а рёбра – работами. Каждой работе поставлено в соответствие число – называемое временем или продолжительностью работы. Удовлетворяющий этим ограничениям взвешенный орграф называется сетью.

Нетрудно понять, что полное время выполнения всех работ представляется самым длинным путём по сети от истока к стоку. Таким образом, возникает задача нахождения длиннейшего пути во взвешенном графе. Этот путь называют критическим.

Изображение графика в масштабе времени начинают с критического пути – путь выпрямляется на нём ставятся временные метки. На полученном графике видно, что часть работ имеют резервы времени. Оптимизация сетевого графика работ состоит в ликвидации свободных резервов времени, чтобы изменился критический путь. Оптимизация производится путём переноса средств с некритических работ, имеющих резерв времени, на работы критического пути, при этом нельзя переносить средства на работы, принадлежащие одному и тому же пути.

Это задача сетевого планирования. Аналогично с распараллеливанием процессов (процессоров) – оптимизацию приходится проводить онлайн.