THUẬT TOÁN VÀ CÁC BÀI THUẬT TOÁN VÀ CÁC BÀI TOÁN LỊCH BIỂU TOÁN LỊCH BIỂU

Trong lĩnh vực lập lịch, một mô hình tổng quát 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 giải được bởi một thuật toán không đơn định trong thời gian đa thức) và nổi tiếng là một trong những bài toán tối ƣu tổ hợp khó tính toán nhất cho tới nay. 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 thúc đẩy mạnh mẽ việc nghiên cứu JSP đó là tính ứng dụng của nó trong thực tiễn cuộc sống và sản xuất.

Luận án tập trung vào giải quyết một số vấn đề chủ yếu sau đây:

1. 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.

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 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 áp dụng cho JSP mà luận án đề xuất.

 Đối tượng nghiên cứu, phạm vi nghiên cứu của luận án

+ Đối tượng nghiên cứu: Thuật toán và các bài toán lịch biểu.

+ Phạm vi nghiên cứu: Ứng dụng thuật toán di truyền giải quyết bài toán lập lịch job shop.

 Phương pháp nghiên cứu của luận án
Luận án sử dụng đồng thời nhiều phương pháp nghiên cứu khoa học như:

– Phương pháp nghiên cứu dựa trên tài liệu: Thu thập, phân tích, xử lý thông tin dựa trên các tài liệu như sách, báo, tạp chí,…đã in ấn hoặc công bố trên internet liên quan đến đề tài.

– Phương pháp nghiên cứu phi thực nghiệm: Tham khảo ý kiến của các chuyên gia thông qua các hội thảo trong và ngoài nước.

Ngoài phần mở đầu, kết luận và phụ lục, nội dung của luận án được bố

cục thành 4 chương như sau:

CHƯƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI TOÁN LẬP LỊCH JOB SHOP

Chương này trình bày vắn tắt về thuật toán di truyền cổ điển (mã hóa nhị phân), phân tích, đánh giá các giải pháp quan trọng nhất cho JSP đã đƣợc công bố trong những năm qua. Nhận diện những khó khăn khi giải quyết bài toán lập lịch job shop mà chúng ta cần phải vượt qua trong hiện tại và tương lai. Sau khi phân tích, đánh giá, luận án đề xuất một số hướng nghiên cứu cho bài toán này.

CHƯƠNG 2: HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP

Bài toán flow shop và flow shop hoán vị là hai trường hợp riêng của bài toán job shop rất thường gặp trong thực tiễn. Chương này trình bày các khái niệm cơ bản liên quan đến hai bài toán con của JSP và thuật toán Johnson cho bài toán flow shop 2 máy và 3 máy có hạn chế điều kiện. Cuối cùng, một thuật toán di truyền mã hóa số tự nhiên được đề xuất cho hai bài toán này.

CHƯƠNG 3: MỘT THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP

Bài toán lập lịch job shop là bài toán lập lịch tổng quát nhất và cũng khó giải quyết nhất. Trong chương này, luận án đề xuất một thuật toán di truyền lai mới cho JSP. Thuật toán này kết hợp thuật toán di truyền với một số kỹ thuật tìm kiếm khác nhƣ các luật ưu tiên nhanh, kỹ thuật tìm kiếm lân cận,… Thuật toán được cài đặt và chạy thử nghiệm trên các bài toán test chuẩn, các kết quả tính toán đã khẳng định tính vượt trội của nó. Để khắc phục độ phức tạp tính toán của JSP, thuật toán đã được song song hóa, cài đặt và chạy thử nghiệm trên các bài toán test chuẩn. Kết quả lời giải tối ưu thu được tương tự như thuật toán tuần tự nhưng thời gian tính toán được cải thiện nhiều lần.

CHƯƠNG 4: 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

Trong chương này, luận án phân tích thuộc tính hội tụ của thuật toán đã đề xuất bằng cách áp dụng các tính chất của xích Markov. Trên cơ sở phân tích xích Markov của thuật toán di truyền, luận án đã chứng minh thuật toán được đề nghị trong chương 3 hội tụ tới tối ưu toàn cục.

Tải về miễn phí bản đầy đủ luận văn tại địa chỉ:

https://www.file-upload.com/slpqwl1j38c1

 

 

Tác giả

NGUYỄN HỮU MÙI

Chuyên ngành

Khoa học máy tính

Mã số

62 48 01 01

Người hướng dẫn khoa học

PGS.TSKH Vũ Đình Hòa, PGS.TS Hoàng Xuân Huấn

Đánh giá

Chưa có đánh giá nào.

Hãy là người đầu tiên đánh giá “THUẬT TOÁN VÀ CÁC BÀI THUẬT TOÁN VÀ CÁC BÀI TOÁN LỊCH BIỂU TOÁN LỊCH BIỂU”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *