Расчет сетевой модели

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

Преимущества, обеспечиваемые за счет выявления критических операция и определения резервов времени, рассматриваются в § 3. В данном параграфе в основном излагаются методы получения этой информации.

I.Определение критического пути

Критический путь определяет непрерывную последовательность критических операций, связывающих исходное и завершав­шее события сети. Другими словами, критический путь задает все критические операции программы. Метод определения такого пути иллюстрируется на численном примере.

Пример 2. Рассмотрим сетевую модель, показанную на рис.8, с исходными событием 0 и завершавшим событием 6. Оценки времени, необходимого для выполнения каждой операции, даны у стрелок.

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

Пусть ES_i ранний срок начала всех операций, выходящих из события i. Таким образом ES_i, является также ранним сроком наступления события i. Если принять i=0, т.е. считать, что номер исходного события равен 0, т.е. при расчете сети ES₀=0. Обозначим символом D_ij продолжительность операции (i, j). Тогда вычисления при прямом проходе выполняются по формуле для всех операций (I, J), где ES₀=0. Следовательно,чтобы вычислить ES_j для события j нужно сначала определить ES_i начальных событий всех операций (I, j), входящих в событие j.

Применительно к рис.8 вычисления при прямом проходе начинаются с ЕS₀=0,как показано в квадрате над событием 0.Поскольку в событие1 входит только одна операция (0,1) продолжительностью D₀₁=2, то ES₁= ES₀+D₀₁=0+2=2.

Этот результат записан в квадрате у события1. Рассмотрим далее событие(Заметим, что событие3 пока рассматривать нельзя, так как срок ЕS₂ (событие2) еще неизвестен.)

Таким образом ЕS₂₌ ES₀+D₀₂=0+3=3. Поместим этот результат в квадрат у события2. Перейдем теперь к событию3. Поскольку в него входят две операции

(1,3)и (2,3), то

Этот результат также записан в квадрате у события3.

Вычисление продолжается аналогичным образом, пока не будут определены значения ES_j для всех j. Имеем

На этом вычисления прямого прохода заканчиваются.

Обратный проход начинается с завершающего события сети. При этом целью является определения LC_i- поздних сроков окончания всех операций, входящих в событие i. Если принять i=n, где n-завершающее событие сети, то LC_n= ES_n является отправной точкой обратного прохода.В общем виде для любого события I

для всех операций (I, J).

Значение LC (указанные в треугольниках) вычисляются следующим образом:

LC₆=ES₆=19

LC₅= LC₆-D₅₆=19-6=13

LC₁= LC₃-D₁₃= 6-2 = 4

Таким образом, вычисления при обратном проходе закончены.

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

(1)

(2)

(3)

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

На рис. 8 критический путь включает операции (0,2), (2,3),(3,4),(4, 5) и (5,6). Критический путь определяет кратчайшую возможную продолжительность всей программы в целом. Заметим, что операции (2, 4), (3,5).(3,6) и (4,6) удовлетворяют условиям (1) и (2), но не условию (3). Поэтому они не являются критическими. Отметим, что критический путь представляет собой непрерывную цепочку операций, соединяющую исходные события сети с завершающими.

Контрольное упражнение 2

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

(а) (Ответ. (0,2,3,4,5,6,) и (0,1,3,4,5,6).)

(б) (Ответ. (0,2,3,6)).

2 Определение резервов времени

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

Прежде чем приступить к вычислению резервов времени:, нужно ввести определения еще двух сроков, связанных с каждой операцией. Это срок позднегоначала (LS)и срок раннего

окончания (EC), которые для любой операции (I,j)задаются соотношениями

Различают два основных вида резервов времени: полныйрезерв (TF) и свободныйрезерв (FF). Полный резерв времени операции (I,j) представляет собой разность между максимальным отрезком времени, в течение которого может быть выполнена операция (), и ее продолжительностью (), т.е.

Свободный резерв времени определяется в предположении, что все операции в сети начинаются в ранние сроки. При этом условии величина FF_ij для операции (I,j) представляет

собой превышение допустимого отрезка времени () над продолжительностью операции (D_ij), т.е.

Результаты расчета критического пути и резервов времени некритических операций можно свести в удобную для пользования таблицу. В столбцах (1), (2), (3), (6) приведены результаты

расчета сети, рассмотренной в примере 2. Остальные данные легко вычислить по приведенным выше формулам.

Таблица содержит всю необходимую для построения календарного графика информацию.

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

Операция (I,J)   (1)	Продолжи Тельность Dij (2)	Раннее	Позднее	Полный Резерв TFij (7)	Свободный Резерв FFij (8)
Начало ESi (3)	Окончание ECij (4)	Начало LSij (5)	Окончание LCj (6)
(0,1)
(0,2)						0*
(1,3)
(2,3)						0*
(2,4)
(3,4)						0*
(3,5)
(3,6)
(4,5)						0*
(4,6)
(5,6)						0*

*-критическая операция

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

§ 3 Стоимостные факторы, учитываемые при календарном планировании программ

Стоимостный аспект вводится в схему календарного планирования программ путем определения зависимости «затраты (стоимость) — продолжительность» для каждой операции программы. При этом рассматриваются только элементы так называемых прямых затрат, а косвенные затраты типа административно-управленческих рас­ходов не принимаются во внимание. Однако их влияние учитыва­ется при выборе окончательного календарного плана программы. На рис. показана типичная линейная зависимость стоимости операции от ее продолжительности, используемая для большинства программ.. Точка (D_п, С_п), где D_п — продолжительность операции, а C_п — ее стоимость, соответствует так называемому нормальному режиму выполнения операции. Продолжительность операции D_п можно уменьшить («сжать»), увеличив интенсивность использования ресурсов (т. е. количество ресурсов, затрачиваемых на выполнение операции в единицу времени), а следовательно, увеличив и стоимость операции. Однако существует предел, называемый минимальной продолжительностью операции. За точкой, соответствующей этому пределу (точкой максимально интенсивного режима), дальнейшее увеличение интенсивности использования ресурсов ведет лишь к увеличению затрат без сокращения продолжительности операции. Этот предел обозначен на рис. 12.10 точкой о координатами (D_c,, С_с).

Линейная зависимость «затраты — продолжительность» принимается прежде всего из соображений удобства, так как ее можно определить для любой операции всего по двум точкам нормального и максимально интенсивного режимов, т. е. по точкам (D_п,, С_п) и (D_c, С_с). Использование нелинейной зависимости существенно ус­ложняет вычисления. Однако иногда нелинейную зависимость можно аппроксимировать кусочно-линейной (рис. 12.11). При таких усло­виях операция разбивается на части, каждая из которых соответ­ствует одному линейному отрезку. Отметим, что наклоны этих отрезков при переходе от точки нормального режима к точке максимально интенсивного режима возрастают. Если это условие не выполняется, то аппроксимация не имеет смысла.

Определив зависимость «затраты — продолжительность», для всех операций программы принимают нормальную продолжительность. Далее производится полный расчет сети и фиксируется сумма прямых затрат на программу при этой продолжительности операций. На следующем шаге рассматриваются возможности сокращения продолжительности программы. Поскольку этого можно достичь за счет уменьшения продолжительности какой-либо критической операции, только такие операции и подвергаются анализу. Чтобы добиться сокращения продолжительности выполнения программы при минимально возможных затратах, необходимо в максимально допустимой степени сжать ту критическую операцию, у которой наклон кривой «затраты — продолжительность» наименьший.

Отрезок, на который можно «сжать» продолжительность операции, ограничен точкой максимально интенсивного режима. Однако, чтобы точно определить, насколько следует сжимать продолжительность выбранной таким образом критической операции, нужно учесть и другие ограничения, которые подробно рассматриваются в приведенном ниже примере 12.4.2.

В результате «сжатия» критической операции получают новый календарный план, возможно, с новым критическим путем. Стоимость программы при новом календарном плане должна быть обязательно выше стоимости при непосредственно предшествующем календарном плане. Далее этот новый план вновь подвергается сжатию за счет следующей критической операции с минимальным наклоном кривой «затраты — продолжительность», при условии что продолжительность этой операции не достигла минимального значения. Описанная процедура повторяется, пока все критические операции не будут выведены в режим максимальной интенсивности, т. е. не окажутся сжатыми до минимума *^}. В результате расчетов получаются ются кривые «затраты — продолжительность» для всех допустимых календарных планов программ и оцениваются затраты, соответст­вующие каждому из этих планов. Типичная кривая такого рода показана на рис. 12.12 нижней сплошной линией. Как уже отмечалось ранее, эта кривая определяет только прямые затраты.

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

В соответствии с кривой «затраты — про­должительность» операцию можно сжать на две единицы времени, т. е. до предела, определяемого точкой максимально интенсивного режима, которая в дальнейшем называется пределом интенсивности. Однако уменьшение продолжительности критической операции до этого предела не обязательно приводит к сокращению продолжительности всей программы на ту же величину. Это объясняется тем, что при сжатии критической операции может возникнуть новый критический путь. В таком случае необходимо перейти к рассмотрению операций нового критического пути.

Один из способов оценки появления нового критического пути до момента достижения предела интенсивности заключается в анализе свободных резервов времени некритических операций. По определению свободный резерв времени некоторой операции не зависит от сроков начала других некритических операций. Таким образом, если при сжатии какой-либо критической операции по­ложительный свободный резерв времени некоторой некритической операции становится равным нулю, то следует прекратить сжатие этой критической операции и проверить, не стала ли некритическая операция с нулевым свободным резервом времени критической. Следовательно, помимо предела интенсивности необходимо учитывать и предел свободного резерва времени.

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

Дата добавления: 2015-04-29