Файл: лекции 2-й семестр.doc

Рис. 2. Сеть проекта издания книги

Анализ методом критического путизаключается в использовании сетевых графиков при определении “критических” мероприятий проекта. Критические действия не гибкие и должны начинаться и заканчиваться вовремя для того, чтобы проект был завершен в срок.

Конечным результатом применения метода критического пути будет построение временного графика выполнения проекта. Для этого проводятся специальные вычисления, в результате чего получаем следующую информацию:

а) общая длительность выполнения проекта;

б) разделение множества процессов, составляющих проект, на критические и некритические.

Процесс является критическим, если он не имеет “зазора” для времени своего начала и завершения. Т.о., чтобы весь проект завершился без задержек, необходимо, чтобы все критические процессы начинались и заканчивались в строго определенное время. Для некритического процесса возможен некоторый “дрейф” времени его начала, но в определенных границах, когда время его начала не влияет на длительность выполнения всего проекта.

Для проведения необходимых вычислений определим событие как точку на временной оси, где завершается один процесс и начинается другой. В терминах сети, событие - это сетевой узел. Введем также следующие обозначения и определения.

 _j- самое раннее возможное время наступления события j;

_j - самое позднее возможное время наступления события j;

D_ij- длительность процесса (i, j).

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

Проход вперед. Здесь вычисления начинаются в узле 1 и заканчиваются в последнем узле n.

Начальный шаг. Полагаем ₁= 0; это указывает на то, что проект начинается в нулевой момент времени.

Основной шаг j. Для узла j определяем узлы p, q, ..., v, непосредственно связанные с узлом j процессами (p, j), (q, j),..., (v, j), для которых уже вычислены самые ранние времена наступления соответствующих событий. Самое раннее время наступления события j вычисляется по формуле

 _j= max {_p+ D_pj,_q+ D_qj,...,_v+ D_vj}.

Проход вперед завершается, когда будет вычислена величина _n для узла n. По определению величина_jравна самому длинному пути (длительности) от начала проекта до узла (события) j.

Проход назад. В этом проходе вычисления начинаются в последнем узле n и заканчиваются в узле 1.

Начальный шаг. Полагаем _n_n; это указывает, что самое раннее и самое позднее времена для завершения проекта совпадают.

Основной шаг j. Для узла j определяем узлы p, q, ..., v, непосредственно связанные с узлом j процессами (p, j), (q, j),..., (v, j), для которых уже вычислены самые поздние времена наступления соответствующих событий. Самое позднее время наступления события j вычисляется по формуле

_j= min {_p- D_pj,_q- D_qj,...,_v- D_vj}.

Проход назад завершается при вычислении величины ₁для узла 1.

Процесс (i, j) будет критическим, если выполняются три условия:

1. _i =  _i

2. _j =  _j

3. _j - _i =  _j -  _i = D_ij

Если эти условия не выполняются, то процесс некритический.

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

Пример 1.

Найдем критический путь для сети проекта, показанной на рис. 23. Длительность всех процессов дана в днях.

Обозначения:

Проход вперед:

Проход назад:

FКритический путь:

B2E11

6

CG

3

12

A

H

5 1

D

8

Рис.23

Проход вперед.

Узел 1. Полагаем ₁= 0.

Узел 2. ₂=₁+ D₁₂= 0 + 5 = 5.

Узел 3. ₃= max {₁+ D₁₃,₂ + D₂₃} = max {0 + 6, 5 + 3}= 8.

Узел 4. ₄=₂+ D₂₄= 5 + 8 =13.

Узел 5. ₅= max {₃+ D₃₅,₄+ D₄₅} = max {8 + 2, 13 + 0} = 13.

Узел 6. ₆= max {₃+ D₃₆,₄+ D₄₆,₅+ D₅₆} = max {8 + 11, 13 + 1, 13 + 12} = 25.

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

Проход назад.

Узел 6. Полагаем ₆=₆= 25.

Узел 5. ₅=₆- D₅₆= 25 - 12 = 13.

Узел 4. ₄= min {₆- D₄₆,₅- D₄₅} = min{25 - 1, 13 - 0} = 13.

Узел 3. ₃= min{₆- D₃₆,₅- D₃₅} = min{25 - 11, 13 - 2} = 11.

Узел 2. ₂ = min{₄- D₂₄,₃- D₂₃} = min{13 - 8, 11 - 3} = 5.

Узел 1. ₁= min{₃- D₁₃,₂- D₁₂} = min{11 - 6, 5 - 5} = 0.

Вычисления без ошибок всегда приводят к результату ₁= 0.

Результаты вычислений, выполняемых при проходах вперед и назад, показаны на рис. 3. Правила определения критических процессов показывают, что критический путь составляют процессы 12456, т.е. этот путь проходит от начального узла 1 до конечного узла 6. Сумма длительностей критических процессов (1, 2), (2, 4), (4, 5) и (5, 6) равна длительности всего проекта (т.е. 25 дней). Отметим, что процесс (4, 6) удовлетворяет первым двум условиям критического пути (₄=₄= 13 и₆=₆= 25), но не удовлетворяет третьему условию (₆-₄D₄₆). Поэтому данный процесс не является критическим.

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

На графике Гантта отмечается время начала и окончания действия и с его помощью легко увидеть, какие из действий должны проистекать в любой временной точке. График Гантта особенно полезен при управлении проектом и планировании ресурсов. Напомним, что _i для процесса (i, j) указывает на самое раннее время начала этого процесса,_j- на самое позднее время завершения процесса. Таким образом, пара величин (_i,_j) ограничивает максимальный интервал времени, в течение которого может выполняться процесс (i, j).

Пример 2.

Построим временной график проекта из примера 1 (рис. 23).

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

1. Критические процессы (показаны на графике сплошными линиями) располагаются последовательно друг за другом без временных зазоров и перекрытий. Таким образом, их суммарная длительность равна длительности выполнения всего проекта (здесь 25 дней).

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

Как выбрать время начала выполнения некритического процесса? Обычно предпочитают начинать некритические процессы (по возможности) в самый ранний срок. В этом случае остается запас времени (остаток максимального интервала выполнения), который можно использовать для решения неожиданно возникших во время выполнения процесса проблем. Вместе с тем при необходимости можно перенести начало выполнения какого-либо процесса. Допустим, если в нашем примере во время выполнения процессов E и F (рис.24) используется одно и то же оборудование, причем в каждый момент времени его можно задействовать только для одного процесса, тогда можно исключить временное наложение этих процессов, начав процесс F после завершения E.

А - 5

Критические

D- 8 процессы

G- 12

B- 6

Некритические

C- 3

E- 2 процессы

F- 11

H- 1

5 10 15 20 25

Дни

Рис.24

Если на некритические процессы не накладываются какие-либо дополнительные ограничения, и все они начинаются в самый ранний момент времени, то временной график проекта строится автоматически. Однако в этом случае могут нарушаться некоторые отношения предшествования. В частности, в примере (см. рис.3) процесс С должен быть завершен до начала процесса Е. Но максимальные интервалы времени выполнения этих процессов перекрываются, поэтому и реальные интервалы времени их выполнения также могут перекрываться. Поэтому необходимо предусмотреть какие-нибудь “красные флажки”, которые автоматически указывали бы, когда тот или иной процесс может начинаться без нарушения отношений предшествования с другими процессами.

Определение запасов времени. Запас времени некритического процесса - это часть максимального интервала времени выполнения этого процесса (который больше реальной длительности процесса). Различают общий запас времени и свободный запас времени процесса.

На рис. 25 показана разность между этими запасами времени процесса (i, j) - общим (TF_ij) и свободным (FF_ij). Общий запас времени процесса (i, j) определяется как превышение над длительностью выполнения этого процесса интервала времени от самого раннего момента осуществления события i до самого позднего времени осуществления события j, т.е.

TF_ij=_j -_i -D_ij.

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

FF_ij=_j-_i -D_ij.

По определению FF_ijTF_ij.

Правило “красного флажка”. Для некритического процесса (i, j)

а) если FF_ij= TF_ij, тогда данный процесс может выполняться в любое время внутри максимального интервала (_i,_j) без нарушения отношений следования;

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

j

TF_ij = _j -  _i - D_ij

FF_ij =  _j -  _i - D_ij

i j

D_ij

i j

Рис.25

Это правило означает, что некритический процесс (i, j) помечается “красным флажком” только тогда, когда FF_ij< TF_ij. Этот флажок принимается во внимание при сдвиге начала процесса относительно самого раннего времени на такую величину, при которой следует рассчитывать сдвиг процессов, следующих из узла j.