Планирование и управление предприятиями железнодорожного транспорта (стр. 7 из 10)

Рисунок 2.1 – Сетевая модель проекта

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

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

Первое, что нужно сделать, имея в виду применение метода критического пути, это составить перечень операций, который может быть детализирован в большей или меньшей степени в зависимости от точности, которую желательно получить. Операции надо стараться выбирать настолько простыми, насколько это возможно, и такими, чтобы времена операций были сравнимы по величине. Затем для каждой операции определяют предшествующие ей операции. Эта часть анализа работ является наиболее важной и часто занимает много времени. Она требует тесного сотрудничества всего персонала (инженеров, мастеров, рабочих), заинтересованного в выполнении проекта, и несомненно является полезной даже сама по себе [13, с. 107].

Представление проекта с помощью сети может быть сделано и другим образом. Будем изображать вершинами не события, а операции; дуги же используем для представления порядка, в котором операции О_ij и O_jk должны следовать так, чтобы можно было задавать сроки между началом О_ij и началом О_jk. В этом представлении принято называть «работами» то, что раньше мы назвали операциями, и «связями» – дуги, которым приписаны сроки. Для этого рассмотрим рисунок 2.2.

Рисунок 2.2 – Сетевая модель с указанием временных сроков

Чтобы до конца разъяснить переход от одного представления к другому, возьмем другой пример – переход от рисунка 2.3 к рисунку 2.5.

Рисунок 2.3 – Начальная сетевая модель

Как видно на рисунке 2.4 и 2.5, принято добавлять две работы D и F, представляющие начало и конец проекта. Рассматривая рисунок 2.5, видно, что работа g помещается после работ b и dмежду g и b существует связь: g может начаться только тогда, когда пройдет 6 единиц времени после начала b; между g и d существует связь: g может начаться только тогда, когда пройдет 4 единицы времени после начала d. В свою очередь работы d, f и е могут начаться только после того, как пройдет 3 единицы времени после начала а. Оба представления обладают и преимуществами и недостатками. Обычно выбирают то или другое представление в зависимости от существа той задачи, для которой составляется проект. Заметим, однако, что представление «работы–связи» позволяет вводить в проект новые связи или изменять отношения порядка между работами простым добавлением дуг без перестройки сети в целом.

Рисунок 2.4 – Сетевая модель с дополнительными операциями

Рисунок 2.5 – Окончательная сетевая модель

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

2.2 Операции, входящие в состав сетевых графиков

Параллельные операции. Предположим, что между двумя событиями Еi и Еj находятся две различные операции b и с, следующие за операцией а.

Введем тогда фиктивное событие Еj и дополнительную фиктивную операцию х между Еi и Еj. В случае, когда имеется три, четыре и т. д. параллельные операции, поступают так же, вводя для каждой из них фиктивное событие и дополнительную фиктивную операцию, как это показано на рисунке 2.6.

Рисунок 2.6 – Параллельные операции в сетевой модели

Операции зависимые и независимые. Рассмотрим на рисунке 2.7 операции с и d, следующие за а и b. Предположим теперь, что с следует за а и b, но d следует только за b и не обязано следовать за а. В этом случае уже нельзя пользоваться данной сетью и необходимо ввести событие Е'₃ и фиктивную операцию х, как это показано на рисунке 2.8.

Рисунок 2.7 – Зависимые операции

Рисунок 2.8 – Независимые операции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Операции P₁₃, P₃₄, P₄₈, P_8,11, P_11,10, P_10,12 называются «критическими операциями». С них нужно начинать работу после наступления начальных событий соответствующих дуг. Так, к примеру, операция Р₄₈ должна начаться в первую очередь после реализации события Е₄, т. е. в момент 20. Если критическая операция будет задержана, это вызовет запаздывание выполнения всего проекта. Например, если операция Р₄₈ начнется только в момент 22, проект будет завершен не раньше, чем к моменту 63.