CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc BẢN TRÍCH YẾU LUẬN ÁN TIẾN SĨ

Tác giả: Ban Hà Bằng
Luận án: Các thuật toán gần đúng giải bài toán cực tiểu hóa độ trễ (minimum latency
problem-MLP)
Chuyên ngành: Khoa học máy tính Mã số: 62480101
Cơ sở đào tạo: Trường Đại học Bách Khoa Hà Nội

Nội dung bản trích yếu:
1. Mục đích và đối tượng nghiên cứu của luận án
Mục đích nghiên cứu của chúng tôi trong luận án này là đề xuất các thuật toán giải bài toán
cực tiểu hóa độ trễ-MLP với chất lượng lời giải tốt hơn chất lượng lời giải của các thuật
toán giải bài toán MLP đã được công bố.
Đối tượng nghiên cứu là bài toán MLP, một trong những bài toán tối ưu hóa tổ hợp có
nhiều ứng dụng trong thực tiễn.
2. Các phương pháp nghiên cứu đã sử dụng
Đối với một bài toán NP-khó như bài toán MLP, hiện tại có ba hướng tiếp cận chính để
phát triển thuật toán giải: 1) hướng tiếp cận đúng; 2) hướng tiếp cận gần đúng cận tỷ lệ; 3)
hướng tiếp cận meta-heuristic. Trước hết, các thuật toán đúng tìm lời giải tối ưu thường có
độ phức tạp tính toán bùng nổ tổ hợp: O(n!) trong tình huống tồi nhất, mặc dù trong thực tế
chúng thường chạy nhanh hơn đánh giá lý thuyết này. Tuy vậy, thuật toán đúng cũng chỉ
có thể giải bài toán MLP với kích thước nhỏ. Trong cách tiếp cận thứ hai, các thuật toán
gần đúng với cận tỷ lệ

có ưu điểm lớn là về mặt lý thuyết chúng đảm bảo đưa ra lời giải
có chi phí không vượt quá


một số kỹ thuật mới được tích hợp vào từng bước của thuật toán di truyền. Nhằm
nâng cao chất lượng lời giải và thời gian chạy thuật toán, chúng tôi đề xuất hai
thuật toán meta-heuristic lai là: Thuật toán (ACO-GA) lai ghép giữa thuật toán di
truyền (GA) và thuật toán đàn kiến (ACO); và thuật toán TS-VNS lai ghép giữa
thuật toán Tabu (TS) và thuật toán lân cận biến đổi (VNS).
Để đánh giá hiệu quả của các thuật toán đề xuất, chúng tôi tiến hành thực nghiệm trên các bộ dữ
liệu đã được các nhóm nghiên cứu trên thế giới sử dụng. Các kết quả tính toán thực nghiệm theo
các thuật toán đề xuất được so sánh với kết quả tính toán thực nghiệm của các công trình nghiên
cứu liên quan.

Ngày 20 tháng 04 năm 2014
Giáo viên hướng dẫn khoa học
Nghiên cứu sinh

PGS.TS. Nguyễn Đức Nghĩa Ban Hà Bằng