Thuật toán và các bài toán lịch biểu

Nghiên cứu về tổng quan của bài toán: Phân tích, đánh giá, so sánh các tiếp cận đã áp dụng cho các bài toán lập lịch job shop, trên cơ sở đó đề xuất một số hướng nghiên cứu cho bài toán này. Nghiên cứu và đề xuất một thuật toán lai mới kết hợp thuật toán di truyền với các kỹ thuật tìm kiếm khác cho bài toán lập lịch job shop. Trong thuật toán đề xuất này, có một số đổi mới trong mã hóa lời giải, toán tử đột biến và toán tử trao đổi chéo. Phương pháp đề xuất này đã được thử nghiệm trên các bài toán test chuẩn và so sánh kết quả với các giải pháp trước đó để chứng tỏ tính vượt trội của nó. Song song hóa thuật toán đã đề xuất cho bài toán lập lịch job shop, thuật toán đã được cài đặt và chạy thử nghiệm cho kết quả tốt và rút ngắn được nhiều lần thời gian thực thi với cùng bộ tham số và dữ liệu vào trong thuật toán tuần tự. Chứng minh tính hội tụ của thuật toán di truyền lai mới với mã hóa tự nhiên cho bài toán lập lịch job shop đã đề xuất.

Lý do chọn đề tài

Lập lịch là một trong những chủ đề quan trọng thuộc lĩnh vực vận trù học xuất hiện từ đầu những năm 1950. Mục tiêu chính của lập lịch là phân phối tài nguyên dùng chung một cách hiệu quả nhất cho các tác vụ đồng thời trong toàn bộ thời gian xử lý. Các bài toán lập lịch rất đa dạng, chúng xuất hiện trong các lĩnh vực khác nhau như: Sản xuất, chăm sóc sức khỏe, giáo dục đào tạo, xử lý tính toán, vận tải,… Trong lĩnh vực sản xuất, các tác vụ thường được xem như là các công việc, các tài nguyên là các máy. Trong bệnh viện, các tác vụ là các bệnh nhân và các tài nguyên là các y tá, các giường bệnh, các trang thiết bị y tế được yêu cầu để điều trị các bệnh nhân. Trong giáo dục đào tạo, các tác vụ là các lớp học và các tài nguyên là các giáo viên, các phòng học, các sinh viên,… Các ví dụ khác về lập lịch bao gồm các bài toán vận chuyển (chẳng hạn như bài toán người du lịch, lập lịch hàng không, lập lịch tầu hỏa,…), các bài toán lập lịch tính toán (chẳng hạn như lập lịch CPU, lập lịch phân công,…).

Trong những năm qua, rất nhiều các công trình nghiên cứu về lập lịch với các giải pháp khác nhau đã được đề xuất, từ các tiếp cận chính xác đến các tiếp cận gần đúng và gần đây là các tiếp cận lai kết hợp đồng thời nhiều kỹ thuật với nhau. Các nhà nghiên cứu về lập lịch cũng rất đa dạng, họ hoạt động trong nhiều lĩnh vực rất khác nhau như: Các nhà nghiên cứu khoa học, các nhà khoa học quản lý và thậm chí cả các công nhân trực tiếp sản xuất. Trong những năm qua, nhiều nhà nghiên cứu thuộc các lĩnh vực tưởng chừng như không liên quan gì tới lập lịch như: Sinh học, di truyền học, thần kinh học,… cũng đã có rất nhiều đóng góp cho lý thuyết lập lịch, đặc biệt là sự đóng góp của họ vào các phương pháp luận mới đầy triển vọng như mạng nơ và tính toán tiến hóa. Chẳng hạn như thuật toán di truyền phỏng theo học thuyết tiến hóa của Darwin được áp dụng khá rộng rãi cho các bài toán lập lịch.

Trong lĩnh vực lập lịch, một mô hình tổng quát nhất về lập lịch đó là bài toán lập lịch job shop (Job shop Scheduling Problem – JSP), bài toán này thuộc lớp NP-hard (NP là lớp các bài toán giải được bởi một thuật toán không đơn định trong thời gian đa thức) và nổi tiếng là một trong những bài toán tối ưu tổ hợp khó tính toán nhất cho tới nay. JSP cũng là một trong những bài toán được nghiên cứu nhiều nhất và là một mô hình phát triển tốt về lý thuyết lập lịch. Ngoài ra, một động lực khác thúc đẩy mạnh mẽ việc nghiên cứu JSP đó là tính ứng dụng của nó trong thực tiễn cuộc sống và sản xuất.

Ban đầu JSP được giải quyết bởi các tiếp cận tìm ra lời giải chính xác như: Các tiếp cận hiệu suất cao, các mô hình toán học, các kỹ thuật nhánh cận. Các tiếp cận này đưa ra các lời giải tối ưu thực sự cho bài toán. Về mặt lý thuyết, các tiếp cận chính xác đóng vai trò quan trọng và đã được áp dụng thành công cho một số bài toán lập lịch có kích cỡ nhỏ. Tuy nhiên, các tiếp cận này đòi hỏi khá nhiều thời gian thực thi ngay cả với các bài toán cỡ trung bình. Thậm chí, để tìm ra một lời giải thỏa mãn hoàn toàn các ràng buộc của bài toán có thể yêu cầu thời gian tính toán tăng theo hàm mũ trong khi cỡ bài toán chỉ tăng theo tuyến tính.

Trong thực tế, chúng ta thường phải giải quyết các bài toán lập lịch có kích cỡ lớn trong một khoảng thời gian khả thi với các kết quả chấp nhận được (các kết quả này không nhất thiết là phải tối ưu thực sự). Các giải pháp cho JSP đáp ứng đòi hỏi này còn được gọi là các tiếp cận gần đúng. Các tiếp cận này thường dựa trên các tiến trình tự nhiên như: Vật lý thống kê, sự tiến hóa sinh học hay dựa trên khung cảnh trí tuệ nhân tạo. Bốn tiếp cận gần đúng đã được nghiên cứu và áp dụng phổ biến nhất cho tới nay đó là: Các luật ưu tiên nhanh, các giải thuật heuristic dựa trên nút cổ chai, trí tuệ nhân tạo, các phương pháp tìm kiếm cục bộ và meta-heuristic. Đánh giá tổng quan về các tiếp cận cho JSP sẽ được trình bày chi tiết trong chương 1 của luận án này.

Tuy nhiên, cho tới nay chưa có một tiếp cận nào đã được đề xuất có thể giải quyết triệt để bài toán lập lịch job shop tổng quát, nhất là đối với JSP có nhiều máy và nhiều công việc. Một số vấn đề chính liên quan tới việc giải quyết bài toán này còn tồn tại như sau:

Các chuẩn thiết kế thử nghiệm để đánh giá thuật toán mới được đề nghị.
Tính hội tụ của các thuật toán mới được đề xuất chưa được chứng minh dựa trên cơ sở toán học.
Phương pháp luận cho việc kết hợp các kỹ thuật tìm kiếm khác nhau để tạo ra một giải pháp mạnh cho JSP còn chưa được nghiên cứu một cách đầy đủ….
Ở nước ta, việc nghiên cứu về bài toán lập lịch job shop vẫn chưa phát triển. Trong các trường đại học, đại đa số các sinh viên, học viên cao học về công nghệ thông tin vẫn chưa biết tới bài toán này. Trong những năm gần đây đã xuất hiện một số báo cáo khoa học đề cập tới bài toán này. Tuy nhiên, kết quả đạt được còn rất khiêm tốn, chưa tương xứng với tầm quan trọng của bài toán.

Vì những lý do trên, luận án chọn đề tài “Thuật toán và các bài toán lịch biểu” làm đối tượng nghiên cứu. Phạm vi nghiên cứu của đề tài chủ yếu tập trung vào thuật toán di truyền và bài toán lập lịch job shop.

Bố cục của luận án

Ngoài phần mở đầu, kết luận và phụ lục, nội dung của luận án được bố cục thành 4 chương như sau:

CHƯƠNG 1. TỔNG QUAN VỀ THUẬT TOÁN DI TRUYỀN VÀ BÀI TOÁN LẬP LỊCH JOB SHOP

Chương này trình bày vắn tắt về thuật toán di truyền cổ điển (mã hóa nhị phân), phân tích, đánh giá các giải pháp quan trọng nhất cho JSP đã được công bố trong những năm qua. Nhận diện những khó khăn khi giải quyết bài toán lập lịch job shop mà chúng ta cần phải vượt qua trong hiện tại và tương lai. Sau khi phân tích, đánh giá, luận án đề xuất một số hướng nghiên cứu cho bài toán này.

CHƯƠNG 2: HAI BÀI TOÁN CON CỦA BÀI TOÁN LẬP LỊCH JOB SHOP

Bài toán flow shop và flow shop hoán vị là hai trường hợp riêng của bài toán job shop rất thường gặp trong thực tiễn. Chương này trình bày các khái niệm cơ bản liên quan đến hai bài toán con của JSP và thuật toán Johnson cho bài toán flow shop 2 máy và 3 máy có hạn chế điều kiện. Cuối cùng, một thuật toán di truyền mã hóa số tự nhiên được đề xuất cho hai bài toán này.

CHƯƠNG 3: MỘT THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP

Bài toán lập lịch job shop là bài toán lập lịch tổng quát nhất và cũng khó giải quyết nhất. Trong chương này, luận án đề xuất một thuật toán di truyền lai mới cho JSP. Thuật toán này kết hợp thuật toán di truyền với một số kỹ thuật tìm kiếm khác như các luật ưu tiên nhanh, kỹ thuật tìm kiếm lân cận,… Thuật toán được cài đặt và chạy thử nghiệm trên các bài toán test chuẩn, các kết quả tính toán đã khẳng định tính vượt trội của nó. Để khắc phục độ phức tạp tính toán của JSP, thuật toán đã được song song hóa, cài đặt và chạy thử nghiệm trên các bài toán test chuẩn. Kết quả lời giải tối ưu thu được tương tự như thuật toán tuần tự nhưng thời gian tính toán được cải thiện nhiều lần.

CHƯƠNG 4: PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JOB SHOP

Trong chương này, luận án phân tích thuộc tính hội tụ của thuật toán đã đề xuất bằng cách áp dụng các tính chất của xích Markov. Trên cơ sở phân tích xích Markov của thuật toán di truyền, luận án đã chứng minh thuật toán được đề nghị trong chương 3 hội tụ tới tối ưu toàn cục.

Link tải tài liệu: https://tii.la/1CsO

Lưu ý: Link tải có chứa quảng cáo được rút gọn bằng Shrinkearn.com

Mật khẩu mở tệp PDF: sharetailieu.net

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Lý do chọn đề tài

Bố cục của luận án

LEAVE A REPLY Cancel reply

Mới Nhất

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Nâng cao độ chính xác định vị robot bằng phương pháp tổng hợp dữ liệu cảm biến lập mã quang với bộ lọc Kalman...

Cùng Chuyên Mục

Đọc Nhiều Nhất

Áp dụng OSGi trong việc xây dựng hệ thống dựa thành...

Kiến trúc hướng dịch vụ và ứng dụng điện toán đám...

Nghiên cứu tính khả kiểm thử của ứng dụng trên nền...

Kiểm thử đơn vị cho hệ thống

Phát triền phần mềm cho người học tại Đại học Quốc...

Các kỹ thuật phân cụm trong khai phá dữ liệu sử...