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

các tài nguyên có thể thực hiện được tác vụ đó. Thang đo ký hiệu là p.

Ví dụ 2.2: cho bộ dữ liệu của bài toán MS-RCPSP với 10 tác vụ, 3 tài nguyên và khả năng thực hiện của các tài nguyên như sau:

- L1 = {W1, W2, W3, W5, W7, W9, W10 }

- L2 = {W2, W3, W5, W6, W8, W10}

- L3 = { W1, W3, W4, W6, W7 }

Khi đó, thang đo có thể được biểu diễn như bảng 2.2 dưới đây.

Thang đo này sẽ được sử dụng để hiệu chỉnh cá thể mới tạo ra khi các chỉ số tài nguyên sau khi tính toán không nằm trong tập tài nguyên thực hiện của tác vụ.

Bảng 2.2: Thang đo tài nguyên thực hiện tác vụ

Thang đo của tác vụ

Chỉ số tài nguyên thứ nhất	Chỉ số tài nguyên thứ hai	Chỉ số tài nguyên thứ ba
p1	1	3
p2	1	2
p3	1	2	3
p4	3
p5	1	2
p6	2	3
p7	1	3
p8	2
p9	1
p10	1	2

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

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

Biểu diễn độ chênh giữa các cá thể

Định nghĩa 2.2: vector d gọi là vector độ chênh giữa 2 cá thể có số phần tử bằng số tác vụ của cá thể, giá trị của mỗi phần tử được tính theo công thức 2.1.

di = mod(abs(pi,j - pi,k),100)(2.1)

trong đó:

- i: tác vụ i;

- j: vị trí của tài nguyên thực hiện tác vụ i của cá thể 2 trên vector thang đo pi;

- k: vị trí của tài nguyên thực hiện tác vụ i của cá thể 1 trên vector thang đo pi.

Tính độ chênh giữa hai cá thể dựa trên thang đo

Trong bài toán MS-RCPSP, mỗi tác vụ có thời gian thực hiện cố định, không phân biệt tài nguyên thực hiện. Do vậy, khoảng giữa các phần tử của thang đo được tính như công thức 2.2 dưới đây.

∆ = 100/(k-1) với k > 1 (2.2)

k: số tài nguyên có thể thực hiện tác vụ. Trường hợp chỉ có 1 tài nguyên

(k=1) thì ∆=100.

Khi đó, giá trị của mỗi phần tử trong thang đo được tính như công thức (2.3)

pi,j = ∆* (j-1) (2.3)

j: là vị trí của phần tử trên thang đo của tác vụ i.

Ví dụ 2.3: tác vụ W1 có 6 tài nguyên có thể thực hiện được, lần lượt là: L1, L3, L4, L5, L9, L10.

L10

Thang đo được biểu diễn như trong hình 2.3.

L10

p1:0 20 40 60 80 100

Hình 2.3. Biểu diễn giá trị trên thang đo

Phép trừ 02 cá thể - tính độ chênh

Phép trừ 02 cá thể tạo ra vector độ chênh được tính theo công thức 2.1.

Ví dụ 2.4:

Có 2 tác vụ W1 và W2. Tài nguyên có thể thực hiện từng tác vụ được biểu diễn trong bảng 2.3.

Bảng 2.3: Tài nguyên có thể thực hiện tác vụ

L1	L3	L4	L5	L9	L10
W2	L3	L6	L7	L8	L10

Số tài nguyên thực hiện được W1 là 6, số tài nguyên thực hiện được W2 là

5. Khi đó:

- với tác vụ W1: ∆1 = 100/5 = 20

- với tác vụ W2: ∆2 = 100/4 = 25

Thang đo khoảng cách như trong bảng 2.4 dưới đây.

Bảng 2.4: Giá trị vector thang đo

0	20	40	60	80	100
p2	0	25	50	75	100

xét 2 cá thể S1, S2 có tài nguyên thực hiện từng tác vụ được biểu diễn như trong bảng 2.5.

S1, S2

Cá thể | Task

W1	W2
S1	L3	L8
S2	L5	L10

Vector độ chênh d được tính như sau:

d1 =mod(abs(p2,8 – p1,3)) = mod(abs(75-20)) = 55 d2 = mod(abs(p2,10 – p1,5)) = mod(abs(100-60)) = 40

Kết quả thu được vector độ chênh d có giá trị được biểu diễn trong bảng

2.6.

Bảng 2.6: Giá trị của vector độ chênh d

Task

W1	W2
d	55	40

Tính độ chênh giữa 2 cá thể được trình bày trong Algorithm 2.1.

Algorithm 2.1. Tính độ chênh giữa 2 cá thể

	Input: - S1,S2: 2 cá thể đầu vào - taskcount: số lượng tác vụ
	Output: vector độ chênh
1	Begin
2	d = {}
3	p = thang đo
4	for i=1 to taskcount
5	j = vị trí tài nguyên thực hiện task i của S1
6	k = vị trí tài nguyên thực hiện task i của S2
7	di = mod(abs(pi,j - pi,k),100)
8	end for
9	return d;
10	End

Phép cộng 02 cá thể - tạo cá thể mới

Phép cộng 02 cá thể tạo ra một cá thể mới, được thực hiện qua các bước như sau:

- Tính độ chênh giữa 02 cá thể

- Cộng thang đo của cá thể 1 với độ chênh

- Cá thể mới nhận được bằng việc tham chiếu kết quả vào thang đo để tìm tài nguyên thực hiện, được thực hiện theo công thức 2.4

Si = index (round(mod((di + pi,j),100)) ) (2.4)

Trong đó:

- i: chỉ số của tác vụ

- j: vị trí tài nguyên thực hiện tác vụ trong thang đo

- index: trả về chỉ số tài nguyên ở vị trí tương ứng trên thang đo Trong ví dụ 2.4 ở trên, xét S = S1 + S2, ta có:

S1 = index (round(mod(d1 + p1,3))) = index(round(75)) = 9

S2 = index (round(mod(d2 + p2,8))) = index(round(115)) = 6

Như vậy, ta được phương án mới S với W1 được thực hiện bởi L9, W2 được thực hiện bởi tài nguyên L6. Chi tiết được thể hiện trong bảng 2.7.

Bảng 2.7: Kết quả cộng hai cá thể

Task

W1	W2
d	55	40
p	20	75
S1 + p	75	115
S	9	6

Phép cộng 2 cá thể được trình bày trong Algorithm 2.2.

Algorithm 2.2. Cộng 2 cá thể để tạo cá thể mới

	Input: - S1,S2: hai cá thể đầu vào - taskcount: số lượng tác vụ
	Output: cá thể mới
1	Begin
2	S = {}
3	p = thang đo
4	d = độ chênh giữa S1 và S2
5	for i=1 to taskcount
6	Si = index (round(mod((di + p1,i),100)) )
7	end for
8	return S;
9	End

2.3. Đề xuất thuật toán M-PSO

Thuật toán tối ưu bầy đàn PSO là thuật toán tiến hóa trong đó mỗi cá thể được tạo ra dựa trên thừa kế kinh nghiệm của cả quần thể và của chính cá thể đó, do vậy nâng cao được khả năng hội tụ, nhanh tìm ra được nghiệm tốt.

Là thuật toán có tốc độ hội tụ nhanh nên PSO được giới nghiên cứu quan tâm và đề xuất nhiều phiên bản cải tiến, trong đó một phương pháp thông dụng là Tìm kiếm lân cận Local search PSO [CT2], [CT6]. Tuy nhiên phương pháp

Tìm kiếm lân cận đôi lúc khiến chương trình mắc kẹt tại bẫy cực trị địa phương. Mục tiếp theo sẽ đề xuất một phương pháp hiệu quả khác, phương pháp Di cư, cho phép thuật toán thoát khỏi vùng cực trị địa phương để tìm tới những vùng nghiệm mới có thể có các nghiệm tốt hơn.

Thuật toán M-PSO (Migration PSO) là thuật toán áp dụng cho bài toán MS- RCPSP nhằm cực tiểu hóa makespan, thuật toán được xây dựng dựa trên thuật toán tối ưu bầy đàn PSO và được cải tiến ở các điểm sau:

(i) Tìm và phát hiện cực trị địa phương;

(ii) Áp dụng kỹ thuật di cư (Migration) để thoát khỏi cực trị địa phương.

2.3.1. Kỹ thuật Di cư

Khi thực hiện tiến hóa, thuật toán PSO có xu hướng rơi vào các vùng cực trị địa phương nghĩa là sau nhiều thế hệ quần thể vẫn bị hút vào khu vực xung quanh một cực trị địa phương. Để hướng dẫn quần thể đi tới giá trị tối ưu, cần phải đưa chúng thoát ra khỏi vùng lân cận xung quanh cực trị địa phương để chuyển tới một vùng không gian nghiệm khác, đó là mục đích của kỹ thuật di cư trong luận án này. Ngoài việc giúp thuật toán thoát khỏi cực trị địa phương, kỹ thuật di cư còn mở rộng không gian tìm kiếm, nâng cao kết quả của thuật toán.

Định nghĩa 2.3:Quần thể được gọi là tiến hóa không thành công nếu giá trị makespan của quần thể không thay đổi qua 2 thế hệ liên tiếp.

2.3.1.1. Ý tưởng của kỹ thuật di cư

Kỹ thuật Di cư áp dụng trong thuật toán M-PSO được thực hiện qua các bước sau:

Bước 1: Tìm và phát hiện cực trị địa phương

Để phát hiện cực trị địa phương, ta dùng một biến nfail để đếm số lần quần

thể tiến hóa không thành công liên tiếp, nếu giá trị này lớn hơn một ngưỡng quy định (nmax), thì quần thể đã rơi vào cực trị địa phương. Công thức 2.5 trình bày cách tính nfail.

𝑛𝑓𝑎𝑖𝑙 =

𝑛𝑓𝑎𝑖𝑙 + 1 𝑖𝑓 𝑛𝑒𝑤𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 = 𝑜𝑙𝑑𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛

{ 0 𝑖𝑓 𝑛𝑒𝑤𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛 ≠ 𝑜𝑙𝑑𝑚𝑎𝑘𝑒𝑠𝑝𝑎𝑛

(2.5)

Bước 2: Di chuyển quần thể

Việc di chuyển quần thể sang vị trí khác được thực hiện như sau:

- Duyệt từng cá thể của quần thể;

- Với mỗi tác vụ i của cá thể, xem xét tập Li các tài nguyên có thể thực hiện được tác vụ i, sắp xếp các tài nguyên thứ tự tăng dần của chỉ số tài nguyên;

- Lấy tài nguyên ở vị trí đối xứng để thực hiện tác vụ i thay cho tài nguyên hiện tại.

Hình 2.4 minh họa việc di cư của tác vụ bằng việc thay đổi tài nguyên thực hiện. Cụ thể, tác vụ đang được thực hiện bởi tài nguyên L2 sẽ được bố trí tài nguyên thực hiện mới là Lm-1 và tác vụ đang được thực hiện bởi tài nguyên Lm sẽ được bố trí tài nguyên mới là L1 để thực hiện.

...

Lm-1

...

Lm-1

Hình 2.4. Thay đổi tài nguyên thực hiện tác vụ

Việc dịch chuyển tài nguyên thực hiện tác vụ cần đảm bảo ràng buộc của bài toán. Sau khi thực hiện với toàn bộ quần thể, ta sẽ được một quần thể mới được di chuyển bằng kỹ thuật Migration.

Ví dụ 2.2:

Xem xét một dự án với các thông tin như sau:

- Tập tác vụ W ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

- Tập tài nguyên L={1, 2, 3, 4};

- Năng lực của các tài nguyên được thể hiện như trong Bảng 2.8.

Bảng 2.8: Năng lực của các tài nguyên

W1	W2	W3	W4	W5	W6	W7	W8	W9	W10
L1	×	×		×		×		×	×
L2	×		×	×	×	×	×		×	×
L3	×	×	×		×	×		×		×
L4	×		×	×			×	×	×	×

Xem xét một phương án lịch biểu với các thiết lập tài nguyên thực hiện tác vụ như trong bảng 2.9.

Bảng 2.9: Lịch biểu khả thi của dự án trong ví dụ 2.2

Tác vụ

1	2	3	4	5	6	7	8	9	10
Tài nguyên	1	1	2	1	2	2	4	1	1	4

Xét tác vụ 1, tập tài nguyên thực hiện tác vụ 1, W1 = {L1, L2, L3, L4}

Áp dụng kỹ thuật di cư với tác vụ 1, ta thấy, tài nguyên thực hiện tác vụ 1 hiện tại là L1, dùng kỹ thuật di cư để thiết lập tài nguyên thực hiện tác vụ 1 bằng cách lấy tài nguyên đối xứng trong tập tài nguyên W1, ta có tài nguyên mới để thực hiện tác vụ 1 là L4.

Áp dụng tương tự với các tác vụ 2, 3, 4, 5, 6, 7, 8, 9, 10, ta sẽ được cá thể sau khi di cư với thiết lập tài nguyên thực hiện được thể hiện trong bảng 2.10.

Bảng 2.10: Lịch biểu mới sau khi di cư

Tác vụ

1	2	3	4	5	6	7	8	9	10
Tài nguyên	4	3	4	4	3	2	2	4	4	2

Ta có thể thấy, trong lịch biểu mới, tại vị trí của tác vụ 6, tài nguyên thực hiện không thay đổi do W6 = {L1,L2,L3}. Điều này hạn chế khả năng tạo ra các