Luận văn thạc sĩ: Nghiên cứu giải quyết bài toán lập lịch công việc nhóm với các ràng buộc xác định

Nghiên cứu hệ thống lập lịch công việc nhóm trong khoa học máy tính, phương pháp định lượng kết hợp định tính, góp phần phát triển khoa học

• Tác giả: Hồ Xuân Long
• Người hướng dẫn: TS Trang Hồng Sơn
• Trường học: Trường Đại học Bách Khoa TP. HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Nghiên cứu giải quyết bài toán lập lịch công việc nhóm với một số ràng buộc xác định
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2024
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT
• LỜI CAM ĐOAN
• 1. GIỚI THIỆU ĐỀ TÀI
• 1.1. Lý do chọn đề tài
• 1.2. Mục đích nghiên cứu
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Ý nghĩa khoa học và thực tiễn của đề tài
• 1.5. Bố cục của luận văn
• 2. CƠ SỞ LÝ THUYẾT VỀ BÀI TOÁN TỐI ƯU TỔ HỢP VÀ LẬP LỊCH CÔNG VIỆC
• 2.1. Bài toán tối ưu tổ hợp
• 2.1.1. Định nghĩa và khái niệm cơ bản
• 2.1.2. Phân loại bài toán tối ưu tổ hợp
• 2.1.3. Một số bài toán tối ưu tổ hợp phổ biến
• 2.1.4. Các phương pháp giải bài toán tối ưu tổ hợp
• 2.2. Bài toán lập lịch công việc cá nhân và công việc nhóm
• 2.2.1. Bài toán lập lịch công việc cá nhân
• 2.2.2. Bài toán lập lịch công việc nhóm
• 3. BÀI TOÁN LẬP LỊCH CÔNG VIỆC NHÓM VỚI RÀNG BUỘC CÔNG VIỆC–NGƯỜI
• 3.1. Phát biểu bài toán
• 3.2. Phân tích bài toán
• 3.2.1. Ràng buộc và mục tiêu
• 3.2.2. Cận trên và cận dưới của lời giải
• 3.3. Mô hình hoá toán học
• 3.4. Các phương pháp giải quyết bài toán
• 3.4.1. Phương pháp chính xác
• 3.4.2. Phương pháp heuristic
• 3.4.3. Phương pháp metaheuristic
• 3.4.4. Phương pháp learn-heuristic
• 3.5. Kết quả thực nghiệm và đánh giá
• 3.5.1. Bộ dữ liệu
• 3.5.2. Các chỉ số đánh giá
• 3.5.3. Thiết lập tham số
• 3.5.4. Kết quả thực nghiệm
• 3.5.5. Đánh giá kết quả
• 3.5.6. Nhận xét và thảo luận
• 4. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 4.1. Những đóng góp chính của luận văn
• 4.1.1. Đóng góp về mặt lý thuyết
• 4.1.2. Đóng góp về mặt thực tiễn
• 4.2. Đánh giá kết quả đạt được so với mục tiêu đề ra
• 4.3. Hướng phát triển của nghiên cứu trong tương lai
• TÀI LIỆU THAM KHẢO
• LÝ LỊCH TRÍCH NGANG
• DANH MỤC CÁC TỪ VIẾT TẮT
• DANH MỤC BẢNG BIỂU
• DANH MỤC HÌNH ẢNH

Tóm tắt

I. Giới thiệu đề tài

Bài toán lập lịch công việc nhóm với ràng buộc công việc–người (TWSPwJP) là một trong những thách thức lớn trong lĩnh vực khoa học máy tính. Việc tối ưu hóa lịch làm việc không chỉ ảnh hưởng đến năng suất mà còn góp phần giảm chi phí hoạt động cho tổ chức. Để giải quyết bài toán này, nghiên cứu đã xây dựng một mô hình toán học chặt chẽ, sử dụng các phương pháp như heuristic, metaheuristic, và learn-heuristic. Mô hình này không chỉ giúp mô tả rõ ràng các ràng buộc mà còn tạo điều kiện thuận lợi cho việc phát triển các thuật toán giải quyết hiệu quả hơn. Theo đó, việc áp dụng công nghệ thông tin trong việc lập lịch công việc nhóm là một bước tiến quan trọng, giúp nâng cao hiệu suất làm việc của các thành viên trong nhóm.

1.1. Lý do chọn đề tài

Sự gia tăng quy mô và độ phức tạp của các dự án hiện nay đòi hỏi các phương pháp lập lịch làm việc phải được cải tiến. Các phương pháp giải quyết truyền thống thường không đáp ứng được yêu cầu của các bài toán lớn và phức tạp. Do đó, việc nghiên cứu lập lịch công việc nhóm với các ràng buộc cụ thể trở thành một nhu cầu thiết yếu. Nghiên cứu này không chỉ mang lại lợi ích cho việc quản lý dự án mà còn mở ra hướng đi mới trong việc ứng dụng các kỹ thuật tối ưu hóa hiện đại vào thực tiễn.

II. Cơ sở lý thuyết về bài toán lập lịch

Chương này trình bày các khái niệm cơ bản về bài toán tối ưu tổ hợp và bài toán lập lịch công việc cá nhân. Đặc biệt, bài toán lập lịch công việc nhóm (TWSPwJP) được phân tích một cách chi tiết, bao gồm các ràng buộc và mục tiêu cụ thể. Mô hình hóa toán học là bước quan trọng để xây dựng các thuật toán giải quyết. Các phương pháp như phương pháp chính xác và các phương pháp xấp xỉ như heuristic và metaheuristic sẽ được nghiên cứu. Mô hình MILP được đề xuất để mô tả chính xác bài toán, giúp các nhà nghiên cứu có thể phát triển các thuật toán mới và cải tiến hơn.

2.1. Phân loại bài toán tối ưu tổ hợp

Bài toán tối ưu tổ hợp có thể được phân loại thành nhiều loại khác nhau, tùy thuộc vào các yếu tố như cấu trúc, ràng buộc và mục tiêu. Các bài toán này bao gồm các dạng như bài toán lập lịch công việc cá nhân và bài toán lập lịch công việc nhóm. Việc hiểu rõ các loại bài toán này sẽ giúp trong việc lựa chọn phương pháp giải quyết phù hợp. Chương này cũng đề cập đến các phương pháp giải bài toán tối ưu tổ hợp, từ các phương pháp chính xác đến các giải pháp xấp xỉ, giúp tối ưu hóa hiệu suất và chất lượng của các lời giải.

III. Phát biểu và phân tích bài toán TWSPwJP

Bài toán lập lịch công việc nhóm với ràng buộc công việc–người (TWSPwJP) được phát biểu rõ ràng với các ràng buộc cụ thể về quan hệ công việc và khả năng của từng thành viên. Mô hình hóa toán học được thực hiện thông qua mô hình mixed integer linear programming (MILP), giúp xây dựng một nền tảng vững chắc cho việc phát triển các thuật toán giải quyết. Các phương pháp như heuristic và metaheuristic được nghiên cứu để tìm kiếm lời giải tối ưu cho bài toán này. Kết quả thực nghiệm cho thấy rằng các phương pháp metaheuristic thường tạo ra lời giải tốt hơn, mặc dù thời gian tính toán có thể lâu hơn. Ngược lại, các phương pháp heuristic cho kết quả nhanh chóng nhưng chất lượng không cao.

3.1. Mô hình hóa toán học

Mô hình hóa toán học là bước quan trọng trong việc giải quyết bài toán TWSPwJP. Mô hình này giúp xác định rõ các ràng buộc và mục tiêu cần đạt được. Việc sử dụng mô hình MILP cho phép mô tả đầy đủ các yếu tố liên quan đến bài toán, từ đó phát triển các phương pháp giải quyết hiệu quả hơn. Mô hình này không chỉ hỗ trợ trong việc tìm kiếm lời giải mà còn giúp các nhà nghiên cứu có thể đánh giá và cải tiến các phương pháp hiện có.

IV. Kết quả thực nghiệm và đánh giá

Kết quả thực nghiệm từ các phương pháp được nghiên cứu cho thấy rõ ưu điểm và nhược điểm của từng phương pháp. Các phương pháp metaheuristic như simulated annealing và genetic algorithm cho thấy khả năng tạo ra lời giải chất lượng tốt hơn so với các phương pháp heuristic truyền thống. Tuy nhiên, thời gian tính toán của các phương pháp này thường lâu hơn. Learn-heuristic với mạng DQN được chứng minh là một giải pháp tiềm năng, đạt được sự cân bằng giữa chất lượng lời giải và thời gian tính toán. Các kết quả này không chỉ có giá trị lý thuyết mà còn mang tính ứng dụng cao trong thực tiễn.

4.1. Đánh giá kết quả

Đánh giá kết quả thực nghiệm là một phần quan trọng trong nghiên cứu này. Các chỉ số đánh giá được sử dụng để so sánh hiệu suất của các phương pháp khác nhau, từ đó xác định phương pháp nào phù hợp nhất cho từng loại bài toán cụ thể. Việc phân tích kết quả cũng giúp nhận diện các điểm mạnh và điểm yếu của từng phương pháp, từ đó đưa ra những đề xuất cải tiến cho các nghiên cứu tiếp theo.

Nội dung chính

Tổng quan nghiên cứu

Lập lịch công việc nhóm là một bài toán tối ưu tổ hợp quan trọng trong quản lý dự án và sản xuất, ảnh hưởng trực tiếp đến năng suất lao động và chi phí vận hành. Theo ước tính, việc tối ưu hóa lịch làm việc có thể giảm thiểu thời gian hoàn thành dự án từ 10% đến 20%, đồng thời nâng cao hiệu quả sử dụng nguồn lực. Bài toán lập lịch công việc nhóm với ràng buộc công việc–người (TWSPwJP) là một dạng bài toán phức tạp thuộc lớp NP-hard, trong đó mỗi công việc chỉ được giao cho một thành viên duy nhất trong nhóm, đồng thời phải thỏa mãn các ràng buộc về thời gian làm việc và kích thước tối thiểu của các phần công việc con.

Mục tiêu nghiên cứu của luận văn là phát triển và đánh giá các phương pháp giải quyết bài toán TWSPwJP, bao gồm phương pháp chính xác dựa trên mô hình MILP, các phương pháp heuristic, metaheuristic và phương pháp học tăng cường kết hợp mạng Deep Q-Network (DQN). Nghiên cứu tập trung vào việc tối thiểu hóa thời gian hoàn thành tổng thể (makespan) trong phạm vi các nhóm từ 2 đến 4 thành viên và số lượng công việc từ 10 đến 50, với các khung thời gian làm việc xác định cho từng thành viên.

Ý nghĩa của nghiên cứu thể hiện qua việc cung cấp các công cụ tối ưu hóa lập lịch hiệu quả, giúp nhà quản lý nâng cao chất lượng quyết định, giảm thiểu thời gian rỗi và chi phí vận hành. Kết quả nghiên cứu cũng góp phần phát triển lý thuyết về tối ưu tổ hợp và ứng dụng trí tuệ nhân tạo trong quản lý nguồn lực, mở ra hướng đi mới cho các bài toán lập lịch phức tạp trong thực tế.

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

Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng lý thuyết của bài toán tối ưu tổ hợp (combinatorial optimization problem - COP), trong đó bài toán TWSPwJP được mô hình hóa bằng mô hình mixed integer linear programming (MILP). MILP cho phép mô tả chính xác các ràng buộc về công việc, người thực hiện, khung thời gian làm việc và kích thước tối thiểu của các phần công việc con.

Các khái niệm chính bao gồm:

• Makespan (Cmax): Thời gian hoàn thành muộn nhất trong lịch trình, mục tiêu cần tối thiểu hóa.
• Ràng buộc công việc–người: Mỗi công việc chỉ được giao cho một thành viên duy nhất.
• Splitmin: Kích thước tối thiểu cho phép của các phần công việc con khi chia nhỏ công việc.
• Khung thời gian làm việc (available windows): Các khoảng thời gian mà thành viên có thể thực hiện công việc.

Ngoài ra, các phương pháp giải bài toán được xây dựng dựa trên các lý thuyết về:

• Heuristic: Phương pháp xấp xỉ nhanh, ví dụ thuật toán First-Come First-Served (FCFS).
• Metaheuristic: Các thuật toán tìm kiếm thông minh như Simulated Annealing (SA) và Genetic Algorithm (GA), giúp thoát khỏi cực trị cục bộ.
• Học tăng cường (Reinforcement Learning - RL): Sử dụng mạng Deep Q-Network (DQN) để học chính sách lập lịch tối ưu thông qua tương tác với môi trường bài toán.

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

Nguồn dữ liệu nghiên cứu là các bộ dữ liệu mô phỏng với số lượng công việc từ 10 đến 50, số thành viên từ 2 đến 4, và kích thước tối thiểu của công việc con (splitmin) từ 3 đến 5. Thời gian thực hiện công việc và khung thời gian làm việc được tạo ngẫu nhiên theo phân phối đồng nhất rời rạc, đảm bảo tính đa dạng và thực tiễn.

Phương pháp phân tích bao gồm:

• Mô hình MILP: Giải bằng các solver như CPLEX, Gurobi để tìm lời giải chính xác cho các bài toán kích thước nhỏ và vừa.
• Heuristic FCFS: Phân công công việc theo thứ tự đến trước được phục vụ trước, ưu tiên khung thời gian sớm nhất.
• Metaheuristic SA và GA: Tìm kiếm lời giải gần tối ưu bằng cách khai thác không gian tìm kiếm thông qua các phép biến đổi hoán đổi và tiến hóa quần thể.
• Learn-heuristic DQN: Huấn luyện mạng nơ-ron sâu để học chính sách lập lịch tối ưu, cân bằng giữa chất lượng lời giải và thời gian tính toán.

Timeline nghiên cứu kéo dài từ tháng 9/2023 đến tháng 6/2024, bao gồm các giai đoạn xây dựng mô hình, phát triển thuật toán, thực nghiệm và đánh giá kết quả.

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

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

1. Chất lượng lời giải của các phương pháp:

   • Phương pháp metaheuristic (SA, GA) đạt độ lệch phần trăm so với cận dưới LB trung bình khoảng 5-8%, cho thấy chất lượng lời giải tốt hơn so với heuristic FCFS với độ lệch khoảng 12-15%.
   • Phương pháp learn-heuristic DQN đạt độ lệch phần trăm trung bình khoảng 7-9%, thể hiện sự cân bằng giữa chất lượng và thời gian tính toán.

2. Hiệu năng tính toán:

   • Heuristic FCFS có thời gian chạy nhanh nhất, trung bình dưới 100 ms cho các bài toán kích thước lớn nhất (n=50, k=4).
   • Metaheuristic SA và GA có thời gian chạy trung bình từ 500 ms đến 2 giây, tăng theo kích thước bài toán.
   • DQN có thời gian chạy trung bình khoảng 300-600 ms, nhanh hơn các metaheuristic nhưng chậm hơn heuristic.

3. Ảnh hưởng của kích thước bài toán:

   • Khi số lượng công việc tăng từ 10 lên 50, độ lệch phần trăm của heuristic tăng từ 8% lên 15%, trong khi metaheuristic và DQN duy trì độ lệch dưới 10%.
   • Thời gian chạy của các phương pháp metaheuristic tăng gần như tuyến tính theo số lượng công việc, trong khi DQN có sự ổn định hơn nhờ khả năng học chính sách.

4. So sánh các phương pháp:

   • Metaheuristic SA và GA phù hợp với các bài toán yêu cầu chất lượng lời giải cao, chấp nhận thời gian tính toán lâu hơn.
   • Heuristic FCFS thích hợp cho các tình huống cần lời giải nhanh, không đòi hỏi tối ưu tuyệt đối.
   • DQN là lựa chọn hiệu quả khi cần cân bằng giữa chất lượng và thời gian, đặc biệt trong môi trường có nhiều biến thể bài toán.

Thảo luận kết quả

Nguyên nhân chính của sự khác biệt về chất lượng lời giải và thời gian tính toán giữa các phương pháp là do cách thức khai thác không gian tìm kiếm. Heuristic FCFS đơn giản, không khai thác sâu, nên nhanh nhưng chất lượng thấp. Metaheuristic sử dụng các phép biến đổi và chọn lọc thông minh, giúp tìm lời giải gần tối ưu nhưng tốn thời gian. DQN học được chính sách lập lịch dựa trên kinh nghiệm, giúp giảm thời gian tìm kiếm trong các trường hợp tương tự.

So với các nghiên cứu trước đây về bài toán lập lịch nhóm, kết quả của luận văn cho thấy sự cải tiến rõ rệt trong việc áp dụng học tăng cường kết hợp mạng DQN, mở rộng khả năng giải quyết các bài toán có ràng buộc phức tạp và kích thước lớn hơn. Việc trình bày dữ liệu qua biểu đồ so sánh độ lệch phần trăm và thời gian chạy theo kích thước bài toán giúp minh họa rõ ràng sự đánh đổi giữa các phương pháp.

Ý nghĩa của kết quả là cung cấp cơ sở khoa học để lựa chọn phương pháp phù hợp tùy theo yêu cầu thực tế về chất lượng và thời gian, đồng thời khẳng định tiềm năng ứng dụng của học máy trong tối ưu hóa lập lịch.

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

1. Áp dụng phương pháp học tăng cường DQN cho các hệ thống lập lịch động:

   • Động từ hành động: Triển khai, huấn luyện.
   • Target metric: Giảm thời gian tính toán và nâng cao chất lượng lời giải.
   • Timeline: 6-12 tháng.
   • Chủ thể thực hiện: Các tổ chức nghiên cứu và doanh nghiệp công nghệ.

2. Kết hợp metaheuristic với heuristic để tạo giải pháp lai (hybrid):

   • Động từ hành động: Phát triển, thử nghiệm.
   • Target metric: Tối ưu hóa cân bằng giữa tốc độ và chất lượng.
   • Timeline: 3-6 tháng.
   • Chủ thể thực hiện: Nhóm nghiên cứu và nhà phát triển phần mềm.

3. Mở rộng mô hình MILP và thuật toán cho bài toán quy mô lớn hơn:

   • Động từ hành động: Mở rộng, tối ưu.
   • Target metric: Giải quyết bài toán với hàng trăm công việc và nhiều thành viên.
   • Timeline: 12-18 tháng.
   • Chủ thể thực hiện: Các viện nghiên cứu và trường đại học.

4. Phát triển giao diện người dùng và công cụ hỗ trợ ra quyết định:

   • Động từ hành động: Thiết kế, triển khai.
   • Target metric: Tăng tính ứng dụng thực tiễn và dễ sử dụng.
   • Timeline: 6 tháng.
   • Chủ thể thực hiện: Doanh nghiệp phần mềm và phòng quản lý dự án.

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

1. Nhà quản lý dự án và nhân sự:

   • Lợi ích: Nắm bắt các phương pháp tối ưu phân công công việc, nâng cao hiệu quả quản lý nhóm.
   • Use case: Lập kế hoạch công việc cho các dự án đa thành viên với nhiều ràng buộc.

2. Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính, Vận trù học:

   • Lợi ích: Tham khảo mô hình toán học, thuật toán giải bài toán tối ưu tổ hợp phức tạp.
   • Use case: Phát triển các nghiên cứu tiếp theo về tối ưu hóa và học máy.

3. Doanh nghiệp sản xuất và dịch vụ:

   • Lợi ích: Ứng dụng các thuật toán lập lịch để giảm chi phí và tăng năng suất.
   • Use case: Tối ưu lịch làm việc cho dây chuyền sản xuất hoặc nhóm nhân viên.

4. Phát triển phần mềm và công nghệ AI:

   • Lợi ích: Áp dụng học tăng cường và mạng nơ-ron sâu trong các bài toán thực tế.
   • Use case: Xây dựng hệ thống tự động lập lịch thông minh cho các ứng dụng doanh nghiệp.

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

1. Bài toán TWSPwJP có khó giải không?
   Bài toán thuộc lớp NP-hard, nghĩa là không có thuật toán đa thức hiệu quả cho mọi trường hợp. Do đó, các phương pháp xấp xỉ và học máy được ưu tiên để tìm lời giải gần tối ưu trong thời gian hợp lý.

2. Phương pháp heuristic FCFS có ưu điểm gì?
   FCFS đơn giản, dễ cài đặt và cho lời giải nhanh chóng, phù hợp với các bài toán nhỏ hoặc khi thời gian tính toán bị giới hạn. Tuy nhiên, chất lượng lời giải thường thấp hơn các phương pháp khác.

3. Metaheuristic SA và GA khác nhau thế nào?
   SA mô phỏng quá trình ủ kim, tập trung vào việc chấp nhận lời giải kém hơn với xác suất giảm dần để thoát cực trị cục bộ. GA mô phỏng tiến hóa tự nhiên, sử dụng quần thể và các toán tử di truyền để khai thác không gian tìm kiếm đa dạng hơn.

4. Học tăng cường DQN có thể áp dụng cho bài toán lớn không?
   DQN có khả năng học chính sách hiệu quả và thích nghi với các bài toán có kích thước lớn hơn, tuy nhiên cần nhiều dữ liệu huấn luyện và thời gian huấn luyện ban đầu. Sau khi huấn luyện, DQN có thể tạo lịch nhanh chóng cho các bài toán mới.

5. Làm thế nào để lựa chọn phương pháp phù hợp cho bài toán thực tế?
   Cần cân nhắc kích thước bài toán, yêu cầu về chất lượng lời giải và thời gian tính toán. Heuristic phù hợp khi cần nhanh, metaheuristic khi cần chất lượng cao, DQN khi cần cân bằng và có điều kiện huấn luyện mô hình.

Kết luận

• Luận văn đã xây dựng mô hình MILP chính xác và phát triển các phương pháp heuristic, metaheuristic, và học tăng cường để giải bài toán TWSPwJP.
• Kết quả thực nghiệm trên bộ dữ liệu đa dạng cho thấy metaheuristic và DQN vượt trội về chất lượng lời giải so với heuristic truyền thống.
• Phương pháp DQN thể hiện tiềm năng lớn trong việc cân bằng giữa chất lượng và thời gian tính toán, mở ra hướng nghiên cứu mới cho bài toán lập lịch phức tạp.
• Nghiên cứu góp phần nâng cao hiệu quả quản lý nguồn lực trong doanh nghiệp và phát triển lý thuyết tối ưu tổ hợp kết hợp trí tuệ nhân tạo.
• Các bước tiếp theo bao gồm mở rộng quy mô bài toán, phát triển giải pháp lai và ứng dụng thực tế trong các hệ thống quản lý dự án và sản xuất.

Để khai thác tối đa giá trị nghiên cứu, các nhà quản lý, nhà nghiên cứu và doanh nghiệp được khuyến khích áp dụng và phát triển các phương pháp đề xuất, đồng thời tiếp tục nghiên cứu mở rộng nhằm giải quyết các bài toán lập lịch ngày càng phức tạp trong thực tế.

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

Chương 1 cung cấp cái nhìn tổng quan về đề tài nghiên cứu, bao gồm động lực lựa chọn đề tài, mục tiêu, phạm vi và đối tượng nghiên cứu, cũng như tầm quan trọng của đề tài về lý thuyết và thực tiễn. • Chương 2 trình bày cơ sở lý thuyết về bài toán tối ưu tổ hợp và bài toán lập lịch công việc. Chương này cung cấp các định nghĩa, khái niệm cơ bản, phân loại bài toán tối ưu tổ hợp, và giới thiệu một số bài toán điển hình. Đồng thời, chương này cũng mô tả chi tiết các bài toán lập lịch công việc cá nhân và lập lịch công việc nhóm, bao gồm phát biểu bài toán và các phương pháp giải quyết.

• Chương 3 tập trung vào bài toán lập lịch công việc nhóm với ràng buộc công việc–người TWSPwJP, bao gồm phát biểu bài toán, phân tích các đặc điểm và tính chất của bài toán, mô hình hoá toán học MILP. Tiếp theo, chương này trình bày các phương pháp giải bao gồm phương pháp chính xác và các phương pháp xấp xỉ như heuristic FCFS, các phương pháp metaheuristic SA và GA, và phương pháp learn-heuristic sử dụng học tăng cường với mạng DQN. Cũng trong chương này, các kết quả thực nghiệm và đánh giá được trình bày chi tiết. 6 Chương 3 cũng mô tả bộ dữ liệu mô phỏng đã sử dụng, thiết kế thực nghiệm và các chỉ số để đánh giá.

Cuối cùng là phần nhận xét, thảo luận về kết quả đạt được. • Chương 4 tổng kết những đóng góp chính của luận văn về cả lý thuyết và thực tiễn, đánh giá kết quả đạt được so với mục tiêu đề ra. Chương này cũng đề xuất những hướng phát triển tiếp theo của đề tài trong tương lai.1 Bài toán tối ưu tổ hợp 2.1 Định nghĩa và khái niệm cơ bản Tối ưu tổ hợp (combinatorial optimization problem – COP) là một lớp bài toán quan trọng trong vận trù học (operations research – OR) và khoa học máy tính (computer science – CS) [4], [5]. Bài toán tối ưu tổ hợp được định nghĩa bởi các thành phần sau: • Tập hữu hạn các phần tử E = {e1 , e2 ,.

• Tập con F ⊆ 2E là tập chứa các lời giải khả thi (feasible solutions). • Hàm mục tiêu f : F → R gán cho mỗi lời giải khả thi một giá trị thực. Mục tiêu của bài toán COP là xác định một lời giải khả thi S ∗ ∈ F sao cho f (S ∗ ) (giá trị của hàm mục tiêu) đạt cực tiểu hoặc cực đại: S ∗ = arg min f (S) hoặc S ∗ = arg max f (S) (2.1) S∈F S∈F Các khái niệm liên quan: • Không gian tìm kiếm (search space): tất cả các lời giải (solutions), bao gồm cả lời giải khả thi và không khả thi của bài toán. • Ràng buộc (constraint): là điều kiện mà một lời giải phải thỏa mãn để trở thành lời giải khả thi.

• Lân cận (neighborhood): với mỗi lời giải S, lân cận của S là tập hợp các lời giải có thể xác định bằng cách biến đổi S theo một quy tắc cho trước. • Tối ưu cục bộ (local optimum): là một lời giải khả thi mà trong lân cận của nó không tồn tại lời giải nào tốt hơn. • Tối ưu toàn cục (global optimum): là lời giải khả thi có giá trị tốt nhất. Bài toán COP thường có không gian nghiệm rất lớn, gia tăng theo hàm mũ của kích thước đầu vào, rất khó xác định nghiệm tối ưu toàn cục.

Nhiều bài toán đã được 8 chứng minh là NP-hard, tức là không tìm được thuật toán đa thức có thể giải chúng một cách hiệu quả. Tuy nhiên, nhiều phương pháp heuristic và metaheuristic đã được đề xuất cho phép tìm các lời giải gần tối ưu trong khoảng thời gian tính toán hợp lý.2 Phân loại bài toán tối ưu tổ hợp 2.1 Theo tính chất của hàm mục tiêu và ràng buộc [6] • Tối ưu hóa tuyến tính (linear optimization): cả hàm mục tiêu và các ràng buộc đều có dạng tuyến tính theo các biến quyết định. Ví dụ: bài toán vận tải, quy hoạch tuyến tính, bài toán cái túi tuyến tính. • Tối ưu phi tuyến (nonlinear optimization): hàm mục tiêu hoặc ít nhất một ràng buộc có dạng phi tuyến.

Ví dụ: bài toán quy hoạch toàn phương, tối ưu lồi phi tuyến. • Tối ưu lồi (convex optimization): hàm mục tiêu là một hàm lồi (hoặc hàm lõm) và tập lời giải khả thi được xác định bởi các ràng buộc lồi. Ví dụ: bài toán quy hoạch lồi, tối ưu normed.2 Theo tính rời rạc của biến quyết định [7] • Tối ưu rời rạc (discrete optimization): những biến quyết định chỉ nhận giá trị thuộc một tập hợp rời rạc, thường là tập hợp các số nguyên. Ví dụ: bài toán quy hoạch nguyên, người bán hàng, bài toán lập lịch.

• Tối ưu liên tục (continuous optimization): những biến quyết định có thể nhận bất kỳ giá trị nào nằm trong một khoảng liên tục, thông thường là tập hợp các số thực. Ví dụ: bài toán quy hoạch tuyến tính liên tục, tối ưu lồi liên tục. • Tối ưu hỗn hợp (mixed-integer optimization): một số biến quyết định nhận giá trị rời rạc, trong khi các biến còn lại nhận giá trị liên tục. Ví dụ: bài toán quy hoạch nguyên hỗn hợp, bài toán đóng gói hình học.3 Theo độ phức tạp tính toán [8] • Lớp đa thức P (polynomial-time): bao gồm các bài toán mà thời gian giải theo thuật toán tốt nhất hiện có tỷ lệ thuận theo đa thức với kích thước dữ liệu đầu 9 vào.

Ví dụ: bài toán đường đi ngắn nhất, quy hoạch tuyến tính, cây khung nhỏ nhất. • Lớp NP (nondeterministic polynomial-time): đây là lớp mà các bài toán với lời giải cho trước có thể được kiểm tra tính đúng đắn trong thời gian đa thức. Lớp NP bao gồm lớp P và được cho là chứa nhiều bài toán khó hơn lớp P. Ví dụ: bài toán người bán hàng, cái túi, tô màu đồ thị.

• Lớp NP-hard: một bài toán được gọi là NP-hard nếu mọi bài toán trong lớp NP đều có thể qui về nó trong thời gian đa thức. Nói cách khác, bài toán NP-hard có độ phức tạp bằng hoặc lớn hơn bài toán khó nhất trong lớp NP. Hầu hết các bài toán tối ưu tổ hợp trên thực tế đều rơi vào lớp này. Ví dụ: bài toán lập lịch tối ưu, thiết kế mạch VLSI.

• Lớp NP-complete: một bài toán được gọi là NP-complete nếu như nó vừa thuộc lớp NP vừa thuộc lớp NP-hard. Có thể hiểu, các dạng bài toán NP-complete là dạng “tiêu biểu” hoặc “khó nhất” của lớp NP. Ví dụ: bài toán tìm clique cực đại trong đồ thị (maximum clique problem), bài toán định danh luận lý mệnh đề (boolean satisfiability problem – SAT). Việc phân loại các bài toán tối ưu hóa tổ hợp (COP) mang lại nhiều lợi ích.

Nó giúp hiểu rõ hơn về đặc điểm, mức độ khó của từng loại bài toán, và còn là cơ sở để lựa chọn phương pháp giải quyết phù hợp. Ví dụ, nếu một bài toán thuộc lớp P, ta có thể tìm lời giải tối ưu bằng các giải thuật đa thức. Trái lại, với các bài toán NP-hard, việc tìm lời giải tối ưu thường rất phức tạp và đòi hỏi thời gian tính toán lớn. Trong trường hợp này, các phương pháp xấp xỉ như các kỹ thuật heuristic và metaheuristic thường được áp dụng để tìm lời giải gần tối ưu trong thời gian hợp lý.

Các phương pháp giải quyết bài toán COP rất đa dạng, bao gồm các kỹ thuật metaheuristic [9], các phương pháp dựa trên học máy [10], [11], và nhiều hướng tiếp cận khác.3 Một số bài toán tối ưu tổ hợp phổ biến 2.1 Bài toán người bán hàng Bài toán người bán hàng (traveling salesman problem – TSP) là một trong những bài toán tối ưu hóa tổ hợp điển hình và được nghiên cứu rộng rãi. Bài toán đặt ra như sau: Cho trước một tập hợp các thành phố và khoảng cách (hoặc chi phí) giữa từng cặp thành phố. Một người bán hàng xuất phát từ một thành phố bất kỳ, phải đi qua mỗi thành phố còn lại đúng một lần, và cuối cùng trở về thành phố ban đầu. Mục tiêu là tìm một hành trình có tổng khoảng cách (hoặc chi phí) là nhỏ nhất.

TSP được chứng minh thuộc lớp bài toán NP-hard [12], và có nhiều ứng dụng quan trọng trong logistics, sản xuất, viễn thông. Một số biến thể của TSP bao gồm: TSP với các ràng buộc về thời gian (TSP with time windows), TSP đa người bán hàng (multiple TSP), TSP cho phép bỏ qua một số thành phố (TSP with profits). Để giải quyết bài toán TSP, các phương pháp chính bao gồm các thuật toán heuristic, metaheuristic và các phương pháp tối ưu chính xác. • Các thuật toán chính xác: dynamic programming, linear programming, branch and cut,.

• Các thuật toán heuristic: greedy algorithm, thuật toán cải tiến k-opt, Lin- Kernighan,. • Các kỹ thuật metaheuristic: genetic algorithm, ant colony optimization, tabu search,. Mặc dù là bài toán NP-hard, đã có nhiều kết quả đạt được trong việc giải quyết bài toán TSP với các trường hợp cụ thể, đồng thời những ứng dụng của bài toán TSP vẫn đang là động lực thúc đẩy cho sự phát triển của các công trình nghiên cứu về các giải pháp tối ưu mới.2 Bài toán cái túi Bài toán cái túi (knapsack problem - KP) cũng là một bài toán tối ưu hóa, trong đó ta có một tập hợp các vật phẩm, mỗi vật phẩm có trọng lượng và giá trị riêng. Bài toán yêu cầu chọn ra một số vật phẩm để đưa vào một chiếc túi có giới hạn về sức chứa sao 11 cho tổng giá trị của các vật phẩm được chọn là lớn nhất có thể, đồng thời tổng trọng lượng của chúng không vượt quá sức chứa của túi.

Bài toán KP cũng đã được chứng minh thuộc lớp NP-hard [13], và có nhiều biến thể như bài toán phân đoạn (fractional knapsack problem), túi nhị phân (0-1 knapsack problem), hay bài toán nhiều cái túi (multiple knapsack problem). Các bài toán được liệt kê đều mang tính nền tảng và nhiều ứng dụng thực tế như chọn danh mục đầu tư, lập kế hoạch sản xuất, cắt vật liệu, nén dữ liệu. Các phương pháp giải quyết bài toán cái túi bao gồm: • Các thuật toán chính xác: dynamic programming, backtracking algorithm, branch and bound,. • Các thuật toán xấp xỉ: greedy algorithm, phương pháp xấp xỉ tỷ lệ (approximate scaling),.

• Các kỹ thuật metaheuristic: genetic algorithm, swarm optimization,. Nghiên cứu về bài toán cái túi và các ứng dụng của nó là một hướng đi quan trọng trong lĩnh vực tối ưu tổ hợp và đang có tiềm lực phát triển mạnh mẽ.3 Bài toán lập lịch Các bài toán lập lịch (scheduling problem) là một trong những lớp bài toán tối ưu được ứng dụng rộng rãi nhất trong thực tế.