Зад лин прогр и мет их решения 16 12 08
.pdf
80
Рекомендуется события изображать в порядке предшествования, поэтому начало проекта, обозначенное {—} лучше расположить слева, конец проекта – справа, предшествующее –— левее от последующего (если это известно).
BD,F,H
— |
C,E,I |
|
D |
|
A,G |
D,H
Шаг 4. Изобразим каждую работу проекта в виде дуги, выходящей из той старой вершины, которая является множеством непосредственно предшествующих работ для данной работы. Конец изображаемой дуги обозначим как новую вершину. Название новой вершины удобно дать в —соответствии с названием изображаемой работы, например, прописной буквой t, если работа называлась T.
|
I |
|
i |
A |
|
|
|
|
|
|
|
|
B |
F |
f |
D,F,H |
a |
|
b |
|
|||
B |
|
|
|
||
|
|
|
|
||
— |
D d |
|
G |
|
C,E,I |
D |
|
g |
|||
|
|
|
E |
||
|
|
|
|
||
|
|
|
|
|
|
|
H |
|
|
A,G |
e |
|
|
|
|
|
C
hD,H
c
Шаг 5. Свяжем полученные части с помощью фиктивных дуг. Начала фиктивных дуг находятся в новых вершинах – концах работ, а концы фиктивных дуг находятся в старых вершинах, а именно в тех, которые содержат эти работы в своём обозначении. Например, H содер-
жится в обозначениях вершин D,H и D,F,H , поэтому рисуются две фиктивные дуги из конца
работы H, т.е. из h . Первая начинается в h и заканчивается в D,H , другая начинается в
hи заканчивается в D,F,H .
|
|
I |
i |
|
|
|
|
B |
F |
|
|
A |
|
B |
b |
|
f |
D,F,H |
a |
|
|
|
|
||||
— |
D d |
|
G |
g |
|
C,E,I |
|
|
D |
|
|
E |
|
|
H |
|
|
|
A,G |
e |
|
|
|
|
|
|
|
|
|
|
|
C |
|
|
|
h |
|
D,H |
c |
|
|
Шаг 6. Правильная нумерация вершин полученной сети.
|
|
|
|
81 |
|
|
|
I |
4 |
|
|
|
|
|
|
|
|
|
3 |
F |
|
A |
|
|
|
|
|
||
|
2 |
|
5 |
12 |
|
B |
|
13 |
|
||
|
|
|
|||
1 |
D |
|
G |
|
16 |
6 |
7 |
|
|
||
|
|
8 |
|
E |
|
|
H |
|
|
14 |
15 |
|
|
|
|
C
9 
10 
11
Рис. 4.
Этап 2.
При сокращении фиктивных дуг используются следующие правила.
Правило 1. Если фиктивная дуга ( i, j ) соединяет вершину I с вершиной J, а из I в J уже есть другой путь (из действительных или фиктивных дуг – неважно), то фиктивную дугу следует удалить, стереть. Вершины I, J при этом не изменяются. ♦
Это правило приоритетное, т.е. оно применяется, если возможно, прежде других правил. Правило 2. Пусть ( i, j ) – фиктивная дуга, которая единственная среди дуг сети начинается в i (единственная выходящая из i) или же единственная среди дуг сети, заканчивается в j. Тогда эту фиктивную дугу можно сократить, объединив вершины i, j в одну (говорят, сжав фиктивную дугу), если при этом не образуются параллельные дуги. Для новой объединённой вершины обычно оставляют обозначение i или j. ♦
Правило 3. Фиктивную дугу ( i, j ) можно сжать, объединив её начало i и конец j в одну вершину, если при этом не образуются лишние связи предшествования, т.е. связи, которых нет в проекте, и не образуются параллельные дуги. ♦
Правило 2 выделено из правила 3, так как образование параллельных дуг легче проверяется, чем образование лишних связей, а при условиях, в которых правило 2 действует, лишние связи не могут возникнуть.
Шаг 7. Применим правила 1–3 для последовательного сокращения фиктивных дуг, пока в сетевом графике не останутся действительные работы и те фиктивные дуги, без которых нельзя обойтись (см. примеры 3, 4).
На рис.4 нет фиктивных дуг для сокращения по правилу 1. Сократим одну дугу, например, (4, 16) по правилу 2. К ней это правило применимо, так как из вершины 4 других выходящих нет, а сокращение (сжатие) дуги (4, 16) не приводит к появлению параллельных дуг – в данном случае двух дуг (3, 16). Для объединённой вершины сохраним обозначение 16. Получим график на рис.5.
|
|
|
|
I |
|
|
3 |
F |
|
A |
|
|
|
|
|
||
|
2 |
|
5 |
12 |
|
B |
|
13 |
|
||
|
|
|
|||
1 |
D |
|
G |
|
16 |
6 |
7 |
|
E |
||
|
|
8 |
|
||
|
H |
|
|
14 |
15 |
|
|
|
|
||
|
|
|
C |
|
|
|
9 |
|
10 |
11 |
|
|
|
|
|
Рис. 5. График после сокращения (4, 16)
82
Так как дуги, которую можно сократить по правилу 1, снова нет, сокращаем следующую по правилу 2 и так далее.
После сокращения (2, 3), (6, 7), (5, 12), (8, 14), (13, 14), (15, 16), (11, 16) по правилу 2 получим сеть
|
|
3 |
|
|
I |
|
|
F |
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
|
D |
|
12 |
A |
E 16 |
1 |
6 |
|
|
||
|
|
|
|
||
|
|
|
G |
14 |
|
|
H |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C |
|
|
9 |
|
10 |
|
|
|
|
|
|
|
Рис. 6.
Оставшиеся фиктивные дуги можно попытаться сократить по правилу 3.
Дуги (6, 12) и (9, 12) сократить нельзя, так как работа C приобретает тогда зависимость от работы F (через фиктивные дуги (6, 10) или (9, 10)), которой нет в исходном проекте. Фиктивную дугу (6, 10) так же нельзя сократить, так как иначе работа G получает зависимость от H, чего нет в исходном проекте (на рис.6).
Фиктивную дугу (9, 10) можно сократить, так как при этом не возникает ни параллельных дуг, ни лишних связей предшествования. После сокращения (9, 10) получим сеть
|
3 |
|
I |
|
F |
|
|
|
B |
|
|
|
|
|
|
|
D |
12 |
A |
1 |
|
E 16 |
|
6 |
|
|
|
|
|
G |
14 |
|
|
|
|
|
H |
|
C |
|
|
|
|
|
|
10 |
|
Рис. 7.
Теперь по правилу 1 нужно удалить (6, 12), так как из 6 в 12 есть другой путь: (6, 10, 12). По-
|
3 |
|
I |
|
F |
|
|
|
B |
|
|
|
|
|
|
|
|
12 |
A |
1 |
D |
|
E 16 |
6 |
|
|
|
|
|
G |
14 |
|
|
|
|
|
H |
|
C |
|
|
|
|
|
|
10 |
|
Рис. 8.
83
лучим сеть
Дугу (10, 12) нельзя сократить, так как иначе появится несуществующая зависимость C от F.
Дугу (6,10) нельзя сократить, так как иначе появится лишняя связь G от H, а также образуются параллельные работы D, H (достаточно лишь одного из этих двух нарушений).
Шаг 8. Сделаем правильную нумерацию в полученной сети. Искомый сетевой график построен.
|
2 |
|
|
I |
|
|
B |
F |
|
|
|
|
|
|
|
|
|
|
D |
5 |
A |
E |
7 |
1 |
|
||||
3 |
|
|
|
|
|
|
|
G |
|
6 |
|
|
|
|
|
|
|
|
H |
4 |
C |
|
|
|
|
|
|
|
Рис. 9. Окончательный сетевой график.
Для хранения полученного графика, т.е. логической структуры проекта достаточно запомнить набор записей вида: {(1,2), B}, {(1,3), D}, {(1,4), H}, {(2,5), F}, {(2,7), I}, {(3,4), фикт.}, {(3,6), G}, {(4,5), фикт.}, {(4,7), C}, {(5,6), A}, {(6,7), E}.
6.3. Календарное планирование
В календарном планировании проект рассматривается как процесс, протекающий во времени. Считаются известными времена ti j выполнения отдельных работ, нормативные, или оце-
ночные, или усреднённые. Конкретный план выполнения работ с указанием времени начала и времени окончания каждой работы называется календарным планом. Он может быть задан в табличной форме, а также с помощью линейных временных диаграмм.
В календарном планировании другие ресурсы, кроме временных, не учитываются. Считается, что независимые работы могут выполняться параллельно во времени и разными исполнителями.
Началом отсчёта времени является момент екта.
Критическое время, критические работы, критический путь
Определение. Наименьшее время, за которое можно выполнить проект, т.е. выполнить все работы проекта, называется критическим временем Tкрит . ♦
Критическое время является внутренней главнейшей числовой характеристикой проекта.
Определение. Наибольшее время, за которое необходимо выполнить проект, называется
проектным временем Tпр . ♦
Проектное время является директивной, т.е. заданной извне ("руководством") характеристикой проекта.
Очевидно, должно выполнятся соотношение
Tкрит ≤ Tпр ,
84
так как иначе проект не может быть выполнен.
Если Tкрит = Tпр , то некоторые работы проекта необходимо выполнять без задержек, начинать
и заканчивать в строго определённые моменты времени. Такие работы называются критическими.
Находить критическое время, критические работы проще всего по сетевому графику проекта. Продолжим рассмотрение примера 1. Пусть времена работ заданы в некоторых условных единицах (часы, дни, недели и т.д.). Проставим эти времена на соответствующих дугах сетевого графика. В дальнейшем исходные названия работ не будем писать на дугах. Пусть проектное время известно и равно Tпр = 25 у.е.
Таблица 4
Работа |
Обозначение на сете- |
Время рабо- |
вом графике |
ты |
|
|
в у.е. |
|
|
|
|
|
|
|
A |
( 5, 6 ) |
2 |
B |
( 1, 2 ) |
13 |
C |
( 4, 7 ) |
10 |
D |
( 1, 3 ) |
12 |
E |
( 6, 7 ) |
3 |
F |
( 2, 5 ) |
1 |
G |
( 3, 6 ) |
5 |
H |
( 1, 4 ) |
6 |
I |
( 2, 7 ) |
5 |
фикт. |
( 3, 4 ) |
0 |
фикт. |
( 4, 5 ) |
0 |
|
|
|
Время фиктивных работ всегда равно нулю.
|
|
2 |
|
|
5 |
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
|
|
1 |
12 |
|
5 |
2 |
3 |
7 |
3 |
|
5 |
|
|
||
|
|
0 |
|
|
6 |
|
|
|
0 |
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
4 |
|
|
|
Рис. 10. Сетевой график с временами работ.
На сетевом графике рассмотрим все пути из начала проекта в конец проекта . Дуги любого такого пути соответствуют цепочкам последовательно предшествующих друг другу работ.
1) ( 1, 2 ) ( 2, 5 ) сумма времён работ = 13 + 1 + 2 + 3 =
( 5, 6 ) ( 6, 7 ) |
19 |
|
85
2)( 1, 2 ) ( 2, 7 ) сумма времён работ = 13 + 5 = 18
3)( 1, 3 ) ( 3, 6 ) ( сумма времён работ = 12 + 5 + 3 = 20 6, 7)
4)( 1, 3 ) ( 3, 4 ) ( сумма времён работ = 12 + 0 + 0 + 2 +
4, 5) |
3 = 17 |
(5, 6 ) ( 6, 7 )
5)( 1, 3 ) ( 3, 4 ) ( сумма времён работ = 12 + 0 + 10 =
4, 7) |
22 |
6) ( 1, 4 ) ( 4, 5 ) |
сумма времён работ = 6 + 0 + 2 + 3 = |
( 5, 6 ) ( 6, 7 ) |
11 |
|
|
7) ( 1, 4 ) ( 4, 7 ) |
сумма времён работ = 6 + 10 = 16 |
Выполнить проект означает выполнить все работы проекта, в том числе все работы во всех цепочках. Следовательно, время выполнения проекта не может быть меньше суммы времён работ любой цепочки, в том числе самой длинной цепочки (с самой большой суммой). Отсюда получаем важное свойство сетевого графика.
Критическое время Tкрит равно длине са-
мого длинного пути из начала проекта в конец проекта.
В примере Tкрит = max{19, 18, 20, 17, 22, 11,16 } = 22 у.е.
Определение. Самый длинный путь из начала проекта в конец проекта в сетевом графике называется критическим путём. ♦
Таким образом, критическое время является длиной критического пути. Критических путей может быть несколько.
Определение. Работы, лежащие на критическом пути, называются критическими работами.
В больших проектах число путей в сетевом графике огромно, поэтому приведённый выше способ перебора – способ перечисления всех путей из начала проекта в конец проекта и выбор самого длинного из них является невозможным даже на современных компьютерах.
Найдём критический путь методом потенциалов [17,18,21] для безконтурных сетей.
На 1-м этапе находим потенциалы — числа для каждой вершины, начиная с первой и далее по возрастанию номеров вершин (для этого и нужна правильная их нумерация) по формуле
y1 |
= 0 ; y j = max{yi + ti j } , j = 2,3,... , номер конца проекта, |
|
i |
где ti j – время работы |
( i, j ), а максимум берётся по всем дугам ( i, j ), входящим в вершину |
J . |
|
На втором этапе, начиная с конца проекта, находятся и выделяются дуги ( i, j ), на которых потенциал конца дуги y j в точности равен сумме потенциала начала дуги yi и времени ра-
боты ti j . Выделенные таким образом дуги и образуют самый длинный, т.е. критический путь (пути). Потенциалы вершин yi , найденные указанным способом, являются длинами самых
86
длинных путей из начала проекта в вершину i. В частности, потенциал y конца проекта будет равен критическому времени.
Обратимся к рис. 10. На 1-м этапе получаем потенциалы
y1 = 0 ;
y2 = y1 + t12 = 0 +13 = 13 ;
y3 = y1 + t13 = 0 +12 = 12 ;
y4 = max{y1 + t14 ; y3 + t34} = max{0 + 6;12 + 0} = 12 ;
y5 = max{y2 + t25; y4 + t45} = max{13 +1;12 + 0} = 14 ;
y6 |
= max{y3 + t36 ; y5 + t56} = max{12 + 5;14 + 2} = 17 ; |
y7 |
= max{y2 + t27 ; y4 + t47 ; y6 + t67 } = max{18; 22; 20} = 22 = Tкрит . |
На втором этапе, начиная с вершины 7, находим, что y7 = 22 = 12 +10 = y4 + t47 . Дугу (4, 7) выделяем и переходим в вершину 4. Далее, y4 = 12 = 12 + 0 = y3 + t34 . Выделяем (3, 4) и переходим в вершину 3. Далее, y3 = y1 + t13 . Выделяем (1, 3).
Выделенные дуги образуют критический путь (1, 3, 4, 7). Критическими работами являются (1,3) = D , (4,7) = C и фиктивная (3, 4), соответственно критическими событиями – вершины 1, 3, 4, 7.
Найденные потенциалы yi |
– "потенциалы, рассчитанные с начала проекта", на рис. 11 выде- |
||||||||||||||||
лены квадратами. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
5 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
13 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
0 |
|
|
|
12 |
|
1 |
|
14 |
|
|
|
|
22 |
|
||
|
|
|
12 |
|
5 |
2 |
|
|
|
7 |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
1 |
|
|
|
3 |
|
|
|||||||||||
|
|
|
|
|
|||||||||||||
|
3 |
|
|
|
5 |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
0 |
|
|
|
|
6 |
|
|
|
|
|
||
|
|
|
|
6 |
0 |
|
|
17 |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
4 |
|
|
10 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
(1, 3, 4, 5) –крит .путь |
||||
|
|
|
|
|
|
12 |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tкрит = 22 |
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
Рис. 11. Критический путь, критические работы. |
||||||||||||||
Критический путь можно найти с помощью потенциалов, рассчитанных с конца. Для этого, на 1-м этапе находим потенциалы vi , начиная с последней вершины и далее по убыванию номеров вершин по формуле
vN = 0 ; vi = max{v j + ti j }, j = N −1, N − 2,...,1., N-номер конца проекта,
j
максимум берётся по всем дугам ( i, j ), выходящим из вершины i .
На втором этапе, начиная с начала проекта, находятся и выделяются дуги ( i, j ), на которых потенциал конца дуги vi в точности равен сумме потенциала конца дуги v j и времени рабо-
ты ti j . Выделенные таким образом дуги дают тот же критический путь (пути). Потенциалы вершин vi , найденные указанным способом, являются длинами самых длинных путей из
87
вершины i в конец проекта. В частности, потенциал v начала проекта будет равен критическому времени.
На рис. 10 на 1-м этапе получаем потенциалы
v7 = 0 ;
v6 = v7 + t67 = 0 + 3 = 3 ;
v5 = v6 + t56 = 3+ 2 = 5;
v4 = max{v5 + t45 ;v7 + t47 } = max{5+ 0; 0 +10} =10 ; v3 = max{v6 + t36 ;v4 + t34} = max{3+ 5;10 + 0} =10 ; v2 = max{v5 + t25 ;v7 + t27 } = max{5+1; 0 + 5} = 6 ;
v1 = max{v2 + t12 ;v3 + t13;v4 + t14} = max{19; 22;16} = 22 = Tкрит .
На 2-м этапе, начиная с вершины 1, находим, что v1 =10 +12 = v3 + t13 . Дугу (1, 3) выделяем и переходим в вершину 3. Далее, v3 =10 + 0 = v4 + t34 . Выделяем (3, 4) и переходим в вершину 4. Далее, v4 = v7 +t47 . . Выделяем (4, 7). Выделенные дуги образуют критический путь (1, 3, 4, 7). Найденные потенциалы vi – "потенциалы, рассчитанные с конца проекта", на рис. выделены треугольниками.
|
|
|
6 |
|
|
|
|
|
2 |
|
|
5 |
|
|
13 |
|
|
|
|
|
|
|
|
5 |
|
|
|
22 |
|
10 |
1 |
|
0 |
|
|
|
|
||||
|
|
|
|
|||
|
|
5 |
2 |
|
|
|
1 |
12 |
|
3 |
7 |
||
3 |
|
5 |
|
|
||
|
|
0 |
|
|
6 |
|
|
|
0 |
|
3 |
|
|
|
|
|
|
|
6 |
|
|
10 |
|
|
4 |
|
|
|
(1, 3, 4, 5) – крит. путь |
|
|
|
|
|
|
10 |
|
Tкрит = 22 |
|
|
|
Временные параметры событий
Каждое событие i проекта P (вершина i на сетевом графике) имеет набор всех предшествующих этому событию работ и набор всех последующих за этим событием работ. Если рассмотреть эти множества работ как самостоятельные проекты, то как бы получаются предшествующий проект P′(i) и последующий проект P ′′(i) .
88
|
|
|
|
|
1 – начало проекта P. |
|||
|
|
|
|
P |
|
|
|
|
|
|
|
|
|
i – событие проекта Р. |
|||
|
1 |
P '( i ) |
i |
P "( i ) |
N |
|
|
|
|
|
|
|
|
N – конец проекта Р. |
|||
|
|
|
|
|
P' |
– |
предшествующие |
|
|
|
|
Рис. 12. |
|
работы. |
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
P" – последующие рабо- |
|||
|
|
|
|
|
ты |
|
|
|
Для P′ событие I является концом проекта, а для P′′ |
– началом проекта. Другие работы ис- |
|||||||
ходного проекта, не входящие ни в P′ , ни в P′′ , являются независимыми от события I . |
||||||||
′ |
′′ |
имеют свои критические времена |
′ |
′′ |
||||
Проекты P (i) и |
P (i) |
Tкрит (i) |
и Tкрит (i) , равные численно |
|||||
длинам максимальных путей, соответственно из 1 в |
i |
и из i |
в N - конец исходного про- |
|||||
екта. Но эти длины равны потенциалам yi , |
vi , рассчитанным, соответственно, с начала и |
конца проекта. Получаем, что |
|
′ |
′′ |
Tкрит (i) = yi , |
Tкрит (i) = vi . |
Значение Tкрит′ (i) показывает согласно определению критического времени и проекта P′(i) , какое наименьшее время требуется для выполнения P′(i) , т.е. до наступления события I .
Значение |
′′ |
|
Tкрит (i) показывает, какое наименьшее время требуется для выполнения проекта |
||
′′ |
|
I . |
P (i) после наступления события |
||
Определение. Ранним сроком tP (i) |
события i называется наименьшее время после начала |
|
|
проекта, через которое событие I может наступить. ♦ |
|
Этот параметр как раз равен наименьшему времени, необходимому для завершения предшествующих работ, т.е.
tP (i) = Tкрит′ (i) = yi ,
где yi – потенциалы, рассчитанные с начала.
В частности, всегда tP (начало проекта) = 0 , tP (конец проекта) = Tкрит . Ранние сроки не зависят от Tпр , т.е. они являются "внутренними" параметрами проекта.
Определение. Поздним сроком tП (i) события i называется наибольшее время (после начала проекта), через которое событие не должно наступить (иначе сорвётся проектное время). ♦
Проект необходимо завершить к моменту Tпр , а минимальное время для вычисления сле-
дующих за событием работ равно T ′′ (i) , поэтому
крит
t (i) = T − T ′′ (i) = T − v ,
П пр крит пр i
где vi – потенциалы, рассчитанные с конца.
В частности, всегда tП (конец проекта) = Tпр , tП (начало проекта) = Tпр − Tкрит . Очевидно (докажите это!), что tП (i) ≥ tР (i) . Поздние сроки являются "внешними" параметрами, т.к. зависят от
Tпр .
89
Определение. Резервом R(i) события i называется разность его позднего и раннего сроков.
♦
Для событий, лежащих на критическом пути, резерв равен разности Tпр − Tкрит , для остальных событий – больше этой разности.
Приведём все временные параметры событий в примере 1.
Параметры событий |
Таблица 5. |
|||||
|
|
|
|
|
|
|
|
i |
tP (i) |
tП (i) |
|
R(i) |
|
|
|
|
|
|
|
|
|
1 |
0 |
3 |
|
3 |
|
|
2 |
13 |
19 |
|
6 |
|
|
3 |
12 |
15 |
|
3 |
|
|
4 |
12 |
15 |
|
3 |
|
|
5 |
14 |
20 |
|
6 |
|
|
6 |
17 |
22 |
|
5 |
|
|
7 |
22 |
25 |
|
3 |
|
|
|
|
|
|
|
|
Временные параметры работ.
В отличие от событий, работа имеет протяжённость, т.е. связана с двумя событиями – своими началом и концом. Каждое из этих событий имеет два срока, поэтому у работы появляются 4 временных параметра по моменту начала и конца и 4 вида резервов. Полезна следую-
|
|
промежуток, отведённый для работы |
|
||
|
|
|
ti j |
|
|
|
|
резерв |
резерв |
|
|
|
|
|
|
|
время |
tP (i) |
i |
tП (i) |
tP ( j) |
j |
tП (i) |
|
|
||||
ранний срок |
|
поздний срок |
ранний срок |
|
]поздний срок |
начала |
|
начала |
конца |
|
конца |
щая схема
Определение. Ранним началом tРН (i, j) работы ( i, j ) называется наименьшее время после начала проекта, через которое работу можно начать выполнять. ♦
Очевидно, работу можно начать, как только закончатся предшествующие работы, т.е. когда наступит событие i – событие начала. Отсюда
tРН (i, j) = tP (i) = yi .