Microsoft Word - 2- GH. Moslehi.doc

Transcription

1 ! " %&' (% ) **. * *,.86 6 ' 7.3!, %6,. /0 (/!/ :&'( )*( %!/! : ) : 09.!" %& '( )* ; ( 78./ / 6 %./!" 3./ B0 BC D!". <. 6/6 /3 < 78 ;<=<* >./ ( E6 8 J6. E;.FG./ H I.G D.."." )* < 78 ;<=<* > K; ( * G. 3.6 G KE;.FG K3 K!" K)* : < ; A Heurisic Algorihm for Projec Scheduling Problem o Maximizing he Ne Presen Value G. Moslehi and H. Ghahar Deparmen of Indusrial Engineering and Sysems, Isfahan Universiy of Technology Absrac: This paper deals wih resource unconsrained projec scheduling problems wih he objecive of maximizing he ne presen value (NPV) of projec cash flows. Here we presen a heurisic algorihm named as differenial procedure (Dif_AOA). In order o evaluae he efficiency of his algorihm, neworks wih node numbers beween 0000 and nework complexiy coefficiens beween.36.6 have been generaed. We have compared boh he oal ime for solving he problem and NPV of he Dif_AOA wih hose of he recursive search procedure. Compuaional resuls show ha he Dif_AOA performs very effecively. Exensive analysis have been performed o evaluae he node number, complexiy nework coefficiens(cnc), and deadline. Keywords: Projec scheduling problems, Ne presen value, Differenial procedure, Recursive search procedure, Cash flow. /0 % **.( % *

2 &w=b9 x=v &w=b9 =0 = 3= =k CU= OM *= A= O=M 8 6=9 3 c A.( 3Q9 8u9 =9 =0 * A &S O. q6r O lq@ Q=@ 86= l*=9 =R x6o ; Q9 &ry 6^ CQi ; &=M *= A= =Q(y Ou= 0 :.( ; A)@.[]60 OM * x6o A 9 '(6R ud * c k * A b xv OM c.= k : uh zq'( lq@ 0 Q9 &.\69 8Q>*R A6=@; =H36=\ =H = 8=9:; ; {7 c A =0 &=H36=\ EQ> &.\69 J9@ ; 3 9 :.(; ;> 0 8 3; ( 9 0& 7 ( QR 9 ( 9V.[v]H& ( 9 = 3= =k m( 8u9 8' * A OM 8 69 []: =PH &=96} &= : c ; =( C=DE 0 []: =uh =b@ (SA):= 6= 8;= D c 6= : uh b@.[]b@ : 60 Y c = AOA M = * 3 m 6^ &ry 8( 8'(6R 3 B=Q@ &=96} c m( : OM 8 69 (60 zq=='( == =='(. []==(60 3== : ; =M 3= m 6=^ &=ry 8( :6R 6 : uh c m=( : O=M 8 6=9 []=6\ 6=a( AON ud=.[]( BQ@ [v] JR6 &.\69 8Q>*R 6=H :\*=Q( K SA : 6K Y c A9 ; =(Q9 36=K =k '( QY K &>( 699 (Q9 6. '( 86='9 ]=@ 6 =9 & =K K 8 : 6K Y c pq=b A= =K &=>( ;.[] SA c 9 D*( Q=9 3= Q( 3 m 6^ 8 7 8( :6R 8Qb 8 69 & =K 8=; 6y=@ 36=\ 6=H 8=( :6R 8H7 B@ :6R 8Qb 8 69 pqb A ; K &bh pqb M A u O m 6^ &ry 8( =9) =& ; DW O9V 8Hm\ B@ &B H7 B@ :=; C= (36=7 =6 := <=bh Q =Y > := <=>(?@ AB@ ; CDE :; * GH A.AB GH F 9 : F 8'B J= :6=K 6LK =M 367 6@; N 6H OP@ ( Q@& TQ=SQ =K &'Q= 6=LK R ; &( OV =M G=H =9 =( 3 &6B CU :; J9= 8'=W X=) T Q( :; C :6K 36=7 &= 8H DR [.( Y 67 8;( Z7 8'W < =R =B : Q=E =9 = []3 6\ 3( ]^ 36=7 6= &= 8=H =DR K &bh.[] 6a( &P &B c; dy :6K 6LK M GH J9@ 9 6a( 8 6=9 efg =.[]&= 9 HB A6D ; dy :6K 6LK M GH :; * 9 A CQ=i 9 B9 9 A ; K)367 8( 8'(6R h&b c; j =k O= lq@ (Q& 3 Z( PSP_MAX_NPV =Q( *= A 9 JR 8; CU O ; B9.[] 8= ; *= A l*9 9 8 (Q\ 9 < K6H K 3.( Y 67 :Q\(Q\ 8=9 :=; &B c; dy B ; 3 H 8U=9 i6 mh 6 W QR l =7 &(UQ=o 8 6=R C (U9 36'9 n6() 8 [\ 6 =7 6=0 6.=9 36=7 8=( 8'(6R p>m :Q9 U9 m( A= ; 3 H Q.@ l 6 A N 6H K&.Q& 6(( B Z( q6r 8 9 ; PSP_MAX_NPV * =H.[]= 3 &69 &) 8HDR ; :Q0@ s : Q=@& 6\ CQi * A 8 0 &H0 =9 J9= =W :60 S % :.6K p*@ ; 'N 6=a( %!.ud= C= 8'M A6\ 6a( %.*.=BV =9 =RQ@ 9 8( 8'(6R X) 8HQb A6\.* OM 8 69 X) 8'Qb k %v c =N :Q0@ W( PSP_MAX_NPV OM 8 69

3 =9 8='Y 67 =6K ; =P(7 8=' dy F ; 8 EQ> 6\ M &E6 P(7 CQ=i =9 d=y 8=( :6R F 8 B N A= ; < =K 6=H 8( :6R dy JR ; K ( 6. :QK@ & 6a( 9 K 8 P(. 3 9 'B < Q=@ 8=( :=6R =M 3.( Y 67 : &69 9 =M A= x = ; &=P.= 6\ =B 6\ 69 3E 6K K &M Y pe 8( :6R ==9 8==( :==6R F== ==B 6==H 8 ; ==9 ==u B N F JVQ 9 OP@ 8 ; 9 ; 67 &P(7 P(7 9 c 7 OL 8( :6R F m( ( H69 F TQV).Q& Y \ 6a( AOA xw@ A PD Z( M F= 8 =K = =B F 3H :.( :K 6H. OP@ 3H :.( 36\6H. QY 9 ｋq96 8( :6R :.=( 36=\ 6H 8( :6R. B N F T6 9 OP@ 9 ｋq96 K &H6R c 7 dy 3H 36=\ A= =9 K &'B EQ> 6K6 JVQ :; 9 T6 9 :7 TQ( ; * 8;( Z7 l9.(q& CQ=i =9 m=( *= 8=( :6R 8Qb. 6i 6Y@. 3 6\ 6a( 3 m 6^ &ry :=6R =9 =RQ@ 9 * 8DQ6 CS6 9 RQ@ 9 &=ry 8( :6R 8Qb m( 6\ B 6\ 8( CU=B CQ=i =9 AOA PD Z( M 3 m 6^ : () Maximize : SubjecTo : NN i= NN NA i ij i Cij) i= j= C ) d i ij d ij ij NN i j j ij (i, j) (i, j) (i, j) () () () (j) (i, j) () : : K.& Z m 3 m Qo 9 CDW 8 6===9 8===P9 pq===b F=== === A=== pq=b A=.= =H QY k W( PSP_MAX_NPV 6 : <bh &M 3 xr ; 8 QY69 AS. ;( CDW 8 69 &K*9 :; C 367 =Y 67 : C=S6 *= X=iQ@ 9 B9 *V 8'. =7 h8=p9 pq=b <Q= *=V.= 3 =.= 3 3 ｏsq@ q6. Qo 9 (&S@ pqb ) 8 6=R ; 3= = =9 &@D=W ｐ=( <='N *=V &.=\69 8Q>*=R pqb 9 : * &S@ pqb C '.=7 86\ >( 6Y *V '(. 3. B6&C :? d=y :6=K 6LK =M =B =9 36=7 89 :; * 8='B 8=9 :=; ; = CDE W( &B c; J9 W ^ &(; 3W F : 367 F 36=7 O=K 8=( 8'(6R &B c; dy K 8 (Q\ 9 36=7 &B c; dy K &(; 3W A.Q 6LK M &=( 6W9 6*= 3; =( 9 OV M Q 6LK M 9 : : ; ( 9 6LK M PD.= &=69 O=9V 3\= ; :; * 6=a( =r( 6=b 3\= =6K 6=a( =r( 3\= F G=H = :; * xw@ A. P(7 &=69 =P(7 3\= ; &B c; dy :6K 6LK M P(7 8' 3H :.( DL 8( :6R [.Q& =9 =P(7 8='Y 67 3=H :.=( &= 8=( :=6R. &E6 : P(7 CQ=i PSP_MAX_NPV 8 :QK=@ K &HK 6\ 8( 8'(6R K 3 6 6\ 6=H 8 ; =9 6=\ =B =M.*H 6\ B ; C=DE =K Q=R d=y 8( :6R F B!

4 .Q 89 :; AP :; 9 8=( :=6R u O 9 Q& am K Qo :H TQ=V :=; =9 8* : OP@ :; & ij B =B 6=H O=P@ :=; 6=b C=DE =9. &(7 36\ :=; C= 3=E =9 : & 9 36\ TQV :; OV M : &(=7 36=\ :=; 6=9 69 6LK M B : 8 6R 6} F B 6H 8 ; 9 u 8R 9 ]@6@ A 9. 8 K &B 6H 8( :6R : Q@& Q S * 9 Q=o =9 6K S : &(7 36\ 9 & 8( :6R : m= =9 DL 8( :6R 8 36\ 6H 8( :6R 9. =9.6K S & 9 36\ 8( :6R 9 6K Om@ : C 6\ 8( :6R 9 3 * F 9 * ]@6@ A =@ (帛) CU=B CQi 9 * 8DQ6 Q& OD@ : & () Maximize : NN Ci i= SubjecTo : i dij i j (i, j) (帛) (f) NN ()?=@ &=M =9 : Q@& * 8H36\ 89 :; ; B9 6=\ =K CQ=i A= =9. = 9 m( 'B OP@ = CDE : OP@?@ DL B 8( :6R : 8 6=R :=; C= 3=E =9 & =9 36\ xw@?@ ; : OP@?@ & B 8( :6R 6\ B. &(7 36\ TQV?@ B G (Dif_AOA)A8C %&' :D 3= 3=( &S@ pqb 3 k 8P9 pqb =b@ K 8 P( &S@ pqb /. =9 =KK&= 6=K =P( A '(. 3 k d=y pmk= =r( 3= m 6^ &ry 8( :6R QR :; A6@6 :; A6@; m 36\ 6H &B c; :.=( &9QY 9 P( A () OP.[f] : xw@ AP (&=ry) C i = a b i CQ=i =9 =K i 36\ 8( :6R = C i i. Om@ OE = 36\ xw@ :; = i ij B 8( :6R= C ij ij B OP@ :;= ij (H )H36\ B@= NN ('B)'(K B@= NA = M 36=7 O=K &=B c; d=y () =B =W () B.K& 6LK M 6\ B 6\ A=@ 6=i 6Y@ :; 9 T6 9 :7 TQ( ; 8;( Z7 =B O=P@?@ K K& Aw@ ()W.K& =B :; C 3E 9 i36\ xw@?@ OV M ij =D( =B 6H OP@?@ K K& :9 (j)v.9 ij ｏ6 =@ ()=V '( K ;>@ : &(7 36\ TQV?@ ; =6 3W 'B 89 :; KK&.6b9 CQi 367 6= Q& 3H. * 8DQ6 K (Q\ :H *= 8H6} B@ 'B H36\ 8 < Q@ 8( :6R 8'=W =B@ m=( =H&= Z m '(K B@ 9 ; 3= =9.=K& 7 Z m &'RQ@ O9V : m 9 * U A.6K6@ 3 * : Q@& 3 U F. H QY 3 :.( L F ]V =H36=\ ; < =K 6=H =K Q 6\ 6a( ij B 6\ Q=o =9 m=( ='( : B 8( :6R F 8 :=6R Q= 6=6\.= 8( :6R F 8 O* 8=( :=6R %fgg j36\ 8( :6R gg i 36\ 8( :6=K 6LK =M 8 69 K A 9 %ggg ij B i 36=\ =9 36=7 8=( 8='(6R &=B c; dy :=; A=P :=; A6@6 j 36\ AP :; A6@; = &= 8( :6R 8 K m( ij B.(Q 89 = v

5 (") %&'()*,./0 %3 '6 789 :(;<=3 (") %&'()*,./0 %3 :(;<=3 %3 '6 789 >? %3 '6 789 >? (D) %&'()*,./0 %3 '6 789 :(;<=3 (D) %&'()*,./0 %3 :(;<=3 %3 '6 789 %3 '6 789 (B) %&'()*,./0 %3 '6 789 :(;<=3 (B) %&'()*,./0 %3 :(;<=3 %EEE3 EEE'6 7EE89 %3 '6 789 (C) %&'()*,./0 %3 '6 789 :(;<=3 (C) %&'()*,./0 %3 :(;<=3 %3 '6 789 >? >? >? >? %3 '6 789 >? >? P < C % K L M > %N &' O.9 :J H0I M 'N A &B c; dy Q( () OP h = = 8H Q( K (Q\ :H.H& :.( &B c; dy pmk r( Q& am () OP = :=; A6=@; = =M ='N A ; < K 6H =K &=bh =P( A 9 RQ@ 9.'( :; A6@6 :=; A=P :; A6@; H36\ H 9 PD F c; d=y Z m= 8 6=9 &H36\ l =( :6R K &bh d). OP A.H& p=>m J9=@ Q= =6\ 6a( 3 m6^ &ry CQi 9 =M ( :=K =7 CQi 'N AP 8( :6R :=6R =M ( (a>0, b=0 &=ry 8( :6R M ( ( 8=( :=6R M (j = 8H Q(.( ) =DL =9y 8=( :6R a<0, b=0) (a>0, b<0) a<0, b<0) & 9y 8( DL 采D ; 6E 9 & 采D ; 6E 9 &ry

6 A=.=9 = 86=K ( 9 ;( u 9 &.=\69 J9=@ F= ; 8=B9 8=H36=\ ( 8 69 pqb =9 8=B9 8=H36=\ :; 6\ J9@ A. 3 3 :=; &B)9 ( :; 6}@ 9 8;( K 9 8 (Q\ j 36=\ :; ; 6PNQK ij :; 6\.Q& XVQ B :; C 3E 9 i 36\ j 36\ 6* ; ( ( (9 3=E 9 i 36\ :;) 9 6}@ 9 ;( 8B9 8H36\ 3=\: (=9 j 36=\ :=; ; 6\m9 ij B :; C (T[i]D[ij]%T[j]);=( Q= 3; =( 9 (j)8b9 36\ :; (j)8=b9 36=\ =9 => =( J9=@ =K&= 7 (.Q& &( QY 6 ; 6 H Q> Q=R 9 ( :P 8 69 PD 8H36\ &69 <bh :?:D =K pq= =R Q &=H36\ 9 AP A6@; Y =( =E =9 :=; A6=@6 =9 &B :; ; '( ( PD= &=B c; d=y = QR 9 8B9 8H36\ =9 36=\ =i OV =M 3; =( =9 '( ( H( QD'9 Z m= 36=7 O=K &B c; dy : 8B9 8H36\.H [= = & 8( :6R 8 i 36\ L : QE 9 36=7 &=B c; d=y Q=D'9 E9 &'@ 9 : ( :=6R 8 : 8=B9 8=H36=\ =u O 9 =E9 : AP :; A6@6 9 i 36\ ( Q& ( DL 8( G6=o ; = Q=&= 367 OK &B c; dy ZHK 8='B Q=& am () OP K Qo :H 6b ==M 8 : 8 =B9 8=H36=\ ==9 36=\ A= A=9 A= OV =M 3; =( =9 i 36\ ( :P [.( 8 36\ 8( :6R :Q9 & 9 RQ@ 9 QR 8 : 8B9 8'B 8 OV M 3; ( 9 36\ A ( i D=W.Q=&= 367 OK &B c; dy QD'9 E9 x=6o ; : 8=B9 8=H36\ 9 (V(i))36\ 6H i OV M d=y =K =( Q=R =9 ( 9V 367 OK &B ; 6.=9 :=; A6=@6 ='( 8=( :=6R &B c; C=DE =9.=9 :=; A6@; '( &B c; dy 36=\ F &B c; dy C@ K &bh l 6b =9 ( :P 9 & AP :; A6@6 &B :; 8=P9 pq=b /= A 69.Q& &69 : 8QR =H =9 (&=S@ pq=b ) = A= 3 k =K& 89 :; AP :; A6@; PD 8H36\ : QE 9 K& DW 367 OK &B c; dy &=S@ pqb.k& 36Y M6 A QR A6'9 6=H =K&= &=69 =9 6Y ; H36\ 8B9 <\ ; 6.=9 :=; A6=@6 : &B c; dy K &H6\ =VQ CQ=i =9 =9 &B :; &B c; dy 36=7 =6 = =9 : 8B9 8H36\ cqy :; c; d=y Q=D'9 =E9 Z m= A 6\ 9& Z m O=K &=B c; d=y H36\ :; Q PD OK &B 8=B9 8=H36=\ 6= =9 pq=b Q& 36Y =\ 6= =9 ｐ( 36Y :9 CQi A 6^.& m=( 86=b CP( pqb 8 6R AM.& 8B9 8='9 QR =Q@ 8 6=9 ='( =E K 3 6\ 6a( =Y 67 C=P( A= 6=K =9 =.= <;U ]=.Q& ; Q> K :=:D 3 d).=@ ;=> 36\ F 8QR 9 ( K &bh A :; ( 6y@ 9 9 ( 36\ : u ; ODV =K A 8 69.Q 6\ 6a( m( : 8B9 8H36\69 36\ 8=H36\ : :; A6@6 3; ( 9 &69 W@ 36\ :;.(Q=&= 3 ( 9 ;( Q K 8 3; ( 9 : 8B9 &P AP K &B A 9 ;( Q 3; ( A &69 <bh D V &69 W@ 36\ 8B9 8H36\ N = ( ( 9 8;( 9 36K 7 ( 6b 8H36\

7 3 i 0 i 0 m j 0 k n ; P &C S, :DH"I ; 6 H Q> :R H0I O=K &=B c; d=y =9 ( A AP. 6V69 6; r9 &B.H Z m 367 NPV () Lr NPV() Lr > NPV(3,) shif () =K c= c ; pqb P( A A6K 6a( = 6\ 6V 3 Q : PH Q'( pqb =H36=\ <=@ &=69 ; =B9 =K CQi A 9.[]Q& &='@ =9 =( =9V ;QH K &H36\ H &DV M6 c= J9=@ ; 3= =9 (Q=&= & 9 ='( < Q=@ ( :P M66H : PH Q'( &.\69 pq=b ; 3= 3Q=W( := A= 8 69.Q& &69 36=\ g =9 8 PD K 6 Dif_AOA pqb c :=; A6=@; H36\ H 89 :; ; {7 K QR c; d=y Z m= E9 '( ( K &H36\ H AP 6=9 &B( m( Q& (36\ QY &B c; dy) '( &B =9.(Q=&= 3 =( Q=R 9 ( QR '( ( 3 6 8=( :=6R =W ; j h36=\ =K =K 6 3E Z m= =E9 ='( ( &B) ( ( 9V :QY.=( 36P( 7 ( QR 9 (Q& '( &B c; dy =( =DL 8=( :=6R =K PD ; 86b 8H36\ 6; 6=\.*H H36\ A ( hj( ( 3 JV H36\ A 8QR 9 ( 6bP 9 &K6. 8B9 36\ (Q\ H 36\ A PD= O=K &B c; dy 86y@ H m( '( < Q@ ( = 6.= 8=B9 36=\ F OV M 36\ A 6\. ( PD= OK &B c; dy AP '( < Q@ ( 9 A= =9 &=S@ pq=b c pqb.h Z m V (i) = min{t(i) D(i, j) jsuccessors(i) T(i)} :6\& CQi (e) B (e) ; 9 %? P &C Q> :D:D = A= 3= 6\ 6a( pqb K 86b P( 6=\&= CQ=i (\ R CQi 9 H36\ &69 :QN K &B c; dy 8 ph 9 36\ N < Q@ ( C 6y =9 *= := A 8 69.Q &( 6\6a( 367 OK.0 RQ@ () OP 9 8H36\Q& 3H. () OP K (Q\ :H 8=H36=\ =K Q 6 6\ M.(Q& &' 36\ =E 9 '( : 6Y@ 9 K 9 8( :6R 8 6H d=y 6=\ m=( Q=&= ='( &B c; dy Z m Z=7 &=M = AP 9 DL j 36\ &B c; 6=H 8=( :=6R p>m 8H36\ &69 <bh K 9 8=H36\ &'@ 9 ( Q( K 9 &( m 9 36\ A ; < K. 6V69 6; l9 &BH ( QR 9 j NPV () Lr < NPV(3,) shif (g) NPV () Lr < NPV(3,) shif () &=B c; d=y =K =H&= :.=( () (g) r9 :=; A6=@6 =(\ R CQ=i =9 () () 8= H 36=\ ; {=7 j 8H36\ &B c; dy ; 6K ( Lr)AP g. ( Q= &=69 < Q=@ Q=o 9 8H36\ ( 6\ M

8 v s! v! v NPV NPV NPV NPV NPV NPV NPV NPV P &C Q> U 3I %&' &3 :TH"I ; {=7 c= pq=b.( =DBR) Q& B 36\ h( j 36=\ =( ｏr ｏr 36\ ( :6K B =B 36=\ ( & ｏr 9 ( DBR)K& B =( :=mh CQi 9 36\ 6H DBR.( DBR) K& D=W PD= OK &B c; dy > [.( 36K 7 Q=9 36=K 7 QD'9 PD OK &B c; dy 6\.Q& 36=Y Q=R 6P( 7 QD'9 QR 6\ Q& 36Y ｐ( ==( h==b6^ ==M ｏr== A==H Q== &==( c; d=y => { =.(j =DBR) Q=& &69 36\ ｐ=( Q9 QD'9 QR 6\.Q& DW PD OK &B =9 =K &=H36=\ =H & ; {7 K K& OE CQi &=P ｏr= 6H ( 3.( O ( ( 9V &'@ 8=B9 8H36\ 36\ QY &B) K& B Q9m 8H36\ A & B9 ｏr 9 (H& ( QR 9 : &=69 36=\ A A9 AP CUM H K 9& &R 8 9 ( m( 36\ A < Q@ ( CQi A 9.Q O=K &=B c; dy 6\ M 6H Q& &69 '( =K (j) OP=.Q=&= 36=Y ｐ=( =9 QD'9 367 j h36\.h& :.( L A 8 69 c pqb ｏr=.q= &69 9 '( :mh ( K ( QR

9 3 "WI (% ;.9 :V H"I SA8C %&' U Q "WI :XH"I =9 =.6=b9 CQi ( : Q& PD OK &B c; iq =Y 36=\ 6=H 8=B9 8'B H &69 u O :=; Z m= ]=RQ U=9 &\=7 ]6=S =9 8=HPD. 6a( G6i : ; Q& CDW Q (% H :T:D 3Q=W( =9 6=V Q=o =9 =L F 6K 9 *V A =9 8 PD= (帛) OP. H QY :9 pqb 6KK C=Eo () =R.= 3= 3 :.=( :K f 36\ 36=\ 6=H :; A6@6 A6@; 8( :6R 9 ｋq96 <=\ &=S@ pq=b 9 L A OM 8 69.H& :.( 8=9 :=; :.=(; A6=@; PD= 8H36\ H.(f) OP Q& d=y :=; A6=@; =H36\ H 89 :; ; {7 A QR A6'9 : QE 9 DW 367 OK &B c;.q& 8 'b( M6 BEST = %/帛 =9 ｐ=( :6K 36Y :9 6P( 7 QD'9 6\ Q& 36Y &=69 j 36=\ =( h=b6^ =M ｏr= =9.=\69 ]=@6@ =9 (j) OP= 8=H=DBR A.( DBR)Q& ='( A=9 AP CUM H K 9& '( 3.Q &69 pq=b = &=S@ pq=b.= :9 K (Q\ :H 3= : :Q=9 8=P9 O=U ; &P 9. 8u9.Q& Q=&= 36\ 'N O K PD F ; &*V () OP =9V K 9 8 (Q\ 9 36\ 8( :6R 6\.H& :.( Q=R =9 j 36\ ( Q( 9 QR 9 36\ : ( =K &=( =7 =( 36=\ CQ=i A= =H ( B 8 M j 3; ( 9 36\ ( 6\ K &@Qi. ( QR m( j 36\ ( 9 8;( 6\ CQi %j 3 OE 9 &@Mi pqb OP. A J 'B K &' 36\ 6H 8 69 K 8 (Q\ 9 d=y Q=D'9 =E9 6=\ Q DW QR : B9 s

10 \%C v!! v s! I H :=QN \%C% U> %N!v %!%. /T v %% T! %% T! %. / %. /!!! % %. /T!s v v ; 3I! v s! g e \03 \%C ; 3 0WI :] H0I V = T[]D[]T[] = 9 = 3 3; =( 9 36\ :; ( K Q& DW { 6Y M NPV( = ) =.30 < NPV( = 8) =.9 =9 A= ; =B9.pH& 6}@ 9 36\ :; [ m=( :=; A6=@6 9 36\ :; ( K pk &69 36=\ &=B :; &B c; dy [ 6Y :Q=N.p=K&= T6= 36\ ; H36\ &69 { QR : :; 6}@ 9 8;( 6i 36\ 8( :6R =DL 8=( :=6R 8 K 36\ 8B9 36\. ( PD= OK &B c; dy : AY ( 6Y@ 9 OV =M = 8=B9 36=\ K 36\ 8 69.H&( Z m.q& DW : 8B9 8H36\ 9 36\ A i

11 =9 36=\ =i OV M 9 3 m 6^ &ry CQi =B9 <=\. 6i K Q& DW ( 36\)8B9 36\ :=; A6=@6 &B :; 36\ &B c; dy.6\& 6V DW Q NPV( T = ) =.67 < NPV( Lr = 37) =.(Q& 3 ( VQ : 8B9 8H36\ 36\ :; A 699 T[]=Lr()=3,T[8]=36, T[9]=37,T[]=38,T[]=39,T[3]=0 NPV(Projec) = 8. =H36\ :; 36K 7 QD'9 &B c; dy :QN.Q& <bh 9 QR A6'9 3 36Y BEST=8. 8=H36\ 9 36\ A. j 36\Q &69 9 K 8B9 36\ &=B :=; : &B c; dy [ ( 8 i 8B9.Q& * DW : 8 69 AP :; A6@6 NPV(T=) =.9< NPV(Lr=) =.3.Q& DW : 8B9 8H36\ j 36\ :; ( A 699 T[]=,T[7]=8,T[0]=0 NPV(Projec) = 6.7 PD= 89 :; [ QD'9 &B c; dy.q& <bh 9 QR A6'9 BEST=6.7 6=V &=69 Q 36\ [ DL 8( :6R 36\ (帛 8H36\)8B9 8H36\ 9 36\ A i OV M.6\&.Q& &69 AP :; A6@6 9 ( [ 6i NPV(T=)= 3. < NPV(Lr=3)=.06 T[]=Lr()=3, T[6]=36 [ ( 9V.( ( :; 6}@ 9 8;( 36\ 8B9 8H36\ 9 NPV(Projec)= =( :6R.(Q& 36Y ｐ( [ QD'9 QR H u O 9.*( : ( 9 8;( 6i m( 36\ QR 9 3.( 3 ( 9 ( 9V K &H6\ :.Q& DW :; A6@6 36\ &B c; dy NPV( = 8) =.9 < NPV(Lr = 38) = 0. Q=o 9 QR 9 ( 9V 36\ A 8( :6R :QN.pH& Z m : 8B9 8H36\ 36\ A :; VQ T[] = 38, T[] = 39, T[3] = 0 NPV(Projec) =. < BEST = OK &B c; dy ( A K Q& am CQ=i 9 8H36\ :; [.H &( Z m e g 8H36\ (.Q& M (ge ]@6@ 9)ODV c; dy ( Q@ &( ( DL 9y 8( :6R K f 36=\ ='( &=69 :=9 [ H Z m 367 OK &B &= =9y 36\ A 8( :6R.6\& 6V &69 Q f 36=\ &=B c; d=y : AY =( 6Y@ 9 [ 36=\) : 8=B9 36=\ 9 36\ A i OV M.H& Z m Z(=; A6=@6 =9 f 36=\ :=; =( [ 6i (g VQ Qo 9 c 8B9 8H36\ f 36\ :;.Q& &69 =7 =( 6=; CQi 9 g f 8H36\.Q& 3 (. ( ( 9 ;( m( 36\ K& T[7] = 8,T[0] = 0 NPV(Projec) =. < BEST =.6 :=; 36P( 7 Z m &B c; dy u O 9 帛 36=\ 8=B9 36=\.(Q=& M 6}@ :9 g f 8H36\ 36\ A i OV M. 9y & 8( :6R K =9 =( [= = &(=; M 6i ( e 36\)8B9 36\ 9.6=\&= 6=V &=69 Q 帛 36\ 8 69 AP :; A6@6 8B9 8H36\ H 3 O AP :; A6@6 9 帛 36\.(Q& O QR 9 ;( Q 3; ( 9 : T[6] = Lr(6) = 36, T[9] = 37, T[]=38, T[] = 39, T[3] = 0 NPV(Projec) =.8 = 36P( 7 QD'9 367 OK &B c; dy :QN 36=\ (Q=&= =M =( ; ODV CQi 9 H36\ :; =9 : 8=( :6R K 36\ \& 6V &69 Q

12 (cpm!"")& ' ()* *, ( (,./0* : ()* *, (, ' & ' 3 *, (" "6 (78 "9 ). :; < =," >?./0* <@* 37A' "" "!&"36 BC <6 D7!" E<F ; ' & ' D7!" : 3* ' &," :D7A* G8!H (7"3!" I ; ' & ' / : * ' & H < =," >? J"K" L9 G!"")3!" 3 / M M& ; ' & *K' D7!" / :.(= O A8C %&' %N &3 :^ H0I =9 &HPD O H3 A.[s] 3 Q9 &6 = 6=H =K Q=9 / PD= &\7 ]6S 9 36\ 帛 ; =u ; {=7 O* A.& O * g M :Q=; 8 6=9 =( 3 Q=) =6 9 &*Q( (69 x6o Q='( &.=\69 pq=b 9 : * &S@ pqb.6\ 6V 3 Q : PH & =K 6=V O=W@ 8 6=9 O*= A 69 3E. Q@ m( 6b * 86 F &S@ pqb :6R 8H 3 Q@ PD Q@ O * Q@ 3= &E =9 pq=b F ; PD Q@ ( Q='( c /= 69 8='(6R =Q@ 3Q=W(. 3 6H 8( :6R 采D ; 6E c A.[] : PH 8( :6R J9@ ] m( [%g g]a9 ( a i )36\ pq=b A= &(=6R Q=(.=9&= :7 pqb (. 3 3 :.( &mr Qo 9 (e) Ou CW,* _% :T O=M * 8; B@ pqb & K : :.( Qa 9 6=H & K 3 X) CU K (Q\ :. 3 6=H & =K 8 69 *M 6 7 N 9 pqb =H6 7 A= =9 D*=( pqb : *M 9 pqb =B@ O PSP_MAX_NPV * 8H6 7.Q( &9; 8='(K =B@ D*=( ) PD &\7 ]6S PD 8H36\.[e] (: 8H36\ B@ 9 PD l=q@ D=V =0 dy 3 86 ; Qa A 8 69 O=9V =(6 x=6o ; 3= =Q@ Z( =PH ZQ=K

13 i = NN =" 3* ' & (i) & <C :F"3@ = V(i) P./0* Q,"3!" (i)& *, D7!" >? J"K" L9 V(i) * (i) & < =," < (i) = (i) V(i) H ()* *, ( (i)& *, EF* D7!" Q,"3!" G). (i) & 3* ' & ' EF* D7!" (( Shif)!"" ),! * ). :; < =," >?./0* :; < =," >? E/" 7.8 ). < =" 3* ' & (i) & *, R "6 (78 "9 ). :; < =," >? QR <@* (" i = i i < O P P; %N &3 :` H0I =9 PD= &\=7 ]6=S ( ; )M 6*= =9 3= =S h=9y = (/ =@ / ; )M 3 Z m= (=M =@ ; )=M g9 ud &( 6W9 TQ=> =(Q( *= gg =M M 6H X= z 8 6=9 A=H.= Q@ (Q( * 帛gg 36\ ggg B@ 9 (Q( * gg &S@ pqb & 0. OM Q@ A=H ='(.=( 3 Q@ [% g] ( b i )36\ 6H g eg 帛g gh=m j 3= =Q@ Ok* 36\ B@ 8 69 / / /h=m PD &\7 ]6S 8 69 &H6\ = = :6=0 =S ; m=( \ 6a(. & 9 ud &( 6W9 6* 9 ( )9y 8='Qb & =K 6=V O=W@ 8 6=9 = A =9 36\ B@ 8H6 7 C 6}@ &.\69 &S@!

14 (cnc= = /V E =V),V_AOA SA8C %&' ; C bcc :? QN d L & e &N Z 6 d U. &N C ( b) V_AOA ( b) SA8C ; C B% v ss! v s ss s!! ss s! v v s vv s s vv s v ss /! s / v s s v ss /s! s / s!s s!/ v s v/!! s / s s v v / s! s / / s / s /! ss! / s /! s / / s s / / s v/ v. am A ( E 9 V_AOA c lq@ Ok* :.( OM H :.( E :=; 6=9 36=7 =6 6y=@ CDW :; 69 36\ B@ CD=W :=; 6=9 PD= &\7 ]6S 6y@ CDW.6\& 6V &69 ; C bcc :=:T =M CD=W :; 69 36\ B@ 6y@ & / 6=9 69 PD= &\=>7 ]6S. 3 6\ 6a( 6=a( 3E 9 &( 6W9 6* Qo ; ( () R pqb 6H 8 6R >(.( 3 6\. c = 3= 3 :.( (g) OP K (Q\ :H &U=9 *M PD 8H36\ B@ 9 D*( V_AOA CD=W :=; PD 8H36\ B@ Z m 9 K 8 (Q\ 9 =u O 9 pqb A AH.K& &( Qo 9 ; 6.=9 36=\ B@ 8 69 ;( 8; am 9 6R 8 69 =9 D*=( CDW :; (.H &( QR eg (I,3J ) >? F ; C bcc &3 :Jf H0I Dif_AOA V_AOA &.=\69 (Dif_AOA)&=S@ pqb * 8 69 m= <6=( =9 pqb A (V_AOA): PH Q'( ==W@ (Visual Sudio.Ne) f )*==( () &== ｇ== /帛 3=(; 67 =9 ='N <Q=7 =( F 8 ggg ; 8=H 3 =9 &*Q( (69 RAM 9b 帛 9 m@6hb\.( 6R 3 Q@ 6y=@ =M = &@D=W ｐ=( *V A v

15 (cnc= Dg =V),V_AOA SA8C %&' ; C bcc :D QN d L & e &N Z 6 d U. &N C ( b) V_AOA ( b) SA8C B% s ss s! s v! s ss v! s v v s v ss v!! ss v! ss v v s v v s s ss v ss v! ss v ss v! ss v v ss v ss v! ss v ss v s ss v s s ss v 36=\ =B@ =9 8H PD 8 69 &9QY & K &S@ pqb. :?:T CD=W :=; 6=9 36=7 6 6y@ & =M.= 6\ 6V &69 Q *V A M / PD= &\7 ]6S g 36\ B@ 9 &H A9 m( S Q& 6\ 6a( 3= = =9 ｐ=(.=k& 6}@ &@ Oi Q 9 gg :.=( () OP= CD=W :; Q( m( () R :=; 6=}@ =9 8=; *=M pq=b 6H K H& 36=\ =B@ < =M.=H &( :.( =9&= Z m= :=; p=h Qo 9 PD &\7 ]6S =6\ 6=a( PD &\7 ]6S g 36\ B@ =M A= 8 6=9 3= = 9 ｐ( (j) R.Q& =K =H&= :.=( () OP= Q=( =(.=H& :.( :=; p=h Q=o =9 &\=7 ]6S 36\ B@ K &bh pq=b ; 6K *9 &S@ pqb 36\ B@ Z m O=M =(Q( O*= xv 8'9 QR i. AOA Q'( () =R =K (Q\ :H &S@ pqb 9 3 i (. 6} i e A9 Q& 3H. = =9 xv 8'9 QR B@ K H& :.( xv 8'9 QR Z m= =9 D*=( &iy *M &S@ pqb ; 3 =B@ 9 8H PD K & 6a( 9 [ ( H36\ B@ = =M A=H &=V 8='9 QR =9 : Q9 m( 6@U9 36\ ; "x=v 6=^ Q= Q=R G=Y =i ":Q=.= 6=^ Q=R =K &*= QR GY i m( () R :.=( V_AOA pq=b x=v 8='9 QR =9 =( 3 xv G=Y =i 6}@ ; & ). ( :Q A.H&.Q &( 3H. '9 QR ggg gg 36=\ =B@ () =R ; X & =K X= &9=; 8 6=9 =M A=.=H&= :.( =9 ='( CD=W :=; =K =( 3 Q@ &S@ pqb =K =\ : Q=@&= [=.= =(y j g =M ]@6@

16 (cnc = D ),V_AOA SA8C %&',, bcc :TQN d L & e &N Z 6 d U. &N C ( b) V_AOA ( b) SA8C E B% s ss v! ss s v ss s!! v ss v ss s v s! v! s s s (I,3J )QRMOS> M>? Dif_AOA V_AOA (I,3J )QRMOS> M>? Dif_AOA V_AOA KLMN %,O:O bcc &3 JRH"I (NN=0,cnc=3) KLMN %,O:O bcc &3 :JJ H0I (NN=30, cnc=.) Q=&= 3H. M 6H K 86b P(. 36K =i 36=7 =6 S Z m 9 K A pq=b = =9 x=v 6=^ Q=R =K 8 Q GY.=K&= 7 O 6i &S@ 36=7 6 :; Z m 9 K 6\ >( : Q@& [ pq=b & =0 PD= 8='B 8= Z m= JDr9.0& 7 QD'9 &S@ V_AOA pq==b CD==W :==; ==K ==7 Z m== QR 9 &S@ pqb.k& 7 8QBi ( &K =9 :=H PD= &\=7 ]6=S 36=\ B@ Z m 6=b G6=o ;. ( *M :; Z m Q=o =9 &S@ pqb xv 8'9 QR B@ M 36\ B@ Z m 9 K i e /f M Ab( =7 Z m= ee/帛 9 < M PD &\7 ]6S

17 (NN= Dg =V)V_AOA SA8C %&' "WI S;h i%abcc :V QN d L & e &N Z 6 d U. &N C ( b) V_AOA ( b) SA8C CNC B% s ss vs / ss / ss! /!!v s / v v s / ss s!/ s!/!!/ sv ss!/ s s ss v/ s v/ v/ /! ss / v v v / /! /!! / (NN= Vg =V)V_AOA SA8C %&' "WI S;h i%abcc :X QN d L & e &N Z 6 d U. &N C ( b) V_AOA ( b) SA8C CNC B% s / v v /!s s / / s / /! / v / v v v s / / s /!/ ss /! s!/! /!/ v s / s!/ s s ss / v/ ss / v v/ v s / s v/ s / /! ss / / v v!s s /! / s / v / ss /! v /! ss / v! / (帛) () =R.= 3= 6\ 6a( 3E 9 &( 6W9 3= 9 ｐ( () (j) () 8H Q( m( (f) :=; 6=9 36=7 =6 6y=@ () OP=.=H& :.( ; =K =(Q\ :=H.H& :.( g 36\ B@ 9 "WI ;h i%a bcc :D:T :=; 6=9 PD= &\=7 ]6=S 6y=@ &=69 8 6=9 6a( fg g ghm PD 8H36\ B@ CDW 6* 3; ( 9 M 6H m( \

18 (NN=]g =V)V_AOA SA8C %&' "WI S;h i%abcc :] QN d L & e &N Z 6 d U. &N C ( b) V_AOA ( b) SA8C CNC B% vv s / s /! ss / v / s!/ /!!! ss / / v v s!/! / /!!/ /!!/! v! s / s!v!/ ss /!!/ s s s /!! v/! s /!! v/ s s /!! v/ s /! /! sv / s!s / v v v/ v / s / v v / s s /!s /! ss / vv v / (I,3J ) QROS> >?,,8,,,7 3 3,3 3,6 3,9,,,8,,,7 (cnc)itru.f%,v,n W'P 6 6,3 6,6 6,9 Dif_AOA "WI S;h i%a bcc &3 :JkH"I (lf ; C) (I,3J )QRMOS> M>? KLMMN %,O:O I*P( Dif_AOA "WI S;h i%a bcc &3 :Jj H"I (jf ; C) 3H.= () (j) () 8'P= V_AOA pqb V_AOA pq=b =K = P( A ; &( Q& =K &@Q=i &=69 =W@ 8=H36\ EQ> ; < K 6H &= Q.=( Q=R Q=D'9 =E9 i OV M ; ( 9 ( : Q= Q=R Q=D'9 =E9 =i 6LK =M ; ( 9 ( J9=@ = =9 Q=&= =S 6Y=@ Y 9 EQ> =B@ =K 8 PD= 6H M.Q& &9; Z( c =9 86.=9 &69 9 ;( :QN Q 6.9 c6y@ 8'Y ;.Q& 6.9 c &@DW :; c J9@ &\=7 ]6=S Z m= =9 :=mh Q& ｋd Q( Z m= XY Qo 9 &S@ pqb CDW :; PD m=( V_AOA pq=b &@DW :; ( ly.k& 7 =( =K =\ : Q=@&=( xv Qo 9 8QBi \ B@ K &bh. 6.9 pqb < K QBi 8'u= =K Q=o :=H =9& Z m fg 9 B9 g &@D=W :=; QB=i =( Q=& 3H. () (j) :=; QB=i =( ; 6.=9 ]=@ 6 =9 V_AOA pq=b Q=( =K &@(=Q(.= &=S@ pq=b &@DW

19 9 ｐ(. k : 8 69 &Qb 6\ ggg =9 &*= 8 69 &S@ pqb K H& :.( 3 pq=b =K &M H& QR &K *9 :; 36\ O*= 8 6=9 ;( &U9 am 9 u O 9 V_AOA..=( 6*= : ; Q=R A6=\ :=P 36=\ eg ; 6.=9 =H36=\ B@ K &bh K :.( &@DW ｐ( AH pq=b 8='9 QR =i gg =@ e A=9 =9&= Z m.( xv &S@ H D6@ &S@ pqb K 3 3 :.( AH Z m m( ( :; 9 D*( &*M 8 Q= h Q R GY i ZHK E pqb.h& xv 6^ QR &S@ pqb K Z m= =9 D*=( &= K *=9 *=M m=( V_AOA &==S@ pq==b ==9 D*=( == 36==7 =6 H36\ B@ N 6H *M A 86.9 *M A=H @U9 PD &\7 ]6S Z m= =9 D*=( pqb 6H K 3 3 :.( &=S@ pq=b &= ( /*M PD &\7 ]6S Z m 9 &K *9 *M V_AOA pqb 9 D*(. PD &\7 ]6S Q= pq=b :Q9 8P9 E : Q@& xw@ F= =9 : : Q=9 :=P CQ=i 6=\ 6=V &69 =W = ]= A=H.60 OD@ '9 pqb =R :6=K =7 A=H.Q= =S pq=b =9 J9 d).=@ '9 CwV 3 k pqb &@DW K& ph 6 : & K ]= C 6=a( =r( =k =9 =K <6=W : ; 6P.@ ( &E ]r 6.9 N 6H 8^ ]RQ.Q& (I,3J ) QROS> >?,,8,,,7 3 3,3 3,6 3,9,,,8,,,7 (cnc)itru.f%,v,n W'P 6 6,3 6,6 "WI S;h i%a bcc &3 (mf ; C ) Dif_AOA V_AOA :JlH"I =Y =H K=9 = Q=R 8 PD= 6\ 6b G6o 8=; *=9 : m 9 : &@DW :; 9 ( 86Y@.9& ZHK : Q=@& *V A 3 9 ｐ( ; K 6b P( xv 8'9 QR B@ K A ' =M Ab(= Q=o 9 &H6\ g M &S@ pqb fg g =9 H36\ B@ Z m 9 K 3Q9 i ee/j : Q=@&= [=.= 3= e/g e/f ]@6@ 9 A Z m= 9 D*( CDW :; &S@ pqb K \ 8='9 QR =B@ &K *M PD &\7 ]6S. ZHK &K xv CD=W :=; GY Q& am K Qo :H () 8'u 8 am O9V : m 9 pqb A9 &=S@ pqb &@DW :;.U9 () (j) =K &=M 6\ 6V (y ; 6K M 6H ; 36=\ =B@ Z m 9 V_AOA pqb &@DW :; A= =K&= 7 Z m &'RQ@ O9V : m 9 fg 9 g m( g M 9 j/ &\7 ]6S ｏr Z ;n :V c; d=y B :; * A 6V &69 Q ( 3 6 W( J9 : K &B s

20 . complexiy nework coefficien(cnc). deadline 3. projec scheduling problem.. projec scheduling problem o maximize he ne presen value. simulaed annealing 6. aciviy on arc 7. aciviy on node 8. milesone 9. shif 0. differenial _aciviy on arc Herroelen!" %! & ' ( )*,,. / Shub & ( & 0 0 & % 3 * %! 6 78 /. 7 Russell &9 : %!!" ; 8., < Vanhoucke 9 &3% 3 &,,7, /,,, * &** =">)) 8 Elmaghraby 9 3 &) 3 <, N ; Egar (?&?@ A *%! ;;. Egar (? & &) A *! 7. / B " 9 &! * Cash%! 7 </,, = ( ( & 6 Survey //,,!