Планирование и управление предприятиями железнодорожного транспорта

Представление проекта с помощью сети может быть сделано и другим образом. Будем изображать вершинами не события, а операции; дуги же используем для представления порядка, в котором операции Оij и Ojk должны следовать так, чтобы можно было задавать сроки между началом О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 – Окончательная сетевая модель

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

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

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

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

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

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

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

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

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

Предположим, что некоторая операция может быть начата только по наступлении какого–то момента, т. е. по прошествии некоторого срока после события Е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 он отмечен жирной линией.

 Скачать реферат