Оптимизация сетевого графика

Метод оценки и проверки планов (РЕRТ) и метод кри­тического пути (СРМ) были разработаны в 1950-х гг. для управления сложными проектами. СРМ появился в 1957 г. для организации строительства и ремонта химических за­водов Дюпона. РЕRТ разрабатывался независимо для нужд военно-морского флота и появился в 1958 г.

Алгоритм методов СРМ и РЕRТ:

1) определить основные работы по проекту и их продол­жительность;

2) установить связи между работами;

3) вычертить сеть, содержащую все работы;

4) рассчитать критический путь (самый продолжитель­ный).

Главное различие в методах состоит в том, что в СРМ продолжительность работы - детерминированная величи­на, а в РЕRТ - случайная.

В РЕRТ используются три временных оценки для каж­дой работы: пессимистическая (t_п), наиболее вероятная (t_нв) и оптимистическая (t_o). Тогда ожидаемая продолжитель­ность работы определяется как:

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

Исходные данные, необходимые для составления сети, представляют в форме таблицы, которая включает после­довательность работ и продолжительность выполнения каж­дой работы (см. табл. 18).

Таблица 18

По исходным данным табл. 18 строится сетевой гра­фик (см. рис. 14), на котором числа над дугами показыва­ют продолжительность каждой работы. События будем обо­значать порядковыми номерами. Два события отметим осо­бо: начальное - состояние, с которого начинается весь комплекс работ; конечное - состояние, которым заверша­тся комплекс работ.

Таблица 19

Рис. 14

Работу будем обозначать двумя индексами i и j, где i - номер события, после которого начинается работа, j - номер события, которым заканчивается работа (рис. 14 и табл. 19).

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

Таблица 20

Путь наибольшей продолжительности называют крити­ческим (в примере - второй). На критическом пути лежат работы 1-2; 2-3; 3-4.

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

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

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

Если руководитель следит за выполнением всех работ в срок, то он должен четко знать и особо контролиро­вать работы критического пути.

В нашем примере критический путь был найден про­стым перебором всех возможных путей. Исследование мо­дели было словесным, без математической формулировки. Это необходимо для уяснения смысла, но недостаточно для сложных сетей.

Перейдем к формализации. В нашем примере время наступления каждого события может быть найдено по за­висимостям

Так как третье событие может наступить после выпол­нения работ 2-3 и 1-3, запишем:

Аналогично найдем время наступления последнего со­бытия:

Окончательное время на­ступления событий: T₁ =0; T₂ =1; T₃ =5; T₄ =11 (рис. 15).

Рис. 15

Из рис. 21 видно, что резерв работы 1-3, который бу­дем обозначать Значит работа 1-3 может быть начата не в начальный момент времени, а спустя 3 ед. времени, или продолжаться на 3 ед. больше, чем первоначально предполагалось, т.е. может длиться 2 + 3 = 5 ед. без увеличения момента наступления конечного события 4.

Аналогично , т.е. продолжительность работы 2-4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, т.е. .

Для третьего события можно записать . Отсюда .

Выражение (Т₃ – Т₁) записано в скобках, чтобы было наглядно видно, что это интервал времени между двумя последовательными событиями. И этот интервал за выче­том резерва Δ₁₃ равен продолжительности работы 1-3. В этой зависимости нам задана продолжительность работы t₁₃ =2(правая часть уравнения), остальные величины - иско­мые переменные. Если их обозначить:

то можно записать:

и получить линейное уравнение с тремя неизвестными.

Если записать аналогичные зависимости для всех собы­тий и работ, входящих в нашу сеть, то получим систему:

Эта система описывает топологию (структуру) нашей сети. Следовательно, сеть может быть представлена не только графически, но и в виде аналитических уравнений, кото­рые можно ввести в ПЭВМ.

Если вместо t_ij подставить их известные (заданные) зна­чения, получим:

Эта система структуры сети содержит пять линейных уравнений с девятью неизвестными. Значит, она имеет бес­численное множество решений. Чтобы ее решить, надо до­бавить граничные условия и целевую функцию.

При этом возможны две постановки задач оптимизации.

Первая постановка: задаемся временем начала работ, т.е. значением Т₁, например Т₁ = 0, и стремимся закон­чить комплекс работ как можно раньше:

Вторая постановка: задан срок завершения всех работ, например Т₄ = 15, и нас интересует как можно позже на­чать работы, но чтобы непременно уложиться в срок:

Обе постановки - это задачи линейного программиро­вания, которые можно решить (табл. 21).

Таблица 21

Поста-новка	Целевая функция	Граничные условия	T1	T2	T3	T4	Δ12	Δ13	Δ23	Δ24	Δ34
		T1 = 0
		T4 = 15

Из таблицы видно, что резерв Δ_ij не зависит от поста­новки задачи. Времена же окончания работ в первой поста­новке и начала работ во второй постановке определяются заданными граничными условиями.

Теперь перейдем к определению критического пути и других параметров сети, заданной в общей постановке.

В общем виде топология сети запишется:

Если S - число событий, R - число работ, то, как видно из (*), система, описывающая сеть, будет включать п переменных, где п = S + R, так как каждому i -му событию соответствует неизвестная Тi, а каждой i, j- й работе - не­известная Δ_ij. А число ограничений m = R, т.е. каждой работе соответствует ограничение.

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

Тогда общие постановки запишутся:

где Т_1пл, Т_ппл - заданные плановые сроки начала и оконча­ния работ сети.

Например, для графика (см. рис. 16) из 11 событий и 20 работ (всего лишь) первая постановка при Т₁ = 0 будет иметь вид:

Рис. 16

В результате решения задачи на ПЭВМ определены кри­тический путь, сроки начала работ и событий, резервы работ, приведенные под стрелками. Решение этой задачи вручную очень трудоемко

Поиск по сайту: