Модели с циклами

Единство всех рассмотренных нами связей («начало-начало», «окончание-начало», «начало-окончание» и «окончание-окончание») выражается в их эквивалентности связи «окончание-начало» с некоторым лагом (FS+ d: А→В), который может быть как положительным, так и отрицательным числом. Данную связь можно интерпретировать двояко: либо работа В не может начаться раньше, чем закончится работа А +d, либо работа А не может закончиться позже, чем начнется работа В – d. В последнем случае связь «не позже» мы обозначали FS^max–d: В→А. Это определяет отношение эквивалентности между связями «не позже» и «не раньше». Итак, связи «не позже» эквивалентны отношению предшествования, т.е. любую модель с такими связями можно преобразовать к модели, в которой есть только связи FS^min+d, но за это мы расплачиваемся тем, что стрелки могут идти в обратном направлении таким образом, что некоторые последовательности работ замыкаются в циклы. Циклом называется путь, в котором есть, по меньшей мере, три работы, из которых первая и последняя совпадают. Циклы становятся вполне терпимыми, если относиться к отношениям предшествования (которые формируют циклы), как к ограничениям на сроки выполнения работ, а не как к стрелочкам, которые указывают на то, какие работы должны выполняться дальше. В таком случае возможно применение метода критического пути для определения расписания, удовлетворяющего всем ограничениям, и изучения его свойств. Если всё же вас смущают циклы, то используйте в моделях связи «не позже» (FS^max+d) и тогда циклов удастся избежать. Рассмотрим еще одно определение, которое позволит нам упростить наши рассуждения. Элементарным циклом называется цикл, в котором повторяются только первая и последняя работа. Очевидно, что в любом цикле существует элементарный цикл, как его подмножество работ. Поэтому мы можем ограничиться рассмотрением только элементарных циклов. К циклу применимо определение длины, которое было дано для пути, и соответствовало минимальному времени, которое нужно затратить на выполнение всех работ цикла. В общем случае, длину можно получить, если: 1) применить к пути расчет ранних сроков с помощью СРМ; 2) рассчитать максимальную разницу между ранними окончаниями и началами разных работ. С циклом связано еще одно важное понятие – внутреннего резерва. Внутренним резервом элементарного цикла называется время, на которое можно задержать выполнение любой работы цикла без увеличения его длины. Для того, чтобы найти внутренний резерв элементарного цикла, достаточно сложить продолжительности всех работ, входящих в цикл, а также сложить лаги всех отношений предшествования, образующих цикл, с каким бы знаком они не были. Если у цикла получается отрицательный резерв, то это означает, что не существует такого расписания выполнения работ цикла, которое бы удовлетворяло всем отношениям предшествования. Другими словами, в такой ситуации задача нахождения приемлемого расписания выполнения работ не имеет решения. Теорема.Расписание выполнения проекта, удовлетворяющее всем обобщенным отношениям предшествования, существует тогда и только тогда, когда в проекте нет элементарных циклов с отрицательным внутренним резервом.

Дата добавления: 2015-10-28