Алгоритм c1

1. Принять для «Начала» ES и EF равными нулю.

2. Пусть a - любая работа, такая, что для всех работ из множества P_a сроки раннего окончания работ уже вычислены. Тогда можно вычислить

а также

3. В конце концов будет вычислен ранний срок окончания F работы «Конец».

Можно показать, что данный алгоритм дает единственные значения ранних сроков начала и окончания для всех работ в J . Далее, для любой работы a в J ранний срок окончания EF(a) есть общее время выполнения работ, составляющих наиболее длинный путь от «Начала» до работы a включительно. Самый ранний срок завершения всех работ есть F .

Для каждого проекта обычно имеется установленная или чем либо обусловленная дата Т , к которой его выполнение должно быть завершено. Установленные сроки выполнимы только при условии, что T  F , ибо F - самый ранний срок завершения всех работ по проекту. Если установленный срок Т проекта известен, то, идя от конца проекта к началу, можно вычислить наиболее поздние сроки окончания каждой работы при условии, что проект должен быть завершен не позднее установленной даты T . Назовем эти сроки наиболее поздними сроками окончания работ LF . Отсюда можно вывести и наиболее поздний срок начала каждой работы LS . Опишем алгоритм вычисления этих сроков.

Алгоритм с2

1. Принять для «Конца» и LS и LF равными T.

2. Пусть a - любая работа, такая. что для всех работ из множества S_a сроки LS уже вычислены. Тогда следует вычислить

, а также LS(a)=LF(a)-t_a .

3. В конце концов буде вычислен поздний срок начала L работы «Начало» .

Определение. Для любой работы a величина

SL(a)=LS(a)-ES(a)=LF(a)-EF(a)

называется резервом времени (или просто резервом) работы a .

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

Матрицы предшествующих и последующих работ

Пусть путь на графике G проекта состоит из k работ, удовлетворяющих условию

a₁<<a₂<< … <<a_k . Два пути считаются различными, если они отличаются один от другого набором принадлежащих им работ или их очередностью. Будем говорить, что длина такого пути равна k-1 . Предположим, что весь проект состоит из упорядоченного множества J=[ a₁<<a₂<< … <<a_n] из n работ. Дадим определение матрицы предшествующих и последующих работ проекта.

Определение. Матрица предшествующих работ Р проекта есть матрица n x n с элементами p_i,j , определяемыми следующим образом:

Матрица последующих работ S может быть определена как

Очевидно, что эти матрицы квадратные и что их элементами могут быть только 0 или 1. Поскольку Р матрица квадратная, то ее можно возводить в степень n . Обозначим через элементы матрицы P⁽ⁿ⁾ .

Можно доказать справедливость теоремы:

Теорема. Если , то существуют m различных путей длиной k от a_i до a_j

Вывод. Если имеется наиболее длинный путь, то есть путь , проходящий через наибольшее число вершин на графике G проекта, и если длина этого пути равна N , P^N  0 и P^N+1 = 0 . Очевидно, что таким путем может быть определена длина критического пути на графике.

Определение. Если Р - матрица с целочисленными элементами; тогда инверсия Неймана для матрицы (I - P) возможна в том и только в том случае, если P^N+1 = 0 для некоторого N .