Задача сетевого планирования и управления (PERT)

По этой ссылке вы найдёте полный курс лекций по математике:

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

В проектно-конструкторских организациях подобный граф называют сетевым графиком. Очевидно, что рассматриваемый граф является ациклическим. ' Например, при строительстве здания в качестве этапов могут рассматриваться закладка фундамента, возведение стен, возведение крыши, вставка окон и т.д., а в качестве событий — начало строительства, окончание возведения фундамента, начало отделочных работ, окончание строительства и т. п-.

Таблица 4 Этап проекта (элементарная работа) Обозначение Опорные работы Время выполнения Разработка технического задания Конструирование оснастки Разработка электросхемы Разработка сборочных чертежей Разработка технологии сборки Изготовление оснастки Монтаж электросхемы Сборка изделия Окраска изделия Задача сетевого планирования и управления (PERT) Пример 1. Рассмотрим построение сетевого графика для планирования производства некоторого изделия.

Перечень элементарных работ, их длительность и логические связи представлены в табл. Дуги сетевого графика мы будем обозначать так же, как и соответствующие работы. Источник графа будет соответствовать началу выполнения проекта, а сток — окончанию. Из таблицы видно, что работы е\ и е2 являются начальными (у них нет предшествующих работ), а работы с8 и е9 — завершающими (они не предшествуют никаким другим). Таким образрм, дуги е, и с2 будут начинаться в источнике графа, а дуги е8 ие,- заканчиваться в стоке.

По окончании работы с, начинаются работы и с« — значит, в графе конец дуги е, будет служить началом дуг е} и е*. Аналогично, конец дуги с, — начало дуг с5 и е?.

Поскольку работе непосредственно предшествуют работы , в графе должна быть вершина, служащая концом дуг е4 и е5 и началом дуги е. Продолжая подобные рассуждения. в конце концов получаем следующий сетевой график (рис.31). Будем считать, что задано конкретное время выполнения каждого этапа — вес дуги t(vi, Vj).

В задаче сетевого планирования и упрамения требуется найти минимальное время выполнения проекта — время, за которое можно пройти по всем дугам графа, двигаясь от начальной вершины (5) к конечной вершине причем движение по каждой дуге может начаться лишь после того, как пройдены все дуги, заходяшие в ее начало. Другими словами, нужно найти самый длинный путь (т.е. путь наибольшего веса) от s к t.

Возможно вам будут полезны данные страницы:

Для решения данной задачи можно модифицировать алгоритм Дейкстры нахождения кра1чайшего пути от s к t: заменить оо на 0,, min на шах. Мы опишем более эффективный алгоритм, учитывающий ацикличность графа. Пронумеруем вершины орграфа ) так, чтобы каждая дуга ) вела из вершины с меньшим номером в вершину с большим номером: в силу ацикличности это всегда возможно). Через ) обозначим наиболее раннее время начала операций, соответствующих дугам, исходящим из вершины Vi (считая l{v 1) = 0), иными словами, l(vi) — длина самого длинного пути из Vi в г/, .

тогда будет равно l(vn). Алгоритм состоит в последовательном вычислении по очевидной формуле: с нулевыми начальными условиями: Пример 2. Для сетевого графика, построенного выше, в результате работы алгоритма находим: Задача сетевого планирования и управления (PERT) Таким образом, если считать, что время выполнения работ проекта было задано в днях, то минимальное время выполнения всего проекта равно 18 дням.

В более обшем случае время выполнения этапа — случайная величина. "> В англоязычной литературе принят термин PERT (Project Evaluation Research Task). Путь наибольшей длины от начальной вершины графа к конечной называют критическим путем. В рассмотренном примере критическим является путь В обшем случае, в графе может быть несколько критических путей.

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

Обозначим через Ь(т) самое позднее время начала операций, отвечающих дугам, исходящим из вершины vt, при котором весь проект все еще может быть выполнен за минимальное время. Для нахождения L(vi) поменяем ориентацию каждой дуги (при этом поменяются местами начальная и конечная вершины) и, повторив предыдущий алгоритм, найдем l'(vi) — самый длинный путь от vn до V,;

нетрудно видеть, что . Теперь для каждой операции () можно определить резерв времени — на сколько единиц времени можно отложить начало ее выполнения, чтобы проект мог быть выполнен за минимальное вре'мя (при отсутствии других задержек): Задача сетевого планирования и управления (PERT) Для последнего примера имеем:

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