Luận án tập trung nghiên cứu một số vấn đề chủ yếu sau đây: 1. Phân tích các tiếp cận đã đề xuất để giải quyết JSP trong những năm qua để 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 số hướng nghiên cứu bài toán này. 2. Đề 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 bài toán JSP cỡ lớn. 3. 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 cho JSP mà luận án đề xuất. | ĐẠ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 TÓM TẮT LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Hà Nội - Năm 2013 Công trình này đƣợc hoàn thành tại Trƣờng Đại học Công nghệ Đại học Quốc gia Hà Nội NGƢỜI HƢỚNG DẪN KHOA HỌC: 1. PGS. TSKH Vũ Đình Hòa 2. PGS. TS Hoàng Xuân Huấn Phản biện 1: PGS. TS Đoàn Văn Ban Phản biện 2: PGS. TS Huỳnh Quyết Thắng Phản biện 3: PGS. TS Đỗ Trung Tuấn Luận án đƣợc bảo vệ trƣớc hội đồng cấp Đại học Quốc gia chấm luận án tiến sĩ tại Phòng 212, Nhà E3, Trƣờng Đại học Công Nghệ. Vào hồi 9h00, ngày 25 tháng 9 năm 2013 Có thể tìm hiểu luận án tại: Thƣ viện Quốc gia Việt Nam. Trung tâm Thông tin - Thƣ viện, Đại học Quốc gia Hà Nội. 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ý. Một mô hình chung nhất về lập lịch đó là bài toán lập lịch job shop (Job shop Scheduling Problem - JSP), bài toán này thuộc lớp NP-hard (NP là lớp các bài toán quyết định có thể giải quyết trong thời gian đa thức trên máy Turing không đơn định). JSP cũng là một trong những bài toán được nghiên cứu nhiều nhất và là một mô hình phát triển tốt về lý thuyết lập lịch. Ngoài ra, một động lực khác giúp cho JSP được thúc đẩy mạnh mẽ là bởi các ứng dụng của nó trong thực tiễn cuộc sống và sản xuất. Đã có nhiều giải pháp được đề xuất cho bài toán lập lịch job shop. Tuy nhiên, cho tới nay chưa có một tiếp cận nào đã đề xuất giải quyết triệt để bài toán này. Một số vấn đề liên quan tới việc giải quyết bài toán JSP còn tồn tại như sau: 1. Các chuẩn thiết kế thử nghiệm để đánh giá một cách chính xác các thuật toán mới được đề xuất. 2. Tính hội tụ của các thuật toán mới được đề xuất chưa được chứng minh dựa trên cơ sở toán học. 3. Phương pháp luận
