Đ
ĐẠ
ẠI
I
H
HỌ
ỌC
C
Q
QU
UỐ
ỐC
C
G
GI
IA
A
H
HÀ
À
N
NỘ
ỘI
I
T
TR
RƯ
ƯỜ
ỜN
NG
G
Đ
ĐẠ
ẠI
I
H
HỌ
ỌC
C
C
CÔ
ÔN
NG
G
N
NG
GH
HỆ
Ệ
N
NG
GU
UY
YỄ
ỄN
N
H
HỮ
ỮU
U
M
MÙ
ÙI
I
T
TH
HU
UẬ
ẬT
T
T
TO
OÁ
ÁN
N
V
VÀ
À
C
CÁ
ÁC
C
B
BÀ
ÀI
I
T
TO
OÁ
ÁN
N
L
LỊ
ỊC
CH
H
B
BI
IỂ
ỂU
U
L
LU
UẬ
ẬN
N
Á
ÁN
N
T
TI
IẾ
ẾN
N
S
SĨ
Ĩ
C
CÔ
ÔN
NG
G
N
NG
GH
HỆ
Ệ
T
TH
HÔ
ÔN
NG
G
T
TI
IN
N
H
Hà
à
N
Nộ
ội
i
–
–
2
20
01
13
3
1
Đ
ĐẠ
ẠI
I
H
HỌ
ỌC
C
Q
QU
UỐ
ỐC
C
G
GI
IA
A
H
HÀ
À
N
NỘ
ỘI
I
T
TR
RƯ
ƯỜ
ỜN
NG
G
Đ
ĐẠ
ẠI
I
H
HỌ
ỌC
C
C
CÔ
ÔN
NG
G
N
NG
GH
HỆ
Ệ
N
NG
GU
UY
YỄ
ỄN
N
H
HỮ
ỮU
U
M
MÙ
ÙI
I
T
TH
HU
UẬ
ẬT
T
T
TO
OÁ
ÁN
N
V
VÀ
À
C
CÁ
ÁC
C
B
BÀ
ÀI
I
T
TO
OÁ
ÁN
N
L
LỊ
ỊC
CH
H
B
BI
IỂ
ỂU
U
C
Ch
hu
uy
yê
ên
n
n
ng
gà
àn
nh
h:
:
K
Kh
ho
oa
a
h
họ
ọc
c
m
má
áy
y
t
tí
ín
nh
h
M
Mã
ã
s
số
ố:
:
6
62
2
4
48
8
0
01
1
0
01
1
L
LU
UẬ
ẬN
N
Á
ÁN
N
T
TI
IẾ
ẾN
N
S
SĨ
Ĩ
C
CÔ
ÔN
NG
G
N
NG
GH
HỆ
Ệ
T
TH
HÔ
ÔN
NG
G
T
TI
IN
N
N
NG
GƯ
ƯỜ
ỜI
I
H
HƯ
ƯỚ
ỚN
NG
G
D
DẪ
ẪN
N
K
KH
HO
OA
A
H
HỌ
ỌC
C:
:
1
1.
.
P
PG
GS
S.
.
T
TS
SK
KH
H
V
Vũ
ũ
Đ
Đì
ìn
nh
h
H
Hò
òa
a
2
2.
.
P
PG
GS
S.
.
T
TS
S
H
Ho
oà
àn
ng
g
X
Xu
uâ
ân
n
H
Hu
uấ
ấn
n
H
Hà
à
N
Nộ
ội
i
-
-
2
20
01
13
3
2
LỜI CẢM ƠN
Về phía cá nhân, tác giả xin bày tỏ lòng biết ơn chân thành tới PGS.
TSKH Vũ Đình Hoà, PGS. TS Hoàng Xuân Huấn đã tận tình hƣớng dẫn tác
giả trong quá trình hoàn thành luận án. Tác giả cũng chân thành cảm ơn TS
Phạm Thọ Hoàn, Giám đốc Trung tâm khoa học tính toán Trƣờng Đại học Sƣ
phạm Hà Nội đã giúp đỡ tác giả rất nhiều trong quá trình thử nghiệm tại
Trung tâm.
Về phía tập thể, tác giả xin chân thành cảm ơn Bộ môn Khoa học máy
tính, Khoa Công nghệ thông tin, Trƣờng Đại học Công nghệ; Bộ môn Khoa
học máy tính, Khoa Công nghệ thông tin, Trƣờng Đại học Sƣ phạm Hà Nội
đã hết lòng ủng hộ và tạo điều kiện thuận lợi cho tác giả trong thời gian hoàn
thành luận án.
Cuối cùng, tác giả vô cùng biết ơn các bàn bè và ngƣời thân trong gia
đình vì sự cổ vũ to lớn của họ trong suốt thời gian hoàn thành luận án này.
Hà Nội, tháng 09 năm 2013
Nguyễn Hữu Mùi
3
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết
quả đƣợc viết chung với các tác giả khác đều đƣợc sự đồng ý của đồng tác giả
trƣớc khi đƣa vào luận án. Các kết quả nêu trong luận án là trung thực và
chƣa từng đƣợc ai công bố trong các công trình nào khác.
Tác giả
Nguyễn Hữu Mùi
4
MỤC LỤC
LỜI CẢM ƠN ................................................................................................... 2
LỜI CAM ĐOAN ............................................................................................. 3
MỤC LỤC ......................................................................................................... 4
DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT .......................................... 8
DANH MỤC CÁC BẢNG................................................................................ 9
DANH MỤC CÁC HÌNH VẼ ........................................................................ 10
MỞ ĐẦU ......................................................................................................... 12
CHƢƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI
TOÁN LẬP LỊCH JOB SHOP ....................................................................... 19
1.1. Thuật toán di truyền cổ điển ................................................................ 19
1.1.1. Cấu trúc của thuật toán di truyền cổ điển ..................................... 20
1.1.2. Một thủ tục đơn giản cho thuật toán di truyền cổ điển ................. 24
1.2. Các lớp bài toán P, NP, NPC và NP-hard ............................................ 25
1.2.1. Các lớp bài toán P và NP .............................................................. 25
1.2.2. Các lớp bài toán NPC và NP-hard ................................................ 25
1.3. Tổng quan về bài toán lập lịch job shop .............................................. 26
1.3.1. Bài toán lập lịch job shop .............................................................. 26
1.3.2. Các tiếp cận chính xác .................................................................. 29
1.3.3. Các tiếp cận gần đúng ................................................................... 32
1.3.4. Tổng kết đánh giá chung về các tiếp cận cho JSP ........................ 50