3.10.3. Сетевое планирование

Предположим, что для осуществления некоторого проекта необходимо выполнить определенный комплекс работ. Построим сетевой график этих работ. Вершины сети (события) будем отождествлять с их номерами, обозначив номером 0 источник (начало работ). Завершающему событию, т. е. окончанию всех работ, которое является стоком сети, присвоим наибольший номер N, в то время, как остальные промежуточные события пронумеруем от 0 до N-1, принимая, насколько это возможно, во внимание очередность их наступления. Если некоторое событие J может наступить только после события I и при этом должна быть выполнена определенная работа, то построим дугу (I, J), присвоив ей вес Tij -- время выполнения соответствующей работы. Если событие J не может наступить раньше события I, но для этого не требуется выполнение специальной работы, то также построим дугу (I, J) и присвоим ей вес 0.

По сетевому графику определим время, необходимое на выполнение всего проекта. Рассмотрим всевозможные (0, N)-пути от начала работ до их окончания. Для каждого пути подсчитаем его длину (время выполнения всех работ данного пути).

Простой (0, N)-путь, имеющий наибольшую длину, называется Критическим путем сети.

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

Теорема. Время, необходимое для выполнения всех работ проекта, равно длине критического пути соответствующей сети.

Работы, лежащие на критическом пути, также называются критическими. Сокращение или увеличение сроков выполнения критических работ соответственно сокращает или увеличивает общую продолжительность выполнения проекта. Остальные работы называются некритическими и допускают некоторое запаздывание в их выполнении, которое не задерживает сроков реализации всего проекта.

< Предыдущая		Следующая >