Анализ критического пути с применением вершинных графов

□ Пример 10.4. В табл. 10.3 указана продолжительность выполнения каждой операции проекта, о котором шла речь в примерах 10.2 и 10.3. Определим общую продолжительность выполнения проекта.

322 f.3. Планирование в бизнесе

Таблица 10.3. Операции и их продолжительность для примера 10.4

Операция	Непосредственно	Время,
	предшествующая операция	дней
А	—
В	—
С	—
D	А, В
Е	В, С
F	С
G	D, Е
Н	F, G •

Вершинный граф, соответствующий данному проекту, был построен в примере 10.3.

Решение

Предположим, что каждая из исходных операций А, В и С начинается в нулевой момент времени. Это наиболее ранний срок начала этих ES операций. Наиболее ранний срок, к которому их выполнение может быть завершено, определяется следующим образом:

Наиболее ранний срок окончания EF=ES+ Продолжительность операции.

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

Таблица 10.4. Расчет наиболее ранних сроков начала и окончания операций для примера 10.4

Операция	Продолжительность, дней	Наиболее ранний срок начала	Наиболее ранний срок окончания	Комментарий
А			0 + 8 = 8
В			0 + 10 = 10
С			0 + 6=6
D			10 + 8 =18	Нельзя начать, пока
Е			10+ 9 =19	не завершены А и В Нельзя начать, пока
F			14+ 6 =20	не завершены В и С Нельзя начать, пока
G			14 + 19 = 33	не завершена С Нельзя начать, пока
Н			33+ 6 =39	не завершены D и Е Нельзя начать, пока не завершены F и О

Гл. 10. Сетевой анализ и календарное планирование проектов 32 3

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

Ключ

	в
А	в

Начальный узел

Обозначение операции


D


Е	в

ES	EF

LS	LF

— Продолжительность

"ЩуУ 33

Рнс.10.10 Вершинный граф для примера 10.4

На данном этапе мы еще не можем определить критические операции. Чтобы это осуществить, необходимо для каждой операции рассчитать два срока, ей соответствующие, а именно наиболее поздний срок начала LS и наиболее поздний срок окончания LF операции. В данном случае процедуру расчетов мы начнем с последней операции в графе и предположим, что наиболее поздний и наиболее ранний сроки ее окончания совпадают. Затем вычитанием из этой величины продолжительности выполнения операций находим наиболее поздний срок ее начала. Ход выполнения расчетов показан в табл. 10.5.

Таблица 10.5. Расчет наиболее поздних сроков начала и окончания операций для примера 10.4

Операция	Продолжительность, дней	Наиболее поздний срок окончания	Наиболее поздний срок начала	Комментарии

Н			39 - 6 = 33
G			33 - 14 = 19	G нужно завершить до наступления наиболее позднего срока начала Н
F			33 - 14 = 19	F нужно завершить до. наступления наиболее позднего срока начала Н
Е			19 - 9 = 10	Е нужно завершить до наступления наиболее позднего срока начала G --------------