Планирование на сети

 

Разница между  продолжительностью критического пути и любого другого пути сети t(L) называется полным резервом времени пути и обозначается через P(L):

 

P(L) = tкр – t(L).                                                                                                  (9)

 

Величина P(L) показывает, насколько в сумме может быть увеличена продолжительность всех работ, принадлежащих пути L, чтобы при этом не изменилась продолжительность критического пути tкр.

Резерв времени события  i обозначается через P(i) и определяется как разница между поздним и ранним сроками свершения данного события, то есть:

 

P(i) = tп(i) – tp(i);                                                                                              (10)

легко показать, что

 

P(i) = P[L(i)max],                                                                                              (11)

 

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

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

В системах СПУ используются четыре вида резервов времени работ: полный, свободный, и два вида частных  резервов времени.

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

Для всех работ критического пути Рп(i,j) = 0.

Величина полного резерва  времени может быть определена по следующей формуле:

Рп(i.j) = tп(j) – tp(i) – t(i,j).                                                                               (12)

 

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

Следует различать  два вида частных резервов:

1) частный резерв первого вида P’п(i,j) образуется у работ, непосредственно следующих за событием, в котором пересекаются пути различной продолжительности;

2) частный резерв второго  вида P”п(i,j) образуется у работ, непосредственно предшествующих событию, в котором пересекаются пути различной продолжительности.

 

P’п(i,j) = Рп(i,j) – P(i),                                                                                      (13)

P”п(i,j) = Pп(i,j) – P(j).                                                                                     (14)

 

Свободным резервом времени работы (i,j) называется та часть ее полного резерва, которая сохраняется у нее при условии, что начальное событие данной работы свершится в самый поздний срок tп(i), а конечное – в самый ранний tp(j):

 

Pc(i.j) = tp(j) – tп(i) – t(i,j).                                                                               (15)

 

Величина свободного резерва времени Pc(i,j) показывает, на какой период времени можно увеличить продолжительность данной работы (i,j), чтобы при этом сохранилась возможность свершения ее конечного события в самый поздний срок.

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

 

kн(i.j) = 1 – Рп(i,j) / t”кр(i,j)max.                                                                     (16)

 

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

Величина коэффициента напряженности у разных работ  в сети лежит в пределах 0 ≤ kн(i,j) ≤ 1, причем у работ критического пути kн(i,j) = 1.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Методы сетевого планирования.

2.1 Метод критического пути.

 

Конечным  результатом применения метода критического пути (СРМ) будет построение временного графика выполнения проекта. Для этого проводятся специальные вычисления, в результате чего получаем следующую информацию.

1. общая длительность выполнения проекта;
2. разделение множества процессов, составляющих проект, на критические 
   и некритические.

Процесс является критическим, если он не имеет "зазора" для времени своего начала и завершения. Таким образом, чтобы весь проект завершился без задержек, необходимо, чтобы все критические процессы начинались и заканчивались в строго определенное время. Для некритического процесса возможен некоторый "дрейф" времени его начала, но в определенных границах, когда время его начала не влияет на длительность выполнения всего проекта.

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

□_j — самое раннее возможное время наступления события j,

∆_j самое позднее возможное время наступления события j,

D_ij — длительность процесса (i, j).

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

Проход вперед. Вычисления начинаются в узле 1 и заканчиваются  в последнем узле n.

Начальный шаг. Полагаем П₁ = 0; это указывает на то, что проект начинается в нулевой момент времени.

– Основной шаг j. Для узла j определяем узлы – р, q, ..., v, непосредственно связанные с узлом j процессами (p,j), {q, j), ..., (v, j), для которых уже вычислены самые ранние времена наступления соответствующих событий. Самое раннее время наступления события j вычисляется по формуле

 

□_{j =} max(□_P, +D_pj , □_q+D_qj, ..., U_v+D_vj)                                                                         (17)

 

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

Проход назад. В этом проходе вычисления начинаются в последнем узле n и заканчиваются в узле 1.

– Начальный  шаг. Полагаем ∆_n = □_n это указывает, что самое раннее и самое позднее времена для завершения проекта совпадают.

– Основной шаг j. Для узла j определяем узлы р, q, ..., v, непосредственно связанные с узлом j процессами (j, р), (j, q), ..., (j, v), для которых уже вычислены самые поздние времена наступления соответствующих событий. Самое позднее время наступления события у вычисляется по формуле:

 

∆_j = min(∆_P - D_jp, ∆_q - D_jq, ..., ∆_{v -}-D_jv.)                                                                         (18)

 

Проход назад  завершается при вычислении величины ∆₁ для узла 1. Процесс (i, j) будет критическим, если выполняются три условия.

1. ∆_i = □_i
2. ∆_j = □_j
3. ∆_j.-∆_i = □_j - □_I = D_ij

Если эти  условия не выполняются, то процесс некритический.

Критические процессы должны образовывать непрерывный  путь через всю сеть от начального события до конечного.

 

 

 

 

2.2 Метод оценки и пересмотра планов (ПЕРТ, PERT)

 

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

Этот метод используется, когда для операции сложно задать и определить точную длительность.

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

Метод PERT отличается от СРМ тем, что здесь длительность процессов характеризуется тремя оценками.

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

2) наиболее вероятная оценка времени m, когда предполагается, что выполнение процесса будет происходить нормально.

3) пессимистическая оценка времени b, когда предполагается, что выполнение процесса будет происходить очень медленно.

Любая возможная  оценка времени выполнения процесса будет лежать в интервале (а, b). Поэтому оценка времени m также должна лежать в этом интервале. На основе этих оценок среднее время D выполнения процесса и дисперсия v вычисляются пo формулам

                                                                                                (19) 

 

 

Вычисления  метода СРМ, выполнимы, если заменить значения длительностей D процессов оценками .

Теперь можно  определить вероятность того, что  узел j модели будет достигнут в  заранее запланированное время S_j Пусть e_j— время наискорейшего достижения узла j. Поскольку длительности выполнения процессов, которые ведут от начального узла к узлу j, — случайные величины, то e_j также является случайной величиной. Предположив, что все процессы в сети статистически независимы, можно определить среднее (математическое ожидание) М{е_j} и дисперсию var{e_j} следующим образом. Если существует только один путь от начального узла к узлу j, то среднее является суммой ожидаемых длительностей D выполнения всех процессов, входящих в этот путь, а дисперсия равна сумме дисперсий v тех же процессов. С другой стороны, если к узлу j ведет более одного пути, то до того, как будут вычислены среднее и дисперсия, необходимо найти вероятностное распределение длительности выполнения процессов, которые составляют самый длинный путь. Эта задача достаточно сложная, поскольку она эквивалентна задаче, вычисляющей распределение ""максимума нескольких случайных величин. Для упрощения этой задачи среднее М{e_j} и дисперсия var{e_j} вычисляются только для пути, для которого сумма ожидаемой длительности выполнения процессов максимальна. Если несколько путей имеют равные значения среднего, то выбирается тот, для которого дисперсия больше, поскольку этот путь отражен наименее четко, и поэтому будет вычислена более общая оценка вероятностей.

После того как  будет вычислено среднее М{e_j} и дисперсия var{e_j), вероятность того, что узелj будет достигнут в запланированное время S_j, можно вычислить по формуле

 

      (20)

 

где z — случайная величина, имеющая стандартное нормальное распределение,

 

                                                                                                            (21)    

                                          

Случайная величина z имеет среднее 0 и стандартное отклонение 1 .В данном случае использование нормального распределения оправдано тем, что e_j является суммой независимых случайных переменных. Согласно центральной предельной теореме величина е_j приближенно распределена по нормальному закону.

 

2.3 Метод графической  оценки и анализа (GERT)

 

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

Основу применения метода GERT составляет использование альтернативных сетей, называемых в терминах данного метода GERT-cетями.

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

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

 

 

3.  Численная реализация задачи сетевого планирования

 

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

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