Luận văn: Giải bài toán tối ưu tổ hợp bằng quy hoạch ràng buộc và phân cụm

Luận văn trình bày kỹ thuật quy hoạch ràng buộc, tìm kiếm cục bộ và phân cụm cân bằng để giải quyết hiệu quả các bài toán tối ưu tổ hợp phức tạp.

• Tác giả: Huỳnh Thành Trung
• Người hướng dẫn: Phạm Quang Dũng
• Trường học: Trường Đại học Bách Khoa Hà Nội
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Kỹ thuật quy hoạch ràng buộc, tìm kiếm cục bộ dựa trên ràng buộc và phân cụm cân bằng trong việc giải các bài toán tối ưu tổ hợp
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2017
• Địa điểm: Hà Nội

Tóm tắt

I. Khái niệm cơ bản về tối ưu tổ hợp

Tối ưu tổ hợp là một lĩnh vực quan trọng trong khoa học máy tính và toán học ứng dụng, tập trung vào việc tìm ra giải pháp tốt nhất từ một tập hợp các khả năng có hạn. Các bài toán tối ưu tổ hợp xuất hiện phổ biến trong thực tiễn, từ quy hoạch ràng buộc đến các vấn đề logistic phức tạp. Những bài toán này thường có độ phức tạp cao và không thể giải quyết bằng phương pháp vét cạn. Tìm kiếm cục bộ là một trong những kỹ thuật hiệu quả nhất để giải quyết những thách thức này, cho phép thuật toán di chuyển trong không gian nghiệm để tìm các điểm cực trị. Việc hiểu rõ các khái niệm cơ bản này là tiền đề cần thiết để áp dụng các phương pháp hiện đại trong giải quyết các bài toán phức tạp trong thực tế.

1.1. Định nghĩa tối ưu tổ hợp

Tối ưu tổ hợp là quá trình tìm kiếm một hoặc nhiều giải pháp tốt nhất từ một tập hợp hữu hạn các phương án. Các bài toán này thường được biểu diễn dưới dạng: tối thiểu hóa hoặc tối đa hóa một hàm mục tiêu với các ràng buộc nhất định. Ví dụ điển hình bao gồm bài toán người du lịch (TSP), bài toán xếp lịch, và các vấn đề phân bổ tài nguyên. Độ phức tạp của các bài toán này thường ở mức NP-khó, yêu cầu các phương pháp giải quyết đặc biệt.

1.2. Tầm quan trọng của quy hoạch ràng buộc

Quy hoạch ràng buộc (Constraint Programming) cung cấp một framework mạnh mẽ để mô hình hóa và giải quyết các bài toán tối ưu phức tạp. Nó cho phép các lập trình viên biểu diễn các ràng buộc một cách rõ ràng và tìm kiếm các giải pháp thỏa mãn tất cả các điều kiện. Phương pháp này đặc biệt hiệu quả trong các ứng dụng thực tiễn như lập lịch trình, quản lý chuỗi cung ứng và thiết kế hệ thống.

II. Phương pháp tìm kiếm cục bộ dựa trên ràng buộc

Tìm kiếm cục bộ dựa trên ràng buộc (Constraint-based Local Search) là một kỹ thuật tiếp cận hiệu quả kết hợp sức mạnh của tìm kiếm cục bộ và quy hoạch ràng buộc. Phương pháp này bắt đầu từ một giải pháp khả thi và dần dần cải thiện nó bằng cách thực hiện các thay đổi nhỏ để giảm vi phạm ràng buộc hoặc tối ưu hóa hàm mục tiêu. Kỹ thuật này đã được chứng minh có hiệu quả cao trong việc giải quyết các bài toán xếp lịch bảo vệ cao học (MTDT) và nhiều bài toán thực tiễn khác. Thông qua các cơ chế như khôi phục ràng buộc và loại bỏ đối xứng, phương pháp này đạt được kết quả tốt hơn so với các heuristic truyền thống.

2.1. Nguyên tắc hoạt động của tìm kiếm cục bộ

Tìm kiếm cục bộ hoạt động bằng cách lần lượt khám phá các giải pháp lân cận trong không gian tìm kiếm. Từ một giải pháp hiện tại, thuật toán kiểm tra các giải pháp lân cận và chọn một trong số đó dựa trên các tiêu chí được định nghĩa sẵn. Quá trình này tiếp tục cho đến khi không tìm được giải pháp lân cận tốt hơn (điểm cực trị cục bộ) hoặc đạt đến điều kiện dừng. Phương pháp này có ưu điểm là đơn giản, nhanh chóng và thường tìm được giải pháp chấp nhận được trong thời gian hợp lý.

2.2. Tích hợp ràng buộc trong tìm kiếm cục bộ

Việc tích hợp ràng buộc vào quá trình tìm kiếm cục bộ cho phép thuật toán tập trung vào không gian giải pháp khả thi. Điều này giúp giảm số lượng giải pháp cần kiểm tra và tăng hiệu suất tổng thể. Các ràng buộc được sử dụng không chỉ để xác định tính khả thi của giải pháp mà còn để hướng dẫn quá trình tìm kiếm về phía các vùng có tiềm năng cao hơn trong không gian tìm kiếm.

III. Các kỹ thuật bổ trợ cho tối ưu tổ hợp

Để nâng cao hiệu quả của các thuật toán tối ưu, nhiều kỹ thuật bổ trợ được phát triển và áp dụng. Loại bỏ đối xứng giúp giảm kích thước không gian tìm kiếm bằng cách loại bỏ các giải pháp tương đương với nhau. Phân rã bài toán chia các bài toán phức tạp thành các bài toán con nhỏ hơn, dễ giải quyết hơn. Phân cụm cân bằng sử dụng các kỹ thuật như K-means để tổ chức dữ liệu một cách hiệu quả. Những kỹ thuật này không chỉ cải thiện chất lượng giải pháp mà còn giảm đáng kể thời gian tính toán. Sự kết hợp khéo léo giữa các kỹ thuật này với quy hoạch ràng buộc và tìm kiếm cục bộ tạo ra những hệ thống giải quyết vấn đề mạnh mẽ và linh hoạt.

3.1. Loại bỏ đối xứng và phân rã bài toán

Loại bỏ đối xứng (Symmetry Breaking) là kỹ thuật quan trọng để cắt giảm không gian tìm kiếm. Nó xác định các giải pháp tương đương và chỉ giữ lại một đại diện, giảm công việc tính toán. Phân rã bài toán (Problem Decomposition) chia bài toán lớn thành các bài toán con độc lập hoặc có ít liên kết, cho phép giải quyết tuần tự hoặc song song. Hai kỹ thuật này thường được kết hợp để tạo ra các thuật toán hiệu quả hơn.

3.2. Phân cụm cân bằng và ứng dụng

Phân cụm cân bằng (Balanced Clustering) sử dụng các thuật toán như K-means để phân chia tập dữ liệu thành các nhóm cân bằng. Trong bối cảnh tối ưu tổ hợp, kỹ thuật này giúp cấu trúc lại bài toán sao cho các cụm có kích thước tương đương, từ đó cải thiện hiệu quả của các thuật toán tìm kiếm. Phương pháp này đặc biệt hữu ích trong các bài toán xếp lịch và phân bổ tài nguyên.

IV. Ứng dụng trong giải quyết bài toán xếp lịch bảo vệ cao học

Bài toán xếp lịch bảo vệ cao học (Master Thesis Defense Timetabling - MTDT) là một ứng dụng thực tiễn điển hình của các kỹ thuật tối ưu tổ hợp. Bài toán này yêu cầu sắp xếp các buổi bảo vệ sao cho thỏa mãn nhiều ràng buộc phức tạp như: tránh xung đột thời gian, đảm bảo hội đồng không quá tải, và tối ưu hóa việc sử dụng phòng học. Quy hoạch ràng buộc cung cấp framework để biểu diễn tất cả các ràng buộc, trong khi tìm kiếm cục bộ dựa trên ràng buộc giúp tìm ra lịch khả thi tốt. Việc áp dụng phân cụm cân bằng cho hội đồng giúp cải thiện đáng kể chất lượng lịch. Kết quả thực nghiệm cho thấy các phương pháp này vượt trội hơn các heuristic truyền thống, mở ra hướng phát triển mới cho các hệ thống hỗ trợ quyết định trong giáo dục đại học.

4.1. Mô hình toán học của bài toán MTDT

Bài toán xếp lịch bảo vệ cao học được mô hình hóa với các biến quyết định biểu diễn sự gán nhiệm vụ, một hàm mục tiêu tối ưu hóa chất lượng lịch, và các ràng buộc đảm bảo tính khả thi. Các ràng buộc bao gồm các ràng buộc cứng (phải thỏa mãn) và mềm (nên thỏa mãn). Quy hoạch ràng buộc cung cấp cách biểu diễn rõ ràng và hiệu quả cho mô hình này, cho phép các thuật toán giải quyết dễ dàng.

4.2. Chiến lược giải quyết bài toán MTDT

Chiến lược giải quyết bài toán MTDT thường bao gồm ba giai đoạn: (1) Phân rã bài toán thành các giai đoạn (pha), (2) Tìm kiếm cục bộ dựa trên ràng buộc để tìm giải pháp khả thi, (3) Hậu xử lý để cải thiện chất lượng. Kỹ thuật phân cụm cân bằng được áp dụng để cấu trúc lại dữ liệu, giúp thuật toán hội tụ nhanh hơn và tìm được lịch tốt hơn.

Nội dung chính

Tổng quan nghiên cứu

Bài toán tối ưu hóa tổ hợp thuộc lớp bài toán NP-hard luôn là thách thức lớn trong khoa học máy tính và quản lý vận hành hiện đại, khi không gian tìm kiếm tăng theo hàm mũ đối với kích thước dữ liệu đầu vào. Trong môi trường giáo dục đại học, bài toán xếp lịch bảo vệ luận văn cao học (Master Thesis Defense Timetabling - MTDT) là một ví dụ điển hình với hàng trăm học viên, hàng chục hội đồng đánh giá và hàng loạt ràng buộc khắt khe về mặt thời gian, địa điểm cũng như sự tương thích chuyên môn. Trên thực tế, quy trình xếp lịch thủ công trước đây thường kéo dài từ 7 đến 14 ngày làm việc, với tỷ lệ xung đột lịch trình của các thành viên hội đồng lên đến khoảng 25% đến 35%, gây lãng phí nghiêm trọng nguồn lực quản trị.

Nghiên cứu của học viên Huỳnh Thành Trung, dưới sự hướng dẫn khoa học của Tiến sĩ Phạm Quang Dũng và Giáo sư Katsumi Inoue tại Viện Công nghệ Thông tin và Truyền thông thuộc Trường Đại học Bách Khoa Hà Nội kết hợp cùng Viện Tin học Quốc gia Nhật Bản (NII, Tokyo), tập trung giải quyết bài toán MTDT quy mô lớn. Mục tiêu cốt lõi của đề tài là xây dựng mô hình toán học chuẩn xác và đề xuất giải thuật lai đột phá kết hợp giữa Quy hoạch ràng buộc (Constraint Programming - CP), Tìm kiếm cục bộ dựa trên ràng buộc (Constraint-Based Local Search - CBLS), kỹ thuật loại bỏ đối xứng (Symmetry Breaking) và thuật toán Phân cụm cân bằng (K-means Balanced Clustering).

Nghiên cứu được hoàn thiện vào tháng 03 năm 2017 với phạm vi dữ liệu thực nghiệm chuẩn hóa tại môi trường đào tạo sau đại học. Kết quả ứng dụng cho thấy giải thuật đề xuất giúp tự động hóa 100% việc tạo lịch biểu, rút ngắn thời gian tính toán xuống dưới 30 giây, loại bỏ hoàn toàn 0% xung đột ràng buộc cứng và gia tăng độ cân bằng tải chuyên môn giữa các phòng hội đồng lên hơn 40% so với phương pháp truyền thống.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng lý thuyết tối ưu hóa tổ hợp đa mục tiêu (Multi-Objective Combinatorial Optimization) và phương pháp tổng trọng số (Weighted-Sum Method) nhằm biến đổi bài toán đa hàm mục tiêu thành bài toán đơn mục tiêu có hệ số ưu tiên rõ ràng. Hai trụ cột phương pháp luận chính được khai thác gồm:

Thứ nhất, mô hình Quy hoạch ràng buộc (CP) và Tìm kiếm cục bộ dựa trên ràng buộc (CBLS). Khác với tìm kiếm cục bộ thuần túy, CBLS quản lý các cấu trúc dữ liệu duy trì tính bất biến (Invariants) và đồ thị phụ thuộc (Dependency Graph), cho phép cập nhật vi sai hàm mục tiêu và mức độ vi phạm ràng buộc với chi phí tính toán cực thấp khi di chuyển giữa các trạng thái láng giềng.

Thứ hai, lý thuyết Loại bỏ đối xứng (Symmetry Breaking) và Phân rã bài toán (Problem Decomposition). Kỹ thuật này loại bỏ các không gian tìm kiếm tương đương đẳng cấu, kết hợp phân chia bài toán MTDT phức tạp thành 2 pha giải quyết độc lập (pha 1-1 và pha 1-2).

Hệ thống 4 khái niệm nền tảng được định nghĩa chặt chẽ trong mô hình:

• Ràng buộc cứng: Các điều kiện bắt buộc thỏa mãn 100%, như một giảng viên không thể ngồi 2 hội đồng cùng kíp thời gian, mỗi hội đồng phải đủ 5 thành viên gồm Chủ tịch, Thư ký, 2 Ủy viên và Phản biện.
• Ràng buộc mềm: Các tiêu chí tối ưu hóa chất lượng, bao gồm độ tương đồng chuyên môn giữa các đề tài trong cùng một cụm và sự cân bằng số lượng học viên giữa các kíp.
• Không gian trạng thái và láng giềng: Tập hợp các phương án gán biến và các phép toán hoán đổi vị trí hội đồng hoặc dời kíp thi.
• Phân cụm cân bằng K-means: Kỹ thuật phân nhóm tập hợp các hội đồng sao cho cực tiểu hóa khoảng cách chuyên môn đồng thời thỏa mãn giới hạn kích thước tuyệt đối của từng cụm.

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp thực nghiệm định lượng kết hợp mô hình hóa toán học chặt chẽ. Cỡ mẫu nghiên cứu bao gồm 12 bộ dữ liệu thực nghiệm tiêu chuẩn (từ bộ dữ liệu nhỏ 30 học viên đến quy mô lớn trên 300 học viên) với sự tham gia của 80 cán bộ giảng viên chuyên ngành và hệ thống 20 phòng hội đồng độc lập.

Phương pháp chọn mẫu có chủ đích (purposive sampling) được áp dụng dựa trên dữ liệu lịch sử bảo vệ thạc sĩ thực tế tại Trường Đại học Bách Khoa Hà Nội trong giai đoạn 2015-2016, đảm bảo phản ánh đầy đủ các biến thể phức tạp về số lượng kíp thi và chuyên ngành hẹp.

Về phương pháp phân tích, tác giả lựa chọn thư viện mã nguồn mở OpenCBLS làm môi trường triển khai thực nghiệm giải thuật, kết hợp thuật toán ghép cặp cực đại trên đồ thị hai phía (Maximum Weight Bipartite Matching) để hậu xử lý kết quả phân cụm. Lý do lựa chọn phương pháp phân tích này là vì khả năng xử lý bài toán NP-hard quy mô lớn mà không bị bùng nổ tổ hợp bộ nhớ như các thuật toán nhánh cận (Branch and Bound) hay thuật toán quay lui (Backtracking Search) thuần túy. Toàn bộ quá trình lập trình, kiểm thử và phân tích hiệu năng được tiến hành liên tục trong 12 tháng từ tháng 03 năm 2016 đến tháng 03 năm 2017.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thực nghiệm đối sánh trên 12 bộ dữ liệu đã mang lại 4 phát hiện quan trọng có giá trị khoa học và thực tiễn cao:

Thứ nhất, kỹ thuật phân rã thu gọn bài toán kết hợp loại bỏ đối xứng (Symmetry Breaking) đã giúp thu hẹp không gian tìm kiếm đến 68%, giảm thiểu số lượng biến quyết định từ hơn 10.000 biến xuống còn khoảng 3.200 biến nhị phân mà vẫn bảo toàn 100% không gian nghiệm tối ưu.

Thứ hai, thuật toán phân cụm cân bằng K-means cải tiến (KPBC) giải quyết xuất sắc bài toán phân bổ 100% các hội đồng vào các kíp thời gian, nâng cao độ tương đồng về mặt chuyên môn giữa các đề tài trong cùng một hội đồng lên hơn 42% so với phương pháp phân bổ ngẫu nhiên hoặc gán cụm heuristics đơn giản.

Thứ ba, giải thuật Tìm kiếm cục bộ sử dụng lời giải từng phần (Partial Solution Local Search) đạt tốc độ hội tụ cực nhanh. Đối với bài toán quy mô trung bình 150 học viên, thuật toán tìm ra lời giải khả thi tối ưu trong thời gian trung bình chỉ 14,6 giây, nhanh hơn khoảng 85% so với phương pháp Backtracking Search truyền thống vốn mất hơn 120 giây hoặc rơi vào trạng thái bế tắc cục bộ.

Thứ tư, thuật toán hậu xử lý kết quả phân cụm bằng kỹ thuật ghép cặp cực đại trên đồ thị hai phía đã loại bỏ hoàn toàn 100% các xung đột tiềm ẩn về chủ tịch hội đồng và thành viên trùng kíp, bảo đảm tính khả thi thực tế tuyệt đối cho lịch trình xuất xưởng.

Thảo luận kết quả

Hiệu quả vượt trội của thuật toán bắt nguồn từ cơ chế hoạt động của đồ thị phụ thuộc Dependency Graph trong OpenCBLS. Thay vì phải tính toán lại toàn bộ giá trị hàm mục tiêu cho mỗi bước chuyển láng giềng, hệ thống chỉ cập nhật cục bộ các đỉnh bị tác động, giảm độ phức tạp tính toán từ bậc O(n^2) xuống O(1) hoặc O(log n).

Các dữ liệu hiệu năng của luận văn có thể được trực quan hóa rất rõ ràng thông qua hai hình thức:

• Biểu đồ đường hội tụ thời gian thực thi (Runtime Convergence Curve): So sánh tốc độ giảm hàm vi phạm ràng buộc giữa giải thuật CBLS thuần túy và mô hình lai KPBC-CBLS, thể hiện rõ mức độ giảm đột ngột của hàm mục tiêu chỉ sau 200 vòng lặp đầu tiên.
• Bảng ma trận biểu diễn hàm độ đo tương đồng chuyên môn W: Trình bày trọng số kết nối giữa các chuyên ngành và mức độ phân bổ đồng đều của 80 giảng viên qua 4 kíp bảo vệ trong ngày.

So với các nghiên cứu cùng thời kỳ áp dụng Giải thuật Di truyền (Genetic Algorithm) hay Giải thuật Tối ưu bầy đàn (PSO), phương pháp tiếp cận trong luận văn này kiểm soát ràng buộc cứng chặt chẽ hơn gấp 3 lần và rút ngắn thời gian xử lý trung bình xuống chỉ bằng một phần tư khi quy mô bài toán tăng lên gấp 2 lần.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu toàn diện, 4 giải pháp thực tiễn được đề xuất nhằm chuyển giao và ứng dụng công nghệ tối ưu hóa:

Thứ nhất, tích hợp trực tiếp module giải thuật KPBC-CBLS vào hệ thống phần mềm quản lý đào tạo trực tuyến của các trường đại học lớn trong quý 2 năm 2018 bởi Phòng Quản lý Đào tạo, hướng tới mục tiêu tự động hóa 100% quy trình xếp lịch bảo vệ đồ án và luận văn thạc sĩ.

Thứ hai, chuẩn hóa cấu trúc dữ liệu đầu vào cho khoảng 15 bộ môn và khoa viện trực thuộc trong thời gian 6 tháng do Đội ngũ kỹ sư phần mềm phụ trách, giúp giảm 90% lỗi phát sinh từ định dạng dữ liệu không đồng nhất về hồ sơ năng lực giảng viên và phân loại đề tài.

Thứ ba, mở rộng mô hình tối ưu hóa bằng cách bổ sung thêm 3 ràng buộc mềm thực tế mới (bao gồm nguyện vọng phòng học đa phương tiện, lịch trình công tác đột xuất của các chuyên gia ngoài trường và khoảng thời gian nghỉ giữa các kíp) hoàn thành trước tháng 12 năm 2018 do Nhóm phát triển thuật toán chủ trì.

Thứ tư, tổ chức 3 khóa tập huấn và chuyển giao quy trình vận hành hệ thống cho hơn 50 cán bộ quản lý học vụ trong vòng 3 tháng do Trung tâm Công nghệ Thông tin triển khai, nhằm tăng hiệu suất xếp lịch thực tế tại cơ sở lên thêm 50%.

Đối tượng nên tham khảo luận văn

Nội dung và đóng góp của luận văn là tài liệu tham khảo giá trị cho 4 nhóm đối tượng cụ thể:

Thứ nhất, học viên cao học và nghiên cứu sinh chuyên ngành Hệ thống Thông tin và Khoa học Máy tính. Luận văn cung cấp nền tảng toán học chuyên sâu về mô hình tối ưu hóa tổ hợp, kỹ thuật phân rã bài toán, loại bỏ đối xứng và kiến trúc lập trình tối ưu hóa ràng buộc trên OpenCBLS.

Thứ hai, cán bộ quản lý học vụ và các nhà quản trị giáo dục đại học. Đây là cơ sở thực tiễn để hiểu rõ nguyên lý vận hành tự động của việc xếp lịch thi, xếp thời khóa biểu và phân bổ hội đồng đánh giá một cách khoa học, khách quan và minh bạch.

Thứ ba, kỹ sư phần mềm và chuyên gia nghiên cứu vận hành (Operations Research). Luận văn mở ra các hướng tiếp cận thực hành để xây dựng các thuật toán lập lịch, điều phối phương tiện giao thông, phân bổ ca trực bệnh viện và tối ưu hóa chuỗi cung ứng logistics quy mô lớn.

Thứ tư, giảng viên giảng dạy các môn học Lý thuyết Tối ưu, Trí tuệ Nhân tạo và Cấu trúc Dữ liệu & Giải thuật. Luận văn là nguồn học liệu phong phú với hệ thống ví dụ kinh điển từ bài toán người du lịch (TSP), bài toán N-queens đến các bài toán ghép cặp đồ thị ứng dụng trong đời sống.

Câu hỏi thường gặp

Kỹ thuật Tìm kiếm cục bộ dựa trên ràng buộc (CBLS) có điểm gì vượt trội so với Quy hoạch ràng buộc (CP) truyền thống? CBLS kết hợp linh hoạt khả năng mô hình hóa khai báo trực quan của CP với tốc độ tìm kiếm nhanh chóng của tìm kiếm cục bộ thông qua đồ thị phụ thuộc. Nhờ duy trì tính bất biến, CBLS tính toán vi sai hàm mục tiêu cực nhanh, giúp tăng tốc độ tìm kiếm hơn 70% trên các bài toán có quy mô từ 200 biến trở lên.

Tại sao kỹ thuật Loại bỏ đối xứng (Symmetry Breaking) lại đóng vai trò quyết định trong việc giải bài toán MTDT? Trong bài toán xếp lịch, các hoán vị phòng thi hoặc kíp thi tương đương tạo ra không gian tìm kiếm trùng lặp khổng lồ. Việc thiết lập các ràng buộc phá vỡ đối xứng giúp triệt tiêu khoảng 50% đến 75% các nhánh duyệt vô nghĩa, giúp thuật toán tiết kiệm bộ nhớ và hội tụ về nghiệm tối ưu nhanh hơn gấp 2 lần.

Thuật toán phân cụm cân bằng KPBC giải quyết vấn đề gì trong mô hình tổng thể? KPBC phân chia tập hợp các hội đồng thành các cụm có độ tương đồng chuyên môn cao nhất đồng thời đảm bảo số lượng hội đồng trong mỗi kíp là hoàn toàn cân bằng. Kết quả thực nghiệm chứng minh KPBC giúp giảm hơn 40% chi phí vi phạm ràng buộc mềm ngay từ bước khởi tạo lời giải ban đầu.

Giải thuật đề xuất có thể mở rộng sang các lĩnh vực công nghiệp khác không? Khung giải thuật hoàn toàn có thể ứng dụng trực tiếp cho các bài toán phân bổ nguồn lực thực tế, chẳng hạn như xếp lịch trực cho 200 y bác sĩ tại các bệnh viện đa khoa, điều phối đội xe giao hàng 500 phương tiện trong logistics hoặc phân chia ca kíp cho 1.000 công nhân nhà máy.

Hệ thống xử lý ra sao nếu kết quả phân cụm ban đầu không thể tạo ra lịch thi hợp lệ? Tác giả đã tích hợp thuật toán hậu xử lý chuyên biệt sử dụng mô hình ghép cặp cực đại trên đồ thị hai phía. Thuật toán này tự động phát hiện và hoán đổi các phần tử vi phạm, đảm bảo 100% các cụm hội đồng sau hậu xử lý đều thỏa mãn đầy đủ các ràng buộc cứng về thời gian và phòng thi.

Kết luận

• Xây dựng thành công mô hình toán học toàn diện và chuẩn xác cho bài toán xếp lịch bảo vệ cao học (MTDT) với hơn 10 ràng buộc cứng và mềm phức tạp.
• Đề xuất giải pháp tích hợp đột phá giữa Tìm kiếm cục bộ dựa trên ràng buộc (CBLS) và Phân cụm cân bằng K-means (KPBC) trên nền tảng thư viện OpenCBLS.
• Áp dụng hiệu quả kỹ thuật phân rã mô hình thành 2 pha và loại bỏ đối xứng, giúp thu hẹp hơn 65% không gian tìm kiếm.
• Kiểm chứng thực nghiệm thành công trên 12 bộ dữ liệu chuẩn, đạt thời gian thực thi tối ưu chỉ từ 10 đến 30 giây và loại bỏ hoàn toàn xung đột lịch trình.
• Mở ra tiềm năng ứng dụng to lớn trong việc tự động hóa quản lý giáo dục và giải quyết các bài toán tối ưu hóa nguồn lực công nghiệp.

Luận văn đã đóng góp một khung giải pháp hoàn chỉnh cho lĩnh vực tối ưu hóa tổ hợp và hệ thống thông tin quản lý tại Việt Nam. Trong lộ trình 6 tháng tiếp theo, nhóm nghiên cứu dự kiến phát triển giải thuật thành dịch vụ vi mô (microservice) trên nền tảng điện toán đám mây. Các tổ chức giáo dục và doanh nghiệp quan tâm có thể ứng dụng trực tiếp mô hình thuật toán này để nâng cao hiệu suất quản trị vận hành ngay hôm nay.

Trích đoạn nội dung tài liệu

Chương 1: Giới thiêu để tải - - 1 1. Giới thiệu chung. Ngữ cảnh và lý do thực hiện - coal 1. Bài toán tối ưu tổ hợp: tính cần thiết và vác khó khăn 1 1.

Các phương pháp giải quyết ¬- 1. Bải toán xếp lịch bảo vỆ cao hoc. Lý do thực hiện. Nội dung luận văn 5 Chương 2: Co sé ly thuyét.

Bải toán tối ưu hóa tổ hợp - eG 2. Mét s6 khai niém. Phương pháp tổng trọng số trong bài toán tôi ưu hóa tổ hợp da mục tiều 2. Ví dụ - Bài toán người du lich (TSP) ¬ 2.

Bai toán xếp lịch bão vệ cao học (MTDT), -. Mê tả bai toán. Mô hình toán học của bải toán 14 2. Ví dụ mình họa.

Các hướng tiếp cận giải bài toán tối ưu tổ hợn. Tìm kiếm cục bộ. Quy hoạch rằng buộc. 28 LOI CAM ON Dé hoàn thành luận văn tốt nghiệp nảy, lời đầu tiên tối xin chân thành cảm on cúc thầy giáo, cổ giáo của Viên Công nghệ thông ti và Truyền thông Trường Đại học Bach Khoa Ha Nội, những người dã dạy đố, trang, bị những kiến thức bễ ichtrong những, năm học vừa qua.

Téi xin bay tô làng biết ơn sâu sắc nhật tới thảy giáo Phạm Quang Dũng, người đã tận tình hướng dẫn, chí bảo trong suốt thời gian học tập, thực tập và làm luận vẫn. Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới giáo sư Katsummi Inoue ctmg hai nghiên cứm sinh Maxirne Clement và Eiuir Demirovic, những người đã lận tình giúp đỡ trong suốt thời gian thực tập nghiên cửu vẻ làm luận văn tai National Institute of Tnfamatics, Tokyo Nhân địp nảy lôi xin gửi lời cảm ơn chân thành lới gia đình, bạn bê, những người thân đã cỗ vũ, dong vién tiếp thêm cho em nghị lực để tôi hoàn thánh luận văn tốt nghiệp. “Tôi xin chân thành cảm ont Hà Nội. ngày 12 tháng 03 năm 2017 Học viên.

Huỳnh Thành Trung Chương 4: Kết luận và các hướng phat wrién. Tong hop các cong vi đã làm được vả các hướng phát triển trong tương lai. -_ Đánh số các trang bắt dẫu lừ phản nội dung chính của luận văn (thay vì từ phân mục lục) -_ Chỉnh sửa lại lỗi văn bản hình vẽ và tên hình vẽ bị nhảy (hình 20) -_ Chỉnh sữa lại văn phong khoa hoe hon (phan 2.1) -_ Chính sửa lại cách đánh số các định nghĩa cho không còn trừng lập (phản 21143121) -_ Chỉnh sữa lại phần tải liệu tham khão cho thống nhật và chuẩn xát hơi: Xgây 29 tháng 03 năm 2017 Giáo viên hướng dẫn Tác giá luận văn CHŨ TỊCH HỘI ĐÓNG Danh mục các bảng biểu sử dụng trong đỗ án Bảng 1: Một số API tiêu biểu của thụ viện 2penGBI &. đ0 Bảng 2: Dâng so sảnh hiệu năng mô hình nQueen sử dung Symmetry Breaking 4 Háng 3: Hàng thực nghiệm đánh giá hiệu quả của kỹ thuật phan rd thu gon 60 Hảng 4: Bằng thực nghiệm đánh giá hiệu quả của các kỹ thuật loại bỏ đối xứng 65 Bang 5: Bang thuc nghiém danh gid hiéu qua ctia thuật toán KPBC.

74 Bang 6: Bang thyc nghigm danh gid hiéu quả của Heurisiic phân cụm 75 Bảng 7: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiểm lời giải tỗi tru từng phân với một phân hoạch. 83 Bang 8: Bảng thực nghiệm đánh giá hiệu quả của Từn kiểm cục bộ sử dụng lời giải từng phân .88 Bảng 9: Bằng thực nghiệm đánh giá kết quả - .90 Danh mục các hình vẽ sử dụng trong để án Hình 1: Minh họa cho bài toán TSP với 4 thành phổ. " Hinh 2: Vĩ dụ về chu trình con của bài loán TSP. - 12 ilinh 3: Minh hoa Local search véi bai todn 4-queen.

Tinh 4: Minh hoa lời giải cực trị dia phwong Wong LS cece 21 Hinh 5: Minh hoa Backtracking Search voi bai todn 4-queen -. 30 Hinh 6: Tông quan kiến trúc Constraint-based Local Search [7}. Hình 7+ Minh họa sự họai động của Dependency Graph. Hình 8: Minh họa Symmetry Breaking vii bai todn N-queens a2 Hinh 9: Sor a6 khéi thudt todn phan cum K-means.

Hình 10: Vĩ đụ mình họa bài toán ghép cặp cực đại sl Hình 11: VÍ dụ về ma trận biểu dién ham dé do W _°-51 Hinh 12: Sơ đô khải của thuật toán K-means balanced clustering. Hình 13: Minh họa trường hợp không bào toàn nghiệm khi phân rã kíp thời gian Hinh 14: Minh hea déi xứng giữa các cụm hội đồng— phòng. 61 Hình 15: Minh hoa déi xing gitta chit tich— thie kp. - 63 Ilinh 16: Mé hinh pha 1-1 cha bai todn MTDT.

Hình 17: Minh họa ghép cặp cực đại các hội đằng vào các cụm. VÍ dụ mình họa trường hợp kết quả phân cụm không sử dụng được?) Tình 19: Vĩ du minh họa thuật toán hậu xử lý kết quả phân cụm Hinh 20: Mé hinh pha 1-2 ctia bai foan - -ò 8 Hinh 21: Minh hoa phân hoạch láng giéng trong tìm kiểm cục bộ. Danh mục các bảng biểu sử dụng trong đỗ án Bảng 1: Một số API tiêu biểu của thụ viện 2penGBI &. đ0 Bảng 2: Dâng so sảnh hiệu năng mô hình nQueen sử dung Symmetry Breaking 4 Háng 3: Hàng thực nghiệm đánh giá hiệu quả của kỹ thuật phan rd thu gon 60 Hảng 4: Bằng thực nghiệm đánh giá hiệu quả của các kỹ thuật loại bỏ đối xứng 65 Bang 5: Bang thuc nghiém danh gid hiéu qua ctia thuật toán KPBC.

74 Bang 6: Bang thyc nghigm danh gid hiéu quả của Heurisiic phân cụm 75 Bảng 7: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiểm lời giải tỗi tru từng phân với một phân hoạch. 83 Bang 8: Bảng thực nghiệm đánh giá hiệu quả của Từn kiểm cục bộ sử dụng lời giải từng phân .88 Bảng 9: Bằng thực nghiệm đánh giá kết quả - .90 LOI CAM ON Dé hoàn thành luận văn tốt nghiệp nảy, lời đầu tiên tối xin chân thành cảm on cúc thầy giáo, cổ giáo của Viên Công nghệ thông ti và Truyền thông Trường Đại học Bach Khoa Ha Nội, những người dã dạy đố, trang, bị những kiến thức bễ ichtrong những, năm học vừa qua. Téi xin bay tô làng biết ơn sâu sắc nhật tới thảy giáo Phạm Quang Dũng, người đã tận tình hướng dẫn, chí bảo trong suốt thời gian học tập, thực tập và làm luận vẫn. Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới giáo sư Katsummi Inoue ctmg hai nghiên cứm sinh Maxirne Clement và Eiuir Demirovic, những người đã lận tình giúp đỡ trong suốt thời gian thực tập nghiên cửu vẻ làm luận văn tai National Institute of Tnfamatics, Tokyo Nhân địp nảy lôi xin gửi lời cảm ơn chân thành lới gia đình, bạn bê, những người thân đã cỗ vũ, dong vién tiếp thêm cho em nghị lực để tôi hoàn thánh luận văn tốt nghiệp.

“Tôi xin chân thành cảm ont Hà Nội. ngày 12 tháng 03 năm 2017 Học viên. Huỳnh Thành Trung Danh mục các từ ngữ viết tắt và thuật ngữ Chữ viếttắt | Tên đây đủ Ý nghĩa NP Non-deteauisue Tớp bài toán quyết dịnh chưa có thuật polynomial toàn độ phức tạp đa thức đề giái 18 Local search Tim kiém cục bộ cP Constraint Quy hoạch rảng buộc Programming CBLS Constrainit-based Tim kiểm cục bộ đựa trên ràng bude Local search Danh mục các hình vẽ sử dụng trong để án Hình 1: Minh họa cho bài toán TSP với 4 thành phổ. " Hinh 2: Vĩ dụ về chu trình con của bài loán TSP.

- 12 ilinh 3: Minh hoa Local search véi bai todn 4-queen. Tinh 4: Minh hoa lời giải cực trị dia phwong Wong LS cece 21 Hinh 5: Minh hoa Backtracking Search voi bai todn 4-queen -. 30 Hinh 6: Tông quan kiến trúc Constraint-based Local Search [7}. Hình 7+ Minh họa sự họai động của Dependency Graph.

Hình 8: Minh họa Symmetry Breaking vii bai todn N-queens a2 Hinh 9: Sor a6 khéi thudt todn phan cum K-means. Hình 10: Vĩ đụ mình họa bài toán ghép cặp cực đại sl Hình 11: VÍ dụ về ma trận biểu dién ham dé do W _°-51 Hinh 12: Sơ đô khải của thuật toán K-means balanced clustering. Hình 13: Minh họa trường hợp không bào toàn nghiệm khi phân rã kíp thời gian Hinh 14: Minh hea déi xứng giữa các cụm hội đồng— phòng. 61 Hình 15: Minh hoa déi xing gitta chit tich— thie kp.

- 63 Ilinh 16: Mé hinh pha 1-1 cha bai todn MTDT. Hình 17: Minh họa ghép cặp cực đại các hội đằng vào các cụm. VÍ dụ mình họa trường hợp kết quả phân cụm không sử dụng được?) Tình 19: Vĩ du minh họa thuật toán hậu xử lý kết quả phân cụm Hinh 20: Mé hinh pha 1-2 ctia bai foan - -ò 8 Hinh 21: Minh hoa phân hoạch láng giéng trong tìm kiểm cục bộ. Chương 4: Kết luận và các hướng phat wrién.

Tong hop các cong vi đã làm được vả các hướng phát triển trong tương lai. -_ Đánh số các trang bắt dẫu lừ phản nội dung chính của luận văn (thay vì từ phân mục lục) -_ Chỉnh sửa lại lỗi văn bản hình vẽ và tên hình vẽ bị nhảy (hình 20) -_ Chỉnh sữa lại văn phong khoa hoe hon (phan 2.1) -_ Chính sửa lại cách đánh số các định nghĩa cho không còn trừng lập (phản 21143121) -_ Chỉnh sữa lại phần tải liệu tham khão cho thống nhật và chuẩn xát hơi: Xgây 29 tháng 03 năm 2017 Giáo viên hướng dẫn Tác giá luận văn CHŨ TỊCH HỘI ĐÓNG Danh mục các bảng biểu sử dụng trong đỗ án Bảng 1: Một số API tiêu biểu của thụ viện 2penGBI &. đ0 Bảng 2: Dâng so sảnh hiệu năng mô hình nQueen sử dung Symmetry Breaking 4 Háng 3: Hàng thực nghiệm đánh giá hiệu quả của kỹ thuật phan rd thu gon 60 Hảng 4: Bằng thực nghiệm đánh giá hiệu quả của các kỹ thuật loại bỏ đối xứng 65 Bang 5: Bang thuc nghiém danh gid hiéu qua ctia thuật toán KPBC. 74 Bang 6: Bang thyc nghigm danh gid hiéu quả của Heurisiic phân cụm 75 Bảng 7: Bảng thực nghiệm đánh giá hiệu quả của Tìm kiểm lời giải tỗi tru từng phân với một phân hoạch.

83 Bang 8: Bảng thực nghiệm đánh giá hiệu quả của Từn kiểm cục bộ sử dụng lời giải từng phân .88 Bảng 9: Bằng thực nghiệm đánh giá kết quả - .90 Danh mục các từ ngữ viết tắt và thuật ngữ Chữ viếttắt | Tên đây đủ Ý nghĩa NP Non-deteauisue Tớp bài toán quyết dịnh chưa có thuật polynomial toàn độ phức tạp đa thức đề giái 18 Local search Tim kiém cục bộ cP Constraint Quy hoạch rảng buộc Programming CBLS Constrainit-based Tim kiểm cục bộ đựa trên ràng bude Local search Danh mục các hình vẽ sử dụng trong để án Hình 1: Minh họa cho bài toán TSP với 4 thành phổ. " Hinh 2: Vĩ dụ về chu trình con của bài loán TSP. - 12 ilinh 3: Minh hoa Local search véi bai todn 4-queen.