Tài liệu Toán: Một số phương pháp gần đúng giải bài toán lập lịch với tài

Chuyên khảo Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới phân tích chuyên sâu các khía cạnh quan trọng trong lĩnh vực

• Tác giả: Đặng Quốc Hữu
• Người hướng dẫn: Ts. Nguyễn Thế Lộc
• Trường học: Viện Khoa học và Công nghệ quân sự
• Chuyên ngành: Cơ sở toán học cho tin học
• Đề tài: Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2021
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về Phương pháp Gần đúng Giải Bài Toán Lập Lịch

Phương pháp gần đúng giải bài toán lập lịch là một lĩnh vực nghiên cứu quan trọng trong toán học ứng dụng và khoa học máy tính. Bài toán lập lịch với tài nguyên giới hạn (RCPSP) là một thách thức lớn trong quản lý dự án hiện đại. Các phương pháp gần đúng được phát triển để tìm kiếm các giải pháp tối ưu hoặc gần tối ưu trong thời gian hợp lý. Luận án tiến sĩ của Đặng Quốc Hữu từ Viện Khoa học và Công nghệ quân sự đã đề xuất nhiều thuật toán metaheuristic hiệu quả. Những phương pháp này kết hợp các kỹ thuật tìm kiếm thông minh để giải quyết các bài toán phức tạp trong lập lịch dự án.

1.1. Định nghĩa Bài Toán Lập Lịch

Bài toán lập lịch với tài nguyên giới hạn (MS-RCPSP) là bài toán xác định thứ tự thực hiện các tác vụ với các ràng buộc về tài nguyên. Mục tiêu chính là tối thiểu hóa thời gian hoàn thành dự án (makespan). Các tác vụ có mối quan hệ phụ thuộc, yêu cầu tài nguyên cụ thể, và phải tuân theo các ràng buộc về khả năng cung cấp tài nguyên.

1.2. Tầm quan trọng của Phương pháp Gần đúng

Do bài toán lập lịch là NP-khó, các phương pháp chính xác không khả thi với quy mô lớn. Phương pháp gần đúng cung cấp giải pháp hiệu quả và thực tế. Chúng cho phép tìm kiếm các lời giải chất lượng cao trong thời gian tính toán hợp lý, phù hợp với các ứng dụng thực tế.

II. Các Thuật toán Metaheuristic Chính

Luận án đã nghiên cứu và phát triển nhiều thuật toán metaheuristic khác nhau để giải bài toán lập lịch. Các thuật toán này bao gồm thuật toán PSO (Particle Swarm Optimization), thuật toán DE (Differential Evolution), và thuật toán Cuckoo Search. Mỗi phương pháp có những ưu điểm riêng trong việc khám phá không gian tìm kiếm. Thuật toán M-PSO được đề xuất kết hợp PSO với kỹ thuật Di cư để cải thiện hiệu suất. Thuật toán DEM áp dụng Tiến hóa vi phân với phương pháp tái thiết lập tài nguyên. Các thuật toán này đã chứng minh hiệu quả cao trong các thử nghiệm thực tế.

2.1. Thuật toán PSO và M PSO

Thuật toán PSO mô phỏng hành vi tập trung của bầy đàn. Phiên bản cải tiến M-PSO kết hợp kỹ thuật Di cư để tăng tính đa dạng của quần thể. Phương pháp này giúp tránh rơi vào cực tiểu địa phương và cải thiện chất lượng lời giải đáng kể.

2.2. Thuật toán DE và Cuckoo Search

Thuật toán DEM sử dụng Tiến hóa vi phân kết hợp với tái thiết lập tài nguyên. Thuật toán Cuckoo Search mô phỏng hành vi đẻ trứng của chim cuckoo. Cả hai phương pháp đều cho kết quả cạnh tranh với các thuật toán truyền thống.

III. Bài Toán Real RCPSP và Ứng Dụng

Bài toán Real-RCPSP là mở rộng của MS-RCPSP khi các tài nguyên là liên tục (không rời rạc). Đây là dạng bài toán gần với thực tế hơn khi tài nguyên có thể được chia nhỏ. Luận án đã phát triển thuật toán A-DEM với phương pháp thích nghi để giải bài toán này. Thuật toán R-CSM và RR-CSM được đề xuất sử dụng Cuckoo Search kết hợp các kỹ thuật tối ưu hóa. Những ứng dụng thực tế bao gồm lập lịch xây dựng, quản lý dự án phần mềm, và các dự án quy mô lớn.

3.1. Phân Loại Graham cho Real RCPSP

Phân loại Graham là cách phân loại hệ thống lập lịch dựa trên các đặc trưng: α (môi trường máy), β (đặc tính công việc), γ (tiêu chí tối ưu). Việc này giúp xác định độ khó của bài toán và lựa chọn thuật toán phù hợp nhất.

3.2. Ứng Dụng Thực Tế

Bài toán Real-RCPSP áp dụng trong quản lý dự án hiện đại, xây dựng hạ tầng, và sản xuất công nghiệp. Việc tối ưu hóa lập lịch giúp giảm chi phí, rút ngắn thời gian dự án, và sử dụng hiệu quả tài nguyên.

IV. Kết Quả Nghiên Cứu và Đánh Giá

Luận án đã tiến hành các thử nghiệm toàn diện để đánh giá chất lượng các phương pháp gần đúng được đề xuất. Các thuật toán được so sánh với GA-M (Genetic Algorithm) trên các bộ dữ liệu tiêu chuẩn. Kết quả cho thấy M-PSO, DEM, A-DEM, R-CSM, và RR-CSM đều vượt trội hơn các phương pháp cũ. Giá trị trung bình (AVG) và giá trị tốt nhất (BEST) của các giải pháp được ghi nhận. Các hình ảnh so sánh minh họa rõ ràng sự cải thiện hiệu suất. Nghiên cứu này góp phần quan trọng vào phát triển lĩnh vực tối ưu hóa lập lịch.

4.1. Các Chỉ Tiêu Đánh Giá

Chất lượng lời giải được đánh giá qua giá trị tốt nhất, giá trị trung bình, và độ lệch chuẩn. Thời gian tính toán là tiêu chí quan trọng khác. Các thuật toán mới đều thể hiện cải thiện đáng kể so với các phương pháp cũ.

4.2. Hướng Phát Triển Tương Lai

Nghiên cứu mở ra các hướng phát triển mới: kết hợp nhiều thuật toán (hybrid), ứng dụng trí tuệ nhân tạo, và mở rộng cho bài toán đa mục tiêu. Phương pháp gần đúng sẽ tiếp tục được cải tiến để xử lý các bài toán phức tạp hơn.

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

Đặt vấn đề Mục tiêu của bài toán RCPSP là tìm phương án lịch biểu tốt nhất để thực hiện các tác vụ (task) của dự án trong điều kiện bị giới hạn về tài nguyên và các tác vụ có ràng buộc về thứ tự thực hiện. Hàm mục tiêu của bài toán RCPSP được đánh giá dựa trên một trong hai đại lượng là thời gian thực thi (makespan) hoặc chi phí thực thi (cost) hoặc kết hợp cả hai đại lượng này (đa mục tiêu). Trong RCPSP, nhiều tác vụ được đưa ra để thực hiện, mỗi tác vụ được mô tả theo thời gian bắt đầu và kết thúc. Một tác vụ bất kỳ khi đã bắt đầu thì không thể dừng lại cho đến khi kết thúc.

Các tác vụ liên quan đến nhau bằng các mối quan hệ ưu tiên về trình tự thực hiện. Theo thứ tự ưu tiên, tác vụ cần phải hoàn thành trước thời gian bắt đầu của tác vụ khác được gọi là những tác vụ tiền nhiệm. Các tài nguyên được cung cấp hữu hạn và được sử dụng để thực hiện các tác vụ. Khi tác vụ cần, một số tài nguyên sẽ được sử dụng, số tài nguyên được cấp không được vượt quá số sẵn có.

Một tác vụ có thể sử dụng nhiều tài nguyên, một đơn vị tài nguyên chỉ dùng cho một tác vụ tại một thời điểm. Bài toán RCPSP: RCPSP [2], [CT4] là bài toán tối ưu tổ hợp, thuộc lớp NP-Khó, gồm các thành phần (V,t,C,L,S,s), trong đó: • V ={W0,.,Wn+1}: tập hợp các tác vụ cần thực hiện., Wn là các tác vụ cần thực hiện 10 - W0, Wn+1 là 2 tác vụ giả định, được bổ sung để phục vụ việc xác định thời điểm bắt đầu và thời điểm kết thúc của dự án.,Wn} tập các tác vụ (thật) cần thực hiện.,tn+1} thời gian thực hiện của các tác vụ. • ti: thời gian thực hiện của Wi. Các giá trị đặc biệt: t0 = tn+1 = 0.

• P: lịch biểu để thực hiện • Bi: thời gian bắt đầu của tác vụ i • Ei: thời gian hoàn thành tác vụ i, dễ nhận thấy: Ei = Bi + ti • Vq = {Wi ∈ W | Bi ≤ q < Bi +ti} tập các tác vụ (thật) đang thực hiện tại thời điểm q. • C: tập các ưu tiên, (Wi, Wj) ∈ C, nghĩa là tác vụ Wi thực hiện trước tác vụ Wj • L: tập hợp các tài nguyên, L = {L1, L2,., Lk }, giả thiết chúng có thể được tái sử dụng., Sk } tập hợp chứa thông tin về dung lượng tài nguyên, Sk thể hiện dung lượng của Lk. • sik: số lượng tài nguyên Lk được huy động để thực hiện Wi. giả sử P0 = 0, một lời giải là khả thi nếu thỏa mãn các ràng buộc sau đây: Bj – Bi ≥ ti  (Wi, Wj)  C (1.2) Cụ thể:  Ràng buộc (1.1): thể hiện ràng buộc ưu tiên giữa hai tác vụ i và j.

Tác vụ cha (task i) phải kết thúc trước thời điểm tác vụ con (task j) bắt đầu, tác vụ con có thể không thực hiện ngay sau khi tác vụ cha kết thúc.2): số lượng tài nguyên k sử dụng để thực hiện tác vụ i tại thời điểm q tối đa bằng dung lượng của tài nguyên k. Makespan của lịch biểu P = Bn+1 là thời điểm bắt đầu của tác vụ cuối cùng.1[2]: RCPSP là bài toán tìm kiếm lịch biểu P sao cho 11 makespan của P là tối thiểu theo các ràng buộc (1. Ký hiệu:  X: tập các lời giải rời rạc, Pall: là tập các lời giải khả thi, Pall ⊆ X  Hàm mục tiêu: f: Pall → ℝ cần tìm lời giải khả thi P ∈ Pall, thể hiện bởi hàm f(P) là min hoặc max.1 dưới đây, RCPSP khởi tạo 10 tác vụ, sử dụng 2 tài nguyên với S1 = 7 và S2 = 4.1: Thông tin đầu vào của dự án Wi W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 ti 0 6 1 1 2 3 5 6 3 2 4 0 si1 0 2 1 3 2 1 2 3 1 1 1 0 si2 0 1 0 1 0 1 1 0 2 2 1 0 Quan hệ ràng buộc về thứ tự ưu tiên của các tác vụ được thể hiện dưới dạng đồ thị như trong Hình 1. Đồ thị ưu tiên thực hiện các tác vụ.

Lịch biểu với makespan tối thiểu Bn+1=12 được thể hiện dưới dạng lược đồ Gantt dạng mảng 2 chiều như trong hình 1.2, trong đó trục x thể hiện thời gian, 12 trục y thể hiện yêu cầu tài nguyên sử dụng. Biểu đồ Gantt về thực hiện các tác vụ theo thời gian 1. Phát biểu bài toán MS-RCPSP MS-RCPSP [4],[6],[22],[31],[CT4] là bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và đa kỹ năng, được mở rộng từ bài toán RCPSP. MS- RCPSP được bổ sung thêm yếu tố đa kỹ năng của tài nguyên, theo đó, mỗi tài nguyên có các kỹ năng (skill) khác nhau và mỗi kỹ năng có một mức/bậc (level) nhất định.

Mỗi tác vụ sẽ yêu cầu tài nguyên đáp ứng kỹ năng và mức kỹ năng cụ thể để thực hiện. Do bổ sung ràng buộc mới, bài toán MS-RCPSP gần với các dự án thực tế có liên quan đến yếu tố kỹ năng và mức kỹ năng hơn. Phát biểu toán học của bài toán MS-RCPSP Các ký hiệu:  Ci: tập tác vụ (task) cần thực hiện trước tác vụ i  S: tập tất các các kỹ năng của các tài nguyên; Si: Tập các kỹ năng của tài nguyên i, Si  S;  Si: kỹ năng thứ i; 13  tj: thời gian thực hiện tác vụ j  L: tập các tài nguyên;  Lk: tập tài nguyên có thể thực hiện tác vụ k; Lk  L  Li: tài nguyên thứ i  W: tập các tác vụ của dự án;  Wk: tập các tác vụ có thể thực hiện bởi tài nguyên k, Wk  W  Wi: tác vụ thứ i  ri: tập các kỹ năng được yêu cầu để thực hiện tác vụ i. Một tài nguyên có thể thực hiện được tác vụ i nếu có kỹ năng giống với kỹ năng yêu cầu của tác vụ i và có mức kỹ năng lớn hơn hoặc bằng mức kỹ năng yêu cầu.

 Bk, Ek: thời gian bắt đầu và thời gian kết thúc thực hiện tác vụ k  Au,vt: biến xác định tài nguyên v có đang thực hiện tác vụ u tại thời điểm t hay không; 1: có, 0: không;  hi: mức kỹ năng của kỹ năng (skill) i;  gi: loại kỹ năng i;  m: makespan của lịch biểu  P: một lịch biểu khả thi của bài toán;  Pall: tập tất cả các lịch biểu  f(P): hàm mục tiêu, để tính makespan của P  n: số tác vụ, z: số tài nguyên Mục tiêu của bài toán MS-RCPSP là tìm lịch biểu P sao cho: f(P)  min Lịch biểu tìm được cần thỏa mãn các ràng buộc sau:  Sk    Lk L (1.5) 14  Ei  Ej - tj WjW, j1, Wi Cj (1.9) Cụ thể:  Ràng buộc (1.3): mỗi tài nguyên phải có tối thiểu một kỹ năng nào đó  Ràng buộc (1.5): thời gian thực hiện của tác vụ bất kỳ tối thiểu phải bằng 0 (thực tế thì mọi tác vụ thật, có thời gian thực hiện tối thiểu luôn > 0, trường hợp bằng 0 để minh họa cho 2 tác vụ giả thể hiện thời điểm bắt đầu và kết thúc của dự án)  Ràng buộc (1.6): tác vụ cha (task i) phải kết thúc trước thời điểm tác vụ con (task j) bắt đầu. Thời điểm tác vụ i kết thúc ký hiệu là Ei, thời điểm tác vụ con j bắt đầu là Ej - tj (thời điểm kết thúc trừ đi thời gian thực hiện).7) nghĩa là: với mọi tác vụ i  Wk (tập các tác vụ mà tài nguyên k thực hiện được), luôn tồn tại kỹ năng S  Sk (tập skill của tài nguyên k) sao cho 𝑔𝑆 = 𝑔𝑆𝑖 : loại skill của r trùng với loại kỹ năng của Li mà tác vụ i yêu cầu. ℎ𝑆𝑞 ≥ ℎ𝑟 𝑖 : mức kỹ năng của tài nguyên thực hiện cao hơn hoặc bằng mức kỹ năng yêu cầu.8): tại mỗi thời điểm (q), mỗi tài nguyên chỉ được thực hiện 𝑞 tối đa một tác vụ. Nếu ∑𝑛𝑖=1 𝐴𝑖,𝑘 = 0 thì tài nguyên k không được gán cho 𝑞 tác vụ nào, nếu ∑𝑛𝑖=1 𝐴𝑖,𝑘 =1 thì tài nguyên k được gán cho một tác vụ duy nhất.9): mỗi tác vụ chỉ được gán cho một tài nguyên duy nhất và chỉ được thực hiện bởi một tài nguyên duy nhất.

Trong bài toán MS-RCPSP, mỗi tác vụ có thêm các yêu cầu về kỹ năng (skill) của tài nguyên cần để thực hiện, mỗi tài nguyên cũng được chia làm nhiều mức kỹ năng khác nhau. Các ràng buộc về kỹ năng của tài nguyên được 15 yêu cầu để thực hiện một tác vụ được mô tả dưới dạng một ma trận như ví dụ được minh họa trong hình 1.3 dưới đây:  Có thể thiết lập Tác vụ  Không thể thiết lập S2. Ma trận quan hệ giữa tác vụ và kỹ năng của tài nguyên Trong hình 1.j nghĩa là kỹ năng Si và mức kỹ năng j. Tác vụ yêu cầu tài nguyên thực hiện phải đáp ứng loại kỹ năng và mức kỹ năng cụ thể.

Tài nguyên thực hiện cần có cùng loại kỹ năng và mức kỹ năng lớn hơn hoặc bằng mức kỹ năng yêu cầu. Cụ thể: Tác vụ W1, yêu cầu tài nguyên có loại kỹ năng S2 và mức kỹ năng lớn hơn hoặc bằng 2. Đối chiếu với bảng tài nguyên, ta thấy tài nguyên L1 có loại kỹ năng S2 và mức kỹ năng của S2 là 2, do vậy L1 có thể thực hiện W1. Một số ứng dụng thực tế của bài toán MS-RCPSP 1.

Ứng dụng trong Fog Computing và Edge Computing Fog Computing [32] được thiết kế để khắc phục những hạn chế của điện toán đám mây (Cloud Computing) bằng cách cung cấp một kiến trúc phân tán trong đó một số dữ liệu sẽ được phân loại để xử lý ngay bởi các thiết bị ở gần nơi phát sinh dữ liệu thay vì phải gửi về trung tâm đám mây, như vậy vừa tiết kiệm được chi phí truyền thông, giảm khả năng bị mất mát hoặc rò rỉ (do vấn đề bảo mật) trên đường truyền lại vừa tránh được nghẽn đường truyền mạng. Những kiến trúc này được thiết kế và xây dựng theo các mô hình của Edge 16 Computing (Điện toán biên). Nhiệm vụ chính của Fog Computing là tìm phương án bố trí các nguồn tài nguyên tính toán bao gồm máy chủ, router, các thiết bị lưu trữ, database sao cho tối đa hóa việc truy xuất và xử lý cục bộ.