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

Метод оценки и проверки планов (PER T) и метод критического пути (CPM) были разработаны в 1950–х годах для управления сложными проектами. CPM появился в 1957 г. для организации строительства и ремонта химических заводов Дюпона. PER T разрабатывался независимо для нужд военно-морского флота и появился в 1958 г.

Алгоритм методов CPM и PER T:

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

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

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

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

Главное различие в методах состоит в том, что в CPM продолжительность работы детерминированная величина, а в PER T – случайная.

В PER T используется три временных оценки для каждой работы: пессимистическая (t _п), наиболее вероятная (t _нв) и оптимистическая (t _о). Тогда ожидаемая продолжительность работы определяется как:

.

Отклонение времени выполнения работы:

.

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

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

Таблица 4.7

Работа	Содержание работы	Следует после работ	Продолжительность	Обозначение
a1 a2 a3 a4 a5	Закупка и доставка оборудования Разработка технологии Монтаж и наладка оборудования Обучение рабочих–операторов Пуск линии в эксплуатацию	– – a1 a1 a2, a4		1–2 1–3 2–3 2–4 3–4

Таблица 4.8

Событие	Время наступления
Начало работ Оборудование получено Технология разработана, оборудование отлажено Персонал обучен, производство запущено	Т1 Т2 Т3 Т4

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

Рис. 4.6

Работу будем обозначать двумя индексами i – j, где i – номер события, после которого начинается работа, j – номер события, которым заканчивается работа (рис. 4.6 и последнюю графу табл. 4.8).

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

Таблица 4.9

Путь	Последовательность работ	Продолжительность
	1–2–4	1 + 3 = 4
	1–2–3–4	1 + 4 + 6 = 11
	1–3–4	2 + 6 = 8

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

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

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

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

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

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

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

Т₁ = 0;

Т₂ = Т₁ + t ₁₂ = 0 + 1 = 1.

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

значит Т3 = 5.

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

значит Т4 = 11.

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

Из рис. 5.7 видно, что резерв работы 1–3, который будем обозначать D₁₃ = 5–2 = 3. Значит работа 1–3 может быть начата не в начальный момент времени, а спустя 3 ед. времени, или продолжаться на 3 ед. больше, чем первоначально предполагалось, то есть может длиться 2 + 3 = 5 ед. без увеличения момента наступления конечного события “4”.

Рис. 4.7

Аналогично D₂₄ = Т₄ – (Т₂ + t ₂₄) = 11–(1 + 3) = 7, то есть продолжительность работы 2–4 может быть увеличена на 7 ед. Очевидно, что для работ критического пути резерв времени равен 0, то есть D₁₂ = D₂₃ = D₃₄ = 0.

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

Т₃ = Т_{1 +} t ₁₃ + D₁₃. Отсюда (Т₃ – Т₁) – D₁₃ = t ₁₃.

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

Т₃ = x ₃; D₁₃ = x ₁₃; Т₁ = x ₁; t ₁₃ = b ₁₃, то можно записать:

(x ₃ – x ₁) – x ₁₃ = b ₁₃ и получить линейное уравнение с тремя неизвестными.

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

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

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

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

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

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

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

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

Таблица 4.10

Постановка	Целевая функция	Граничные условия	Т1	Т2	Т3	Т4	D12	D13	D23	D24	D34
	T4® min	T1 = 0
	T1® max	T4 = 15

на + 4 больше, чем в 1-й постановке

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

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

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

(_*) (Т _j – T _i) – D _ij = t_ij (для всех i, j).

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

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

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

где T_{1 пл,} T _{n пл} – заданные плановые сроки начала и окончания работ сети.

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

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

Рис. 4.8