Giải Bài Toán Real-Rcpsp Bằng Phương Pháp Tiến Hóa Vi Phân Và Phương Pháp Cuckoo

Chương này trình bày về phương pháp biểu diễn cá thể của bài toán MS- RCPSP và đề xuất thang đo độ chênh lệch giữa các cá thể. Thang đo là thành phần quan trọng để phục vụ cho quá trình tính toán tiến hóa của các cá thể. Để phục vụ cho việc thực nghiệm, kiểm chứng thuật toán, chương này cũng giới thiệu về bộ dữ liệu iMOPSE, bộ dữ liệu chuẩn được Myszkowski [42],[45] và các cộng sự phát triển riêng cho bài toán MS-RCPSP. Trên cơ sở đó, luận án đề xuất hai thuật toán mới đề giải bài toán MS-RCPSP:

- Thuật toán M-PSO được phát triển từ thuật toán tối ưu bầy đàn PSO

- Thuật toán DEM được xây dựng trên cơ sở thuật toán tiến hóa vi phân DE

Để kiểm chứng các thuật toán đề xuất, luận án tiến hành thực nghiệm, tổng hợp kết quả thực nghiệm, phân tích và đánh giá tính hiệu quả.

Chương 3. Bài toán Real-RCPSP

Chương 3 trình bày về bài toán mới đề xuất Real-RCPSP, bao gồm các nội dung như phát biểu toán học của bài toán, giới thiệu ứng dụng thực tế của bài toán và xếp loại bài toán.

Chương 4. Giải bài toán Real-RCPSP bằng phương pháp Tiến hóa vi phân và phương pháp Cuckoo Search

Trong chương 4, luận án trình bày các vấn đề để giải bài toán Real-RCPSP gồm: mã hóa cá thể, xây dựng bộ dữ liệu thực tế và ba thuật toán mới để giải bài toán Real-RCPSP.

- Thuật toán A-DEM, được xây dựng trên cơ sở thuật toán tiến hóa vi phân DE để ứng dụng tìm lời giải cho bài toán mới

- Thuật toán R-CSM, thuật toán mới này được đề xuất trên cơ sở của thuật toán tiến hóa Cuckoo Search (CS)

- Thuật toán RR-CSM, thuật toán mới này được cải tiến dựa trên thuật toán

R-CSM

Các thuật toán này mang lại kết quả tốt với bài toán Real-RCPSP. Các thực nghiệm được tiến hành trên bộ dữ liệu iMOPSE và bộ dữ liệu TNG do nghiên cứu sinh tự thu thập và xây dựng. Kết quả thực nghiệm được thu thập, tổng hợp, phân tích và đánh giá tính hiệu quả.

CHƯƠNG 1

TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP

Các bài toán lập lịch đã được đề xuất, nghiên cứu từ năm 1950 [37], nhiệm vụ chính của việc lập lịch là tìm ra một lịch biểu để thiết lập các tài nguyên sẵn có trong việc thực hiện các công việc/tác vụ (task) và thỏa mãn tập ràng buộc cho trước nhằm đạt được một mục tiêu cụ thể, thường là tối thiểu hóa chi phí và/hoặc thời gian thực hiện của toàn dự án hoặc một quy trình sản xuất. Bài toán lập lịch được ứng dụng trong nhiều lĩnh vực khác nhau như lập lịch điều phối tài nguyên trong hệ điều hành [39], lập lịch cho dây chuyền sản xuất,... hoặc ứng dụng trong lĩnh vực kinh tế, tài chính [11],[62],[CT4], quân sự [17],[18],[28],[CT4], … Nhiều bài toán lập lịch tổng quát đã được chứng minh là thuộc lớp NP-Khó [2],[22],[46].

Ngày nay, rất nhiều ứng dụng trong nghiên cứu khoa học và thực tiễn có sử dụng đến dữ liệu dạng luồng công việc, đặc trưng của các ứng dụng này là phải xử lý nhiều tác vụ với dữ liệu vào/ra giữa các tác vụ là rất lớn. Tìm ra một lịch biểu tốt để gán các tài nguyên thực hiện từng tác vụ trong một chuỗi công việc một cách hiệu quả là rất cần thiết và thu hút sự tập trung của nhiều nhà khoa học.

RCPSP (Resource-Constrained Project Scheduling Problem) [2],[46], [CT4] là bài toán lập lịch dự án với tài nguyên giới hạn, đã được chứng minh là bài toán thuộc lớp NP-Khó. Mục tiêu là tìm ra lịch biểu thực hiện dự án với thời gian tối thiểu trong điều kiện hạn chế về tài nguyên thực hiện. Hiện nay, bài toán này được nghiên cứu và ứng dụng trong nhiều lĩnh vực. Luận án tập trung tìm hiểu một trường hợp mở rộng của bài toán RCPSP, được đặt tên là MS-RCPSP.

Chương này gồm các nội dung chính sau:

Phần 1.1: Trình bày về 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 (MS-RCPSP), các ứng dụng của bài toán này.

Phần 1.2: Trình bày 03 thuật toán metaheuristic để tìm nghiệm gần đúng áp dụng cho các bài toán thuộc lớp NP-Khó, gồm: PSO, DE, CS.

1.1. Bài toán MS-RCPSP

1.1.1. Mô tả bài toán

1.1.1.1. Đặ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. trong đó:

- W1,..., Wn là các tác vụ cần thực hiện

- 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.

• W = {W1,...,Wn} tập các tác vụ (thật) cần thực hiện.

• t = {t0,t1,...,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.

• S = {S1,..., 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.1)

∑𝑊𝑖𝑉𝑞 𝑠𝑖𝑘 ≤ 𝑆𝑘 ∀𝐿𝑘 ∈ 𝐿, ∀𝑞 ≥ 0 (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.

 Ràng buộc (1.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.

Định nghĩa 1.1[2]:RCPSP là bài toán tìm kiếm lịch biểu P sao cho

makespan của P là tối thiểu theo các ràng buộc (1.1), (1.2).

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.

Ví dụ 1.1[2]:

Trong bảng 1.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.

Bảng 1.1: Thông tin đầu vào của dự án

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

Có thể bạn quan tâm!

Xem toàn bộ 156 trang tài liệu này.

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.1.

W10

W11

Hình 1.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,

trục y thể hiện yêu cầu tài nguyên sử dụng.

Hình 1.2. Biểu đồ Gantt về thực hiện các tác vụ theo thời gian

1.1.1.2. 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;

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.3)
tj 0	WjW	(1.4)
Ej 0	WjW	(1.5)