I. Tổng Quan Thuật Toán Lịch Biểu Nghiên Cứu Phát Triển
Lập lịch là một chủ đề quan trọng trong lĩnh vực vận trù học từ những năm 1950. Mục tiêu chính là phân phối tài nguyên dùng chung hiệu quả cho các tác vụ đồng thời. Các bài toán lập lịch rất đa dạng, xuất hiện trong nhiều lĩnh vực như sản xuất, chăm sóc sức khỏe, giáo dục, xử lý tính toán, vận tải. Trong sản xuất, các tác vụ thường là công việc, tài nguyên là máy móc. Trong bệnh viện, tác vụ là bệnh nhân, tài nguyên là y tá, giường bệnh, thiết bị y tế. Trong giáo dục, tác vụ là lớp học, tài nguyên là giáo viên, phòng học, sinh viên. Nhiều công trình nghiên cứu về lập lịch đã đề xuất các giải pháp khác nhau, từ tiếp cận chính xác đến gần đúng và lai kết hợp nhiều kỹ thuật. Các nhà nghiên cứu về lập lịch cũng rất đa dạng, hoạt động trong nhiều lĩnh vực khác nhau. Nhiều nhà nghiên cứu thuộc các lĩnh vực tưởng chừng không liên quan như sinh học, di truyền học, thần kinh học cũng đóng góp cho lý thuyết lập lịch, đặc biệt là các phương pháp luận mới đầy triển vọng như mạng nơ-ron và tính toán tiến hóa. Ví dụ, thuật toán di truyền phỏng theo học thuyết tiến hóa của Darwin được áp dụng rộng rãi cho các bài toán lập lịch.
1.1. Giới Thiệu Bài Toán Lập Lịch Job Shop JSΡ
Trong lĩnh vực lập lịch, mô hình tổng quát nhất là bài toán lập lịch Job Shop (JSΡ). Bài toán này thuộc lớp NP-hard 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. JSΡ 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, tính ứng dụng của nó trong thực tiễn cuộc sống và sản xuất cũng thúc đẩy mạnh mẽ việc nghiên cứu JSΡ. Ban đầu JSΡ được giải quyết bằng các tiếp cận tìm ra lời giải chính xác như tiếp cận hiệu suất cao, mô hình toán học, kỹ thuật nhánh cận. Các tiếp cận này đưa ra lời giải tối ưu thực sự cho bài toán. Về mặt lý thuyết, tiếp cận chính xác đóng vai trò quan trọng và đã được áp dụng thành công cho một số bài toán lập lịch cỡ nhỏ. Tuy nhiên, các tiếp cận này đòi hỏi nhiều thời gian thực thi ngay cả với bài toán cỡ trung bình. Thậm chí, để tìm ra một lời giải thỏa mãn hoàn toàn các ràng buộc của bài toán có thể yêu cầu thời gian tính toán tăng theo hàm mũ trong khi cỡ bài toán chỉ tăng theo tuyến tính.
1.2. Các Phương Pháp Tiếp Cận Gần Đúng Cho Bài Toán JSΡ
Trong thực tế, chúng ta thường phải giải quyết các bài toán lập lịch cỡ lớn trong một khoảng thời gian khả thi với các kết quả chấp nhận được (không nhất thiết phải tối ưu thực sự). Các giải pháp cho JSΡ đáp ứng đòi hỏi này được gọi là tiếp cận gần đúng. Các tiếp cận này thường dựa trên các tiến trình tự nhiên như vật lý thống kê, sự tiến hóa sinh học hay dựa trên khung cảnh trí tuệ nhân tạo. Bốn tiếp cận gần đúng đã được nghiên cứu và áp dụng phổ biến nhất cho tới nay là: luật ưu tiên nhanh, giải thuật heuristic dựa trên nút cổ chai, trí tuệ nhân tạo, phương pháp tìm kiếm cục bộ và meta-heuristic. Đánh giá tổng quan về các tiếp cận cho JSΡ sẽ được trình bày chi tiết trong chương 1 của luận án này. Tuy nhiên, cho tới nay chưa có một tiếp cận nào có thể giải quyết triệt để bài toán lập lịch job shop tổng quát, nhất là đối với JSΡ có nhiều máy và nhiều công việc.
II. Thách Thức Vấn Đề Nghiên Cứu Thuật Toán Lịch Biểu
Một số vấn đề chính liên quan tới việc giải quyết bài toán lập lịch Job Shop còn tồn tại. Các chuẩn thiết kế thử nghiệm để đánh giá thuật toán mới được đề nghị chưa được thống nhất. Tính hội tụ của các thuật toán mới đề xuất chưa được chứng minh dựa trên cơ sở toán học. Phương pháp luận cho việc kết hợp các kỹ thuật tìm kiếm khác nhau để tạo ra một giải pháp mạnh cho JSΡ còn chưa được nghiên cứu đầy đủ. Ở Việt Nam, việc nghiên cứu về bài toán lập lịch job shop vẫn chưa phát triển. Trong các trường đại học, đa số sinh viên, học viên cao học về công nghệ thông tin vẫn chưa biết tới bài toán này. Trong những năm gần đây đã xuất hiện một số báo cáo khoa học đề cập tới bài toán này. Tuy nhiên, kết quả đạt được còn rất khiêm tốn, chưa tương xứng với tầm quan trọng của bài toán.
2.1. Các Tiêu Chí Đánh Giá Thuật Toán Lập Lịch
Việc đánh giá hiệu quả của một thuật toán lập lịch đòi hỏi các tiêu chí rõ ràng và thống nhất. Các tiêu chí này bao gồm thời gian hoàn thành trung bình, thời gian chờ trung bình, độ trễ, và chi phí. Tuy nhiên, việc lựa chọn tiêu chí phù hợp phụ thuộc vào đặc điểm cụ thể của bài toán và mục tiêu của hệ thống. Ví dụ, trong một hệ thống thời gian thực, độ trễ có thể là tiêu chí quan trọng nhất, trong khi trong một hệ thống sản xuất, chi phí có thể là yếu tố quyết định.
2.2. Chứng Minh Tính Hội Tụ Của Thuật Toán
Tính hội tụ là một thuộc tính quan trọng của một thuật toán tối ưu hóa. Một thuật toán hội tụ đảm bảo rằng nó sẽ tìm thấy một giải pháp tối ưu (hoặc gần tối ưu) sau một số lượng hữu hạn các bước. Việc chứng minh tính hội tụ của một thuật toán lập lịch là một thách thức lớn, đặc biệt đối với các thuật toán phức tạp như thuật toán di truyền. Các phương pháp chứng minh tính hội tụ thường dựa trên các khái niệm toán học như xích Markov và lý thuyết độ phức tạp.
III. Giải Pháp Thuật Toán Di Truyền Lai Cho Bài Toán JSΡ
Luận án tập trung vào giải quyết một số vấn đề chủ yếu sau: Phân tích, đánh giá các tiếp cận đã đề xuất cho JSΡ để 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. Đề xuất một thuật toán di truyền lai mới cho JSΡ 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 JSΡ cỡ lớn. 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 JSΡ mà luận án đề xuất.
3.1. Thuật Toán Di Truyền Lai Mã Hóa và Toán Tử
Trong thuật toán di truyền lai, việc mã hóa lời giải đóng vai trò quan trọng. Mã hóa phải đảm bảo tính hợp lệ của lời giải và cho phép các toán tử di truyền hoạt động hiệu quả. Các toán tử di truyền bao gồm toán tử đột biến và toán tử trao đổi chéo. Toán tử đột biến tạo ra sự đa dạng trong quần thể, trong khi toán tử trao đổi chéo kết hợp các đặc tính tốt của các cá thể cha mẹ để tạo ra các cá thể con tốt hơn.
3.2. Song Song Hóa Thuật Toán Di Truyền Lai
Để giảm thời gian tính toán, thuật toán di truyền lai có thể được song song hóa. Có nhiều cách để song song hóa thuật toán di truyền, bao gồm song song hóa ở mức độ cá thể, song song hóa ở mức độ toán tử, và song song hóa ở mức độ quần thể. Việc lựa chọn phương pháp song song hóa phù hợp phụ thuộc vào kiến trúc phần cứng và đặc điểm của bài toán.
3.3. Kết Quả Thử Nghiệm và So Sánh
Thuật toán di truyền lai được thử nghiệm trên các bài toán kiểm thử 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ó. 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 JSΡ, 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 kiểm thử 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.
IV. Phân Tích Tính Hội Tụ Thuật Toán Di Truyền Lai Mới Cho JSΡ
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.
4.1. Xích Markov và Tính Hội Tụ
Xích Markov là một mô hình toán học mô tả một chuỗi các sự kiện, trong đó xác suất của mỗi sự kiện chỉ phụ thuộc vào trạng thái của sự kiện trước đó. Xích Markov có thể được sử dụng để phân tích tính hội tụ của các thuật toán tối ưu hóa. Nếu một thuật toán có thể được mô hình hóa bằng một xích Markov, thì có thể chứng minh rằng thuật toán sẽ hội tụ tới một giải pháp tối ưu nếu xích Markov có các thuộc tính nhất định.
4.2. Chứng Minh Hội Tụ Thuật Toán Di Truyền Lai
Luận án chứng minh tính hội tụ của thuật toán di truyền lai bằng cách sử dụng các tính chất của xích Markov. Chứng minh này cho thấy rằng thuật toán sẽ hội tụ tới một giải pháp tối ưu toàn cục sau một số lượng hữu hạn các bước. Điều này đảm bảo rằng thuật toán sẽ tìm thấy một giải pháp tốt cho bài toán lập lịch Job Shop.
V. Ứng Dụng Thực Tế Triển Vọng Thuật Toán Lịch Biểu
Luận án đã được sử dụng làm tư liệu giảng dạy cho môn học chuyên đề tự chọn ở bậc đại học ngành công nghệ thông tin tại Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội. Luận án có thể được sử dụng làm tài liệu tham khảo cho các sinh viên đại học và các học viên cao học ngành công nghệ thông tin làm đề tài về thuật toán di truyền và ứng dụng giải các bài toán tối ưu. Nếu được đầu tư về tài chính và nhân lực, luận án có thể được hoàn thiện và áp dụng để giải quyết các bài toán trong thực tiễn về qui hoạch và tối ưu hóa.
5.1. Lập Lịch Trong Hệ Thống Sản Xuất
Trong hệ thống sản xuất, thuật toán lập lịch được sử dụng để tối ưu hóa việc phân bổ tài nguyên và thời gian cho các công việc khác nhau. Mục tiêu là giảm thiểu thời gian hoàn thành, chi phí, và độ trễ. Các thuật toán lập lịch có thể được sử dụng để lập lịch cho các máy móc, công nhân, và vật liệu.
5.2. Lập Lịch Trong Hệ Thống Y Tế
Trong hệ thống y tế, thuật toán lập lịch được sử dụng để tối ưu hóa việc phân bổ tài nguyên và thời gian cho các bệnh nhân khác nhau. Mục tiêu là giảm thiểu thời gian chờ đợi, chi phí, và rủi ro. Các thuật toán lập lịch có thể được sử dụng để lập lịch cho các bác sĩ, y tá, giường bệnh, và thiết bị y tế.
5.3. Lập Lịch Trong Hệ Thống Vận Tải
Trong hệ thống vận tải, thuật toán lập lịch được sử dụng để tối ưu hóa việc phân bổ tài nguyên và thời gian cho các phương tiện khác nhau. Mục tiêu là giảm thiểu thời gian di chuyển, chi phí, và ô nhiễm. Các thuật toán lập lịch có thể được sử dụng để lập lịch cho các xe buýt, tàu hỏa, máy bay, và tàu thuyền.
VI. Kết Luận Hướng Nghiên Cứu Tiếp Theo Thuật Toán Lịch
Luận án đã trình bày một nghiên cứu toàn diện về thuật toán lập lịch, đặc biệt là thuật toán di truyền lai cho bài toán Job Shop. Luận án đã đề xuất một thuật toán mới, chứng minh tính hội tụ của nó, và thử nghiệm nó trên các bài toán kiểm thử chuẩn. Kết quả cho thấy rằng thuật toán mới có hiệu quả và có thể được sử dụng để giải quyết các bài toán lập lịch trong thực tế.
6.1. Hướng Nghiên Cứu Mở Rộng Thuật Toán Di Truyền Lai
Các hướng nghiên cứu tiếp theo có thể tập trung vào việc cải thiện hiệu quả của thuật toán di truyền lai bằng cách sử dụng các kỹ thuật tối ưu hóa khác nhau. Ví dụ, có thể sử dụng các thuật toán tìm kiếm cục bộ để cải thiện các lời giải được tạo ra bởi thuật toán di truyền. Ngoài ra, có thể sử dụng các kỹ thuật học máy để tự động điều chỉnh các tham số của thuật toán di truyền.
6.2. Ứng Dụng Thuật Toán Cho Bài Toán Thực Tế
Một hướng nghiên cứu quan trọng khác là áp dụng thuật toán di truyền lai cho các bài toán lập lịch trong thực tế. Điều này đòi hỏi việc điều chỉnh thuật toán cho phù hợp với các đặc điểm cụ thể của từng bài toán. Ngoài ra, cần phải phát triển các công cụ phần mềm để hỗ trợ việc sử dụng thuật toán trong thực tế.
