- ()
- -, - - [32].
(- ) (): , . .
- () , : ( ), ( ).
- () , () .
- , [12]:
, , , ;
, ( ) , , , ..;
, - (-) ;
- (-), - ( , .).
- .
, , , , . - .
- :
1) , - (- -) , ;
2) ;
3) - ;
4) - () .
. : , , .
|
|
|
, . ( ).
- (- , .) (. 7.1).
7. 1 -
| / | (, ) | , -, , t | ||
, (. 2, 3).
, , . , . : , , .
.
, . . 3 - 5.
. , . :
) (tmin), .. ( ) ;
) (t..), .. ;
) (tmax), .. ( ) .
(t)
.
(t) (D) (σ)
(t.) , (tmin tmax). (t)
.
, , ,
|
|
|
, . , . , tmax, tmin.
( ) (. 7.2).
7. 2
| tmin | t. | tmax | t | D | ||
| 1. |
(. 4-6).
- , . , , .
7.2.
- - ( ), ().
. , , . . .
, ( ).
i, , . j, , .
i j , , () (i, j), i<j.
(i, j) t(i, j) .
(). , . ( ). , .
, () . , , .
, .. , ( ). (), t(i, j) = 0.
, , .
, .. .
:
1. , .
|
|
|
2. , . . , , , .
3. . (i) , (j), .. i < j. .
4. (), .. , .
5. - , , .
- .
6. , , , , , .
7. . , . (. 7.1).
7.1
8. , . . .
9. , () , () .
, , () t(i, j)=t. .
() . : , , , , , .
, . :
1) , L;
2) , i, () (L(1,i));
3) , i, () n- (L(i,n)).
(to) .
|
|
|
.
(L) . ( ) . ( ) . , , .
, . - , , , . .
, , .
:
1. .
p(1) =0; p(j) = max íp(i) + t(i,j)ý.
.
tpi , , i.
p(n).
2. .
(n) = p(n); (j) = min í(j) + t(i,j)ý.
.
tni , . .
3. i
R(i) = Tn(i) Tp(i).
i ; j ; i < j; i j .
, , .
, , , R(i) = 0.
R(L) t(L) t(L)
R(L) = t (L) t (L).
, , .. . , , .. , .
(. 7.3).
7.3 ,
| , (i) | , (tpi) | , (tni) | , (Ri) |
. , , , p(n).
.
t(i, j) i , .. t(i, j) =tpi.
t(i, j) j t(i, j):
tn(i, j) = tni t(i, j).
t(i, j) i (i, j):
t(i, j)= tni + t(i, j).
t(i, j) j, .. tn(i, j) = tnj.
.
Rn(i, j) j ( ) i ( ) () t(i,j), ..
Rn(i, j) = tnj tni t (i, j) = tno(i, j) tpn(i, j) t (i, j).
|
|
|
Rc(i,j) , , , , .
Rc(i, j) = tpj tpi t (i, j).
.
(. 7.4).
7.4 ,
| (i, j) | t(i, j) | ||||||
| , t (i, j) | , t (i, j) | , tn(i, j) | , tn(i, j) | Rn(i,) | R(i, j) | ||
. , , . , , . , , (. 7.2).
7.2
- . , , . .
, . , ( ) : .
, (. Gantt chart, ) , - . . 1910 .
: - (i,j), - . t(i,j), tp(i) (. 7.4).
, , . .
: , , . , , .
( )
(. 3-6).
7.1. 7.3.
 |  |
 |  |
7.3
:
1) (. 7.5)
Tp (1) = 0, tp(j) = max ítp(i) + t(i;j)ý.
tp(2) = max ítp(1) + t(1,2)ý = 0+4 = 4,
tp(3) = max ítp(2) + t(2,3); tp(1) + t(1,3)ý = 4+3; 0+5 = 7,
tp(4) = max ítp(1) + t(1,4)ý = 0+4 = 4,
tp(5) = max ítp(2) + t(2,5); tp(3) + t(3,5)ý = max í4+7; 7+4ý = 11,
tp(6) = max ítp(5) + t(5,6); tp(4) + t(4,6)ý = max í11+1; 4+2ý = 12,
tp(7) = max ítp(2) + t(2,7); tp(6) + t(6,7)ý = max í4+8; 12+4ý = 16,
2)
T (N) = Tp (N), T (i) = min ít(j) t(i,j)ý.
T (7) = min ít(7)ý = 16,
T (6) = min ít(7) t(6,7)ý = 16-4 = 12,
T (5) = min ít(6) t(5,6)ý = 12-1 = 11,
T (4) = min ít(6) t(4,6)ý = 12-2 = 10,
T (3) = min ít(5) t(3,5)ý = 11-4 = 7,
T (2) = min ít(7) t(2,7);t(5) t(2,5);t(3) t(2,3); ý = min í16-8; 11-7; 16-3ý= 4
T (1) = min ít(2) t(1,2);t(3) t(1,3);t(4) t(1,4); ý = min í4-4; 7-5; 10-4ý = 0
3) R(i) = Tn(i) Tp(i)
7.5
| , i | , Tp(i) | , Tn(i) | , R(i) |
,
tp(7) =t(7) = 16.
, 0 . : {1-2-5-6-7}, {1-2-3-5-6-7}, 16 , .
. 7.4 .7.5 .
7.4
7.6
| N | |||||||||||||||||||
| (1,2) | |||||||||||||||||||
| (1,3) | |||||||||||||||||||
| (1,4) | |||||||||||||||||||
| (2,3) | |||||||||||||||||||
| (2,5) | |||||||||||||||||||
| (2,7) | |||||||||||||||||||
| (3,5) | |||||||||||||||||||
| (4,6) | |||||||||||||||||||
| (5,6) | |||||||||||||||||||
| (6,7) |
7.6 . , Prodject Expert, Microsoft Project, Projects Profiler . , .
