Реферат: Сетевые методы в планировании

Сетевое планирование и управление программами включает три основных этапа: структурное планирование, календарное планирование и оперативное управление.

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

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

Заключительным этапом является оперативное управление процессом реализации программы. Этот этап включает использование ñåòåâîé ìîäåëè è êàëåíäàðíîãî ãðàôèêà äëÿ ñîñòàâëåíèÿ ïåðèîäèческих отчетов о ходе выполнения программы. Сетевая модель под­вергается анализу и в случае необходимости корректируется. В этом случае разрабатывается новый календарный план выполне­ния остальной части программы.

Сетевая модель

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

1

i j

3 4

2

(а) (б)

Рис. 3.1

На рис. 3.1 а приведен типичный пример графического отображения операции i, j с начальным событием i и конечным событием j. На рис. 3.1 б показан другой пример, из которого видно, что для возможности начала операции (3, 4) требуется завершение операций (1,3) и (2, 3). Протекание операций во времени задается порядком нумерации событий, причем номер начального события всегда меньше номера конечного. Такой способ нумерации особенно удобен выполнении вычислений на ЭВМ.

Правила построения сетевой модели

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

Правило 2. Ни одна пара операций не должна определяться оди­наковыми начальным и конечным событиями. Возможность неод­нозначного определения операций через события появляется в слу­чае, когда две или большее число операций допустимо выполнять одновременно. Пример этого случая приведен на рис. 3.2 а, где операции А' и В имеют одинаковые начальное и конечное события. Чтобы исключить такую «ошибку» между А и

(a) (б)

рис 3.2

конечным (начальным) событием или между В и конечным (начальным) событием, вводится фиктивная операция D . Рис. 3.2 б иллюстрирует различные ва­рианты введения такой фиктивной операции D. В результате опе­рации А и В определяются теперь однозначно парой событий, отлича­ющихся либо номером начального, либо номером конечного со­бытия. Следует обратить внимание на то, что фиктивные операции не требуют затрат ни времени, ни ресурсов.

Фиктивные операции позволяют также правильно отображать логические связи, которые без их помощи нельзя задать на сети. Предположим, что в некоторой программе операции А и В должны непосредственно предшествовать С, а операции Е непосредственно предшествует только В. На рис 12.3 а эти условия отраженыневерно, так как, хотя упорядочения между А . В и С показаны пра­вильно, из этого фрагмента следует, что операции Е должны непо­средственно предшествовать обе операции А и В. Правильное пред­ставление указанных условий дает фрагмент, изображенный на рис 12.3 б в котором используется

(а) (б)

Рис 3.3

фиктивная операция D. Поскольку на операцию D не затрачиваются ни время, ни ресурсы заданные отношения упорядочения выполняются.

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

а) Какие операции необходимо завершить непосредственно перед началом рассматриваемой операции?

б) Какие операции должны непосредственно следовать после завершения данной операции?

в) Какие операции могут выполняться одновременно с рассматриваемой?

Это правило не требует пояснений. Оно позволяет проверять (и перепроверять) отношения упорядочения в процессе построения сети.

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

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

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