I H C QU C GIA TP.HCM
I H C BÁCH KHOA
…………o0o…………

C KHÁNH

XÂY D NG MƠ HÌNH T
TH I GIAN – CHI PHÍ – NHÂN L C CHO D

ÁN

XÂY D NG ( NG D NG THU T GI I GA-PSO VÀ
LÝ THUY T M )

Chuyên ngành :

CÔNG NGH VÀ QU N LÝ XÂY D NG

Mã s :

60.58.90

LU

Thành ph H Chí Minh, tháng 02

4


CƠNG TRÌNH

C HỒN THÀNH T I
I H C BÁCH KHOA

I H C QU C GIA TP.HCM

Cán b

ng d n khoa h c: PGS.TS. Ph

ng Luân ................................

.............................................................................................................................
Cán b ch m nh n xét 1: PGS.TS.

ng .....................................

.............................................................................................................................
Cán b ch m nh n xét 2: TS.

Công T nh ..................................................

.............................................................................................................................
Lu

cb ov t i

ngày 15 tháng 02

iH


2014.

Thành ph n H

m:
c Long

2.
3.

ng

4.

nh

5. PGS.TS Ph

ng Luân

CH T CH H

NG

C LONG

NG KHOA
K THU T XÂY D NG



IH

C NG HÒA XÃ H I CH
I H C BÁCH KHOA

T NAM

c l p - T do - H nh phúc

NHI M V LU
H tên h c viên:

10080284

C KHÁNH
– 02 – 1986

Chuyên ngành: Công ngh và qu

I.

ng Nam
ng

:

60.58.90

TÀI:
Xây d


i gian – chi phí – nhân l c

cho d án xây d ng ( ng d ng thu t gi i GA-PSO và Lý thuy

)

II. NHI M V VÀ N I DUNG:
ng d ng thu t gi i k t h p GAhình t

tm

c tiêu th i gian – chi phí –

d

ng m t mô
c cho các d

n s không ch c ch n trong chi phí c a các d

án.
xu t v i nh ng nghiên c
ng mơ hình thành m
quy t các bài toán ti

s d

gi i


c th .

III. NGÀY GIAO NHI M V : 24/06/2013
IV. NGÀY HOÀN THÀNH NHI M V : 22/11/2013
V. CÁN B

CÁN B

NG D N: PGS.TS. PH M H NG LUÂN

NG D N

CH NHI M
B

PGS.TS. PH M H NG LUÂN

O

C LONG

NG KHOA
K THU T XÂY D NG


L IC
Lu

cu i cùng th hi n nh ng n


h c viên trong su

c và c g ng c a

c t p và nghiên c u v
n tồn th

Thi cơng và Qu

ng –

i h c Bách Khoa thành ph H Chí

y và truy
viên theo h c t

t kinh nghi

c

ng. Nh ng ki n th c, kinh nghi

ng n n t

c và nghiên c u sau này.
Xin g

ic

n PSG.TS. Ph


t

n h c viên trong su

Nh

i th
c hi

n c a th y góp ph

ng vào thành cơng

c
Và cu
viên, c
Xin c

ic

ng

tr h c viên trong su
tc

ct

i!


TP. H
i th c hi


TÓM T T LU
Th

u t quan tr ng c n ph

d

t

i

i nhu n, nhà th u c n ph i c g ng gi m thi

th i th i gian và chi phí d án. Ngồi ra, các v
cơng tác ph

ng

n vi c t
n ph

Trong nh

u nghiên c

quy


i th i gian – chi phí hay t

c. Tuy nhiên, các nghiên c u này ít nhi

c ti

gi i

i gian – chi phí –

t

u t n t i nh ng h n ch .

t thu t gi i k t h p gi a thu t gi i di truy n (GA) và
thu t gi i t

n th

tiêu th i gian – chi phí –

cs d

gi i quy t bài tốn t

c trong các d

kh


ng.

t

xu

ng th i th i gian – chi phí; và

ng v i t

nh cách th c th c hi n d

m b o m c bi

p nh

h p s khơng ch c ch

tích

ng g p trong chi phí c a các d

hình b ng cách áp d

tm

ng vào mơ
ng chi phí d án.

c vi t b ng ngơn ng

c ti n hàn

ng, và hai ví d

so sánh hi u qu c

t qu ch ra r
nhi

c

ng h p.

C KHÁNH -

xu t so v i nh
xu t t

t


ABSTRACT
ruction

–
-

-cost-

– cost –


C KHÁNH -


L
c Khánh, xin cam k t r ng trong quá trình th c hi
"

ng mơ hình t

i gian – chi phí –

( ng d ng thu t gi i GAnghiên c

c cho d

t m )" các s

ng

u tính tốn và k t qu

c th hi n hoàn toàn trung th

c công b

b tk

nghiên c u nào khác (ngo i tr các bài báo c a chính tác gi ). Tơi xin ch u trách
nhi m hoàn toàn v nghiên c u c a mình.


i th c hi

c Khánh

C KHÁNH -


M CL C
M

U ______________________________________________________________

tv
M c tiêu nghiên c u

3

Ph m vi nghiên c u

3

ki n c a nghiên c u

3

1.4.1 V m t h c thu t ......................................................................................................... 3
1.4.2 V m t th c t .............................................................................................................. 3
T


_________________________________________________________ 5
ng

2.1.1

5

......................................................................... 5

2.1.2

m

....................................................................................... 6

Các nghiên c u v bài toán t

ng

7

2.2.1

.............................. 8

2.2.2

...................................... 11

2.2.3


........................... 13

2.2.3.1 Thu

-

........................................ 14

2.2.3.2 Thu

-

2.2.3.3 Thu
2.2.3.4 Thu

............ 20
-

... 23

th
............................................................... 24

Các nghiên c u v bài toán t
2.3.1 Thu

c tiêu
-


2.3.2 Thu

............................ 27
-

............................................................................................................... 32
2.3.3
.................................................................................................. 38

C KHÁNH -

Trang i


Các nghiên c u

ng Lý thuy t m trong t

ng
38

Các nghiên c u v bài toán t

ng t i Vi t Nam

LÝ THUY T ________________________________________________
Thu t gi

m


3.1.1 Thu

........................................................................................................ 49

3.1.2

m

Lý thuy
3.2.1

.......................................................... 49

m ng
m

50
............................................................................................... 50

3.2.1.1 Th

m

.................................................................... 50

3.2.1.2
3.2.2

............................................ 51
m


............................................................................ 52

3.2.2.1

........................................................................................... 52

3.2.2.2
3.2.3

th

........................................................ 53

m

................................................................................. 55

3.2.3.1
3.2.3.2

.................... 55
u ch

m

c........................................................ 56

Lý thuy t thu t gi
3.3.1

3.3.2

u .................................................................................................................... 56
th

a thu

............................................... 58

3.3.2.1

............................................................................................. 58

3.3.2.2

............................................................... 59

3.3.2.3

............................................................................. 59

3.3.2.4

......................................................................................... 61

3.3.2.5

.................................................................................................................. 62

Thu t gi

3.4.1

-II
a thu

3.4.2 Thu

tr

C KHÁNH -

................................................. 64
-

........................ 65

Trang ii


3.4.3

............................................... 67

3.4.4

c ch

.......................................................................................... 68

Lý thuy t thu t gi i t

3.5.1

n th

........................................................................................................ 68

3.5.2

th

a thu

Thu t gi i t

............................... 70

n th

Logic m

73

3.7.1

u .................................................................................................................... 73

3.7.2 T

.................................................................................................. 73


3.7.3

tm

3.7.3.1

.............. 75
............................................................ 75

3.7.3.2

t

-

................................................................................................... 75

3.7.3.3 T

....................................................................... 75

3.7.3.4 T

............................................................. 75

3.7.3.5

m

...................................................................................... 76


3.7.3.6

............................................................ 77

3.7.3.7 Lu t m

...................................................................................... 77

3.7.4

........................... 78

3.7.4.1

.............................................................. 78

3.7.4.2 H

........................................................................... 78

3.7.4.3 Bù c a t
3.7.5

–
tc at

................................................. 79

...................................................................................... 79


3.7.6

m ............................................................................................... 80

3.7.7

................................... 81

tv
4.1.1 D
4.1.2

MƠ HÌNH T

C TIÊU ________________________________ 83

bài tốn

83
........................................................................................................ 83

u ra .......................................................................................................... 83

C KHÁNH -

Trang iii


Mơ hình t


i gian –

–

4.2.1 H th

........................................................... 83

4.2.1.2 H th

m

4.2.2 H th

–

4.2.2.1

.................................................................... 84
–

thu

................................................................. 85

-

4.2.2.4


..................................................................... 84
................................................................... 84

c th

4.2.2.2

–

c...................................................................................... 93

4.2.3.1

c th

4.2.3.2

.................................................................... 93
................................................................................. 94

thu

-

c ................................................ 96

4.2.3.4

c................................................... 97
C VÀ VÍ D ÁP D


i thi

................................................................ 99

5.1.2

u ra c

................................................................. 102

1 ........................................................................................................................ 105

5.2.1.1 D

.................................................................................................. 105

5.2.1.2 K

t

5.2.1.3 K

t

5.2.2

________________

c


5.1.1

5.2.1

.............................. 86

................................................................................................... 91

4.2.3 H th

4.2.3.3

83

.................................................................... 83

4.2.1.1 H th

4.2.2.3

c

–

............................................................... 108

c .................................................................................. 109

2 ........................................................................................................................ 112


5.2.2.1 D

.................................................................................................. 112

5.2.2.2 K

t

5.2.2.3 K

t

–

............................................................... 114

c .................................................................................. 121
kh

C KHÁNH -

xu t

Trang iv


K T LU N VÀ KI
K


_______________________________________

n

6.1.1

................................................................................................. 127

6.1.2

u ................................................................................... 128

6.1.2.1 V m t h c thu t ............................................................................................... 128
6.1.2.2 V m t th c t .................................................................................................... 128
Ki n ngh
TÀI LI U THAM KH

N ________________________________________

C KHÁNH -

Trang v


DANH M C CÁC B
B

Các thu t gi

B


Các nghiên c u v thu t gi

B

U

c tiêu ph

gi a hai công tác A và B

B

s

B

i các nghiên c

B

c

s

B

i các nghiên c

nh, chi phí


gián ti
B

i chi phí gián ti

B

i chi phí gián ti

B

i nghiên c u c

C KHÁNH -

n

Trang vi


DANH M C CÁC HÌNH V
Quan h

gi a th i gian và chi phí trong nghiên c u Leu
trong nghiên c u Zheng và

chi phí trong nghiên c u c
i r c hóa s


th i gian trong nghiên c u c a Zahraie và

cs
hi n công tác trên nút
th i gian – chi phí tuy n tính
th i gian – chi phí tuy
th i gian – chi phí r i r c
th i gian – chi phí phi tuy n

nguyên

n nhi
thu t gi i NSGAtr i
a kho ng cách t
a thu t gi i PSO
t gi a t
i và t

và t p rõ v chi u cao
khôn

n ngôn ng v tu i
a hai t

C KHÁNH -

Trang vii


p c a hai t

at

A
t nhi

c th (hay cá th

u trúc v n t c c

t cá th

thu t gi i GA-PSO t
t nhi

i gian – chi phí

th i gian – chi phí

c th (hay cá th

thu t gi i GA-PSO t

c
c
a

u ra c
tính tốn t

c


i gian –
c t cơng c
ct
c t công c
ct

i gian –
c

và Zhang và Afshar

c

và Zhang và Afshar

c t công c

v

gi i h
ct
gi i h
c t công c

v

gi i h
ct
gi i h


C KHÁNH -

Trang viii


c t công c

v

gi i h
ct
gi i h

C KHÁNH -

Trang ix


DANH SÁCH T
GA

:

ACO

:

PSO


:

GA-PSO :

VI T T T

– Thu t gi i di truy n
– Thu t gi i t
– Thu t gi i t

n
n th

Thu t gi i k t h p gi

et al.

:

và các

ng tác gi

NST

:

Nhi m s c th

CN


:

C KHÁNH -

Trang x


M

U

tv
n n n kinh t
d

p nhi

t trong nh ng ngành ch u

n nh

ng s n hay nh ng c

c nh ng th thách r

t n t i và phát tri n.
kh
nh


, các công ty b t

u ki

i các công ty c n ph i không ng ng

chuyên môn

mb

ng

cc

tác qu

y m nh các bi n pháp qu n

i nhu n c n thi t. Do v y, công

t trong s nh ng công tác c n ph

Công tác qu

t công tác quan tr ng trong m i d

bao g m các quá trình ho
ngu

c


c chú tr ng.

nh, t ch

o và ki m sốt các cơng vi c và

hồn thành các m

nh t c a qu

ra.

p ti

ng,

t trong nh

c quan tr ng

(k ho ch) d án, v i m c tiêu

mb od

án hoàn thành trong th

c thành

qu mong mu n. T

nh

mc

c ti

i quan h

ti

mà m c tiêu quan tr ng

i gian, c c ti

c – tài nguyên hi u qu nh t [1].
v

p ti

d ng ngu n

, m i quan h th i gian – chi phí –

n c n ph

c chú tr ng gi i quy t

p

c a m i d án.

Trong m i quan h

, mu n rút ng n th i gian d án thì ph

vi c hàng ngày, ph i tuy n m

ng, ph i thuê thêm thi t b

u này s d

. ìv yc

th i gian và kh

kinh phí d án [2].
n ph i

quá kh

nh

c gi a kh
ng th i, vi c s d

m b o ngu n

ng c
c di n ra thu

i nh t. Do v


i gian – chi phí –

TCRO) mà b t c

i p ti

C KHÁNH -

t

m b o cho vi

ng

c n ph

t

t t nh t và phù h p nh t v

a ch

cc
c

c
c

p ti


ng th i ba y u t th i gian – chi phí –

tốn t

n

c

p ti
-cost-

n ph i gi i quy t.

Trang 1


Nh

truy n th

gi i quy t các bài tốn t
mơ hình t
ra quy

n thi t ph i nghiên c

i gian – chi phí –
nh


nh ng nhà ho

ng nh ng

c nh m cung c p các công c h tr
nh

a ch n k ho ch th c

hi n d án cho phù h p nh t.
u nghiên c u v
v t

i th i gian –

mơ hình t
c

– cost –

c tiêu th i gian – chi phí –

c

,

– cost

:


tìm ki m

ch tốn h c hay các

thu t gi i di truy n (

- GA), thu t gi i t

- ACO), thu t gi i t

n (Ant
swarm o

-

Tuy nhiên, các mơ hình này ít nhi u

u t n t i nh ng h n ch

ch tìm

t ch

ch

t hàm

m c tiêu duy nh t, ch

n th (


mb

áp d ng v i nh ng d án quy mô nh hay c n th i
c k t qu t

Thu t gi i GA-

h p gi a thu t gi i di truy n (GA) và thu t gi i t
d

t

t thu t gi i k t
n th

c a c 2 gi i thu t này. Thu t gi i này
t

mt n

ck v

tìm

v i th i gian tính tốn

i

c tiêu.

ng th i, trong các d
th

ng c a r t nhi u y u t không ch c ch

v

c hi

ng, …

vào trong mơ hình t
b
nhi

ng; th i gian và chi phí c a m

, vi c tích h p s không ch c ch n này

th i gian – chi phí –

nh c

c

vào trong mơ hình t

ơ hình ti n
c s d ng r t


n s không ch c ch n. Nh ng mơ hình

này cho k t qu khá t t trong nh ng d

nhi u nghiên c u

n thi t.

k thu t mô ph ng

gi i quy t

cc

i ti

i

mb

áp d ng Logic m
th i gian – chi phí

C KHÁNH -

nh ng gi i pháp
i pháp t

[3].
khơng ch c ch n


c nh ng k t qu kh quan.

Trang 2


T

c g ng
c

ng m t mơ hình t

th i gian – chi phí –

n s khơng ch c c a các bi

i gian h i t

ng cách áp d ng thu t gi i GA-

tm .

M c tiêu nghiên c u
ng d ng thu t gi i k t h p GAhình t

và

tm


x

ng m t mơ

c tiêu th i gian – chi phí –

khơng ch c ch n v

a các d án.

ng mơ hình thành m
quy t các bài tốn ti
Ph

ns

c

s d ng

gi i

c th .

u

Gi i quy t bài tốn v
Ch

m c a nhà th u thi cơng.


n s khơng ch c ch n v chi phí.
i quan h gi a th i gian – chi phí –

i r c.

Trong y u t tài nguyên, nghiên c u ch

Ch

ny ut

i quan h Finish –

c (c th

a các công tác.

ki n c a nghiên c u
V

t h c thu t

Gi i thi u m t thu t gi i m i k t h p gi a thu t gi i di truy n (GA) và thu t
gi i t

n th

gi i quy t bài tốn t


chi phí –

ng.

ng th y trong các d
V

c tiêu th i gian –

tích h p s khơng ch c ch n
ng vào mơ hình.

t th c t

Cung c p cho các nhà qu

m

c hi n d
u ki n gi i h n v
án
cc ad

:

i gian

ng

c c a nhà th u.


c

ng
p nh t trong

ng th i, ng v i t

c th c hi n sao cho bi
t.

C KHÁNH -

Trang 3


Cung c p m t công c h tr ra quy

các nhà qu

a ch n

p.

C KHÁNH -

Trang 4


T NG QUAN

l p ti
Ti

thi công

ch

xây d ng

ng
nh nh m

u thi t k

bi n pháp t

nh các yêu c u sau [4,5] :

Trình t ti n hành các cơng tác.
ràng bu c gi a chúng v i nhau.
Th i gian hoàn thành t ng h ng m c và toàn b cơng trình.
Nhu c u v

c c n thi t cho thi công t i nh ng th

Ti

ch

nh.

ch gi a th c

t s n xu t và k ho
quy

m nh

i cán b ch

ng

ng

u ch nh thi công [5].
b

i ti

[3,4]:
Gantt)

Ti

xiên –
m ng

nh
Ti

n

: bao g m ti
m

m

m ng b t

p.

ma tr n
c s d ng ph bi

m

m
thanh ngang
xu
trong d án, th i gian th c hi n và các thông s
i d ng bi

ngang. Bi

c bi u di n b ng các thanh

ngang ph n ánh m i

th i

gian gi a các bi n c c a m t d án [3].
[3]:

n, tr c quan, d nh n bi t công vi c.
[4,5]:
Không th hi n rõ và ch t ch m i quan h v công ngh và t ch c gi a các
công vi c.

C KHÁNH -

Trang 5


Không ch ra nh ng công vi c quan tr ng quy
gian c a ti

nh s

i

.
c q trình thi cơng nh ng cơng trình ph c t p.

D b

c khi quy

n.

cs

ng c a ti


th c hi n t ng công vi

n ti n

chung.
Trong th i gian thi công n u ti

c tr

gi i pháp kh c ph c.
ng
kh c ph c nh

mc

d án ph c t

thanh ngang, trong nh ng d án

i ta s d

thi cơng.

m ng coi d

c trình di

m ng

p ti


t t p h p các công vi

id

i nhau,

th g m các nút và c

ch m

gi a

các công vi c [3].
c

ng [4,5]:

Cho th y m i qua h ch t ch v công ngh , t ch c gi a các công vi c.
Ch ra nh ng công vi c quan tr ng, quy

n th i h n hồn thành cơng

trình (các cơng vi c này g
t p trung ch
Lo i tr

i qu

t


m.
c nh ng khi m khuy t c a

Gi m th i gian tính tốn do s d
u hành ti

thanh ngang.
nt

p, tính, qu n

.

m

a nhi

ng
giá d

và

m ng cơng vi c
[3].
th trình bày k ho ch c a d án

c phát tri n nh

-1958 b


C KHÁNH -

Trang 6


thi t r ng th i gian c a các cơng vi

nh chính

xác và b t bi n trong q trình th c hi n d án [3].
b
Hoa K

c phát tri

u tiên b i H

n ch t c

u t không

ng th i gian th c hi n c a các cơng vi c và th i gian hồn
thành d

ng cơng vi

hồn thành chính xác d
khác nhau.


d

nh th i gian

n vi c th i gian hoàn thành d

tin c y

t khi k ho ch bao g m nh ng y u t

nh thì vi c hồn

u nhiên.
ho

i ta d a

xác xu t. [5].

Nh

truy n th ng

xét vi c

trên

n ch

nh ng gi i h n v tài nguyên vào các công tác trong d án ho c không

kh

t ki m th i gian và chi phí b

ho c thơng qua vi

u ch

c [6].

a nh ng công c này ch
tác mà không

i ti
ng th i, v

t p trung vào t

t

ng
t ic

toàn d án.
ng th i th i gian – chi phí –

2.2 Các nghiên c u v bài tốn t

d án


các cơng

nh ng công c này
c [ ].

xây d ng

c tiêu nghiên c u,

t

ng có th

ng sau:
i th i gian –

-cost

n, d án ph
c n ph

y nhanh ti

-

)

c m t th
d


s

c và
i hoàn thành m t

i m i công tác, th i gian hoàn
ng và th i gian hoàn thành rút ng
ng và chi phí rút ng n cho cơng tác
nc am

bao g

ng b

,
a thi t

, vi c rút ng n th i gian c a m t cơng tác s

phí [8]

c rút ng n và m c

C KHÁNH -

Trang


rút ng n c


v i cùng m t th i gian hoàn thành d án, chi
p nh t.

tài nguyên

)
tài nguyên c g ng s p x

i trình t các cơng tác c a d

m t s tài nguyên b gi i h

c s d ng hi u qu trong khi

v n gi cho vi c kéo dài không th tránh kh i c a d án

m c t i thi u [9].

ng tài nguyên c g ng gi m thi u s bi

t ng t gi a

a bi

s d ng tài nguyên trong su t th i gian d án

[9]. T

u s d ng tài nguyên qua


nc a

d án [10].
Nh ng mơ hình k t h p các tiêu chí trên.
u,

m

(

t

ng có th

.

(

).

vào s

ng th i,

t

ng có th
T

tm


T
Lu

i và

c a nghiên c u.
(
tìm ki m
gi i quy t v

, v i các quy t

nghiên c u ph bi n nh t v
trong

)

d a trên nh ng kinh nghi m trong quá kh
i ra quy
c Zhou

t ra. Nh ng
[11]

c p

c a mình :

C KHÁNH -


Trang 8