Luận án tiến sĩ thuật toán và các bài toán lịch biểu luận án ts công nghệ thông

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN HỮU MÙI THUẬT TOÁN VÀ CÁC BÀI TOÁN LỊCH BIỂU LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2013 TIEU LUAN MOI download : skknchat@gmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN HỮU MÙI THUẬT TOÁN VÀ CÁC BÀI TOÁN LỊCH BIỂU Chuyên ngành: Khoa học máy tính Mã số: 62 48 01 01 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1.TS Hoàng Xuân Huấn Hà Nội - 2013 1 TIEU LUAN MOI download : skknchat@gmail.com 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 2 TIEU LUAN MOI download : skknchat@gmail.com 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 3 TIEU LUAN MOI download : skknchat@gmail.com MỤC LỤC LỜI CẢM ƠN. 2 LỜI CAM ĐOAN. 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Ẽ. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI TOÁN LẬP LỊCH JOB SHOP. Thuật toán di truyền cổ điển.

Cấu trúc của thuật toán di truyền cổ điển. Một thủ tục đơn giản cho thuật toán di truyền cổ điển. Các lớp bài toán P, NP, NPC và NP-hard. Các lớp bài toán P và NP.

Các lớp bài toán NPC và NP-hard. Tổng quan về bài toán lập lịch job shop. Bài toán lập lịch job shop. Các tiếp cận chính xác.

Các tiếp cận gần đúng. Tổng kết đánh giá chung về các tiếp cận cho JSP. 50 4 TIEU LUAN MOI download : skknchat@gmail. Một số tồn tại và các đề xuất.

HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP. Bài toán lập lịch flow shop hoán vị. Mô tả bài toán. Cách tính thời gian hoàn thành trong một lịch biểu hoán vị.

Thuật toán Johnson cho PFSP 2 máy và PFSP 3 máy. Một thuật toán di truyền mã hóa tự nhiên cho bài toán lập lịch flow shop hoán vị tổng quát. Các kết quả thử nghiệm. Bài toán lập lịch flow shop.

Mô tả bài toán. Một thuật toán di truyền mã hóa tự nhiên cho bài toán lập lịch flow shop tổng quát. Các kết quả thử nghiệm. MỘT THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP.

Các lịch biểu tích cực và bán tích cực. Thuật toán GT. Một thuật toán di truyền lai mới cho bài toán lập lịch job shop. Mã hoá lời giải.

Khởi tạo tập lời giải cho thế hệ ban đầu. 90 5 TIEU LUAN MOI download : skknchat@gmail. Xây dựng hàm thích nghi. Các toán tử di truyền.

Thuật toán tiến hóa. Tính đúng đắn của thuật toán đƣợc đề nghị. Song song hóa thuật toán di truyền lai mới cho bài toán lập lịch job shop. Mô tả thuật toán.

Thủ tục di truyền song song cho JSP. Cài đặt thuật toán. Kết quả thử nghiệm. Kết quả thử nghiệm thuật toán tuần tự.

Kết quả thử nghiệm thuật toán song song. PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP. Lý thuyết Xích Markov. Khái niệm xích Markov.

Các tính chất của Xích Markov. Xích Markov Ergodic. Phân tích tính hội tụ của thuật toán di truyền lai tuần tự cho bài toán lập lịch job shop. Phân tích tính hội tụ của thuật toán di truyền truyền thống.

114 6 TIEU LUAN MOI download : skknchat@gmail. Phân tích tính hội tụ của thuật toán di truyền với cá thể tinh hoa và toán tử sao chép. 127 HƢỚNG NGHIÊN CỨU TIẾP THEO. 128 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN.

129 TÀI LIỆU THAM KHẢO. 141 7 TIEU LUAN MOI download : skknchat@gmail.com DANH MỤC CÁC KÝ HIỆU VÀ TỪ VIẾT TẮT 1 ACO Ant Colony Optimization 2 AI Artificial Intelligence 3 AS Ant System 4 BB Branch and Bound 5 CPU Central Processing Unit 6 FSP Flow shop Scheduling Problem 7 GA Genetic Algorithms 8 GLS Genetic Local Search 9 GT Giffler and Thompson 10 HTT Hyper Threading Technology 11 IM Iterative Improvement 12 JSP Job shop Scheduling Problem 13 MIP Mixed Integer linear Programming 14 MPP Massively Parallel Processor 15 PFSP Permutation Flow shop Scheduling Problem 16 RISC Reduced Instructions Set Computer 17 SA Simulated Annealing 18 SB Shifting Bottleneck 19 TA Threshold Acceptance 20 TS Tabu Search 8 TIEU LUAN MOI download : skknchat@gmail.01 DANH MỤC CÁC BẢNG Bảng 1.1 - JSP 3 công việc, 3 máy.1 - PFSP 5 công việc 4 máy .2 - PFSP 4 công việc 2 máy .3 - Các công việc chƣa đƣợc lập lịch .4 - Các công việc chƣa đƣợc lập lịch .5 - Các công việc chƣa đƣợc lập lịch .6 - PFSP 5 công việc 3 máy .7 - Thời gian xử lý các công việc trên 2 máy G và H .8 - Mã hóa lời giải theo số tự nhiên .9 - Kết quả chạy thử nghiệm .10 - FSP 4 máy 2 công việc .11 - Mã hóa lời giải theo số tự nhiên .12 - Kết quả chạy thử nghiệm .1 - JSP 3 công việc, 3 máy.2 - Mã hoá các thao tác bằng số tự nhiên của JSP 3  3 .3 - Nhiệm vụ của Master và Slave.4 - Kết quả chạy thử nghiệm trên các bài toán test của Lawrence .5 - So sánh kết quả chạy thử nghiệm .6 - Kết quả chạy thử nghiệm NHGA và PHGA trên các bài toán test do Muth & Thompson đề nghị .7 - So sánh thời gian chạy thử nghiệm NHGA và PHGA .01 TIEU LUAN MOI download : skknchat@gmail.01 DANH MỤC CÁC HÌNH VẼ Hình 1.1 - Một lời giải đƣợc mã hóa nhị phân.2 - Hai cá thể cha cho phép trao đổi chéo .3 - Hai cá thể con sau phép trao đổi chéo .4 - Hai cá thể con sau phép trao đổi chéo 2 điểm .5 - Cá thể con sau phép trao đổi chéo đồng nhất .6 - Cá thể cha và cá thể con sau phép đột biến .7 - Các tiếp cận chủ yếu giải quyết JSP .1 - Biểu đồ Grant biểu diễn một lời giải của PFSP 5 công việc 4 máy .2 - Đồ thị không liên thông biểu diễn một lời giải của PFSP .3 - Cách tính thời gian hoàn thành trong đồ thị không liên thông .4 - Các cạnh tới hạn của đồ thị không liên thông .5 - Đồ thị cạnh tới hạn.6 - Đồ thị đƣờng tới hạn .7 - Makespan của PFSP 2 máy.8 - Biểu đồ Grant của lịch biểu tối ƣu bài toán 2 máy .9 - Biểu đồ Grant của lịch biểu tối ƣu bài toán 3 máy .10 - Một lời giải hợp lệ cho PFSP 4 công việc 5 máy .12 - Cá thể con sau phép đột biến .13 - Các cá thể cha tham gia trao đổi chéo .01 TIEU LUAN MOI download : skknchat@gmail.14 - Cá thể con sau phép trao đổi chéo .15 - Một lời giải hợp lệ cho FSP 3 máy  5 công việc .16 - Cá thể cha cho phép đột biến .17 - Cá thể con sau phép đột biến .18 - Các cá thể cha tham gia trao đổi chéo .19 - Cá thể con sau phép trao đổi chéo .1 - Các lớp lịch biểu .2 - Lịch biểu không tích cực .3 - Một lịch biểu bán tích cực .4 - Một lịch biểu tích cực .5 - Một lời giải hợp lệ cho JSP 3  3 .6 - Cá thể cha cho phép đột biến .7 - Cá thể con thu đƣợc sau phép đột biến .8 - Trao đổi chéo dùng GT và thực hiện trên 3 cá thể cha .9 - Các cha tham gia đổi chéo và cá thể con sau đổi chéo .10 - Thời gian chạy máy của NHGA và PHGA đối với bài toán mt06 .11 - Thời gian chạy máy của NHGA và PHGA đối với bài toán mt10 .12 - Thời gian chạy máy của NHGA và PHGA đối với bài toán mt20 .1 - Gen ở vị trí thứ 2 trạng thái i của quần thể .01 TIEU LUAN MOI download : skknchat@gmail.01 MỞ ĐẦU  Lý do chọn đề tài Lập lịch là một trong những chủ đề quan trọng thuộc lĩnh vực vận trù học xuất hiện từ đầu những năm 1950. Mục tiêu chính của lập lịch là phân phối tài nguyên dùng chung một cách hiệu quả nhất cho các tác vụ đồng thời trong toàn bộ thời gian xử lý. Các bài toán lập lịch rất đa dạng, chúng xuất hiện trong các lĩnh vực khác nhau nhƣ: Sản xuất, chăm sóc sức khỏe, giáo dục đào tạo, xử lý tính toán, vận tải,.

Trong lĩnh vực sản xuất, các tác vụ thƣờng đƣợc xem nhƣ là các công việc, các tài nguyên là các máy. Trong bệnh viện, các tác vụ là các bệnh nhân và các tài nguyên là các y tá, các giƣờng bệnh, các trang thiết bị y tế đƣợc yêu cầu để điều trị các bệnh nhân. Trong giáo dục đào tạo, các tác vụ là các lớp học và các tài nguyên là các giáo viên, các phòng học, các sinh viên,. Các ví dụ khác về lập lịch bao gồm các bài toán vận chuyển (chẳng hạn nhƣ bài toán ngƣời du lịch, lập lịch hàng không, lập lịch tầu hỏa,.), các bài toán lập lịch tính toán (chẳng hạn nhƣ lập lịch CPU, lập lịch phân công,.

Trong những năm qua, rất nhiều các công trình nghiên cứu về lập lịch với các giải pháp khác nhau đã đƣợc đề xuất, từ các tiếp cận chính xác đến các tiếp cận gần đúng và gần đây là các tiếp cận lai kết hợp đồng thời nhiều kỹ thuật với nhau.