Определение запасов времени

Общий запас времени работы (i, j)

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

Свободный резерв времени работы (i, j)

определяется как превышение над длительностью выполнения этой работы интервала времени от самого раннего момента осуществления события i до самого раннего осуществления события j.

Замечание. По определению

.

Правило «красного флажка»

Для некритической работы (i, j)

· если , тогда данную работу можно выполнять в любое время внутри максимального интервала () без нарушения отношений следования;

· если , тогда без нарушения отношений следования данную работу можно начать со сдвигом, не превышающем , относительно самого раннего момента начала работы t _i. Сдвиг начала работы на величину времени, превышающую   (но не более ), должен сопровождаться равным сдвигом относительно t _j всех работ, начинающихся с события j.

Вычислим запасы времени некритических работ в сети проекта из примера 7.2 и поместим в таблицу 7.3.

Таблица 7.3 Запасы некритических работ проекта из примера 7.2

Некритическая работа (i,j)	Длительность работы	Общий запас времени для работы (i,j)	Свободный запас времени для работы (i,j)
B(1,3) flag	6	11 - 0 – 6 = 5	8 – 0 – 6 = 2
C(2,3) flag	3	11 - 5 – 3 = 3	8 - 5 – 3 = 0
E(2,5)	2	13 - 8 – 2 = 3	13 - 8 – 2 = 3
F(3,6)	11	25 - 8 – 11 = 6	25 - 8 – 11 = 6
H(4,6)	1	25 - 13 – 1 = 11	25 - 13 – 1 = 11

Правило «красного флажка» следует применять только к работам B и С, поскольку только для них . Оставшиеся работы (E, F и H) имеют , поэтому они могут выполняться в любое время внутри своих максимальных интервалов времени выполнения.

Рассмотрим работу В, помеченную «красным флажком». Поскольку для этой работы дней, она может начаться в любой день из интервала 0-5 дней от начала выполнения проекта. Но у нас дня, то поскольку работа В начнется в 0-ой, 1-й или 2-й день от начала выполнения проект, это не окажет никакого эффекта на последующие работы E, F. Однако если работа В начнется в (2+D)-й день (2+D < 5), начало выполнения работ E, F необходимо сдвинуть от самого раннего срока их начала (8-й день от начала выполнения проекта) на величину, не меньшую D; только при таком условии не нарушается отношения следования между работами В, E и F.

Для помеченной работы С имеем . Это означает, что любой сдвиг начала выполнения этой работы должен сопровождаться таким же (не меньшим) сдвигом начала выполнения процессов E и F.

Контрольные вопросы

1 Что называется сетевым графиком?

2 Сформулируйте основные правила построения сетевых графиков.

3 Назовите основные шаги метода критического пути?

4 В чем суть «правила красного флажка»?

Тема 8 Задача о максимальном потоке