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

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.

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.