Luận án TS: Thuật toán và các bài toán lập lịch Job Shop, Flow Shop của Nguyễn Hữu Mùi

Bài toán Lịch biểu Job Shop (JSP) mô tả quy trình sản xuất thực tế. Nhiều công việc cần được xử lý trên các máy khác nhau. Mỗi công việc yêu cầu một trình tự các phép toán cụ thể. Thời gian xử lý của mỗi phép toán trên từng máy là khác nhau. Các ràng buộc bao gồm việc mỗi máy chỉ có thể xử lý một phép toán tại một thời điểm. Mỗi công việc cũng chỉ có thể được xử lý bởi một máy tại một thời điểm. Không có sự gián đoạn trong quá trình xử lý phép toán. Mục tiêu là tìm một lịch biểu tối ưu. Lịch biểu này giúp tối thiểu hóa thời gian hoàn thành tổng thể. Đây là thời điểm phép toán cuối cùng kết thúc. Giải quyết JSP mang lại lợi ích kinh tế đáng kể. Nó giúp tăng hiệu quả sản xuất. Nó cũng giảm chi phí hoạt động trong nhiều ngành công nghiệp.

Các bài toán được phân loại theo độ phức tạp tính toán. Lớp P chứa các bài toán có thể giải quyết trong thời gian đa thức. Lớp NP bao gồm các bài toán mà lời giải có thể kiểm chứng trong thời gian đa thức. Bài toán Lịch biểu Job Shop thuộc lớp NP-hard. Điều này có nghĩa là JSP ít nhất khó như bất kỳ bài toán nào trong lớp NP. Bài toán không thể giải quyết hiệu quả bằng các phương pháp vét cạn. Đối với các bài toán NP-hard, việc tìm kiếm lời giải tối ưu trở nên không khả thi trong nhiều trường hợp thực tế. Do đó, các phương pháp gần đúng là cần thiết. Các phương pháp này tìm kiếm lời giải đủ tốt. Luận án khám phá các cách tiếp cận này.

Ban đầu, các phương pháp chính xác được sử dụng cho Bài toán Lịch biểu Job Shop. Các phương pháp này bao gồm quy hoạch tuyến tính và quy hoạch nguyên. Quy hoạch tuyến tính biểu diễn bài toán dưới dạng hệ phương trình và bất phương trình. Mục tiêu là tối ưu hóa một hàm mục tiêu tuyến tính. Quy hoạch nguyên mở rộng điều này bằng cách yêu cầu các biến quyết định là số nguyên. Tuy nhiên, kích thước mô hình nhanh chóng trở nên quá lớn. Điều này gây khó khăn cho việc giải quyết các bài toán quy hoạch nguyên. Các thuật toán như nhánh và cận (Branch and Bound) cũng được áp dụng. Nhưng chúng thường chỉ hiệu quả với các trường hợp kích thước nhỏ. Hiệu quả giảm đi nhanh chóng khi kích thước bài toán tăng. Điều này thúc đẩy sự phát triển của các phương pháp gần đúng.

Tiếp cận gần đúng là thiết yếu cho các bài toán tối ưu hóa phức tạp. Đối với Bài toán Lịch biểu Job Shop, các thuật toán Heuristic được sử dụng để xây dựng lịch biểu. Chúng thường dựa trên các quy tắc ưu tiên đơn giản. Ví dụ, quy tắc công việc ngắn nhất trước (SPT) hoặc thời gian xử lý sớm nhất (EDD). Tuy nhiên, Heuristic đơn giản có thể mắc kẹt ở các lời giải cục bộ kém tối ưu. Các thuật toán Metaheuristic được thiết kế để khắc phục hạn chế này. Chúng thực hiện tìm kiếm toàn diện hơn. Chúng sử dụng các chiến lược để khám phá không gian lời giải. Đồng thời, chúng cũng cố gắng tránh các cực tiểu cục bộ. Việc lựa chọn và thiết kế Metaheuristic phù hợp rất quan trọng. Nó ảnh hưởng trực tiếp đến chất lượng của lịch biểu cuối cùng.

Các thuật toán Metaheuristic cung cấp nhiều công cụ mạnh mẽ. Thuật toán di truyền (GA) mô phỏng quá trình chọn lọc tự nhiên. Nó sử dụng các toán tử như lai ghép và đột biến để tạo ra các thế hệ lời giải mới. Thuật toán tìm kiếm Tabu (TS) sử dụng bộ nhớ ngắn hạn. Bộ nhớ này ngăn chặn việc quay lại các lời giải đã thăm. Nó cho phép tìm kiếm khám phá các vùng lân cận mới. Thuật toán Simulated Annealing (SA) lấy cảm hứng từ quá trình tôi luyện kim loại. Nó cho phép chấp nhận các lời giải kém hơn với xác suất nhất định. Điều này giúp thoát khỏi cực tiểu cục bộ. Ngoài ra, Tối ưu hóa bầy đàn (PSO) cũng là một Metaheuristic phổ biến. Nó mô phỏng hành vi bầy đàn của chim hoặc cá. Tất cả các phương pháp này đã được áp dụng thành công trong nhiều bài toán tối ưu hóa, bao gồm cả JSP. Luận án này tập trung vào việc cải tiến GA.

Mặc dù tập trung vào các phương pháp Metaheuristic, quy hoạch tuyến tính và quy hoạch nguyên vẫn là nền tảng quan trọng. Chúng cung cấp các mô hình toán học chặt chẽ cho Bài toán Lịch biểu Job Shop. Các mô hình này hữu ích để hiểu cấu trúc của bài toán. Chúng cũng được dùng để kiểm chứng chất lượng của các lời giải gần đúng. Với các bài toán kích thước nhỏ, quy hoạch nguyên có thể tìm ra lời giải tối ưu tuyệt đối. Đối với các bài toán lớn hơn, việc kết hợp quy hoạch nguyên với các Heuristic có thể tạo ra các phương pháp lai. Ví dụ, phương pháp Branch-and-Cut kết hợp giữa Branch-and-Bound và cắt bỏ (cutting plane). Luận án cũng xem xét các tiếp cận chính xác này. Điều này giúp đánh giá toàn diện các phương pháp giải quyết JSP.

Bài toán Lịch biểu Flow Shop hoán vị (PFSP) là một trường hợp đặc biệt của FSP. Thứ tự các công việc là như nhau trên tất cả các máy. Điều này làm giảm không gian tìm kiếm so với FSP tổng quát. Thuật toán Johnson là một phương pháp chính xác cho PFSP 2 máy và 3 máy. Tuy nhiên, với số lượng máy lớn hơn, bài toán trở thành NP-hard. Luận án đề xuất một thuật toán di truyền mã hóa tự nhiên cho PFSP tổng quát. Mã hóa này giúp biểu diễn trình tự các công việc một cách hiệu quả. Các toán tử lai ghép và đột biến được thiết kế để duy trì tính hợp lệ của lịch biểu. Các thử nghiệm được thực hiện trên các bộ dữ liệu tiêu chuẩn. Kết quả cho thấy thuật toán di truyền có thể tìm ra các lời giải cạnh tranh. Thậm chí nó vượt trội hơn các phương pháp khác trong một số trường hợp.

Khác với PFSP, trong Lịch biểu Flow Shop tổng quát (FSP), thứ tự công việc có thể khác nhau trên mỗi máy. Điều này làm tăng độ phức tạp của bài toán. Luận án tiếp tục phát triển một thuật toán di truyền mã hóa tự nhiên cho FSP tổng quát. Kỹ thuật mã hóa được điều chỉnh để phù hợp với sự linh hoạt này. Các toán tử di truyền được thiết kế để tạo ra sự đa dạng trong quần thể lời giải. Điều này giúp khám phá không gian tìm kiếm hiệu quả hơn. Hàm thích nghi đánh giá chất lượng của mỗi lịch biểu dựa trên makespan. Các kết quả thử nghiệm trên các bài toán FSP khác nhau được phân tích. Điều này chứng minh khả năng của thuật toán trong việc tìm kiếm các lịch biểu gần tối ưu. Các cải tiến được đề xuất để tăng cường hiệu suất.

Các thuật toán di truyền được phát triển cho PFSP và FSP bao gồm nhiều cải tiến. Các cải tiến này về mã hóa lời giải, khởi tạo quần thể và thiết kế toán tử. Mã hóa tự nhiên giúp dễ dàng thao tác với các lịch biểu. Các chiến lược khởi tạo thông minh tạo ra quần thể ban đầu đa dạng và chất lượng cao. Các toán tử lai ghép và đột biến được tinh chỉnh để giữ gìn các đặc tính tốt của lời giải. Các thử nghiệm được thực hiện trên các bộ dữ liệu benchmark tiêu chuẩn. Các kết quả được so sánh với các thuật toán hiện có. So sánh này bao gồm cả các phương pháp Heuristic và Metaheuristic khác. Phân tích kết quả chỉ ra hiệu quả và độ mạnh mẽ của các thuật toán di truyền được đề xuất. Điều này cung cấp bằng chứng thực nghiệm cho khả năng giải quyết các bài toán Flow Shop hiệu quả.

Thuật toán Di truyền lai (HGA) mới cho JSP được xây dựng trên một cấu trúc vững chắc. Nó tích hợp thuật toán di truyền truyền thống với các kỹ thuật cải tiến cục bộ. Điều này giúp tối ưu hóa hiệu suất tìm kiếm. Cấu trúc bao gồm các giai đoạn chính: khởi tạo quần thể, đánh giá hàm thích nghi, lựa chọn, lai ghép, đột biến và cải thiện cục bộ. Thành phần lai được thực hiện thông qua việc sử dụng các heuristic cục bộ. Các heuristic này được áp dụng sau các toán tử di truyền. Chúng tinh chỉnh các lịch biểu mới được tạo ra. Mục tiêu là đưa chúng đến các cực tiểu cục bộ tốt hơn. Việc này kết hợp khám phá không gian lời giải rộng với khai thác chi tiết các vùng có triển vọng.

Hiệu quả của Thuật toán Di truyền phụ thuộc vào mã hóa lời giải. Mã hóa lời giải được thiết kế để dễ dàng thao tác và giữ tính hợp lệ. Phương pháp mã hóa này ánh xạ trực tiếp từ một cá thể di truyền sang một lịch biểu Job Shop. Khởi tạo quần thể ban đầu được thực hiện một cách chiến lược. Nó không chỉ tạo ra các lịch biểu ngẫu nhiên. Nó còn sử dụng các quy tắc ưu tiên để tạo ra các lời giải ban đầu có chất lượng. Các toán tử di truyền bao gồm lai ghép và đột biến. Chúng được thiết kế đặc biệt cho cấu trúc của JSP. Toán tử lai ghép kết hợp thông tin từ hai lịch biểu cha mẹ. Toán tử đột biến tạo ra sự thay đổi nhỏ trong một lịch biểu. Mục tiêu là khám phá các vùng lân cận mới trong không gian tìm kiếm. Các toán tử này đảm bảo rằng các lịch biểu mới vẫn hợp lệ và tiềm năng.

Để tăng cường hiệu quả tính toán, luận án đã song song hóa Thuật toán di truyền lai mới cho JSP. Phương pháp song song hóa được thiết kế để tận dụng kiến trúc đa lõi của bộ xử lý hiện đại. Nó phân chia quần thể cá thể thành nhiều quần thể con nhỏ hơn. Mỗi quần thể con được xử lý độc lập trên một lõi hoặc luồng. Việc trao đổi thông tin giữa các quần thể con được thực hiện định kỳ. Điều này giúp duy trì sự đa dạng và tránh hội tụ sớm. Kết quả thử nghiệm trên các bộ dữ liệu benchmark đã chứng minh hiệu suất vượt trội của phiên bản song song. Thời gian chạy được giảm đáng kể. Đồng thời, chất lượng lời giải vẫn được duy trì hoặc cải thiện. Việc này cho thấy tiềm năng ứng dụng của thuật toán trong môi trường thực tế với quy mô lớn.

Lý thuyết Xích Markov là công cụ toán học mạnh mẽ. Nó được sử dụng để phân tích tính hội tụ của các thuật toán Metaheuristic. Một Xích Markov là một chuỗi các trạng thái. Trạng thái tiếp theo chỉ phụ thuộc vào trạng thái hiện tại, không phụ thuộc vào các trạng thái trước đó. Trong ngữ cảnh của Thuật toán di truyền, mỗi thế hệ của quần thể có thể được xem là một trạng thái. Các toán tử di truyền (lai ghép, đột biến, lựa chọn) xác định các xác suất chuyển tiếp giữa các trạng thái. Luận án sử dụng các khái niệm như tính bất khả quy, tính chu kỳ và tính Ergodic của Xích Markov. Mục tiêu là chứng minh rằng quần thể sẽ cuối cùng đạt đến trạng thái tối ưu. Việc này cung cấp bằng chứng toán học về khả năng tìm kiếm lời giải tốt của thuật toán.

Việc đánh giá tính hội tụ của thuật toán di truyền lai tuần tự cho JSP là bước quan trọng. Nó khẳng định tính đúng đắn của thuật toán. Dựa trên lý thuyết Xích Markov, các điều kiện được thiết lập. Các điều kiện này đảm bảo rằng thuật toán sẽ hội tụ. Cụ thể, khả năng đột biến cho phép mọi trạng thái có thể truy cập được từ bất kỳ trạng thái nào khác. Điều này đảm bảo tính bất khả quy của Xích Markov. Với một hàm thích nghi được định nghĩa tốt và các toán tử di truyền phù hợp, thuật toán có thể chứng minh là hội tụ về tập các lời giải tối ưu toàn cục. Phân tích này cũng xem xét các yếu tố như kích thước quần thể và tỷ lệ các toán tử. Mục tiêu là tối ưu hóa tốc độ hội tụ và chất lượng lời giải cuối cùng.

Các chiến lược chọn lọc như cá thể tinh hoa (elitism) có ảnh hưởng đáng kể đến tính hội tụ của Thuật toán di truyền. Cá thể tinh hoa là việc sao chép trực tiếp cá thể tốt nhất từ thế hệ hiện tại sang thế hệ tiếp theo. Điều này đảm bảo rằng lời giải tốt nhất không bị mất đi. Nó cũng đẩy nhanh tốc độ hội tụ. Tuy nhiên, việc này cũng có thể dẫn đến hội tụ sớm. Nó làm giảm sự đa dạng của quần thể. Luận án phân tích cách thức các toán tử sao chép và chiến lược cá thể tinh hoa ảnh hưởng đến thuộc tính của Xích Markov. Nó chỉ ra rằng dưới các điều kiện nhất định, thuật toán vẫn duy trì khả năng khám phá không gian lời giải. Nó vẫn đảm bảo hội tụ về lời giải tối ưu. Việc cân bằng giữa khám phá và khai thác là chìa khóa để đạt được hiệu suất tốt nhất.