ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐỖ ĐỨC ĐÔNG

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN
LẬP LỊCH SẢN XUẤT

LUẬN VĂN THẠC SĨ

Hà Nội - 2008


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Đỗ Đức Đông

PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN
LẬP LỊCH SẢN XUẤT

Ngành: Công Nghệ thông Tin
Mã số: 1.01.10

LUẬN VĂN THẠC SĨ
NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS.TS. HOÀNG XUÂN HUẤN

Hà Nội - 2008





MỤC LỤC

MỤC LỤC ....................................................................................................... 12
DANH SÁCH CÁC HÌNH VẼ ....................................................................... 14
DANH SÁCH CÁC BẢNG ............................................................................ 15
BẢNG TỪ VIẾT TẮT .................................................................................... 16
TỪ KHÓA ....................................................................................................... 17
MỞ ĐẦU ......................................................... Error! Bookmark not defined.
CHƢƠNG 1 : TỐI ƢU HÓA ĐÀN KIẾN VÀ ỨNG DỤNGError! Bookmark not def
1.1 Lịch sử phát triển ................................... Error! Bookmark not defined.
1.1.1 AS và bài toán TSP ......................... Error! Bookmark not defined.
1.1.2 Các cải tiến của AS ......................... Error! Bookmark not defined.
1.2 Phƣơng pháp tối ƣu hóa đàn kiến .......... Error! Bookmark not defined.
1.2.1 Bài toán tổng quát ........................... Error! Bookmark not defined.
1.2.2 Thuật toán tổng quát........................ Error! Bookmark not defined.
1.2.3 Đặc tính hội tụ của ACO................. Error! Bookmark not defined.
1.2.4 Các thuật toán và các tham số ......... Error! Bookmark not defined.
1.3 Một số nguyên lý ứng dụng tối ƣu đàn kiếnError! Bookmark not defined.
1.3.1 Thông tin học tăng cƣờng ............... Error! Bookmark not defined.
1.3.2 Các thông tin heuristic .................... Error! Bookmark not defined.
1.3.3 Kết hợp tì m kiếm đị a phƣơng ......... Error! Bookmark not defined.
1.3.4 Cân bằng giữa sự khai thác và sự khám pháError! Bookmark not defined.
1.3.5 Sử dụng danh sách ứng cử viên ...... Error! Bookmark not defined.
1.3.6 Một số ví dụ .................................... Error! Bookmark not defined.
CHƢƠNG 2 : BÀI TOÁN LẬP LỊCH SẢN XUẤT VÀ CÁC PHƢƠNG
PHÁP GIẢI CHÍNH.............................................. Error! Bookmark not defined.
2.1 Giới thiệu bài toán lập lịch sản xuất (Job shop scheduling - JSS)Error! Bookmar
2.2 Các cách tiếp cận truyền thống .............. Error! Bookmark not defined.

Hình 6: Một hành trình của kiến trên đồ thị cấu trúc Error! Bookmark not defined.
Hình 7: Lƣợc đồ thuật toán ACO giải bài toán lập lịch sản xuất Error! Bookmark not


DANH SÁCH CÁC BẢNG
Bảng 1: Bài toán lập lịch sản xuất 3 công việc thực hiện trên 3 máy Error! Bookmark

Bảng 2: Bài toán lập lịch sản xuất 10 công việc thực hiện trên 10 máy Error! Bookmar
Bảng 3: Bài toán gia công trên 2 máy ............ Error! Bookmark not defined.

Bảng 4: Bài toán lập lịch sản xuất gồm 2 công việc thực hiện trên 3 máy Error! Bookm

Bảng 5: Độ phức tạp của các thuật toán MMAS, SMMAS, MLAS Error! Bookmark n
Bảng 6: Các tham số sử dụng cho các thuật toán ACO Error! Bookmark not defined.

Bảng 7: Kết quả thực nghiệm MMAS với 4 bộ dữ liệu Orb1 đến Orb4 Error! Bookmar

Bảng 8: Kết quả thực nghiệm MMAS cho các bộ dữ liệu chuẩnError! Bookmark not d
Bảng 9: So sánh kết quả tốt nhất sau 10 lần chạy của MMAS, SMMAS và
MLAS .................................................................... Error! Bookmark not defined.
Bảng 10: So sánh kết quả trung bình sau 10 lần chạy của MMAS, SMMAS
và MLAS .............................................................. Error! Bookmark not defined.


BẢNG TỪ VIẾT TẮT

STT

Từ viết tắt


Optimization

8

Avg

Average

9

TSP

10

JSS

11

g-best

global-best

12

i-best

iteration-best

Ant Colony Optimization
(Tối ƣu hóa đàn kiến)

rules of Ant Colony Optimization approaches for the job shop scheduling problem. In:
the 11th Pacific Rim International Conference on Multi-Agents, pp. 153–160 (2008).
[5] M.Dorigo, V.Maniezzo and A.Corloni. Positive feedback as a search strategy,
Technical Report 91-109, Departimento di electronica e informatica, Poletico di
Milano, IT, 1991.
[6] M.Dorigo. Optimization, learning and natural algorithms, PhD.dissertation, Milan
Polytechnique, Italy, 1992.
[7] M.Dorigo, V.Maniezzo and A.Corloni. The Ant System : Optimization by a colony
of cooperating agents, IEEE, Trans.Syst., Man, Cybern.B, vol.26, no.2, 1996, pp 2941.
[8] M.Dorigo and L.M. Gambardella. Ant Colony System : A cooperative learning
approach to the travelling salesman problem, IEEE Trans, on Evolutionary
Computation, vol.1, no.1, 1997, pp 53-66.
[9] M.Dorigo and M.D.Caro. The Ant Conoly Optimization metaheuristic, A New Idea
in Optimization, D.Corne, M.Dorigo and F.Glover, Eds. London, U.K, McGraw-Hill,
1999, pp.11-32.
[10] M.Dorigo and Thomas Stutzle. The Ant Colony Optimization Metaheuristic :
Algorithms, Applications and Advances, 2000.
[11] M.Dorigo and Thomas Stutzle. A short Convergence Proof for a class of Ant
Colony Optimization Algorithms, IEEE, 2002.
[12] S.Even, A. Itai, and A.Shamir. On the complexity of timetable and
multicommodity flow problems, SIAM Journal on Computing 5(4), 1976, pp 691-703.
[13] W.J. Gutjahr. ACO Algorithms with guaranteed convergence to the optimal
solution problem, Info.Processing Lett., vol.83, no.3, 2002, pp 145-153.
[14] Hoang Xuan Huan & Dinh Trung Hoang. On the ant colony system for the
postman problem, Journal of Science, Natural Sciences and Technology, Viet Nam
National Univeristy, Ha Noi, vol.18, no 1, 2002, pp 29-37.


[15] Hoang Xuan Huan. Convergence Analysis of ACO Algorithms and New
Perpectives, manuscript, 2003.