6.1. Алгоритм нахождения самого длинного (критического) пути в ориентированном ациклическом графе

Пусть вершины пронумерованы так, что дуга всегда ориентирована от вершины к вершине имеюшей больший номер. Для ациклического графа такая нумерация всегда возможна и производится очень легко. При этом начальная вершина получает номер 1, а конечная — номер

Присвоим вершине пометку равную длине самого длинного пути от 1 до используя для этого соотношения

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

Пометка равна длине самого длинного пути от 1 до Сами дуги, образующие путь, могут быть найдены обычным способом последовательного возвращения. А именно дуга принадлежит пути тогда и только тогда, когда Начиная с вершины равной полагаем на каждом шаге равной такой вершине (скажем, для которой выполняется это последнее равенство, и так продолжаем до тех пор, пока не будет достигнута начальная вершина (т. е. пока не будет

Совершенно очевидно, что пометка вершины дает длиннейший путь от 1 до т. е. самое раннее возможное начало выполнения этапа, изображаемого вершиной Таким образом, если дуга в графе, то (неотрицательная величина, как это видно из дает самое большое возможное время задержки начала этапа не оказывающее влияния на время начала этапа Из вышесказанного видно, что если

Рис. 8.5. (см. скан) (а) Граф из примера 6.1.1. (б) Окончательные пометки вершнн и критический путь.

два последовательные этапа в самом длинном пути, то

6.1.1. Пример.

Рассмотрим диаграмму ПЕРТ, изображенную на рис. где числа, стоящие у дуг, указывают продолжительность задержек в днях. Каков наименьший возможный срок выполнения этого проекта? (Предполагается, что вершина 13 является конечной и ей соответствует нулевая продолжительность.) Вершины графа уже пронумерованы так, что дуга существует лишь при Применение выражения (8.7) к графу, изображенному на рис. приводит к расстановке

пометок, показанной на рис. 8.5 (б); критический путь изображен жирной линией. Длина этого пути и, следовательно, наименьший возможный срок выполнения проекта равен 93 дням.

Если один из этапов, принадлежащих критическому пути, задерживается на дней, то и весь проект задержится на тот же срок. С другой стороны, задержка, скажем, этапа 8 (не принадлежащего критическому пути) возможна на дней, причем это не отразится на общем сроке реализации проекта. Лишь задержка на срок дней повлияет на пометку вершины 12 (принадлежащую критическому пути).

Метод ПЕРТ описан в этой главе в терминах самого длинного пути в графе, вершины которого отвечают этапам выполнения проекта, а дуги — отношениям предшествования, причем вес дуги равен интервалу времени между началом этапа На практике диаграммы ПЕРТ истолковываются несколько иначе, а именно дуги представляют этапы, а вершины изображают абстрактные «события», указывающие начала или окончания этапов. Хотя такое представление само по себе является неполным (так как при зтом отношения предшествования точно не описываются), указанный недостаток можно устранить, добавляя фиктивные этапы для точного описания отношений предшествования [34]. С другой стороны, такое представление имеет важное преимущество перед первоначальным, поскольку приводит на практике к более простым диаграммам. Это происходит в силу Того, что временная задержка между началами этапов является, вообще говоря, постоянной для данного и совершенно не зависит от следующего зтапа. Редкие исключения всегда можно учесть, вводя некоторые фиктивные этапы. В таких случаях подобное представление приводит на практике к более простым графам (даже с учетом фиктивных вершин), в то время как представление, рассмотренное ранее, остается неизменным. Другой особенностью практического использования метода ПЕРТ является то, что интервалы времени (т. е. временные задержки) между этапами считаются случайными величинами, а не детерминированными, как считалось здесь.

Задачи планирования, решаемые с помощью метода ПЕРТ, не учитывают наличие ресурсов и не рассматривают потребности этапов в ресурсах. Вместо этого производится (после нахождения критического пути такое распределение ресурсов по этапам проекта, при котором задерживается выполнение этапов, не принадлежащих критическому пути. Если же ограничения на ресурсы учитывать на стадии планирования, то задача из очень легкой превращается в очень трудную [1, 30, 37] и решить ее удается лишь для размерностей на 3—4 порядка меньших, чем в случае соответствующей задачи без ограничений.