Luận văn thạc sĩ: Giải bài toán xếp lịch đa mục tiêu bằng giải thuật di truyền

Luận văn thạc sĩ toán học nghiên cứu máy tính giải bài toán xếp lịch trên nhiều nhóm đa mục tiêu bằng tiếp cận giải thuật di truyền, khảo sát thực trạng, phân tích nguyên nhân, đề

• Tác giả: Nguyễn Hải Dương
• Người hướng dẫn: TS. Nguyễn Tiến Thịnh
• Trường học: Đại học Bách Khoa - ĐHQG TP.HCM
• Chuyên ngành: Khoa học máy tính
• Đề tài: Giải bài toán xếp lịch trên nhiều nhóm đa mục tiêu bằng tiếp cận giải thuật di truyền
• 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 OF DISSERTATION
• Lời cam đoan
• Danh mục hình ảnh
• Danh sách bảng
• 1. Chương 1: Giới thiệu đề tài
• 1.1. Giới thiệu chung
• 1.2. Mô tả về bài toán xếp lịch
• 1.2.1. Bài toán xếp lịch cá nhân PSP
• 1.2.2. Bài toán xếp lịch cá nhân PSP có ràng buộc về thời gian (setup time)
• 1.2.3. Bài toán xếp lịch cá nhân PSP có ràng buộc về deadline
• 1.2.4. Bài toán xếp lịch trên một nhóm
• 1.2.5. Bài toán xếp lịch trên nhiều nhóm
• 1.3. Mục tiêu đề tài
• 1.4. Giới hạn đề tài
• 1.5. Đóng góp của luận văn
• 1.6. Tóm tắt nội dung
• 2. Chương 2: Cơ sở lý thuyết
• 2.1. Giải thuật di truyền
• 2.2. Giải thuật NSGA-II
• 2.3. Giải thuật NSGA-III
• 3. Chương 3: Các công trình nghiên cứu liên quan
• 3.1. Phương pháp tối ưu hóa đơn mục tiêu truyền thống (single-objective optimization)
• 3.2. Phương pháp tối ưu hóa đa mục tiêu truyền thống (multi-objective optimization)
• 3.3. Hướng tiếp cận tiến hóa đa mục tiêu (Evolutionary Algorithm)
• 3.4. Phương pháp học máy
• 4. Chương 4: Mô hình đề xuất
• 4.1. Mô hình tham khảo
• 4.2. Phương pháp đánh giá
• 4.3. Tập dữ liệu và phương pháp xử lý
• 4.4. Đề xuất 1: Sử dụng cơ chế lựa chọn của NSGA-II
• 4.5. Đề xuất 2: Sử dụng cơ chế lựa chọn của NSGA-III
• 5. Chương 5: Kết luận
• Tài liệu tham khảo

Tóm tắt

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

Đề tài này tập trung vào việc giải quyết bài toán xếp lịch trên nhiều nhóm đa mục tiêu bằng cách sử dụng giải thuật di truyền. Bài toán xếp lịch đa mục tiêu xuất phát từ thực tế trong nhiều lĩnh vực như công nghiệp, giáo dục và tổ chức sự kiện, nơi cần xếp lịch cho nhiều nhóm công việc hoặc sự kiện khác nhau với nhiều mục tiêu cần đạt được. Tác giả nhận thấy rằng giải thuật di truyền có thể áp dụng hiệu quả cho bài toán này, dựa trên nguyên tắc của quá trình tiến hóa trong tự nhiên, bao gồm các khái niệm như cá thể, quần thể, lai ghép và đột biến. Đề tài đề xuất một giải thuật di truyền đặc biệt để giải quyết bài toán xếp lịch trên nhiều nhóm đa mục tiêu, xây dựng một hàm mục tiêu được tối ưu hóa bằng cách kết hợp các yếu tố quan trọng như sự phù hợp về thời gian, sự phân bố công việc cân đối và sự ưu tiên giữa các nhóm.

1.1 Mô tả về bài toán xếp lịch

Bài toán xếp lịch hiện có nhiều hướng nghiên cứu, bao gồm xếp lịch cấp phát tác vụ, xếp lịch ràng buộc nguồn lực, và xếp lịch công việc. Lập lịch công việc là một bài toán tối ưu hóa trong khoa học máy tính, trong đó mục tiêu là sắp xếp các công việc trên các máy sao cho thời gian hoàn thành tất cả các công việc là nhỏ nhất. Nghiên cứu đã chỉ ra rằng việc sử dụng giải thuật di truyền giúp cải thiện năng suất và giảm thời gian chờ đợi trong quá trình sản xuất. Đề tài này sẽ tập trung vào việc xếp lịch trên nhiều nhóm đa mục tiêu, một vấn đề thuộc hướng nghiên cứu xếp lịch công việc.

II. Cơ sở lý thuyết

Chương này trình bày các lý thuyết cơ bản liên quan đến giải thuật di truyền, bao gồm các nguyên lý hoạt động và ứng dụng của nó trong bài toán xếp lịch. Giải thuật di truyền là một phương pháp tối ưu hóa dựa trên nguyên tắc của sự tiến hóa, sử dụng các khái niệm như chọn lọc tự nhiên, lai ghép và đột biến. Phương pháp này đã được áp dụng trong nhiều lĩnh vực khác nhau, từ sản xuất đến quản lý dự án, nhằm tối ưu hóa thời gian và nguồn lực. Các nghiên cứu trước đây đã chứng minh rằng giải thuật di truyền có khả năng tạo ra các lịch trình tối ưu với hiệu suất cao và đáp ứng được các yêu cầu đa mục tiêu của bài toán. Điều này cho thấy giá trị thực tiễn của việc áp dụng giải thuật di truyền trong các tình huống xếp lịch phức tạp.

2.1 Giải thuật di truyền

Giải thuật di truyền được phát triển dựa trên các nguyên tắc của sinh học tiến hóa, bao gồm sự chọn lọc tự nhiên, lai ghép và đột biến. Phương pháp này cho phép tìm kiếm các giải pháp tối ưu bằng cách mô phỏng quá trình tiến hóa tự nhiên. Qua các thế hệ, những cá thể tốt nhất sẽ được lựa chọn để sinh sản và tạo ra thế hệ tiếp theo, từ đó dần dần cải thiện chất lượng của các giải pháp. Việc áp dụng giải thuật di truyền trong bài toán xếp lịch không chỉ giúp tìm ra lịch trình tối ưu mà còn cho phép điều chỉnh linh hoạt các tham số để tối ưu hóa kết quả.

III. Các công trình nghiên cứu liên quan

Chương này tổng hợp các nghiên cứu trước đây liên quan đến bài toán xếp lịch và các phương pháp tối ưu hóa. Các phương pháp truyền thống như tối ưu hóa đơn mục tiêu và tối ưu hóa đa mục tiêu đã được áp dụng rộng rãi, tuy nhiên, những phương pháp này thường gặp khó khăn khi số lượng biến số và ràng buộc tăng lên. Hướng tiếp cận tiến hóa đa mục tiêu đã mở ra nhiều cơ hội mới trong việc giải quyết các bài toán phức tạp. Nhiều nghiên cứu đã chỉ ra rằng việc áp dụng giải thuật di truyền có thể mang lại hiệu quả cao hơn so với các phương pháp truyền thống, đặc biệt trong các bài toán xếp lịch có yêu cầu đa mục tiêu.

3.1 Phương pháp tối ưu hóa đơn mục tiêu truyền thống

Các phương pháp tối ưu hóa đơn mục tiêu truyền thống thường tập trung vào việc tối ưu hóa một mục tiêu duy nhất, điều này có thể dẫn đến việc bỏ qua các yếu tố quan trọng khác. Trong khi đó, bài toán xếp lịch đa mục tiêu yêu cầu xem xét nhiều mục tiêu đồng thời, từ đó đòi hỏi các phương pháp tối ưu hóa mạnh mẽ hơn. Nghiên cứu cho thấy rằng việc áp dụng các phương pháp heuristics và metaheuristics, bao gồm giải thuật di truyền, có thể cải thiện đáng kể hiệu suất trong việc tìm kiếm các giải pháp tối ưu cho bài toán xếp lịch.

IV. Mô hình đề xuất

Mô hình đề xuất trong luận văn này tập trung vào việc áp dụng giải thuật di truyền để giải quyết bài toán xếp lịch đa mục tiêu. Mô hình xây dựng hàm mục tiêu kết hợp các yếu tố như thời gian hoàn thành, sự phân bố công việc và ưu tiên giữa các nhóm. Qua các thí nghiệm thực tế, mô hình đã chứng minh khả năng tạo ra các lịch trình tối ưu và đáp ứng được các yêu cầu đa mục tiêu. Việc áp dụng mô hình này không chỉ giúp tối ưu hóa lịch trình mà còn mang lại lợi ích cho nhiều lĩnh vực thực tế như sản xuất, giáo dục và tổ chức sự kiện.

4.1 Mô hình tham khảo

Mô hình tham khảo được xây dựng dựa trên các nguyên lý của giải thuật di truyền và các nghiên cứu trước đó về bài toán xếp lịch. Mô hình này cho phép điều chỉnh linh hoạt các tham số để tối ưu hóa kết quả, đồng thời cung cấp một cái nhìn tổng quan về cách thức hoạt động của giải thuật di truyền trong việc giải quyết bài toán xếp lịch đa mục tiêu. Kết quả từ mô hình này đã cho thấy hiệu suất cao trong việc tối ưu hóa lịch trình cho nhiều nhóm công việc khác nhau.

V. Kết luận

Luận văn đã trình bày một cách tiếp cận mới để giải quyết bài toán xếp lịch đa mục tiêu thông qua việc sử dụng giải thuật di truyền. Kết quả nghiên cứu đã chứng minh rằng giải thuật di truyền không chỉ hiệu quả trong việc tìm kiếm các giải pháp tối ưu mà còn có khả năng linh hoạt điều chỉnh các tham số để phù hợp với yêu cầu cụ thể của bài toán. Công trình này có thể áp dụng trong nhiều lĩnh vực thực tế, từ sản xuất đến giáo dục, và mang lại lợi ích đáng kể cho việc tối ưu hóa lịch trình cho các nhóm công việc khác nhau. Việc phát triển và cải tiến mô hình trong tương lai sẽ góp phần nâng cao hiệu quả của giải thuật di truyền trong các bài toán xếp lịch phức tạp.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh công nghiệp hóa hiện đại và chuyển đổi số quy trình quản lý, việc sắp xếp lịch trình làm việc khoa học có thể giúp các tổ chức giảm từ 15% đến 30% chi phí vận hành, đồng thời nâng cao hiệu suất sử dụng máy móc lên hơn 25%. Tuy nhiên, bài toán xếp lịch công việc vốn thuộc lớp bài toán NP-Hard kinh điển trong khoa học máy tính, nơi không gian tìm kiếm lời giải tăng theo cấp số nhân khi số lượng nhiệm vụ và nhân sự mở rộng. Phần lớn các mô hình truyền thống trước đây chỉ tập trung giải quyết bài toán xếp lịch cá nhân đơn lẻ hoặc trong phạm vi một nhóm độc lập với một mục tiêu duy nhất là rút ngắn thời gian.

Luận văn thạc sĩ của học viên Nguyễn Hải Dương, thực hiện tại Khoa Khoa học và Kỹ thuật Máy tính thuộc Trường Đại học Bách Khoa – Đại học Quốc gia TP. Hồ Chí Minh dưới sự hướng dẫn khoa học của TS. Nguyễn Tiến Thịnh và PGS. Quản Thành Thơ, đã tập trung giải quyết bài toán xếp lịch trên nhiều nhóm đa mục tiêu bằng hướng tiếp cận giải thuật di truyền. Mục tiêu nghiên cứu cụ thể bao gồm việc phân tích cấu trúc bài toán xếp lịch nhiều nhóm phức tạp, xây dựng mô hình tối ưu hóa đồng thời 3 hàm mục tiêu gồm cực tiểu hóa thời gian hoàn thành toàn bộ công việc, cân bằng tải trọng làm việc giữa các nhóm và tối ưu hóa việc phân bổ khung thời gian khả dụng.

Nghiên cứu được triển khai trong phạm vi thời gian từ ngày 04/09/2023 đến ngày 18/12/2023 và bảo vệ thành công vào tháng 01 năm 2024. Đề tài sử dụng tập dữ liệu thực nghiệm chuẩn từ dự án POC Biển Đông. Kết quả cho thấy phương pháp đề xuất giúp tự động hóa hoàn toàn quy trình xếp lịch phức tạp trong vòng dưới 60 giây tính toán, mang lại giải pháp phân phối công việc khoa học với mức độ cải thiện hiệu suất tiến độ đạt tới 33,3% so với các phương pháp thủ cô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 được xây dựng dựa trên hai trụ cột lý thuyết tiến hóa đa mục tiêu hiện đại bao gồm Giải thuật di truyền xếp hạng không bị thống trị thế hệ 2 (NSGA-II) và thế hệ 3 (NSGA-III), tích hợp cùng lý thuyết tối ưu hóa đa mục tiêu Pareto. Khung lý thuyết này kết hợp 5 khái niệm cốt lõi:

• Mã hóa nhiễm sắc thể (Encoding): Mỗi phương án xếp lịch được mô hình hóa dưới dạng một cá thể với chuỗi gen đại diện cho thứ tự tác vụ, chỉ định máy và phân bổ khung giờ thực thi.
• Quan hệ thống trị Pareto (Pareto Dominance): Cơ chế so sánh đa chiều giúp xác định các giải pháp tối ưu mà tại đó không thể cải thiện bất kỳ mục tiêu nào nếu không làm suy giảm ít nhất một mục tiêu khác.
• Khoảng cách tập trung (Crowding Distance): Chỉ số định lượng mật độ xung quanh một giải pháp trong NSGA-II nhằm duy trì tính đa dạng của quần thể giải pháp, với chỉ số phân phối điều khiển dao động từ 5 đến 20.
• Điểm tham chiếu trên siêu phẳng chuẩn hóa (Reference Points): Kỹ thuật định hướng không gian của NSGA-III sử dụng 15 điểm tham chiếu chuẩn mực cho không gian 3 mục tiêu với tham số phân chia bằng 4, giúp quần thể bao phủ đồng đều toàn bộ mặt biên Pareto.
• Hàm vô hướng hóa thành tựu (Achievement Scalarization Function): Công cụ toán học xác định các điểm cực biên để chuẩn hóa không gian mục tiêu trước khi thực hiện phép liên kết cá thể.

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

• Nguồn dữ liệu: Dữ liệu thực nghiệm được trích xuất trực tiếp từ dự án POC Biển Đông, bao gồm danh mục chi tiết các công việc cha, các công việc con được phân rã, ma trận thời gian thực thi của từng loại máy và bảng khung thời gian trống khả dụng của từng nhân sự thuộc các nhóm.
• Cỡ mẫu và phương pháp chọn mẫu: Cỡ mẫu nghiên cứu bao gồm hơn 200 tác vụ phức tạp được cấu trúc thành các bộ dữ liệu thử nghiệm tiêu chuẩn như data_T3_1 và data_T3_2. Tác giả áp dụng phương pháp chọn mẫu có chủ đích kết hợp phân tầng theo năng lực chuyên môn giữa 3 nhóm làm việc chính (Nhóm A, Nhóm B, Nhóm C) cùng các nhóm dự phòng thay thế.
• Phương pháp phân tích và lý do lựa chọn: Nghiên cứu áp dụng phương pháp tiến hóa meta-heuristic kết hợp toán tử lai ghép nhị phân mô phỏng và toán tử đột biến đa thức. Phương pháp này được lựa chọn vì các bộ giải quy hoạch tuyến tính số nguyên hỗn hợp truyền thống thường rơi vào tình trạng bùng nổ tổ hợp và không thể tìm ra lời giải trong thời gian chấp nhận được khi xử lý bài toán NP-Hard quy mô lớn.
• Timeline nghiên cứu: Quá trình thiết kế mô hình toán học, tiền xử lý dữ liệu, cài đặt thuật toán và thực nghiệm kiểm chứng được hoàn thành trong vòng 15 tuần liên tục, từ đầu tháng 9 năm 2023 đến giữa tháng 12 năm 2023.

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

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

Nghiên cứu đã ghi nhận 4 phát hiện quan trọng có giá trị khoa học và ứng dụng thực tiễn cao:

• Tối ưu hóa thời gian hoàn thành tổng thể: Trên bộ dữ liệu data_T3_1, giải thuật di truyền đã tìm ra lịch trình tối ưu giúp rút ngắn chỉ số thời gian hoàn thành lớn nhất từ mốc 15 giờ xuống còn 10 giờ, tương đương mức cải thiện hiệu suất tiến độ đạt 33,3%.
• Tốc độ hội tụ của thuật toán thế hệ mới: Giải thuật NSGA-III chứng minh khả năng định hướng vượt trội khi đạt trạng thái hội tụ ổn định cho cả 3 hàm mục tiêu ngay tại thế hệ thứ 85, nhanh hơn 15% về số vòng lặp so với NSGA-II (cần tới 100 thế hệ để đạt độ ổn định tương đương).
• Cân bằng tải trọng nguồn lực vượt bậc: Việc phân chia nhiệm vụ cho nhiều nhóm đã giảm độ lệch thời gian làm việc giữa các máy từ mức chênh lệch 42% trong phương án ban đầu xuống dưới 8,5%, triệt tiêu hiện tượng thắt nút cổ chai tại các máy chủ chốt.
• Tỷ lệ duy trì nghiệm tối ưu đa dạng: Cơ chế điểm tham chiếu của NSGA-III giúp giữ lại hơn 95% cá thể không bị thống trị trên đường biên Pareto thực tế, cao hơn 13% so với tỷ lệ 82% của giải thuật di truyền đơn mục tiêu truyền thống.

Thảo luận kết quả

Diễn biến biến thiên của 3 hàm mục tiêu F1, F2 và F3 được trực quan hóa rõ nét thông qua hệ thống biểu đồ đường hội tụ qua từng thế hệ và biểu đồ phân tán không gian 3 chiều của tập nghiệm Pareto. Các kết quả này chứng minh rằng việc áp dụng cơ chế phân loại điểm tham chiếu chuẩn hóa giúp các cá thể phân bố đều khắp không gian tìm kiếm, không bị co cụm cục bộ vào một mục tiêu đơn lẻ như các phương pháp gán trọng số truyền thống.

Khi so sánh với phương pháp quy hoạch động và giải thuật nhánh cận từng được công bố trong các nghiên cứu trước đây, mô hình đề xuất trong luận văn cho tốc độ tính toán nhanh hơn khoảng 40 lần trên cùng một kích thước tập dữ liệu lớn. So với phương pháp Heuristic lập lịch ưu tiên tác vụ ngắn nhất hoặc tác vụ đến trước phục vụ trước chỉ đạt mức cải thiện 12% về mặt thời gian, phương pháp tiếp cận bằng NSGA-II và NSGA-III mang lại lời giải toàn diện hơn hẳn, vừa đảm bảo tính khả thi về mặt kỹ thuật với 100% ràng buộc thời gian chuẩn bị và thời hạn chót được thỏa mãn, vừa tối ưu hóa đồng thời lợi ích của nhiều đơn vị tham gia.

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

• Tích hợp module NSGA-III vào hệ thống hoạch định nguồn lực: Đội ngũ kỹ sư công nghệ thông tin và bộ phận điều độ sản xuất cần lập trình tích hợp thuật toán NSGA-III vào hệ thống phần mềm quản lý nội bộ. Mục tiêu nhằm giảm 90% thời gian lập lịch thủ công và tiết kiệm ít nhất 20% chi phí vận hành dự án, hoàn thành triển khai trong vòng 6 tháng đầu năm 2024.
• Chuẩn hóa cơ sở dữ liệu về năng lực và khung thời gian: Bộ phận quản lý vận hành cần tái cấu trúc và cập nhật định kỳ cơ sở dữ liệu về năng lực thiết bị, thời gian chuẩn bị và khung thời gian trống của nhân sự. Mục tiêu đạt độ chính xác dữ liệu trên 98% để đảm bảo đầu vào chuẩn xác cho thuật toán, tiến hành trong 3 tháng.
• Mở rộng nghiên cứu cơ chế lai ghép thích nghi: Các nhóm nghiên cứu phát triển thuật toán cần nâng cấp toán tử lai ghép SBX và đột biến đa thức bằng cách kết hợp kỹ thuật học tăng cường. Mục tiêu rút ngắn thêm 25% thời gian tính toán đối với các bài toán có quy mô trên 1000 công việc, thực hiện trong lộ trình 12 tháng.
• Đào tạo chuyển giao năng lực vận hành hệ thống: Lãnh đạo doanh nghiệp cần tổ chức các khóa tập huấn chuyên sâu về cách thức thiết lập tham số thuật toán và đọc hiểu báo cáo tập nghiệm Pareto cho 100% cán bộ quản lý dự án, triển khai định kỳ mỗi quý một lần.

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

• Giám đốc vận hành và Quản trị viên dự án công nghiệp: Vận dụng khung thuật toán để tự động hóa quy trình phân công nhiệm vụ cho hàng trăm nhân sự thuộc nhiều tổ đội, giải quyết triệt để bài toán chồng chéo lịch trình và tối ưu hóa chi phí nhân công.
• Kỹ sư phát triển phần mềm và Chuyên gia dữ liệu: Tham khảo chi tiết phương pháp lập trình toán tử di truyền, cách thức cài đặt cấu trúc dữ liệu nhiễm sắc thể và cơ chế tính toán điểm tham chiếu của NSGA-III để áp dụng vào các bài toán phân bổ tài nguyên điện toán đám mây.
• Giảng viên, Học viên cao học và Nghiên cứu sinh ngành Khoa học Máy tính: Sử dụng luận văn như một tài liệu học thuật hoàn chỉnh về phương pháp mô hình hóa bài toán tối ưu tổ hợp NP-Hard, phương pháp luận thực nghiệm và kỹ thuật đánh giá tập nghiệm Pareto.
• Chuyên gia tư vấn chuyển đổi số và Quản lý chuỗi cung ứng: Khai thác các phát hiện nghiên cứu để xây dựng giải pháp tối ưu hóa mạng lưới logistics, lập kế hoạch bảo trì thiết bị định kỳ và điều phối dòng công việc liên phòng ban cho các doanh nghiệp sản xuất.

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

• Bài toán xếp lịch trên nhiều nhóm khác biệt như thế nào so với xếp lịch một nhóm truyền thống? Trong bài toán xếp lịch một nhóm, công việc chỉ được luân chuyển giữa các cá nhân trong cùng một bộ phận với nguồn lực đồng nhất. Ngược lại, xếp lịch trên nhiều nhóm đòi hỏi phân chia tác vụ cho nhiều tổ đội độc lập có năng lực chuyên môn và khung thời gian rỗi khác nhau. Điều này làm tăng độ phức tạp tính toán lên gấp nhiều lần để đạt mục tiêu giảm thời gian hoàn thành từ 15 xuống 10 đơn vị.

• Vì sao NSGA-III lại vượt trội hơn NSGA-II trong bài toán xếp lịch có từ 3 hàm mục tiêu trở lên? Khi số lượng hàm mục tiêu đạt từ 3 trở lên, chỉ số khoảng cách tập trung của NSGA-II bị suy giảm hiệu quả do phần lớn các cá thể đều trở thành nghiệm không bị thống trị. NSGA-III giải quyết triệt để vấn đề này bằng cách phân bố các cá thể dựa trên các điểm tham chiếu định sẵn trên siêu phẳng chuẩn hóa, giúp duy trì độ đa dạng quần thể và tăng tốc độ hội tụ thêm 15%.

• Mô hình trong luận văn có thể xử lý các ràng buộc phức tạp nào trong thực tế sản xuất? Mô hình giải thuật đã giải quyết thành công 4 ràng buộc thực tế then chốt: khung thời gian trống khả dụng của từng máy, khả năng chia nhỏ tác vụ có chặn dưới, thời gian chuẩn bị chuyển đổi giữa các công việc và thời hạn chót bắt buộc phải hoàn thành của từng hợp đồng, đảm bảo 100% phương án đầu ra đều có tính khả thi tuyệt đối.

• Dữ liệu thực nghiệm của luận văn có nguồn gốc từ đâu và đảm bảo độ tin cậy như thế nào? Toàn bộ dữ liệu thử nghiệm được trích xuất từ dự án thực tế POC Biển Đông với hơn 200 tác vụ phân bổ trên nhiều nhóm máy thực tế. Dữ liệu bao gồm đầy đủ ma trận thời gian và các khoảng gián đoạn vận hành thực tế, đảm bảo tính đại diện khách quan và khả năng ứng dụng thực chiến trực tiếp của mô hình thuật toán.

• Doanh nghiệp có quy mô vừa và nhỏ có thể áp dụng giải pháp trong luận văn được không? Hoàn toàn khả thi vì thuật toán di truyền được thiết kế tối ưu, có thể chạy mượt mà trên hệ thống máy chủ văn phòng thông thường mà không cần đầu tư siêu máy tính đắt đỏ. Doanh nghiệp quy mô từ 50 đến 100 nhân viên có thể tích hợp mã nguồn để tối ưu hóa lịch làm việc tự động với chi phí đầu tư ban đầu rất thấp.

Kết luận

• Công trình đã hệ thống hóa và giải quyết trọn vẹn bài toán xếp lịch trên nhiều nhóm đa mục tiêu, một bài toán NP-Hard có tính ứng dụng cao trong thời đại số.
• Cài đặt và thực nghiệm thành công hai giải thuật tiến hóa tiên tiến NSGA-II và NSGA-III với các toán tử di truyền đặc thù cho bài toán phân bổ nguồn lực.
• Chứng minh tính hiệu quả vượt bậc trên tập dữ liệu POC Biển Đông khi rút ngắn thời gian hoàn thành tới 33,3% và giảm chênh lệch tải trọng công việc xuống dưới 8,5%.
• Khẳng định ưu thế vượt trội của NSGA-III trong việc duy trì độ đa dạng tập nghiệm Pareto và tăng tốc độ hội tụ nhanh hơn 15% so với NSGA-II.
• Mở ra hướng đi mới trong việc ứng dụng trí tuệ nhân tạo và thuật toán tối ưu hóa vào tự động hóa điều độ sản xuất công nghiệp 4.0.

Lộ trình phát triển và nâng cấp mô hình tích hợp trí tuệ nhân tạo tăng cường sẽ tiếp tục được hoàn thiện trong vòng 12 tháng tới. Các nhà nghiên cứu và doanh nghiệp quan tâm hãy tham khảo toàn văn luận văn thạc sĩ của tác giả Nguyễn Hải Dương để khai thác chi tiết giải pháp công nghệ đột phá này.

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 Hiện nay, rất nhiều công việc hằng ngày yêu cầu phải sắp xếp lịch. Từ sắp xếp lịch làm việc cho công nhân, lập kế hoạch sản xuất kinh doanh, đến lập thời khóa biểu cho sinh viên. Vì vậy nhu cầu có một lịch công việc khoa học là rất cần thiết. Bài toán này yêu cầu tìm cách phân bổ các tài nguyên, sự kiện, hoạt động hay công việc sao cho thỏa mãn các ràng buộc và tối ưu hóa một mục tiêu nào đó.

Ví dụ, bài toán xếp lịch học cho các lớp học, bài toán xếp lịch làm việc cho các nhân viên, bài toán xếp lịch thi đấu cho các đội bóng, v. Bài toán xếp lịch có nhiều ứng dụng thực tế và có thể giải quyết được nhiều vấn đề phức tạp. Tuy nhiên, bài toán xếp lịch cũng gặp nhiều khó khăn và thách thức khi số lượng các biến số và ràng buộc tăng lên. Bài toán xếp lịch thuộc vào lớp bài toán NP-Hard [1], nghĩa là không có thuật toán nào có thể giải được bài toán này trong thời gian đa thức.

Do đó, các nhà nghiên cứu đã đề xuất nhiều phương pháp heuristics và metaheuristics để tìm kiếm các lời giải gần đúng cho bài toán xếp lịch. Các phương pháp này bao gồm: thuật toán di truyền, thuật toán tìm kiếm cục bộ, thuật toán tìm kiếm nhánh cận, thuật toán tìm kiếm tabu, thuật toán tìm kiếm ràng buộc, v. Một số công cụ giúp sắp xếp lịch làm việc đã ra đời dựa trên nhu cầu đó, tuy nhiên vẫn dựa vào con người là chính, mang nặng tính thủ công. Không những thế, với những lịch công việc có khối lượng nhiệm vụ lớn, việc này sẽ tốn rất nhiều thời gian cho người lập lịch.1: Công cụ lập lịch Google calendar Tuy nhiên, lập lịch cho một người vẫn là chưa đủ.

Trong cuộc sống hiện nay đã xuất hiện nhu cầu về việc lập lịch cho nhiều người trên nhiều nhóm. Bài toán xếp lịch cho nhiều người thuộc nhiều nhóm là một bài toán phức tạp và thú vị trong lĩnh vực khoa học máy tính và quản lý dự án. Bài toán này đòi hỏi việc xác định một lịch trình công việc cho một số lượng lớn người, mỗi người có thể thuộc về một hoặc nhiều nhóm khác nhau. Ví dụ trong nhà máy, một công việc ngoài nhóm chính phụ trách ra thì còn có một số nhóm khác dự phòng có thể thay thế.

Việc tìm ra một lịch trình hiệu quả có thể giúp tiết kiệm thời gian và nguồn lực, đồng thời cải thiện hiệu suất và năng suất của tổ chức. Rõ ràng việc giải quyết bài toán không hề đơn giản, nhất là nếu có nhiều mục tiêu cần thỏa mãn ngoài việc tổng thời gian xử lý là ngắn nhất của bài toán xếp lịch cho một nhóm truyền thống. Đó là lý do tôi thực hiện đề tài “Giải bài toán xếp lịch trên nhiều nhóm đa mục tiêu bằng cận giải thuật di truyền” 2 1.2 Mô tả về bài toán xếp lịch Hình 1.2: Các hướng nghiên cứu bài toán xếp lịch PSP: personal scheduling problem TWSP: Team work scheduling problem Bài toán xếp lịch hiện có rất nhiều hướng nghiên cứu (xem hình 1.2), có thể liệt kê một số hướng như sau: • Xếp lịch cấp phát tác vụ (task allocation scheduling) là bài toán cấp phát tài nguyên cho các máy thực thực thi với chi phí tối thiểu, thường được áp dụng trong hệ thống phân tán, các hoạt động trong nhà máy sản xuất • Xếp lịch ràng buộc nguồn lực (resource constrained scheduling), có thể kể đến lập lịch điều phối nguồn lực cho dự án, sắp xếp thời khóa biểu giảng dạy phù hợp với số lượng giáo viên hiện có, … • Xếp lịch công việc (Job shop scheduling), là sắp xếp các thứ tự công việc được tiến hành, có thể kể đến như sắp xếp lịch trình làm việc một ngày đối với 1 cá nhân. Task allocation scheduling, hay còn gọi là lập lịch phân công nhiệm vụ, là một quá trình quan trọng trong nhiều lĩnh vực, bao gồm hệ thống nhúng, điện toán đám mây và quản lý dự án.

Trong hệ thống nhúng, lập lịch nhiệm vụ là quyết định thứ tự 3 mà các nhiệm vụ được thực hiện [2]. Scheduler, hay bộ lập lịch, là phần mềm quyết định nhiệm vụ nào nên được chạy tiếp theo. Trong điện toán đám mây, lập lịch nhiệm vụ và phân bổ tài nguyên là hai khía cạnh quan trọng [3]. Một số nghiên cứu đã được tiến hành để tìm ra các chiến lược phân bổ nhiệm vụ hợp lý trong môi trường đám mây.

Ví dụ, một phương pháp kết hợp giữa quy trình phân tích phân cấp sửa đổi (MAHP), lập lịch chia sẻ băng thông (BATS) và tối ưu hóa BAR, thời gian xử lý dự kiến dài nhất (LEPT), và phương pháp chia để trị đã được đề xuất để thực hiện lập lịch nhiệm vụ và phân bổ tài nguyên. Lập lịch phân bổ tài nguyên (Resource-Constrained Scheduling - RCS), còn được gọi là cân bằng tài nguyên, là một thuật ngữ được sử dụng trong quản lý dự án để mô tả quá trình tối ưu hóa lịch trình tập trung vào khả năng sẵn có của tài nguyên [4][5]. Mục tiêu chính là nhận biết bất kỳ hạn chế nào về tài nguyên của bạn, để bạn có thể tạo ra một lịch trình thực tế và thực tế cho các hoạt động của dự án. RCS được sử dụng khi tài nguyên bị giới hạn.

Trái ngược với lập lịch dựa trên thời gian, RCS không liên quan đến việc thuê nhà thầu để tăng tốc độ [3]. Hầu hết các dự án có ràng buộc tài nguyên, và do đó, kỹ thuật này có tiềm năng để giúp hầu hết các quản lý dự án¹. Bằng cách nhận biết sớm về các ràng buộc tài nguyên hoặc xung đột tiềm năng, người quản lý dự án có cơ hội điều chỉnh lịch trình hoặc tạo ra các giải pháp khác, thay vì giả định rằng dự án sẽ tiếp tục như thể không có giới hạn [4]. Trong bài toán này, mỗi công việc có một thời gian thực hiện cố định và yêu cầu sử dụng một số lượng nguồn lực nhất định.

Nguồn lực có thể có giới hạn hoặc không đủ để đáp ứng tất cả các yêu cầu từ các công việc. Do đó, việc xếp lịch phải đảm bảo rằng các công việc không xung đột với nhau trong việc sử dụng nguồn lực và tuân thủ các ràng buộc nguồn lực. Lập lịch công việc job shop scheduling là một bài toán tối ưu hóa trong khoa học máy tính và nghiên cứu hoạt động, trong đó mục tiêu là sắp xếp các công việc trên các máy sao cho thời gian hoàn thành tất cả các công việc là nhỏ nhất. Mỗi công việc bao gồm một tập hợp các thao tác cần được thực hiện theo một thứ tự nhất định trên các máy khác nhau.

Mỗi thao tác chỉ có thể được xử lý trên một máy nhất định và chỉ có một thao tác trong một công việc có thể được xử lý tại một thời điểm. Bài toán này 4 có nhiều biến thể và ứng dụng trong các lĩnh vực như sản xuất, dịch vụ, y tế, giáo dục, v. Trong nghiên cứu của Chengbin Chu và Hu Ding (2015) [6]đã đề xuất một phương pháp lập lịch thông minh dựa trên thuật toán di truyền để giải quyết vấn đề Job Shop Scheduling. Phương pháp này đã được áp dụng thành công trong một nhà máy sản xuất gạch bê tông và cho thấy hiệu quả cao trong việc tối ưu hóa thời gian sản xuất và tăng năng suất.

Trong Nghiên cứu của Morteza Mahjoubi và Saeed Gholami (2019) [7] đã sử dụng thuật toán di truyền để giải quyết vấn đề Job Shop Scheduling trong một nhà máy sản xuất ô tô. Kết quả nghiên cứu cho thấy việc sử dụng thuật toán di truyền giúp cải thiện năng suất và giảm thời gian chờ đợi trong quá trình sản xuất. Đề tài tập trung nghiên cứu về việc xếp lịch trên nhiều nhóm đa mục tiêu, một vấn đề thuộc hướng nghiên cứu xếp lịch công việc (Job shop scheduling). Trước khi đi đến mô tả bài toán xếp lịch công việc trên nhiều nhóm, tác giả sẽ trình bày các dạng bài toán lập lịch công việc cơ bản.1 Bài toán xếp lịch cá nhân PSP Đây là bài toán lập lịch cá nhân có thể cắt nhỏ bị chặn dưới vào những khung thời gian trống sao cho thời điểm hoàn thành tất cả các công việc là nhỏ nhất (gọi là bài toán PSP), trong đấy: • Cá nhân (Machine) là một đối tượng cần xếp lịch • Các công việc (Job) đều có thời gian thực thi, thời gian bắt buộc phải hoàn thành • Những khung thời gian trống có thể sắp xếp công việc vào đó và những khung thời gian bận hoặc không được xếp lịch Các ký hiệu trong bài toán lập lịch cá nhân PSP được mô tả như sau: • Có n công việc Ji (i = 1,.

,n) và m khung thời trống Wj (j = 1,. Trong mỗi công việc Ji còn có các thông tin liên quan như sau: • pi: thời gian xử lý của công việc Ji • ri: Thời điểm bắt đầu thực thi của công việc Ji 5 • Các ràng buộc của bài toán • Các công việc có thể chia nhỏ pi để thực hiện trên các máy khác nhau tuy nhiên không thể nhỏ hơn một khoảng splitmin định trước • Các phần được chia nhỏ của công việc chỉ được xếp vào những khoảng thời gian trống của máy (available – windows) • Mục tiêu của bài toán: • Cmax = max (Ci) : là thời điểm hoàn thành lớn nhất của tập hợp công việc, với Ci là thời gian hoàn thành công việc Ji. Mục tiêu này càng nhỏ càng tốt • ∑Ci: Tổng thời gian thực hiện các công việc Ji. Mục tiêu này càng nhỏ càng tốt Hình 1.3: Hình minh họa lịch làm việc của một cá nhân Trong [8] của nhóm tác giả J.Wesley Barnes và John B.

Chambers, đã trình bày một cách tiếp cận tìm kiếm tabu hiệu quả cho vấn đề lập kế hoạch của một cửa hàng. Quy trình bắt đầu từ phương án tốt nhất được tìm bởi một bộ 14 giải pháp heuristic. Sau đó, họ sử dụng biểu diễn mạng phân tách truyền thống của vấn đề và lặp đi lặp lại việc chuyển sang giải pháp khả thi khác bằng cách đảo ngược thứ tự của hai thao tác quan trọng liền kề được thực hiện bởi cùng một máy. Trong [9], nhóm tác giả đã đề cập đến hai vấn đề tối ưu hóa NP-hard: các vấn đề lập lịch cửa hàng công việc linh hoạt (FJSP) bao gồm các vấn đề phụ về định tuyến và sắp xếp thứ tự, và các FJSP với tính linh hoạt của kế hoạch quy trình (FJSP-PPF) bao gồm thêm việc lựa chọn kế hoạch quy trình phụ vấn đề.

Nghiên cứu được thực hiện theo hai bước.