Сетевое планирование

 

Рис. 1.5. 

Рис. 1.6. 

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

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

Рис. 1.7. 

     Если  эти условия не выполнены, то необходимо добавить еще одно исходное событие  и соединить его стрелками  с имеющимися несколькими начальными событиями или добавить еще одно конечное событие, к которому ведут  стрелки от нескольких имеющихся  конечных событий.

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

Анализ  сетевой модели

   Параметры сетевой модели. Параметрами сетевой  модели являются:

• наиболее ранее возможное время наступления j-го события, обозначаемое символом ;
• самое позднее допустимое время наступления i-го события, обозначаемое символом ;
• резерв времени данного события, обозначаемый символом ;
• полный резерв времени работы (I;j) , обозначаемый символом ;
• свободный резерв времени работы (I;j), обозначаемый символом .

   Наиболее  раннее возможное время наступления  j-го события определяется следующий рекуррентной формулой: 

    (1.1)

   где — продолжительность (I;j)-й работы; — множество событий, предшествующих j-му событию.

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

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

     (1.2)  

   где  — множество событий, следующих за i-м событием.

   Для определения    по формуле (1.2) надо двигаться от конечного события n к исходному событию 0, при этом .

   Резервом  времени данного события называется разность между  и , которая вычисляется по формуле 

      (1.3)

     Полный  резерв времени работы (I; j)  вычисляется по формуле 

      (1.4)

     Свободный резерв времени работы (I; j)  вычисляется по формуле 

      (1.5) 
 
 

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

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

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

     Задержка  в выполнении работы на величину приводит к задержке в наступлении завершающего события на величину .

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

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

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

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

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

Формирование  временных оценок работ

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

     Для определения временных и других характеристик, необходимых для  оценки длительности работ или расхода  ресурсов, могут использоваться статистические данные, полученные опытным путем. Такие  оценки однозначно определяются из нормативов. Если такие нормативы отсутствуют, то разработчиками сетевого графика  даются три оценки времени:

• оптимистическая (t min);
• пессимистическая (t max);
• наиболее вероятная (t нв).

   Оптимистическая оценка — продолжительность работы в наиболее благоприятных условиях.

   Пессимистическая  оценка — продолжительность работы при самом неблагоприятном стечении обстоятельств.

   Наиболее  вероятная оценка — продолжительность  работы при условии, что не возникнет  никаких неожиданных трудностей.

   На  основании этих оценок вычисляются  оценки и их дисперсии по следующим эмпирическим формулам: 

(1.6)

(1.7)

     В этом случае все расчеты проводятся так, как было рассмотрено выше. Затем  рассчитываются вероятности того, что  полученные параметры сетевой модели (ранние сроки, поздние сроки, резервы  и т.д.) действительно будут находиться в тех или иных числовых границах. При этом вводится допущение, что  продолжительности двух любых работ  являются независимыми величинами, а  величина определенная формулой (1.6), принимается равной математическому ожиданию продолжительности данной работы ( I; j). Тогда математическое ожидание любого параметра сетевой модели, являющегося суммой величин вида , есть сумма математических ожиданий слагаемых, то есть . Точнее, это оценка снизу, так как все параметры сетевой модели носят, так сказать, экстремальный характер. Соответственно, дисперсия параметра будет . Если считать, что время выполнения работ подчиняется нормальному закону, вероятность совершения j-го события в расчетный срок можно определить по следующей формуле: 

      (1.8)

где  —Ф функция Лапласа;  — директивный срок;  — время раннего свершения j-го события;  — сумма дисперсий работ, которые использовались при вычислении раннего срока наступления j-го события. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Сетевой график – это ориентированный  граф, в котором вершинами обозначены работы проекта, а дугами – временные  взаимосвязи работ.

     Сетевой график должен удовлетворять следующим свойствам:

1. Каждой работе соответствует одна и только одна вершина. Ни одна работа не может быть представлена на сетевом графике дважды. Однако любую работу можно разбить на несколько отдельных работ, каждой из которых будет соответствовать отдельная вершина графика.
2. Ни одна работа не может быть начата до того, как закончатся все непосредственно предшествующие ей работы. То есть если в некоторую вершину входят дуги, то работа может начаться только после окончания всех работ, из которых выходят эти дуги.
3. Ни одна работа, которая непосредственно следует за некоторой работой, не может начаться до момента ее окончания. Другими словами, если из работы выходит несколько дуг, то ни одна из работ, в которые входят эти дуги, не может начаться до окончания этой работы.
4. Начало и конец проекта обозначены работами с нулевой продолжительностью. Такие работы называются вехами и обозначают начало или конец наиболее важных этапов проекта.

Пример. В качестве примера рассмотрим проект "Разработка программного комплекса". Предположим, что проект состоит из работ, характеристики которых приведены в табл.2.1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

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

     Рис. 2.1.  Сетевой график проекта 

     Сетевой график позволяет по заданным значениям  длительностей работ найти критические  работы проекта и его критический  путь.

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