6.4. Задачи типа ПЕРТ

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

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

определяемую ниже, и установить все существенные отношения предшествования.)

Хотя некоторые операции проекта независимы друг от друга, в общем случае между ними существует достаточно сильная зависимость по времени, например, операция должна быть закончена прежде, чем может быть начата операция Если заданы все такие временные зависимости, то их можно удобно представить в виде ориентированного графа, как показано на рис. 6.2. Каждая дуга графа соответствует одной операции, а каждая вершина, называемая событием, соответствует некоторому моменту времени. В частности, вершина представляет собой начало всего проекта, его окончание. Промежуточные вершины служат для отражения взаимосвязи операций во времени. Вершины выбираются и сопоставляются с дугами так, что для каждой операции (дуги) и события (вершины) справедливо следующее основное утверждение: если операция а имеет начальное событие в виде вершины то она не может быть начата до тех пор, пока все операции, заканчивающиеся в не будут выполнен. Естественно а может начаться в любой другой момент после того, как выполнены все предшествующие операции. Например, на рис. 6.2 операция 10 (так же как и 12) может быть начата только после выполнения операций 5 и 7.

Рис. 6.2.

Косвенно начало операции 10 зависит также от моментов выполнения операций 1, 2 и 4, так как они непосредственно определяют начало операций 5 и 7. В начале проекта могут выполняться только операции 1, 2 и 3. Проект считается законченным после выполнения операций следовательно, всех операций проекта).

Граф такого типа, представляющий процесс выполнения операций, является основой многих методов организационного управления и, в частности, широко известного метода ПЕРТ и метода критического пути. Он позволяет проводить анализ различных вариантов выпол»: нения проектов.

Для иллюстрации основного типа проводимого анализа предположим, что для выполнения каждой операции а требуется известное время

Несколько операций можно, конечно, выполнить одновременно, если ни одна из операций рассматриваемой группы не ограничена моментами выполнения других операций, входящих в группу. (Это произойдет в случае, если ни одна из рассматриваемых операций не входит в путь, ведущий из в начальное событие другой операции).

Предположим, что числа на дугах графа рис. 6.3 соответствуют продолжительностям операций.

Рис. 6.3.

(В данном случае считается, что продолжительность каждой операции известна и постоянна. На самом деле продолжительность операций часто меняется, и ее описывают некоторым распределением вероятности, общий вид которого известен, а оценки его параметров могут быть получены.)

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

(время) следующим образом:

где обозначает длину пути и максимум берется по всем путям из к

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

Рис. 6.4.

(Предполагается, что каждая вершина графа достижима, по крайней мере, по одному пути.)

Соответствующее дерево показано на рис. 6.4, продолжительности операций для него даны на рис. 6.3, а значения приведены в вершинах.

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

и проект в целом будет выполнен за единиц времени, что соответствует наиболее раннему возможному моменту его окончания.

(см. скан)

Длиннейший по времени путь от начального события до конечного называется критическим путем. Его длина (в нашем примере 13) соответствует кратчайшему времени, за которое может быть выполнен проект. Минимальное время достигается только в случае, если каждая операция критического пути начинается сразу же после окончания предшествующей. Вообще говоря, критический путь не является единственным, (Читатель может заметить другой критический путь в нашем примере.) Операция называется критической, если она принадлежит одному или нескольким критическим путям. Если проект нужно выполнить за минимальное время, некоторые операции проекта остаются некритическими и существует определенная свобода в их планировании. Измерение этой свободы приводит к определению резерва времени операций. Задача нахождения резерва времени операций будет рассмотрена ниже.

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

Таким образом, пусть

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

восстановить первоначальную ориентацию дуг. На рис. 6.5 показано дерево, соответствующее нашему примеру. В вершинах графа указаны значения

Рис. 6.5.

Так как величины измеряются от конца проекта, а время выполнения всего проекта то удобно связать времена следующим соотношением:

где определяет самое позднее время осуществления события не увеличивающее длительности всего проекта.

Рис. 6.6.

На рис. 6.6 показаны значения для каждой вершины одновременно с определенными ранее значениями Величины удовлетворяют отношению

Величины позволяют определить резерв времени при планировании отдельных операций Хири постоянном минимальном времени проекта).

Например, время операции, соответствующей дуге от к рис. 6.3), равно одной единице, и мы определили, что Следовательно, эту операцию можно было бы начать самое раннее в момент 3 и самое позднее в момент 6. При этом событие наступило бы не позднее момента 7. Естественно, что если мы использовали некоторую часть резерва времени рассматриваемой операции, начав ее позже момента 3, то мы тем самым сократили резервы времени у последующих операций, в нашем случае у операций и Вообще говоря, каждое событие буде происходить в интервале между в зависимости от распределения резерва времени.

До сих пор мы предполагали, что на каждую операцию требуется постоянное время и что эта величина времени заранее известна. Если это не так (а на самом деле это почти всегда не так), то разумно предположить, что продолжительность каждой операции есть некоторая случайная величина, определяемая распределением вероятностей, соответствующим данной операции. Далее нужно получить возможно лучшие оценки параметров этого распределения и использовать их при последующем анализе. В первоначальном варианте метода ПЕРТ, например, предполагалось, что продолжительность операции получается из так называемого «бета-распреде-ления» (природа «бета-распределения» для нас сейчас не существенна, интересующиеся могут найти подробности в литературе, посвященной При этом для каждой операции находятся три временные оценки: и где соответственно оптимистическая и пессимистическая оценка времени выполнения операции, наиболее вероятная оценка. Среднее значение времени выполнения операций и ее стандартное отклонение оцениваются по следующим формулам:

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

При работе с переменной длительностью операций возникают серьезные математические трудности, даже если точно известно распределение, соответствующее каждой операции, и все распределения считаются независимыми. В этом случае приходится использовать различные приближенные методы. Проиллюстрируем одно из возможных осложнений общего характера. Предположим, что путь является критическим, некоторый путь из начального события в конечное, очень мало отличающийся от Пусть найдены на основе средних значений времен выполнения операций. Может оказаться, что времена операций пути имеют малый разброс, а пути большой. Например, соответствующие распределения могут иметь вид рис. 6,7. В этом случае существует достаточно большая вероятность того, что время выполнения проекта будет определяться путем а не и выводы, сделанные из расчета того, что является критическим путем, окажутся неточными.

Рис. 6.7.

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

данном случае состояла только в том, чтобы показать принципиальное значение графов, представляющих процессы выполнения операций при решении задач планирования проектов. Основные методы решения таких задач рассмотрены в работах [53], [54], [61]. Интересное обсуждение основных допущений дается в работе [60].

Дополнительные сведения

Метод ПЕРТ показывает, что теория графов является мощным инструментом решения задач планирования реализации проектов, С графотеоретической точки зрения ПЕРТ оперирует с временными характеристиками, определенными на графе. Такие временные характеристики позволяют найти график выполнения операций, распределение событий во времени и дерево длиннейших путей (критический путь).

Успех метода ПЕРТ содействовал применению теории графов для решення других задач управления проектами. Как указывалось выше, первоначальный метод ПЕРТ был основан на определении временных параметров на графе. Не удивительно, что впоследствии были введены на графе и характеристики другого типа, например, такие, как стоимость, ресурсы. (Под ресурсами имеются в виду люди, материалы, механизмы.) Помимо чисел, каждой дуге графа можно сопоставить такие функции, как, например, время-стоимость, или время-ресурсы. Эти функции показывают, как изменяются стоимость или ресурсы операции в зависимости от ее длительности. Задание функции стоимости на каждой дуге графа проекта позволяет найти кривую стоимость-время для всего проекта. Для вычисления таких кривых было предложено множество алгоритмов. Эти алгоритмы можно использовать также для нахождения такого графика выполнения проекта, который обеспечивает минимальную стоимость выполнения при заданном времени.

Алгоритмы Келли (1961), Фалкерсона (1962), Гросмана и Лерха (1961), оптимизирующие проект по стоимости, иллюстрируют возможности теории графов при построении моделей задач, разработке вычислительных алгоритмов и проведении простых доказательств. Трудность восприятия названных работ обратно

пропорциональна степени использования теории графов. Доказательства Келли, основанные на методике параметрического линейного программирования Гасса и Саати (1955), оказываются очень громоздкими. Метод Фалкерсона, заключающийся в сведении исходной задачи параметрического линейного программирования к задаче определения потока в сети, проще метода Келли. Наконец полностью графотеоретический подход Гроссмана и Лерха представляется почти очевидным, но вместе с тем он является достаточно строгим. Аналогичный подход использован Берманом (1964) при нелинейных функциях стоимости и Фейем (1964) для планирования многотемных разработок.

- Делается довольно много попыток решения задач на графах при заданных функциях ресурсов (Ламбурн,

1963, Фей, 1964). В этом случае типичная задача состоит в том, чтобы найти такое распределение ресурсов, при котором выдерживаются все требуемые графики выполнения проектов и количество ресурсов, необходимое для их выполнения, никогда не превышает имеющегося на данном интервале времени. Решение такого рода задач пока еще вызывает серьезные затруднения.

Основные допущения, лежащие в основе метода ПЕРТ, были исследованы Мак-Криммом (1964), который показал, что одна из проблем обусловлена заданием длительности операций не в виде действительных чисел, а в виде распределений вероятности. Для преодоления осложнений, вызванных стохастическими переменными, Фей (1963) и Ван Слейк (1963) предложили метод статистического моделирования сетей.

ЛИТЕРАТУРА К РАЗДЕЛУ 6.4

(см. скан)

(см. скан)