Thuật toán di truyền và các bài toán lập lịch Job Shop - Luận án tiến sĩ Công nghệ Thông tin của Nguyễn Hữu Mùi

Bài toán lập lịch job shop mô tả quá trình xử lý tập hợp gồm n công việc trên m máy khác nhau. Mỗi công việc bao gồm một chuỗi các nguyên công theo thứ tự công nghệ nghiêm ngặt. Mỗi nguyên công yêu cầu một máy cụ thể và có thời gian gia công xác định trước. Mục tiêu chính là cực tiểu hóa tổng thời gian hoàn thành tất cả công việc, hay còn gọi là makespan. JSSP thuộc lớp bài toán NP-hard cực kỳ khó giải. Không gian tìm kiếm phát triển bùng nổ theo hàm mũ khi số lượng công việc và máy móc gia tăng. Nghiên cứu trong luận án tiến sĩ chỉ ra rằng việc tìm nghiệm tối ưu toàn cục bằng phương pháp vét cạn là bất khả thi trong thực tế. Các phương pháp giải chính xác như nhánh cận (Branch and Bound) hay quy hoạch tuyến tính nguyên hỗn hợp (MIP) gặp bế tắc về thời gian tính toán. Do đó, việc ứng dụng các kỹ thuật xấp xỉ và metaheuristic là hướng đi bắt buộc.

Thuật toán di truyền là kỹ thuật tìm kiếm ngẫu nhiên có định hướng dựa trên cơ chế tiến hóa sinh học. Cấu trúc cơ bản của GA bao gồm các thành phần chính: không gian biểu diễn nhiễm sắc thể, quần thể cá thể ban đầu, hàm thích nghi (fitness function) và các toán tử di truyền. Toán tử chọn lọc giữ lại các cá thể có độ thích nghi cao. Toán tử lai ghép (crossover) kết hợp thông tin di truyền từ hai cá thể cha mẹ để sinh ra cá thể con mới. Toán tử đột biến (mutation) biến đổi ngẫu nhiên cấu trúc nhiễm sắc thể nhằm duy trì tính đa dạng của quần thể. Quá trình tiến hóa lặp đi lặp lại qua nhiều thế hệ cho đến khi thỏa mãn điều kiện dừng. Thuật toán di truyền có ưu điểm vượt trội trong việc khám phá không gian tìm kiếm rộng lớn. Tuy nhiên, GA cổ điển dễ rơi vào cực trị địa phương nếu không có cơ chế cân bằng tốt giữa khám phá và khai thác.

Các tiếp cận giải quyết bài toán lập lịch job shop được phân loại thành hai nhóm chính: phương pháp chính xác và phương pháp gần đúng. Phương pháp chính xác đảm bảo tìm được nghiệm tối ưu nhưng giới hạn ở kích thước bài toán nhỏ. Phương pháp gần đúng bao gồm các thuật toán heuristic kinh nghiệm và tối ưu hóa metaheuristic. Các thuật toán heuristic như Shifting Bottleneck hay các quy tắc ưu tiên thực thi nhanh nhưng chất lượng nghiệm không ổn định. Các giải thuật metaheuristic như thuật toán di truyền, Simulated Annealing (SA), Tabu Search (TS) và Ant Colony Optimization (ACO) đạt hiệu năng vượt trội. Luận án tiến sĩ đã tổng kết và chỉ ra những tồn tại lớn của các công trình đi trước. Điểm mấu chốt nằm ở việc biểu diễn nhiễm sắc thể và thiết kế toán tử di truyền đặc thù để đảm bảo tính hợp lệ của lịch biểu sau biến đổi.

Bài toán lập lịch flow shop hoán vị (PFSP) yêu cầu tất cả các công việc đi qua các máy theo cùng một thứ tự công nghệ cố định. Thứ tự gia công công việc trên mọi máy đều giống nhau. Luận án tiến sĩ phân tích chi tiết cách tính thời gian hoàn thành trong một lịch biểu hoán vị. Thuật toán Johnson cung cấp lời giải tối ưu chính xác cho PFSP với trường hợp 2 máy và một số trường hợp đặc biệt của 3 máy. Khi số lượng máy và công việc mở rộng, PFSP trở thành bài toán NP-hard. Nghiên cứu đề xuất thuật toán di truyền mã hóa tự nhiên cho PFSP tổng quát. Chuỗi nhiễm sắc thể là một hoán vị trực tiếp của các số nguyên đại diện cho công việc. Các toán tử lai ghép và đột biến được thiết kế đặc thù nhằm bảo toàn cấu trúc hoán vị, tránh trùng lặp công việc và tối ưu hóa giá trị makespan hiệu quả.

Bài toán lập lịch flow shop tổng quát (FSP) nới lỏng ràng buộc hoán vị so với PFSP. Thứ tự xử lý các công việc trên mỗi máy có thể khác nhau, miễn là tuân thủ thứ tự các công đoạn công nghệ. Luận án tiến sĩ thiết lập không gian tìm kiếm mở rộng cho bài toán FSP. Thuật toán di truyền mã hóa tự nhiên được phát triển để xử lý cấu trúc lịch biểu linh hoạt này. Hệ thống sử dụng nhiễm sắc thể nhiều đoạn hoặc ma trận mã hóa để đại diện cho thứ tự trên từng máy riêng biệt. Hàm thích nghi được tính toán dựa trên thời gian kết thúc của nguyên công cuối cùng. Các thử nghiệm số học trên bộ dữ liệu chuẩn chứng minh thuật toán di truyền hội tụ nhanh về vùng nghiệm tốt. Nghiên cứu này đặt nền tảng vững chắc để phát triển thuật toán di truyền lai cho bài toán JSSP phức tạp hơn.

Lịch biểu bán tích cực và lịch biểu tích cực là hai khái niệm nền tảng trong lý thuyết lập lịch biểu. Một lịch biểu được gọi là tích cực nếu không thể dời bất kỳ nguyên công nào sang trái mà không làm trễ nguyên công khác hoặc vi phạm ràng buộc công nghệ. Thuật toán Giffler and Thompson (GT) là công cụ kinh điển để sinh ra toàn bộ các lịch biểu tích cực. Luận án tiến sĩ tích hợp thuật toán GT vào thủ tục giải mã của thuật toán di truyền lai. Cơ chế này thu hẹp không gian tìm kiếm từ tập hợp tất cả các lịch biểu khả thi xuống chỉ còn tập các lịch biểu tích cực. Nhờ vậy, thuật toán loại bỏ hoàn toàn các phương án kém chất lượng ngay từ giai đoạn sinh nghiệm. Quá trình tiến hóa tập trung hoàn toàn vào vùng không gian chứa các nghiệm tối ưu của makespan.

Để giải quyết triệt để bài toán JSSP, luận án đề xuất phương pháp mã hóa lời giải dựa trên danh sách các nguyên công. Mỗi gen trong nhiễm sắc thể đại diện cho một công việc và số lần xuất hiện của gen tương ứng với số thứ tự nguyên công. Cơ chế này loại bỏ hoàn toàn khả năng sinh ra lịch biểu không hợp lệ trong quá trình tiến hóa. Hàm thích nghi được xây dựng nghịch đảo hoặc chuẩn hóa theo giá trị makespan nhận được từ thuật toán GT. Các toán tử lai ghép như POX (Precedence Preserving Crossover) giữ nguyên thứ tự ưu tiên của các công việc cha mẹ. Toán tử đột biến hoán đổi vị trí các gen tạo ra sự đa dạng cần thiết mà vẫn bảo toàn tính hợp lệ. Quá trình chọn lọc áp dụng kỹ thuật giữ lại cá thể tinh hoa để bảo tồn nghiệm tốt nhất.

Không gian tìm kiếm của bài toán lập lịch job shop vô cùng đồ sộ, dẫn đến chi phí thời gian tính toán lớn. Luận án tiến sĩ đã thực hiện song song hóa thuật toán di truyền lai trên kiến trúc đa luồng và hệ thống đa bộ xử lý (MPP). Mô hình di truyền song song phân chia quần thể thành nhiều quần thể con độc lập theo mô hình đảo. Các quần thể con tiến hóa độc lập trên từng lõi CPU và định kỳ trao đổi các cá thể ưu tú thông qua cơ chế di cư. Nghiên cứu cài đặt chi tiết thủ tục di truyền song song cho JSP và tiến hành thử nghiệm trên các bộ dữ liệu chuẩn quốc tế. Kết quả thực nghiệm cho thấy thuật toán song song đạt tốc độ tăng tốc gần như tuyến tính, đồng thời nâng cao chất lượng nghiệm tìm được.

Xích Markov là một quá trình ngẫu nhiên có bộ nhớ hữu hạn, trong đó xác suất chuyển sang trạng thái tương lai chỉ phụ thuộc vào trạng thái hiện tại. Luận án tiến sĩ hệ thống hóa các định nghĩa và tính chất cơ bản của xích Markov rời rạc thời gian. Xích Markov Ergodic là xích thỏa mãn đồng thời tính bất khả quy và tính phi chu kỳ. Đối với xích Markov Ergodic, tồn tại duy nhất một phân phối dừng xác định độc lập với trạng thái khởi đầu. Ma trận chuyển trạng thái của thuật toán di truyền được phân tích thành tích của các ma trận chuyển tương ứng với phép chọn lọc, phép lai ghép và phép đột biến. Việc thiết lập ma trận chuyển giúp lượng hóa xác suất di chuyển giữa các cấu hình quần thể trong không gian tìm kiếm nghiệm của JSSP.

Luận án tiến sĩ phân tích sâu sắc tính hội tụ của hai mô hình di truyền: GA truyền thống và GA cải tiến có toán tử tinh hoa. Trong thuật toán di truyền truyền thống, xác suất tìm thấy nghiệm tối ưu tại thế hệ vô cùng phụ thuộc vào phân phối dừng và có thể không đạt giá trị 1 do hiện tượng trôi dạt di truyền. Ngược lại, khi tích hợp chiến lược lưu giữ cá thể tinh hoa và toán tử sao chép, trạng thái chứa cá thể tốt nhất trở thành trạng thái hấp thụ hoặc duy trì đơn điệu không giảm về độ thích nghi. Nghiên cứu chứng minh định lý toán học khẳng định: dãy nghiệm tốt nhất do thuật toán di truyền lai sinh ra sẽ hội tụ với xác suất bằng 1 về tập nghiệm tối ưu toàn cục của bài toán lập lịch job shop khi số thế hệ tiến ra vô cùng.

Bài toán flexible job shop scheduling (FJSP) là bước mở rộng tự nhiên và thực tế hơn của bài toán lập lịch job shop truyền thống. Trong FJSP, không gian bài toán gồm hai bài toán con lồng ghép: phân công máy cho từng nguyên công (machine assignment) và sắp xếp thứ tự gia công trên từng máy (operation sequencing). Độ phức tạp của FJSP cao hơn đáng kể so với JSSP kinh điển. Để giải quyết FJSP, cấu trúc nhiễm sắc thể trong thuật toán di truyền cần được thiết kế dạng hai chuỗi: một chuỗi quy định gán máy và một chuỗi quy định thứ tự nguyên công. Luận án chỉ ra rằng thuật toán di truyền lai có thể tích hợp thêm các heuristic chọn máy như phân phối tải tối thiểu để tối ưu hóa đồng thời cả hai bài toán con, mang lại lời giải lịch biểu khả thi cao.

Trong môi trường sản xuất thực tế, việc tối ưu hóa duy nhất chỉ số makespan là chưa đủ để đáp ứng yêu cầu quản lý toàn diện. Các hệ thống hiện đại đòi hỏi bài toán tối ưu hóa đa mục tiêu (Multi-objective Optimization) cân nhắc đồng thời nhiều tiêu chí cạnh tranh. Các mục tiêu này bao gồm: cực tiểu hóa makespan, cực tiểu hóa tổng độ trễ hạn của các đơn hàng, giảm thiểu chi phí điện năng tiêu thụ và tối đa hóa độ tin cậy của thiết bị. Thuật toán di truyền đa mục tiêu như NSGA-II có thể kết hợp với các toán tử di truyền lai của luận án để tìm tập nghiệm không bị chi phối (Pareto front). Đây là định hướng nghiên cứu có giá trị ứng dụng cao trong chuyển đổi số và tự động hóa nhà máy thông minh.