Определение 2. Наиболее ранним возможным сроком наступления j-го события является наиболее ранний возможный срок завершения всех работ, подходящих к j-му узлу.
Пусть ljр— наиболее ранний возможный срок наступления j-го события, j=0,1, 2, ..., n, где n+1— число событий (узлов) в сети. Величина tij —продолжительность работы, соединяющей два события (узлы) — i-е и j-е.
Поскольку j-е событие не может произойти, пока не будут завершены все работы, ведущие к j-му узлу, и поскольку работа не может начаться, пока не произойдет предшествующее ей событие, наиболее ранний возможный срок наступления каждого события вычисляется как продолжительность самого длинного пути от начального события до данного. Так как в сети установлена правильная нумерация, то ljр можно
 |
вычислять последовательно, начиная с l0р =0 , по формуле
Применяя формулу (1), предлагается запоминать для каждого j значение ljр и номер i(j), на котором достигается максимальное значение. Это позволит по окончании вычислений найти не только величину наиболее длинного пути, но и сам этот путь.
Определение 3.Наиболее длинный путь из начального события в конечное называется критическим путем.
Длину критического пути обозначим Ткр. Тогда Ткр=lnр. Узлы, через которые проходит критический путь можно легко получить, исходя из следующего.
Алгоритм 1:
1. конечный узел критического пути всегда имеет номер n,
2. если узел с номером j принадлежит критическому пути, то номер предшествующего ему узла равен i(j) (см. формулу (1)),
3. начальный узел всегда имеет номер 0.
Длина критического пути определяет минимальное время, необходимое для завершения проекта.
Пример 2.
Для всех узлов (событий) сети из примера 1 определить наиболее ранний возможный срок наступления события и критический путь.
Решение.
Последовательно применяя формулу (1) для j=0,1,2,3,…,8, получаем
l0р =0, предшествующего события здесь нет.
l1р =max{l0р+t0,1}=max{0+4}=4, i(1)=0.
l2р =max{l0р+t0,2}=max{0+6}=6, i(2)=0.
l3р =max{l2р+t2,3}=max{6+7}=13, i(3)=2.
l4р =max{l0р+t0,4, l3р+t3,4}=max{0+9,13+0}=13, i(4)=3.
l5р =max{l1р+t1,5, l3р+t3,5}=max{4+8,13+0}=13, i(5)=3.
l6р =max{l4р+t4,6, l5р+t5,6}=max{13+10,13+6}=23, i(6)=4.
l7р =max{l6р+t6,7}=max{23+4}=27, i(7)=6.
l8р =max{l7р+t7,8}=max{27+9}=36, i(8)=7.
Итак, для каждого события найден наиболее ранний возможный срок его наступления, определяющий момент времени, начиная с которого это событие становится возможным. Длина критического пути равна Ткр= l8р=36. Критический путь проходит через следующие узлы сети:
8, i(8)=7, i(7)=6, i(6)=4, i(4)=3, i(3)=2, i(2)=0.
Следовательно, в данном примере критический путь имеет вид
(0,2)-(2,3)-(3,4)-(4,6)-(6,7)-(7,8), ·
11.3. Наиболее поздний допустимый срок наступления события
Определение 4. Наиболее поздним допустимым сроком наступления i-го события является наиболее поздний срок завершения всех работ, идущих к i-му узлу, не влияющий на время завершения всего проекта за Ткр.
Пусть liп ¾ наиболее поздний допустимый срок наступления i-го события. Чтобы гарантировать, что продолжительность критического пути не будет превышена, необходимо положить lnп =Ткр.
 |
Начиная с n-го события, двигаемся в обратном направлении к событию 0, вычисляя очередное liп при i<n по формуле
и номер j*(i), при котором достигается минимум.
Вычисления ведутся до тех пор, пока не будет определен наиболее поздний срок наступления начального события (событие 0).
Пример 3.
Для всех узлов (событий) сети из примера 1 определить наиболее поздний допустимый срок наступления события.
Полагаем l8п =Ткр=36. Затем последовательно применяя формулу (2) для j=8,…,1, получаем
l7п =min{l8п - t7,8}=min{36-9}=27, j*(i)=8,
l6п =min{l7п-t6,7}=min{27-4}=23, j*(i)=7,
l5п =min{l6п-t5,6}=min{23-6}=17, j*(i)=6,
l4п =min{l6п-t4,6}=min{23-10}=13, j*(i)=6,
l3п =min{l4п-t3,4, l5п-t3,5}=min{13-0,17-0}=13, j*(i)=4,
l2п =min{l3п-t2,3}=min{13-7}=6, j*(i)=3,
l1п =min{l5п-t1,5}=min{17-8}=9, j*(i)=5,
l0п =min{l1п-t0,1,l4п-t0,4, l2п-t0,2}=min{9-4,13-9,6-6}=0, j*(i)=2.
Отметим, что при правильно проведенных вычислениях всегда должно получиться l0п =0.
11.4. Резерв времени и критический путь
При сетевом планировании методом критического пути можно выделить три показателя резерва времени: полный, свободный и независимый резервы времени.
Определение 5. Полный резерв времени rijп для работы (i, j) есть максимальная продолжительность задержки работы, не вызывающая задержки в осуществлении всего проекта. Он вычисляется по формуле
rijп =ljп - liр-tij
Определение 6. Свободный резерв времени rijс для работы (i, j) является показателем максимальной задержки работы (i, j), не влияющей на начало последующих работ. Он вычисляется по формуле
rijс =ljр - liр-tij.
Определение 7. Независимый резерв времени rijн для работы (i, j) представляет собой максимальную продолжительность задержки работы (i, j) без задержки последующих работ, если все предшествующие работы заканчиваются как можно позже. Он вычисляется по формуле
rijн=max{0, ljр - liп-tij }.
Очевидно, верны следующие утверждения.
Утверждение 1.Полный резерв работ, лежащих на критическом пути равен нулю.
Утверждение 2. Увеличение продолжительности некритических работ за счет использования всего ее полного резерва обязательно влечет появление нового критического пути, в состав которого войдет эта работа.
Расчет всех параметров сетевого графика удобно свести в следующие две таблицы.
Таблица 2.
Номер события | Наиболее ранний возмож-ный срок | Номер предшествующего события, принадлежащего наиболее длинному пути из события 0 в событие j. | Наиболее поздний допусти-мый срок | Номер события, следующего за событием j и принадлежащего кратчайшему пути от j до конечного. |
0 | l0р | ¾ | l0п | n |
……….. | ………… | ………………… | …………. | ………………. |
j | ljр | i(j) | ljп | j*(j) |
……….. | ………… | ………………… | ………… | ……………… |
n | lnр | i(n) | lnп | ¾ |
Таблица 3.
Работа | Полный резерв времени | Свободный резерв времени | Независимый резерв времени |
(i, j) | rij п | rijс | rijн |
…………. | ……………….. | ………………… | …………………… |
Величины резервов времени связаны соотношением
rijп ³rijс ³rijн.
Если продолжительность работы (k, l), не лежащей на критическом пути, увеличить на величину ее полного резерва времени, то в сети появится новый критический путь. Этот путь можно найти по данным таблицы 2, исходя из следующего.
Алгоритм 2:
1. узел с номером k принадлежит новому критическому пути,
2. если узел с номером j (j£k) принадлежит критическому пути, то номер предшествующего ему узла равен i(j) (см. формулу (1)),
3. начальный узел всегда имеет номер 0.
4. узел с номером l принадлежит новому критическому пути,
5. если узел с номером j (j³l) принадлежит критическому пути, то номер следующего за ним узла равен i*(j) (см. формулу (2)),
6. конечный узел всегда имеет номер n.
Пример 4.
Для всех дуг (работ) сети из примера 1 определите полный резерв времени, свободный резерв времени и независимый резерв времени.
Решение.
Необходимо использовать результаты, полученные в примерах 2,3 и сведенные в таблицу 4.
Таблица 4.
Номер события j | Наиболее ранний возмож-ный срок ljр | Номер предшеству-ющего собы-тия, принадле-жащего на-иболее длин-ному пути из события 0 в событие j. i(j) | Наиболее поздний допусти-мый срок ljп | Номер события, следующего за событием j и принадлежа-щего кратчай-шему пути от j до конечного. j*(j) |
0 | 0 | ¾ | 0 | 2 |
1 | 4 | 0 | 9 | 5 |
2 | 6 | 0 | 6 | 3 |
3 | 13 | 2 | 13 | 4 |
4 | 13 | 3 | 13 | 6 |
5 | 13 | 3 | 17 | 6 |
6 | 23 | 4 | 23 | 7 |
7 | 27 | 6 | 27 | 8 |
8 | 36 | 7 | 36 | ¾ |
В таблицу 5 занесем значения резервов времени для всех работ. Анализ таблицы 5 подтверждает результат примера 2, что в данной сети критическим является путь
(0,2)-(2,3)-(3,4)-(4,6)-(6,7)-(7,8),
так как именно для этих работ полный резерв времени равен 0.
Таблица 5.
Работа | Продолжи-тельность работы | Полный резерв времени rijп | Свободный резерв времени rijс | Независимый резерв времени rijн |
(0,1) | 4 | 5 | 0 | 0 |
(0,2) | 6 | 0 | 0 | 0 |
(0,4) | 9 | 4 | 4 | 4 |
(1,5) | 8 | 3 | 1 | 0 |
(2,3) | 7 | 0 | 0 | 0 |
(3,4) | 0 | 0 | 0 | 0 |
(3,5) | 0 | 4 | 0 | 0 |
(4,6) | 10 | 0 | 0 | 0 |
(5,6) | 6 | 4 | 4 | 0 |
(6,7) | 4 | 0 | 0 | 0 |
(7,8) | 9 | 0 | 0 | 0 |
Критический путь представляет собой взаимосвязанную последовательность работ и событий — от начального до завершающего. Задержка наступления любого события, принадлежащего критическому пути, приведет к задержке срока завершения всего проекта. Напротив, работы и события, не находящиеся на критическом пути, могут быть задержаны на ненулевой промежуток времени без влияния на срок завершения всего проекта. Например, задержка события 6 на 4 единицы времени относительно наиболее раннего возможного срока его наступления не повлияет на срок завершения всего проекта и, более того, не повлияет на начало работы (5,6). Увеличение продолжительности выполнения работы (0,4) на 4 единицы времени приводит к появлению в сети еще одного критического пути
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
