Аннотация

В классической задаче сетевого планирования длительность выполнения проекта равна длине критического пути в соответствующем графе-сети. Критические пути могут быть разными для одного и того же графа в зависимости от значений весов дуг. На практике это соответствует тому, что над одинаковыми проектами могут работать люди с разной производительностью труда. От способа их расстановки на соответствующие работы будет зависеть длительность выполнения проекта (длина критического пути).
Работы, лежащие на одном пути, могут выполняться лишь последовательно, поэтому для их реализации необходимо и даже достаточно одного работника. Работы, не лежащие на одном пути, могут выполняться одновременно, при условии наличия незанятых на других работах работников. Возможность начала очередной работы зависит от того, как быстро завершены предшествующие ей работы. Менеджеру проекта важно знать, сколько нужно иметь в наличии работников в каждый момент времени для того, чтобы, во-первых, работы не простаивали и критический путь не удлинился; а во-вторых, чтобы не держать в резерве работников, которые не понадобятся.
В статье доказана теорема о том, какое количество работников необходимо и достаточно для того, чтобы любой проект в зависимости от структуры соответствующего графа-сети выполнялся без простоев работ.