Luận án Tiến sĩ Công nghệ thông tin: Thuật toán và các bài toán lịch biểu

Luận án tập trung vào giải quyết một số vấn đề chủ yếu sau đây: Phân tích, đánh giá các tiếp cận đã đề xuất cho JSP để thấy được ưu điểm, nhược điểm của mỗi giải pháp. Trên cơ sở đó đề xuất một giải pháp mới cho bài toán này. Đề xuất một thuật toán di truyền lai mới cho JSP và song song hóa thuật toán nhằm khắc phục độ phức tạp tính toán vốn có của các JSP cỡ lớn. Chứng minh tính hội tụ của thuật toán di truyền lai với mã hóa tự nhiên áp dụng cho JSP mà luận án đề xuất.
Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Công nghệ thông tin: Thuật toán và các bài toán lịch biểuĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆNGUYỄN HỮU MÙITHUẬT TOÁN VÀ CÁC BÀITOÁN LỊCH BIỂULUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TINHà Nội – 2013ĐẠI HỌC QUỐC GIA HÀ NỘITRƯỜNG ĐẠI HỌC CÔNG NGHỆNGUYỄN HỮU MÙITHUẬT TOÁN VÀ CÁC BÀITOÁN LỊCH BIỂUChuyên ngành: Khoa học máy tínhMã số: 62 48 01 01LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TINNGƯỜI HƯỚNG DẪN KHOA HỌC:1. PGS. TSKH Vũ Đình Hòa2. PGS. TS Hoàng Xuân HuấnHà Nội - 20131LỜI CẢM ƠNVề 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ácgiả trong quá trình hoàn thành luận án. Tác giả cũng chân thành cảm ơn TSPhạ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ạiTrung 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áytính, Khoa Công nghệ thông tin, Trường Đại học Công nghệ; Bộ môn Khoahọ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ànthà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 2013Nguyễn Hữu Mùi2LỜI CAM ĐOANTôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kếtquả đượ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ùi3MỤC LỤCLỜI CẢM ƠN ................................................................................................... 2LỜI CAM ĐOAN ............................................................................................. 3MỤC LỤC ......................................................................................................... 4DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT .......................................... 8DANH MỤC CÁC BẢNG................................................................................ 9DANH MỤC CÁC HÌNH VẼ ........................................................................ 10MỞ ĐẦU ......................................................................................................... 12CHƢƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀITOÁN LẬP LỊCH JOB SHOP ....................................................................... 191.1. Thuật toán di truyền cổ điển ................................................................ 191.1.1. Cấu trúc của thuật toán di truyền cổ điển ..................................... 201.1.2. Một thủ tục đơn giản cho thuật toán di truyền cổ điển ................. 241.2. Các lớp bài toán P, NP, NPC và NP-hard ............................................ 251.2.1. Các lớp bài toán P và NP .............................................................. 251.2.2. Các lớp bài toán NPC và NP-hard ................................................ 251.3. Tổng quan về bài toán lập lịch job shop .............................................. 261.3.1. Bài toán lập lịch job shop .............................................................. 261.3.2. Các tiếp cận chính xác .................................................................. 291.3.3. Các tiếp cận gần đúng ................................................................... 321.3.4. Tổng kết đánh giá chung về các tiếp cận cho JSP ........................ 504