Особые ограничения. Критический путь. Резерв времени

Предположим, что некоторая операция может быть начата только по наступлении какого–то момента, т. е. по прошествии некоторого срока после события Е1 принимаемого за начальное [13, с. 124]. Такое ограничение выражается введением фиктивной операции z между Е1 и событием Еi, где начинается рассматриваемая операция. Это показано на рисунке 2.9.

Рисунок 2.9 – Ограничение с одной фиктивной операцией

Рисунки 2.10 и 2.11 относятся к случаю, когда приходится вводить две фиктивные операции x и z: операция с, следующая за а, должна быть отсрочена на время z.

Рисунок 2.10 – Ограничение с двумя фиктивными операциями

Рисунок 2.11 – Критический путь

Во многих задачах встречаются некоторые «условия отсрочки начала выполнения операции»; ими могут быть, например, сроки поставки материалов, климатические условия и т. п. Как мы видим, такие особые условия легко могут быть введены в сеть.

Для того чтобы иметь возможность учесть такие ограничения и ввести их в сеть, сформулируем их по–другому: «Для того чтобы некоторая работа j могла быть начата, необходимо, чтобы время, прошедшее с момента начала другой работы j, было не меньше данного (–tij)»; это приводит к обычным связям, но с отрицательной длительностью (длина соответствующей дуги будет отрицательна), что необязательно означает усложнение решения задачи.

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

Время завершения комплекса операций. Критический путь. Когда сеть проекта построена, встает следующий вопрос: каково время завершения всего комплекса операций, т. е. какова продолжительность реализации проекта. Это время не может быть меньше суммы длительностей операций, взятой вдоль «самого неблагоприятного пути» из Е1 в Еn, т. е. вдоль такого пути между этими двумя точками, который дает максимальную сумму длительностей операций. Такой путь (их может оказаться несколько) называется «критическим путем».

Беря в качестве продолжительности выполнения комплекса работ сумму длительностей операции вдоль «наименее благоприятного пути из Е1 в Еn», мы тем самым обеспечиваем возможность действительного выполнения всех намеченных операций с учетом их длительностей [13, с. 136].

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

Начиная с события Е1, которому припишем время наступления 0, рассмотрим для каждой вершины сети дуги, которые в нее входят; для каждой из этих дуг сложим время соответствующей операции, которое приписано дуге, с временем наступления события, соответствующего началу дуги; сравнивая результаты и выбирая из них наибольший, приписываем его рассматриваемой вершине.

Рассмотрим рисунок 2.11. В Е2 входит только одна дуга (1,2). Поскольку для Е1 имеем 0, то для Е2 получим 0+8=8. В Е3 входят две дуги (2,3) и (1,3); сравнивая 8+4=12 с 0+13=13, приписываем Е3 значение 13; это означает, что наступление события Е3 нельзя ожидать раньше 13. В Е4 входят две дуги (3,4) и (1,4); сравнивая 13+7=20 с 0+9=9, приписываем Е4 значение 20. Е5 приписываем значение 17. В Е6 входят две дуги (2,6) и (3,6); сравнивая 8+ 6=14 с 13+10=23, приписываем Е6 значение 23. В Е8 входят три дуги (6,8), (3,8) и (4,8); сравнивая 23+3=26, 13+6=19 и 20+9=29, приписываем Е8 значение 29. Так продолжаем вплоть до события Еn, которому приписываем окончательно значение 61.

Это число представляет собой время выполнения проекта, начинающегося с нулевого момента. Путь, соответствующий этому времени в 61 единицу, легко получить, возвращаясь шаг за шагом обратно из Е12 в Е1; это и будет критический путь. На рисунке 19 он отмечен жирной линией.

Если проект (комплекс операций) будет разворачиваться без неожиданных нарушений, его продолжительность должна будет составить 61 неделю и соответствующие события произойдут в моменты, указанные на рисунке 19.

Операции P13, P34, P48, P8,11, P11,10, P10,12 называются «критическими операциями». С них нужно начинать работу после наступления начальных событий соответствующих дуг. Так, к примеру, операция Р48 должна начаться в первую очередь после реализации события Е4, т. е. в момент 20. Если критическая операция будет задержана, это вызовет запаздывание выполнения всего проекта. Например, если операция Р48 начнется только в момент 22, проект будет завершен не раньше, чем к моменту 63.

Таким образом, критические операции представляют собой те операции проекта, на ход выполнения которых руководитель должен направить все свое внимание, так как от их своевременного выполнения зависит общий срок завершения всего проекта (всего комплекса работ). «Некритические операции» допускают некоторое запаздывание в выполнении операций.

Перейти на страницу: 1 2 3