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.