#)( %&’ “#$ !

THE USE OF SIMULATED ANNEALING AND GENETIC ALGORITHMS
FOR A MULTI-MODE RESOURCE-CONSTRAINED PROJECT
SCHEDULING PROBLEM WITH DISCOUNTED CASH FLOWS

M. Seifi, R. Tavakkoli-Moghaddam & F. Jolai

Department of Industrial Engineering, Faculty of Engineering, University of Tehran
massoud_seify@yahoo.com, tavakoli@ut.ac.ir, fjolai@ut.ac.ir
Abstract: This paper presents a multi-mode resource-constrained project scheduling problem (MRCPSP) with maximizing the net present value (NPV) form the project contractor’s point of view. Positive and negative cash flows are considered in this model. Furthermore, to make the model close to the real situations, four different models for positive cash flows are considered. Two meta-heuristics, called simulated annealing and genetic algorithms, are used in order to solve the proposed model of the forgoing problem. To schedule all activities, a bi-directional scheduling generation scheme (SGS) for the multi-mode version is proposed, and the activity list structure selects for presenting a permutation of activities. Finally, computational results for a set of test problems taken from the project scheduling problem library (PSPLIB) are presented and discussed.

!
“# $% & ‘ ($ &’) *+ $
1268732040128

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

, -$ .

( )

,

$ ” % !” # : / ’01 *2 , 3 4 ‘5 ” / %- . , ‘ ( ) * ‘+& = >- .< 7 8&, 2 ” / %- :+8; ‘( 67 4 89 ! *A >- < 7 58< B 8 A < 7 08 & ?8*@ >9 4 .< 7 8&, 0 / & CD 8E< 7 <*A *< $
= +A 1GA * I B 80 ; 8 =I F*DG ‘A< H8 >
., ‘ (

?8*@ !B 8 ?8*@ !JE ‘+& $ !’I- ! :
A < 7

/ / :
//: massoud_seify@yahoo.com .” # $! % &’ ! ,
tavakoli@ut.ac.ir .” # $! % &’ ! (! ,!” #$ % &’$ fjolai@ut.ac.ir .” # $! % &’ ! (! ,()* +&,&- &’$
/0- !12 34 * 5-6 7 *’+, -!
8&, ( -*A * 8 Nf” MMRCPSPDCF
” / %- # [h] ? g< .<
) * [GA < *- ‘5
>9 # + ?8*@ B >S . (
. ( = +A * S < ‘A< H8
MMRCPSPDCF ‘ [i] *
/ %- %S *D I , [GA ![GA ‘ l5A / / / & j8 ‘5 ”
.< 7 8&, 2 E 4 > # mD/ 8&
‘” ( = $ !8&, N*M N” “A ^<
. *- MRCPSPDCF

.
1G 7 MnE !4 58< * /8
F N*Q /8 < α=1A o ! Pj F*DG !G P,
., ‘ :A p M
/ & A : n
/ CD ] P, : G !T j & TG #0D ‘- / A : M j
. j =1,…,n
j =1,…,n !T m T j & TG % : d jm
. m =1,…,M j
m T j & = D0A j8 ‘5 ” %- : CFjm−
. m =1,…,M j j =1,…,n !T
!T j & = D0A j8 ” %- : CFj+
. j =1,…,n T j & U7 % : STj
T j & = D0A % : FTj
T j & = D0A % #A : EFj
T j & = D0A % #A : LFj
T j & 9 / & F*DG : Pj
[GA A : R
k =1,…,R !T k [GA < / A : Rkρ
TG T k [GA * / A : rjkmρ
T m T j &
=1A o :α
= D0A % f ) Y& :T
.(7 ‘ / & TG % U*DG
MMRCPSPCDF 7 :A Q8E ?InF 58< :< I = ( N*Q

1268732040128

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

.

N*M # (MRCPSPDCF) 8& =1A ” / % < 7 = 09A & n B .*7 ‘ :A IG = (V,E)P, N*Q (AON) , O7 B 6<*A / %DR / & / %9 / , P, # .*7 ‘ *- O7 (i, j)%DR , .8/ 9 6 @D % j & =( ‘ i & @S !7 87
956686842409

:A V ={1,…,n} N*Q / & F*DG .< .7 ‘ TDA U7 G / & n 1 *7 ‘ ‘- # G = (V,E)O7 j∈V & / 8&, 2 j & / F*DG M j . *- U7 m∈{1,…, M j } ‘8 & O V .*7 ‘
N p jm . % m WA % 5( % 7 TG X < T m ‘I- T j & TG % Y& T , .*7 ‘ :A ‘ * #80* k [GA R *7 ‘ Z& !7
< *-* Rkρ%1 t =1,…,T /* B / rjkmρ !*7 TG T m T j & ,
0D . t =1,…,T /* T k [GA E ‘* CFmj− %1 m j & = D0A !%S ‘I- 2&M j & = D0A D ‘
F*DG #8& !P/ .D ‘ & & CFj+ ., > P/ A 0*) < -* /

.
8&, 2 ‘5+8; P/ *A =I / # %*A ‘ ‘+ ? “A B .*7 ‘ 4*\ % =( . “\ ‘* ‘* ] / 8< < ‘* ] #8*D #88 – N %S *7 ‘ 8&, 0 # “” 6<*A .[`] *7 ‘ TG % ‘ ^<
7 I [dcb] =I U* ‘- N” “A
.< N*Q 4*\ ‘Q;9 ” /%- ‘@/ / E *7 ‘ E / & TG 1/ $ ![ N*M 1- = D0A 1 % ?> B (NPV) ‘+& JE
# ^< .[e] 7 ‘ .[ ‘ N*M 1/ ‘

2. Makespan Minimization
P/ A # .D ‘ E 7 = D0A 😕 <
LFjM j
Max Z

t .x jmt (w)
624141-232563

479366-231290

=1= =1 t EFj m=1 1

.
. *A < *< $ Y “A # !< *< $ .*7 ‘ 58< ‘I1- # mD/ (FS) *+- ‘I1- 0A / .*7 ‘ 8&, 2 %1D/ (BS) N*Q X”F
= ( N>- ‘0 , >A , < = ( j &
.7 .? ‘ :A F*DG < *A S& %9/ 9 8/ ‘>8 & F*DG 4 F*DG *+- >- # ! 7 %9/ 8/ ‘/ & T F*DG . S X”F >- >S ( 7 ?/ / 9 ?/ 8/ ‘>8 & T*< F*DG ? 8/ >- / >S %*A ‘ 7 %9/ = ( *+- >- ‘/ & 0A / . *7 ‘ 4″8 B F*DG 8/ 8/ = ( X”F >- ‘/ & # # x89 / & .*7 ‘ =”8 F*DG = ( / & F*DG T*< F*DG !F*DG P[ d ` / F*DG ‘ 4″8 !< >- / 4 F*DG ‘&QA N*M & B yz< .*7 ‘ ‘- / ‘0 ‘&QA {;8 y *7 ‘ {;8 #0D % #A *+- >- !%S
t +1,…,t + d jm /* t ≤ ES j (FS) .*7 ‘ ! ‘D V” > .*7 ‘ # A D ( %1 S < ‘I1 >- = ( / & j & 1 T@/ ` F*DG / & *7’ P[ *+ N*M / & ‘0 1 X”F >- .*7 ‘ ‘ J Q;A %S ‘&QA B {;8 ‘&QA 9 / & ‘ #A 9, / & j & .*7 ‘ !D V” T@/ d F*DG P[ X”F >- = ( @ F*DG / & -*A 1 r F*DG *7 ‘ >A ‘8 & | / @ A ‘ # *7 ‘ T@/
nLFj+M j
1268732040128

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

CF j
Max Z =∑∑ ()t .∑m x jmt
i= =1 t EFj 1+α =1
13678039028

nLFjM jCF−

t .x jmt (`)
= =1 t EFj m=1 1
s.t.

M jLFj
∑∑ x jmt = 1 ,∀j (d)
m= =1 t EFj

98041-69904

t x ≤td.x jmt,∀j;w∈ Pj (r)
tt

j
FTn =∑∑MLFn t.xnmt ≤ T ,T ≤∑∑M jn max{ }d jm (b)
m=1 Efnm=1 j=1

Mt+d −1

x jmb ≤ Rkρ ,∀k,t (e) j=1 m=1b=t

x jmt ∈{ }0,1,∀j,m,t (h)

, >A , < B < ? DQA W8 B x jmt
] *7 = D0A T t % T m T j & $ (` ) ) P/ A 4 D( .< 5M N*Q < (/ &) ” / %- JE ‘+&
‘5 ” / %- JE $ T D( D ‘
.D ‘ 3 (/ E) >A & / D ‘ # DsA (d) / F*DG
6 . = D0A % B t” ( *7’ TG ‘- B T1 (b) .*7 ‘ u (r) 6<*A 9 (e) 6 .*7 = D0A %S Y& D ‘ D’ # DsA [GA / :A ? DQA / W8 %* B 5M (h) / / %- JE ‘+& $ P/ A 4 D( .D ‘ N .D ‘ < (/ &) ” E *- B <n E * 7 U* > E !/ U*( % E !U*DG D ( * 7 Z& , .*7 ‘ D8 E ‘ =M*& E %1 !U*DG D ( E * 7 *7
A @S !7 / & + ” / %- U*DG :S < ) 58< %*A ‘ P/
Max Z =CFLSP (1+α)−FTn −∑∑∑nLFjM j (CFjm)t .x jmt (i)
i= =1 t EFj m=1 1+α
n
.7 ‘ CFLSP =∑CFj+ %S
j=1

U*( 2 & !/ U*( % E B / = D0A % ft *D 7 J;9 C / / & B / v* 1/ !< / & ‘/ {;8 TDA .*7 ‘ G ‘9>- ‘\”A !G ‘1@- *7 ‘ TG ‘+& D- \”A G *A
T* `~~ Pe × PS A ‘+& D- .8/ ‘ 4″8 = D- / / T* #A X< .7 ‘ – D- PS ; o Pe @+DF , .*7 ‘ 8&, 2 Pc 4D8 ‘\”A @+DF %* T* @S *7 {;8 = *A ‘\”A 1, !’, 4*( = ( ^< ‘+& D- # Pm 4D8 C>- @+DF .S ‘ *-* & *7 ‘ A 1 0A / . ‘ =DF – D-
*A o Pr *7’ *A – T * `~~ Pr × PS
# A C A ‘ B 8 ?8*@ .< G .*7 ‘ :(*8 !*D = *A 7

0* * 1 / .+ T* / < N*M # 7 I T* 8E<
B ; % n .</ & A n % 2n
%9 T* ‘>8 % n & /*E Q8E & ‘- *, 8/ / & ‘- / / % < 8&, ( T* % # j ‘8 &
I T* # .< 7 J;9 T j + n
.< CD = ( I = (A1I ,…, AnI ,M1I ,…,M nI )

$234 5″6 .+ < 7 58< ‘\”A @+DF B >9 ?8*@ & % o7 [w] #DA/ 6<*A BA @+DF # !

67 Y )A >- .< 7 8&, 0 [€]
, .< 7 <*A
 Pa

,…,An

,…,Mn2) Pa1 =(A11,…,An1,M11,…,Mn1) ‘&QA F .7 ‘\”A @+DF 7 {;8
*A [1,n −1] !7 r1 < r2 v7 # r2 r1p M & .8/ \”A v” J;9 *7 ‘
CH

,…,ArC

C ,…,AnC1,M1C1,…,M

C ,
CH

,…,ArC12,ArC1+21,…, MrC,…,MrCC ,…,MnC1)
.*7′ *A ACr22,ACr22+1,…,ACn2,M1C2,…,MrC12,MrC12+1,…,MrC22,MrC22+1,…,MnC2)
,…,A,…,A 4 &
b < a=r1 +1,…,r2 ! M aC AaC1 = Ab2 # mD/ # mD/ .7 Ab,…, AaC < ‘ #80*
‘ #80* b a AaC1 = Ab1 %*A ‘ 9 ‘”\ .7 Ab1∈ <
CH2 = (A1C2,…,ArC12,ArC1+21,…,ArC22,ArC22+1,…,AnC2,M1C2,…,MrC12
.*D :A 1 ,MrC1+21,…,MrC22,MrC22+1,…,MnC2)
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017

/ & >A # .7 = ( >- B # % .7 ‘ T*< F*DG / & !9 y *7 ‘ {;8 & B ‘&QA N*Q / & N>- ‘0 ‘&QA N*Q %S !’&QA B J Q;A & yz< ? ‘ X”F *+- ‘>A % A # .? ‘ P[ r F*DG 7 {;8 S& # % .*7 ‘ 0A r F*DG %7 (FS) *+- >- ‘0 < 7 =M & %S < y .7 ‘ (BS) X”F >- @ # ‘ !X”F *+- G B T] @0 ‘I1 X AA PnE d F*DG / & *2 # . .? ‘ &u 4 F*DG / & F*DG >S {;8 / %S #0D % #80* @ %
A # J Q;A & *7 ‘ S 9
. ‘ ! 9 / & + 0

. !” # .
n B / B ‘7 {*- / CD ‘7 ‘*A B ! 4 D( .*7 ‘ 58< *sF y & / %S < 9 6 3
.*7 ‘ TG $ / & C 9 / & ” T D( .*7 ‘ “/ & ” D( # / %9 < 7 = 09A *sF n ! T “/ # n + j *\ < 4 D( / & TG .< & # j TG / %9 # *sF

$%”& ‘( )* . )” {*- s& )” B 58< * ?8*@ < #0D @ % . , ‘ N*M ‘&QA N*Q @ < 7 *A ?8*@ 6<*A #ES .7 87 ?8*@ – ‘8/7 *@m /

,- .+
/ .+ *) D- /T* !>9 B 8 ?8*@ < *< *A $ 58< ‘&QA A ‘ “S T* *A S& .S ‘ *-*
G ‘7 T* !7 ‘ 1 *; D-
2 ?8*@ ‘+& = %*F D- .*7
*A /@+DF 58< %S – = *7’ 8&, – % #80* ‘- ! & B 0*) – % #A ‘f*\ ” %- #8,1 & %S 7 *A ” %- #80* !7 87 6<*8 1 & / ” %- . ‘ J Q;A Xu ” u & %D/ / ” / %-
* ` D7 4- .S ‘ < !*7 ‘ (RR) S
.< 7 J;9 / /8 X A [,

.
Data Set LSP & PEO
RR α
1 1.25 0.01
2 1.25 0.05
3 1.50 0.01
4 1.50 0.05
?8*@ / 6<*A !=I 7 :A / B /
h~*`~* b *d =bw~~ U*DG [ 7 = `~
.< 8&[ N*M ?8*@ / < E„ / * 7 ?8*@ ” H8 r d D7 4 / & A 4 %*8< ./ ‘ %9 :+8; E J Q;A !T %*8< ./ ‘ %9 / G ] 4- Y ) / ‘ %9 4 /8 8& ?8*@ / ‘A& A T*< %*8< .7 ‘ ` D7 7 8> {*- % Y&* @ ?8*@ ” P/ A #8> ” 6<*8 T> %*8< ./ ‘ %9 !< 6<*8 ?G %*8< ./ ‘ %9 `~ = =M 7 =M {*- #8> ?8*@ / ‘ P %9 1 ES %*8< / ‘ CD ?8*@ %D/ 6<*A
# =M {*- #8> Y+) P 6<*8 / .7 ‘ ?8*@
1268732040128Downloaded from ijiepm.iust.ac.ir at 16:24 IRST on Saturday November 4th 2017



قیمت: تومان


پاسخ دهید