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ỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> <br /> NGUYỄN HỮU MÙI<br /> <br /> THUẬT TOÁN VÀ CÁC BÀI<br /> TOÁN LỊCH BIỂU<br /> LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> Hà Nội – 2013<br /> <br /> ĐẠI HỌC QUỐC GIA HÀ NỘI<br /> TRƯỜNG ĐẠI HỌC CÔNG NGHỆ<br /> NGUYỄN HỮU MÙI<br /> <br /> THUẬT TOÁN VÀ CÁC BÀI<br /> TOÁN LỊCH BIỂU<br /> Chuyên ngành: Khoa học máy tính<br /> Mã số: 62 48 01 01<br /> <br /> LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN<br /> <br /> NGƯỜI HƯỚNG DẪN KHOA HỌC:<br /> 1. PGS. TSKH Vũ Đình Hòa<br /> 2. PGS. TS Hoàng Xuân Huấn<br /> <br /> Hà Nội - 2013<br /> 1<br /> <br /> LỜI CẢM ƠN<br /> <br /> 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.<br /> TSKH Vũ Đình Hoà, PGS. TS Hoàng Xuân Huấn đã tận tình hƣớng dẫn tác<br /> 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<br /> Phạm Thọ Hoàn, Giám đốc Trung tâm khoa học tính toán Trƣờng Đại học Sƣ<br /> phạm Hà Nội đã giúp đỡ tác giả rất nhiều trong quá trình thử nghiệm tại<br /> Trung tâm.<br /> 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<br /> tính, Khoa Công nghệ thông tin, Trƣờng Đại học Công nghệ; Bộ môn Khoa<br /> học máy tính, Khoa Công nghệ thông tin, Trƣờng Đại học Sƣ phạm Hà Nội<br /> đã 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<br /> thành luận án.<br /> 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<br /> đì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.<br /> <br /> Hà Nội, tháng 09 năm 2013<br /> <br /> Nguyễn Hữu Mùi<br /> <br /> 2<br /> <br /> LỜI CAM ĐOAN<br /> <br /> 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<br /> quả đƣợc viết chung với các tác giả khác đều đƣợc sự đồng ý của đồng tác giả<br /> 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à<br /> chƣa từng đƣợc ai công bố trong các công trình nào khác.<br /> <br /> Tác giả<br /> <br /> Nguyễn Hữu Mùi<br /> <br /> 3<br /> <br /> MỤC LỤC<br /> <br /> LỜI CẢM ƠN ................................................................................................... 2<br /> LỜI CAM ĐOAN ............................................................................................. 3<br /> MỤC LỤC ......................................................................................................... 4<br /> DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT .......................................... 8<br /> DANH MỤC CÁC BẢNG................................................................................ 9<br /> DANH MỤC CÁC HÌNH VẼ ........................................................................ 10<br /> MỞ ĐẦU ......................................................................................................... 12<br /> CHƢƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI<br /> TOÁN LẬP LỊCH JOB SHOP ....................................................................... 19<br /> 1.1. Thuật toán di truyền cổ điển ................................................................ 19<br /> 1.1.1. Cấu trúc của thuật toán di truyền cổ điển ..................................... 20<br /> 1.1.2. Một thủ tục đơn giản cho thuật toán di truyền cổ điển ................. 24<br /> 1.2. Các lớp bài toán P, NP, NPC và NP-hard ............................................ 25<br /> 1.2.1. Các lớp bài toán P và NP .............................................................. 25<br /> 1.2.2. Các lớp bài toán NPC và NP-hard ................................................ 25<br /> 1.3. Tổng quan về bài toán lập lịch job shop .............................................. 26<br /> 1.3.1. Bài toán lập lịch job shop .............................................................. 26<br /> 1.3.2. Các tiếp cận chính xác .................................................................. 29<br /> 1.3.3. Các tiếp cận gần đúng ................................................................... 32<br /> 1.3.4. Tổng kết đánh giá chung về các tiếp cận cho JSP ........................ 50<br /> 4<br /> <br />