Том 11. Карты метро и нейронные сети. Теория графов - страница 16
К важнейшим подобным методам относятся следующие.
1. PERT (Program Evaluation and Review Technique — техника оценки и анализа программ). Была разработана по заказу ВМС США в 1958 году. Этот метод доказал свою эффективность при планировании длительных, сложных и затратных проектов.
2. СРМ (метод критического пути). Этот метод особенно подходит для планирования последовательности задач и изучения критических путей, то есть последовательности координируемых действий, невыполнение которых может вызвать задержки проекта. Похожими методами являются СРА (анализ критического пути), РЕР (процедура оценки программы), LESS (оценка наименьших затрат и планирование) и SCANS (планирование и контроль посредством автоматизированной сети).
3. RAMPS (выделение ресурсов и многопроектное планирование). Этот метод включает метод PERT и применяется при распределении ограниченных ресурсов между несколькими независимыми проектами.
Схема анализа по системе PERT
В общем виде последовательность действий при анализе PERT можно изложить так, как показано на следующей диаграмме:
* * *
СОСТАВЛЕНИЕ РАСПИСАНИЯ С ИСПОЛЬЗОВАНИЕМ КРИТИЧЕСКИХ ПУТЕЙ
В отраслях, где в производственной цепочке задействуется различное оборудование и персонал, интерес представляют алгоритмы производства, методы составления расписания и анализ критических путей. Наиболее важным для этого является изучение зависимостей между задачами или их отсутствия. Рональд Грэхем разработал алгоритм обработки списка задач с помощью m обработчиков. При оптимальном времени выполнения задач Т алгоритм гарантирует, что будет найдена последовательность, время выполнения которой не будет превышать (2 — (1/m))Т. Обработчиком может быть человек, устройство или система, время работы которых запрограммировано. В алгоритме, в котором задачи выполняются в порядке убывания сроков выполнения, общее время не будет превосходить [4/3 — 1/(3m)]Т. Однако никогда не стоит недооценивать частные эвристические решения.
* * *
Система PERT, которую мы сейчас обсудим, основана на следующих принципах.
1. Формируется упорядоченное структурное разделение задач проекта. Разделение задач может выполняться с помощью органиграммы, на которой отображаются основные действия. Также можно сформировать группы действий, которые должна выполнить каждая группа, участвующая в реализации проекта.
2. Определяются задачи. Описание основных задач и необходимых технологий позволяет разграничить участки проекта. На этом этапе определяются все действия и их последовательность.
3. Каждой задаче присваиваются ресурсы, фиксируются сроки выполнения задач. Здесь необходимо составить «календарь» реализации проекта, в котором будет указано общее время и время выполнения отдельных действий с учетом всех возможных факторов: ресурсов, технологий, рабочих групп и так далее.
Одна из оригинальных особенностей PERT — введение различных понятий времени:
а) Т>о — оптимистичное время выполнения, достигающееся при безукоризненном выполнении всех задач без сбоев;
б) Т>р — пессимистичное время, в котором учитываются все возможные действия и события, препятствующие выполнению проекта;
в) Т>т — среднее, или вероятное время, или время, рассчитанное с помощью статистических методов на основе прошлого опыта;
г) Т>е — реальное время, которое используется в PERT для каждого действия и рассчитывается по формуле (обосновывается статистически):
Иными словами, реальное время вычисляется как средневзвешенное оптимистичного, пессимистичного и среднего времени. Также рассчитывается стандартная ошибка (Т>p + Т>o)/6, квадрат которой будет оценкой отклонения.
4. Анализируются и определяются зависимости. На этом этапе определяются все возможные зависимости между действиями проекта: ограниченность ресурсов, физического пространства, рабочих групп; ограничения, вызванные особенностями месторасположения, и другие.
5. Формируется сеть, или граф, который является основной моделью системы.
При построении этого графа нужно руководствоваться следующими правилами:
а) события (начало или завершение действия) являются вершинами графа. Они изображаются кругами и прямоугольниками, внутри которых записывается название события и его порядковый номер;
