GMAS-1DMCSP: Hệ thống đa tác tử gen giải bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô

 37
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ Tập 48, số 6, 2010 Tr. 
GMAS-1DMCSP: HỆ THỐNG ĐA TÁC TỬ GEN GIẢI BÀI TOÁN 
CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚC 
VẬT LIỆU THÔ 
PHAN THỊ HOÀI PHƯƠNG, LƯƠNG CHI MAI 
1. GIỚI THIỆU 
Bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô (One-Dimensional Cutting 
Stock Problem with Multiple Stock Sizes) là bài toán tối ưu thuộc lớp bài toán NP-Hard. Trong 
thời gian gần đây đã có nhiều công trình đề cập tới các giải pháp cho bài toán này, trong đó có 
[1, 10, 11, 12, 13, 16, 18]. Do bài toán có độ phức tạp tính toán lớn nên việc tăng tốc độ tính 
toán cho các giải pháp mang một ý nghĩa quan trọng khi áp dụng vào thực tế. 
Bài báo này đề xuất xây dựng một hệ thống đa tác tử để nâng cao hiệu quả giải bài toán cắt 
vật tư với nhiều kích thước vật liệu thô trên cơ sở thuật toán GA-CG được công bố trong [1]. 
Với hệ thống này, một mặt các công việc tính toán của thuật toán GA-CG được song song hóa 
và phân chia cho các tác tử khác nhau đảm nhiệm. Điều đó cho phép giảm thiểu một cách đáng 
kể thời gian thực hiện thuật toán; Mặt khác các tác tử được phân bổ trên toàn bộ các tài nguyên 
tính toán có thể có của mạng cục bộ nên tận dụng được sức mạnh tính toán của tài nguyên và vì 
vậy thích hợp cho việc giải các bài toán thực tế có kích thước rất lớn. 
Hệ thống này được thiết kế theo kiến trúc A-Team trên nền tảng JADE (Java Agent 
DEvelopment Framework) – một phần mềm trung gian (middle-ware) nguồn mở hỗ trợ cho việc 
phát triển các hệ thống đa tác tử được cài đặt hoàn toàn bằng Java và tuân thủ chặt chẽ các đặc 
tả của FIPA (The Foundation of Intelligent Physical Agents). Phần còn lại của bài được cấu trúc 
như sau. Mục 2 dành cho việc phát biểu bài toán cắt vật tư một chiều mở rộng (nhiều loại vật 
liệu thô) và trình bầy tóm tắt các kết quả lí thuyết về mối liên quan ngữ nghĩa của bài toán mở 
rộng này với bài toán cắt vật tư một chiều kinh điển (một loại vật tư) làm cơ sở đề xuất thuật 
toán phân tán giải bài toán cắt vật tư mở rộng. Thiết kế và cài đặt của hệ thống đa tác tử giải bài 
toán cắt vật tư mở rộng trên nền tảng JADE dựa trên thuật toán đề xuất trong Mục 2 được trình 
bày trong Mục 3. Mục 4 đưa ra một số đánh giá hệ thống trong môi trường ứng dụng thực tế. 
Cuối cùng là một số kết luận của bài báo. 
2. BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚC VẬT TƯ VÀ 
THUẬT TOÁN GIẢI 
Bài toán cắt vật tư một chiều với một loại vật liệu thô (bài toán kinh điển) được xác định 
bởi các dữ liệu sau: ( ) ( )( )mm bbblllLm ,...,,,...,,, 11 == , trong đó L là bề rộng của tấm vật liệu thô, 
m là số dạng vật liệu thành phẩm được cắt từ vật liệu thô và đối với mỗi dạng vật liệu thành 
phẩm j, jl là bề rộng và jb là đơn hàng cho loại vật liệu thành phẩm đó. Bài toán đặt ra là tìm 
cách cắt sao cho số lượng tấm vật liệu thô sử dụng là ít nhất mà vẫn đáp ứng được đơn hàng. 
 38
Gilmore và Gomory [14, 15] lần đầu tiên đưa kĩ thuật tạo sinh cột (Column Generation) do 
Ford và Fulkerson đề xuất và sau đó được Dantzig và Wolfe hoàn thiện vào ứng dụng trong thực 
tế với việc giải bài toán cắt vật tư kinh điển này. Có thể tóm tắt phương pháp giải bài toán cắt vật 
tư một chiều của Gilmore và Gomory như sau. 
Một phương án cắt được biểu diễn bới một vectơ cột ( ) m
mjj
j Zaaa +∈= ,...,1 , j = 1,,n sẽ cho 
biết số lượng vật tư thành phẩm được cắt từ tấm vật liệu thô. Phương án cắt được chấp nhận nếu 
nó thỏa mãn điểu kiện: 
 ∑
=
≤
m
i
iji Lal
1
. (1) 
Giả sử njx j ,...,1, = là số lần phương án cắt chấp nhận được được sử dụng trong nghiệm. 
Mô hình của Gilmore và Gomory trở thành: 
 xxblLmDCSP
n
j
jG minmin),,,(1
1
== ∑
=
 (2) 
Trên miền ràng buộc: 
 j
n
j
jij bxa ≥∑
=1
 i=1,,m (3) 
 +∈ Zx j , j=1,,n (4) 
 Mô hình (1)-(4) là bài toán quy hoạch nguyên với số lượng biến n tăng theo hàm lũy 
thừa của m. Mô hình này có suy yếu liên tục mạnh với tính chất làm tròn nguyên cải biên 
(Modified Integer Round-Up Property – MIRUP). 
 Trên cơ sở đó, Gilmore và Gomory đề xuất cách tiếp cận giải bài toán (1)-(4) gồm 2 
bước: 1/ giải bài toán suy yếu liên tục của (1)-(4); 2/ Làm tròn số nghiệm tối ưu của bài toán suy 
yếu liên tục để nhận được nghiệm của bài toán (1)-(4). 
 Để giải bài toán suy yếu liên tục của (1)-(4) với số lượng biến n rất lớn, Gilmore và 
Gomory đề xuất sử dụng kĩ thuật tạo sinh cột (Column Generation) trong đó mỗi biến chỉ được 
sinh ra khi nó thực sự cần thiết cho việc cải thiện nghiệm tìm được trước đó. Sau khi thêm vào 
các biến bổ xung (slacks) ta có thể đưa bài toán (1)-(4) về dạng chuẩn: 
{ }nG ZxbAxxblLmDCSP +∈== ,:min),,,(1 (5) 
 Suy yếu liên tục của (5) nhận được bằng việc loại bỏ ràng buộc nguyên trên các biến và 
được gọi là bài toán chủ (Master Problem - MP) sẽ có dạng: 
 { }nLPG RxbAxxblLmDCSP +∈== ,:min),,,(1 
(6) 
Xuất phát, kĩ thuật tạo sinh cột sẽ làm việc với một tập con các cột của A được gọi là 
variable pool hoặc Restricted Master Problem (RMP). RMP có thể được khởi tạo dễ dàng, ví dụ 
bởi cơ sở kiến thiết ban đầu của phương pháp đơn hình. Giả sử 'A là các cột trong A được lựa 
chọn. Khi đó RMP có dạng: 
 { }nLPG RxbxAxblLmDCSP +∈== ,':min),,,(1 . (7) 
 39
Nhận xét rằng giá suy giảm của một biến ứng với phương án cắt chấp nhận được a trong 
(7) được xác định bởi công thức ua−1 , với mRu +∈ là các giá trị biến đối ngẫu tối ưu của (7). 
Do vậy nghiệm tối ưu của bài toán xác định giá (Pricing Problem): 
 { }mZaLalua +∈≤ ,:max (8) 
sẽ lần lượt được thêm vào RMP nếu nếu giá trị tối ưu của (8) lớn hơn 1. Nếu (8) không có 
nghiệm tối ưu như vậy thì nghiệm tối ưu của bài toán RMP (7) chính là nghiệm tối ưu của bài 
toán MP (6). 
Sau khi đã giải được bài toán ),,,(1 blLmDCSPLPG , bước tiếp theo trong cách tiếp cận của 
Gilmore và Gomory là việc thực hiện thủ tục làn tròn số để nhận được nghiệm nguyên cho bài 
toán ),,,(1 blLmDCSPG . Nhiều tác giả đã đưa ra các heuristics khác nhau để giải quyết vấn đề 
này. Một số thủ tục có thể tra cứu trong [10, 17]. 
Việc mở rộng bài toán cắt vật tư một chiều kinh điển trong trường hợp có nhiều kích thước 
vật liệu thô đã được một số tác giả đề cập đến [1, 10, 11, 12, 13, 16, 18]. Các tác giả đều thống 
nhất rằng việc xây dựng giải thuật heuristic cho bài toán là cần thiết vì các cách tiếp cận chính 
xác là không phù hợp trong trường hợp này. 
Sau đây chúng ta sẽ trình bày tóm tắt một đề xuất lai ghép giữa thuật toán gen với phương 
pháp của Gilmore và Gomory để giải lớp bài toán cắt vật tư một chiều với nhiều kích thước vật 
liệu thô đã được công bố trong [1]. 
Bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô (One-Dimensional Cutting 
Stock Problem with Multiple Stock Sizes – 1DMCSP) là mở rộng tự nhiên của bài toán 1DCSP 
trong đó các tấm vật liệu thô có thể có kích thước khác nhau. Bài toán 1DMCSP có thể được đặc 
trưng bằng các dữ liệu sau: 
 ( ) ( ) ( ) ( )( )MMmm cccLLLbbblllMm ,...,,,...,,,...,,,...,,, 1111 ==== (9) 
trong đó m, l và b mang ý nghĩa như trong bài toán 1DCSP; M là số các loại vật liệu thô sẽ được 
sử dụng và tham số L trong 1DCSP được thay thế bởi vectơ ( )MLLL ,...,1= , với iL là bề rộng 
và ic là giá của vật liệu thô thứ i, i = 1,,M. Trong bài này ta giả thiết rằng giá của vật liệu thô 
tỉ lệ thuận với bề rộng của vật liệu. 
Mô hình của bài toán trên (Machine Balance Model) được Gilmore và Gomory xây dựng 
trong [15]. Mô hình có thể được phát biểu như sau: 
 Đặt Mmm +=' . Một vectơ ( ) '
'1,...,
m
m Zaaa +∈= là biểu diễn của một phương án cắt 
nếu 
 mi
M
i
i
m
i
ii aLal +
==
∑∑ ≤
11
 và 1
1
=∑
=
+
M
i
mia (10) 
Các thành phần ia , i=1,,m, xác định có bao nhiêu vật tư thành phẩm loại i được cắt. 
Thành phần mka + sẽ bằng 1 nếu loại vật liệu thô thứ k được sử dụng còn các thành phần mia + 
với { } kMi \,...,1∈ bằng 0. 
Giả sử ia , i=1,,n, là tất cả các phương án cắt và mỗi thành phần ix của vectơ 
( )nxxx ,...,1= là số lần sử dụng phương án cắt ia . Nhận xét rằng n có thể rất lớn. Ta xây dựng 
 40
một vectơ n chiều 'c từ c theo cách sau. Nếu phương án cắt ia được thực hiện trên tấm thép loại 
k thì ki cc =
'
, i=1,,n và k=1,,M. Khi đó ta có mô hình: 
 ( ) xccLblMmDMCSP 'min,,,,,1 = (11) 
Trên miền ràng buộc: 
 ji
n
i
ij bxa ≥∑
=1
, j=1,,m (12) 
 )(
11
mji
M
j
j
m
j
ijj aLal +
==
∑∑ ≤ (13) 
 1
1
)( =∑
=
+
M
j
mjia (14) 
nZx +∈ (15) 
'm
i Za +∈ i=1,,n (16) 
Từ các phát biểu (1)-(4) và (11)-(16) ta có mối liên hệ giữa hai bài toán như sau: 
Định lí 1. [1] ),,,,,(1 cLblMmDMCSP ≤ 1 ( , , , )G kDCSP m L l b với mọi { }1,...,k M∈ . Nói 
cách khác, bài toán cắt vật tư với nhiều kích thước vật liệu thô sẽ tốt hơn việc cắt chỉ trên một 
loại vật liệu. 
Định lí 1 khẳng định ý nghĩa của việc xây dựng các giải pháp cho bài toán cắt vật tư với 
nhiều kích thước vật liệu thô. 
 Giả sử x* là nghiệm tối ưu của (11)-(16). Ta ký hiệu: 
- )(kΩ , k=1,,M, là tập tất cả các phương án cắt trên vật liệu thô thứ k được sử dụng 
trong (11)-(16) tương ứng x* ; 
- )(/* kx Ω là thu hẹp của x* trên )(kΩ ; 
- 
kb là vectơ vật tư thành phẩm nhận được từ (11)-(16) với việc sử dụng số lần cắt theo 
các phương án cắt trong )(kΩ được xác định bằng các thành phần tương ứng của )(/* kx Ω . 
Định lí 2. [1] Nếu x* là nghiệm tối ưu của bài toán ),,,,,(1 cLblMmDMCSP (11)-(16) thì 
)(/* kx Ω là nghiệm tối ưu của bài toán ),,,(1 kkG blLmDCSP (1)-(4), k = 1,,M. 
Trên cơ sở của Định lí 2, chúng ta có thể mô hình hóa bài toán 1DMCSP dưới dạng phát 
biểu mới như sau. 
 k
k
k
M
k
G cblLmDCSPcLblMmDMCSP ),,,(1min),,,,,(1
1
∑
=
= . (17) 
 41
Trên miền ràng buộc: 
 bb
M
k
k ≥∑
=1
 (18) 
mk Zb +∈ . (19) 
Định lí 3. [1] Nghiệm tối ưu của bài toán (17) - (19) sẽ xác định trên tập các vectơ kb thỏa 
mãn bb
M
k
k
=∑
=1
. Tập các vectơ kb như vậy được gọi là phân hoạch của b. Nói cách khác 
nghiệm tối ưu của (17) - (19) được xác định trên tập các phân hoạch của vectơ b. 
Các định lí 2, 3 và phát biểu mới của bài toán 1DMCSP trong (17) - (19) gợi cho chúng ta ý 
tưởng phân rã bài toán 1DMCSP thành các bài toán cơ sở là bài toán ),,,(1 kkG blLmDCSP để 
có thể áp dụng được phương pháp giải sử dụng kĩ thuật tạo sinh cột của Gilmore và Gomory. 
Các nghiệm tối ưu của từng bài toán cơ sở sẽ được kết hợp lại để tạo nên nghiệm chấp nhận 
được của bài toán 1DMCSP. Việc tìm nghiệm tối ưu cho bài toán 1DMCSP sẽ do thuật toán gen 
đảm nhiệm với không gian tìm kiếm là tập các phân hoạch của vectơ đơn hàng. 
Sau đây chúng ta sẽ lần lượt hình thức hóa ý tưởng đó trên ngôn ngữ của thuật toán gen và 
kĩ thuật tạo sinh cột. 
Biểu diễn bài toán. Chúng ta sử dụng nhiễn sắc thể có cấu trúc ( )Mbb ,...,1 , mk Zb +∈ để biểu 
diễn các cá thể (các điểm) trong không gian tìm kiếm. Mỗi quần thể là một tập bao gồm một số 
cố định các cá thể. 
 Độ đo thích nghi. Với mỗi cá thể ( )Mbbs ,...,1= ta xác định mức độ thích nghi của cá 
thể, )(sf , bằng công thức sau: 
∑
=
= M
k
k
k
kG cblLmDCSP
sf
1
),,,(1
1)( (20) 
Toán tử hôn phối. Giả sử ( )Mbbs 1111 ,...,= và ( )Mbbs 2122 ,...,= là 2 cá thể bất kì, k là một số 
được lựa chọn ngẫu nhiên, mk ≤<1 . Từ hai cá thể trên ta tạo ra hai hậu duệ '1s và '2s với các 
vectơ cột tương ứng của chúng được xác định như sau: 
 [ ] [ ] ;1,...,1,1'1 −== kiibib jj [ ] [ ] mkiibib jj ,...,,2'1 == ; j=1,,M (21) 
 [ ] [ ] 1,...,1,2'2 −== kiibib jj ; [ ] [ ] ;,...,,1'2 mkiibib jj == j=1,,M (22) 
Toán tử đột biến. Chọn ngẫn nhiên một bộ 3 các số nguyên (p,q,r), Mqp ≤≤ ,1 và 
mr ≤≤1 , với xác suất: 
 20
1
mMp = . (23) 
Toán tử đột biến tác động lên cá thể ( )Mbbs ,...,1= để tạo nên cá thể ( )Mbbs 1111 ,...,= với 
bộ (p,q,r) đã chọn như sau: 
 42
ii bb =1 khi qipi ≠≠ & i=1,,M (24) 
 [ ] [ ]jbjb pp =1 , [ ] [ ]jbjb qq =1 khi j=1,,m và rj ≠ (25) 
 [ ] [ ] 11 −= rbrb pp , [ ] [ ] 11 += rbrb qq nếu [ ] 0>rb p (26) 
 [ ] [ ]rbrb pp =1 , [ ] [ ]rbrb qq =1 nếu [ ] 0=rb p (27) 
Toán tử chọn lọc. Toán tử chọn lọc được xác định theo luật tỉ lệ thuận với mức độ thích nghi: 
∑
∈
=
Gs
s
sf
sfp )(
)(
 (28) 
trong đó s là cá thể và G là quần thể đang xem xét có chứa s. 
Định lí 4. [1] Giả sử hai cá thể cha-mẹ là các phân hoạch của cùng một vectơ. Khi đó các toán 
tử hôn phối và toán tử đột biến xác định như trên sẽ bảo đảm các hậu duệ cũng là những phân 
hoạch của vectơ đó. 
Dựa trên các Định lí 1,2,3,4 chúng ta có thể xây dựng thuật toán lai ghép như sau: 
Thuật toán GA-CG 
Input: m, M , l, L, b, c 
Output: Nghiệm tối ưu của bài toán ),,,,,(1 cLblMmDMCSP và các phương án cắt 
tương ứng với nghiệm tối ưu đó 
Step 0. Khởi tạo quần thể gồn K cá thể { }0010 ,..., KssG = . Việc khởi tạo này có thể thực hiện 
dễ dàng bằng việc tạo ra K phân hoạch khác nhau của b, mỗi phân hoạch sẽ tương ứng với một 
đối tượng của quần thể. Các cá thể được biểu diễn như sau: 
 ( )0010 ,..., iMii bbs = , mij Zb +∈0 , ∑
=
=
M
j
ij bb
1
0
, i=1,,K 
Step 1. Giải các bài toán ),,,(1 tikkG blLmDCSP bằng phương pháp tạo sinh cột , i=1,,K, 
k=1,,M, t là thứ tự bước lặp (thứ tự của quần thể). Tính mức độ thích nghi )( tisf cho từng cá 
thể của tG theo (20). 
Step 2. Lựa chọn các cha-mẹ trong tG theo mức độ thích nghi để ghép cặp theo toán tử 
hôn phối (21)-(22) để tạo nên tập các hậu thế 'tG với 1K phần tử 
Step 3. Tác động toán tử đột biến (24)-(27) vào 'tt GG ∪ để nhận được ''tG . 
Step 4. Thực hiện tính toán giống như trong Step1 cho các cá thể của ''tG . 
Step 5. Áp dụng toán tử chọn lọc (28) lên ''tt GG ∪ để chọn ra K cá thể có mức độ thích 
nghi lớn nhất tạo quần thể mới 1+tG . 
 43
Step 6. Nếu điều kiện dừng chưa thỏa mãn quay lại Step 2. Ngược lai thuật toán dừng và 
cho nghiệm tối ưu cùng tập các phương án cắt tương ứng với nghiệm tối ưu. 
Định lí 5. [1] Thuật toán GA-CG đạt được nghiệm tối ưu toàn cục trong khoảng thời gian hữu 
hạn với xác suất 1 không phụ thuộc vào quần thể khởi đầu. 
Các kết quả lí thuyết trong mục này sẽ được dùng làm cơ sở cho việc xây dựng hệ thống đa 
tác tử với tên gọi GMAS-1DMCSP được trình bày trong mục tiếp theo. 
3. HỆ THỐNG GMAS-1DMCSP 
Các Định lí 2 và 3 phản ánh mối quan hệ ngữ nghĩa giữa bài toán 
),,,,,(1 cLblMmDMCSP và bài toán ),,,(1 kkG blLmDCSP . Việc giải bài toán 
),,,,,(1 cLblMmDMCSP theo thuật toán GA-CG chính là việc áp dụng thuật toán gen trên 
không gian tìm kiếm được tạo thành từ các tổ hợp nghiệm của các bài toán 
),,,(1 kkG blLmDCSP với các kb thỏa mãn ràng buộc bb
M
k
k
=∑
=1
. Từ quan sát này, chúng ta có 
thể xây dựng một hệ thống đa tác tử theo mô hình A-Team để giải bài toán 
),,,,,(1 cLblMmDMCSP với hai kiểu tác tử chính. Kiểu tác tử đầu tiên thực hiện thuật toán 
GA-CG và đóng vai trò khởi tạo, quản lí, lựa chọn nghiệm của bài toán 
),,,,,(1 cLblMmDMCSP trên cơ sở nghiệm của các bài toán thành phần 
),,,(1 kkG blLmDCSP . Kiểu tác tử thứ hai nhận nhiệm vụ giải bài toán ),,,(1 kkG blLmDCSP 
bằng kĩ thuật tạo sinh cột. Ngoài ra hệ thống cũng bao gồm một số tác tử đặc biệt cung cấp các 
dịnh vụ khác như quản lí tài nguyên, quản lí và báo cáo công việc... Các tác tử hoạt động phân 
tán, song song, không đồng bộ và có thể di trú một cách linh hoạt phụ thuộc vào tài nguyên được 
cấp phát. Hệ thống được cài đặt trên nền tảng JADE – một phần mềm nguồn mở hỗ trợ thiết kế 
và khai thác các hệ thống đa tác tử thà ... chỉ có tác dụng tăng cường hiệu quả 
 50
của hệ thống trong việc quản lí tài nguyên và cho phép hệ thống có khả năng giải quyết đồng 
thời nhiều bài toán cắt vật tư khác nhau. 
- Các tác tử 1DCSP-Solver thực hiện việc giải các bài toán ),,,(1 kkG blLmDCSP nằm trong 
Step 1 và Step 4 của thuật toán GA-CG 
- Các tác tử 1DMCSP-Solver thực hiện các Step 0, Step 2, Step 3, Step 5 và Step 6 của thuật 
toán GA-CG. 
- Nhờ cấu trúc miền bộ nhớ chung giành cho từng bài, sự phối hợp của hai loại tác tử được 
ghi nhận bởi việc cập các biến trạng thái tuân theo đúng logic tính toán của thuật toán GA-CG. 
- Trong trường hợp có sự cố xảy ra, hệ thống có khả năng khôi phục lại trạng thái của bài 
toán từ thời điểm cuối cùng khi TaskManager thành công trong việc chuyển đổi dữ liệu của bộ 
nhớ chung thành định dạng XML và ghi vào thiết bị ngọai vi. Các tác tử sẽ thực hiện công việc 
tiếp tục từ thời điểm này. 
Từ đó, tính đúng đắn của hệ thống trong việc giải quyết từng bài toán đơn lẻ được suy ra 
trực tiếp từ Đinh lí 5. Điều này cũng khẳng định tính đúng đắn của toàn bộ hệ thống khi giải 
quyết đồng thời nhiều bài toán nhờ sự phối hợp của các tác tử TaskManager và ResouceManager 
với cấu trúc miền nhớ dành cho từng bài toán. 
1DMCSP_Solv er
create the population of solutions
read data and paramenters
TaskManager
print the result
>
read instance data
manage the population of solutions
>
1DCSP_Solv er
solv e
>
ResourceManager
create agents
Hình 4. Hoạt động của các tác tử trong hệ thống 
System 
 51
4. ĐÁNH GIÁ HỆ THỐNG TRONG THỰC TẾ 
Mối liên hệ ngữ nghĩa của bài toán cắt vật tư 1 chiều cho nhiều loại vật tư với bài toán cắt 
vật tư 1 chiều cho một loại vật tư được thể hiện trong các Định lí 1,2,3 là nền tảng lí thuyết cho 
việc song song và phân tán hóa thuật toán GA-CG để tăng tính hiệu quả về thời gian của thuật 
toán. Trong thực tế cài đăt, nhóm tác giả đã cài đặt thuật toán dưới dạng một hệ thống đa tác tử 
(Multi-agent System) GMAS-1DMCSP. Hệ thống gồm 2 lớp tác tử chính. Lớp trên gồm 1 agent 
thực hiện thuật toán gen có nhiệm vụ lập kế hoạch (tạo ra các phân hoạch của vectơ kế hoạch), 
điều phối các agent ở lớp dưới và đồng bộ hóa kết quả (tính độ đo thích nghi, thực hiện các toán 
tử gen). Lớp dưới gồm các agent thuần nhất (các agent đều cùng thực hiện thuật toán tạo sinh 
cột để giải bài toán cắt vật tư 1 chiều cho 1 loại vật liệu thô). Các agent của lớp dưới là các agent 
di động (Mobile agent) được agent lớp trên tạo sinh khi có nhu cầu và có thể khu trú tại những 
node tính toán bất kì trên mạng cục bộ có đủ tài nguyên. Đây cũng là điều vượt trội của thuật 
toán của chúng tôi so với các thuật toán mà các tác giả khác đề xuất. Việc cài đặt như vậy đã tận 
dụng được sức mạnh tính toán của mạng LAN và góp phần giảm đáng kể thời gian giải bài toán. 
Nếu bỏ qua vấn đề truyền thông trong mạng LAN, sự cải thiện về tốc độ tính toán của hệ thống 
GMAS-1DMCSP so với phiên bản cài đặt tập trung của thuật toán GA-CG được thể hiện bởi 
những ước lượng sau 
Gọi thời gian tính toán tối đa để giải bài toán1 ( , , , )GDCSP m L l b bằng phương pháp tạo 
sinh cột là GT . Tại mỗi vòng lặp của thuật toán GA-CG, chúng ta cần giải M bài toán 
),,,(1 kkG blLmDCSP với M là số lượng các loại kích thước vật liệu thô. Như vậy nếu thuật toán 
đáp ứng được điều kiện dừng sau N bước lặp, ước lượng thời gian tính toán của GA-CG sẽ là 
 GN M T× × . (29) 
Giả sử số lượng các tác tử 1DCSP-Solver có thể được tạo ra trong hệ thống GMAS-
1DMCSP là K. Khi đó trong mỗi vòng lặp của 1DMCSP-Solver, M bài toán 
),,,(1 kkG blLmDCSP sẽ được K tác tử 1DCSP-Solver chia nhau giải một cách độc lập bằng 
phương pháp tạo sinh cột. Như vậy thời gian đòi hỏi của mỗi vòng lặp trong 1DMCSP-Solver có 
thể xấp xỉ bởi công thức : 
 G
M T
K
 
×  
. 
Nhận xét rằng để bảo đảm thỏa mãn điều kiện dừng, tác tử 1DMCSP-Solver của hệ thống 
GMAS-1DMCSP cũng có số bước lặp đúng như số bước lặp của GA-CG. Như vậy thời gian để 
đòi hởi của hệ thống để giải bài toán xấp xỉ là : 
 G
MN T
K
 
× ×  
. 
Trong thực tế triển khai tại nhà máy ống thép Việt-Đức thì số lượng các loại kích thước vật 
liệu thô M thường ít hơn 20 và mạng LAN của nhà máy được bố trí tập trung tại tòa nhà điều 
hành với 15 node mạng. Mỗi node mạng được phân phối một container và được liên kết theo 
kiến trúc của JADE. Số lượng các tác tử 1DCSP-Solver trong mỗi container phụ thuộc cấu hình 
của node và trên thực tế triển khai chúng tôi có thể tạo ra một số lượng khá lớn. Bởi vậy số 
lượng K các tác tử 1DCSP-Solver trên hệ thống lớn hơn M nhiều lần. Do đó: 
 52
 G G
MN T N T
K
 
× × = ×  
 . (30) 
So sánh (29) với (30), ta thấy hệ thống GMAS-1DMCSP có thể nhanh gấp M lần so với 
phiên bản tập trung của GA-CG. Các ghi nhận thực tế cũng cho thấy việc truyền thông của hệ 
thống trên mạng LAN làm tăng không quá 2% thời gian ước lượng trong (30). Điều này cho thấy 
khi M càng lớn thì GMAS-1DMCSP càng thể hiện tính ưu việt so với GA-CG. 
 Hệ thống này đã được triển khai phục vụ sản xuất tại nhà máy ống thép Việt-Đức trong 4 
năm qua. Kết quả cho thấy trên thực tế chưa gặp một đợt sản xuất nào có lượng phế thải lớn hơn 
3% bề rộng của tấm vật tư có kích thước lớn nhất. Điều đó chỉ ra rằng thuật toán GA-CG được 
thiết kế như trên có tính chất tương tự như tính chất IRUP bằng chính các thẩm định thực tế, 
điều mà các tác giả khác không đề cập tới. 
5. KẾT LUẬN 
Bài báo trình bày tóm tắt việc thiết kế và cài đặt một hệ thống đa tác tử di động nhằm nâng 
cao hiệu quả việc giải các bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô trên cơ 
sở các kết quả phân tích lí thuyết của bài toán và thuật toán được trình bày trong [1]. 
Hệ thống được xây dựng theo kiến trúc A-team và được triển khai trên nền tảng JADE 
bằng ngôn ngữ Java. 
Tính đúng đắn của hệ thống được chứng minh chặt trẽ bằng Định lí 6 phát biểu trong Mục 
3 của bài này. 
Hệ thống đã được triển khai và khai thác hiệu quả tại nhà máy ống thép Việt-Đức [1]. 
TAI LIệU THAM KHảO 
1. Phan Thị Hoài Phương, Lương Chi Mai, Nguyễn Văn Hùng - Một thuật toán lai ghép giải 
bài toán cắt vật tư một chiều với nhiều kích thước vật liệu thô, Tạp chí Tin học và Điều 
khiển học 25 (3) (2009) 214-230. 
2. D. D. Corkill - Blackboard systems. AI Expert 6 (9) (1991) 40-47. 
3. R. S. Engelmore and A. Morgan (Ed.) - Blackboard Systems, Addison-Wesley, 1988. 
4. V. Jagannathan, R. Dodhiawala, and L. S. Baum (Ed.) - Blackboard Architectures and 
Applications, Academic Press, 1989. 
5. A. Kazemi and M.H. Fazel Zarandi - An Agent-Based Framework for Building Decision 
Support System in Supply Chain Management, Journal of Applied Sciences 8 (7) (2008) 
1125-1137. 
6. Dariusz Barbucha and Piotr Je¸drzejowicz - An Agent-Based Approach to Vehicle 
Routing Problem, World Academy of Science, Engineering and Technology 26 2007 
7. C. Chira, C.-M. Pintea, D. Dumitrescu - An Agent-Based Approach to Combinatorial 
Optimization, Int. J. of Computers, Communications & Control III (2008), Suppl. issue: 
Proceedings of ICCCC 2008. pp. 212-217. 
8. S. Talukdar - Asynchronous Teams, Proceedings of The 4th International Symposium on 
Expert Systems Applications to Power Systems, LaTrobe University, Melbourne, 
Australia, 1993. 
 53
9. S. Talukdar et all. - Asynchronous Teams: Co-operation Schemas for autonomous, 
Computer-Based agents, Technical Report EDRC 18-59-96, Engineering Design Research 
Center, Carnegie Mellon University, 1996. 
10. G. Belov and G. Scheithauer - A cutting plane algorithm for the one-dimensional cutting 
stock problem with multiple stock lengths, European Journal of Operational Research, 
Special issue on cutting and packing 141 (2) (2002) 274-294. 
11. G. Belov and G. Scheithauer - A branch-and-cut-and-price algorithm for one-dimensional 
stock cutting and two-dimensional two-stage cutting, Technical report, Dresden 
University, 2003, URL: www.math.tu-dresden.de/˜capad. 
12. G. Belov and G. Scheithauer - Setup and open stacks minimization in one-dimensional 
stock cutting, Technical report, Dresden University, 2003. 
13. Gleb Belov - Problems, Models and Algorithms in One- and Two-Dimensional Cutting, 
Dissertation. TU Dresden, 2004. 
14. Gilmore P. C., R. E. Gomory - A linear programming approach to the cutting-stock 
problem, Oper. Res. 9 (1961) 849–859. 
15. Gilmore P. C., R. E. Gomory - A linear programming approach to the cutting stock 
problem, Part II. Oper. Res. 11 (1963) 863–888. 
16. J. Rietz and S. Dempe - Large Gaps in One-dimensional Cutting Stock Problems. Discrete 
Applied Mathematics 156 (10) (2008). 
17. Sirinat Wongprakornkul - Round Down Technique for Solving an Integer Linear 
Programming, KKU Science Journal 36 (2008) 187-198 
18. O. Holthaus - Decomposition approaches for solving the integer one dimensional cutting 
stock problem with different types of standard lengths, European Journal of Operational 
Research 141 (2002) 295-312. 
19. Piotr Jędrzejowicz and Izabela Wierzbowska - JADE-Based A-Team Environment, 
Lecture Notes in Computer Science 3993 (2006) 719-726. 
20. Gawinecki Maciej, Frackowiak Grzegorz - Multi-Agent Systems with JADE: A Guide 
with Extensive Study. Distributed Systems Online, IEEE 9 (3) (2008). 
21. Charles V. Trappey et all. - The design of a JADE-based autonomous workflow 
management system for collaborative SoC design, Expert Systems with Applications 36 
(2009) 2659–2669. 
22. Fabio Bellifemine et all. - JADE: A software framework for developing multi-agent 
applications. Lessons learned, Information and Software Technology 50 (2008) 10-21. 
23. F. Bellifemine, G. Caire, D. Greenwood - Developing multi-agent systems with JADE, 
Wiley Series in Agent Technology, ISBN 978-0-470-05747-6, February 2007. 
 54
PHỤ LỤC 
Giả mã Đặc tả chức năng của các loại tác tử 
A. Giả mã đặc tả chức năng của tác tử TaskManager 
Start; 
Receive “Resource information from User”; 
Create ResourceManager; 
Send “Resource information” to ResourceManager; 
Wait for “success platform preparation respond” from ResourceManager; 
If (respond=failure) Then 
 { 
 Inform user about the failure; 
 Stop 
 }; 
Confirm “New batch?”; 
If (New Batch=”Esc”) 
 Then 
 { 
 Receive “link to immediate results of old batch”; 
 Download « immediate results of old batch to common memory » ; 
 Create 1DMCSP-Solvers corresponding to the unsolved problems 
 } 
 Else 
 Receive « link to new batch » ; 
Set Timer(600s); 
While “unsolved problem is available in the folder” 
 Do 
 { 
 Send Request “to allocate common memory space for new problem” to 
ResourceManager; 
 Wait for “success allocation respond” from Resource Manager; 
 If (respond=failure) 
 Then 
 While “the common memory is not empty” 
 Do 
 55
 { 
 Repeat 
 Look for “solved problem in the common memory” 
 Until “solved problem found”; 
 Print “The result of the solved problem”; 
 Send Request “to free the common memory space for the 
solved problem” to ResourceManager 
 } 
 Else 
 { 
 Create 1DMCSP-Solver for New problem ; 
 Move New problem from the folder 
 } ; 
 If (Timer expire or KeyboardHook= « Shift » ) 
 Then 
 { 
 Store « common memory content in secondary memory » ; 
 Set Timer(600s) 
 } ; 
 If (KeyboardHook= « Ctrl ») 
 Then 
 { 
 Receive « New Resource information from user » ; 
 Send request « To instruct the agents to move to new locations » to 
ResourceManager 
 } 
 } ; 
While (“the common memory is not empty”) 
 Do 
 { 
 Repeat 
 Look for “solved problem in common memory” 
 Until “solved problem found”; 
 Print “The result of the solved problem” 
 }; 
Send Request “Stop Request” to ResourceManager; 
Stop 
 56
B. Giả mã đặc tả chức năng của tác tử ResourceManager 
Start; 
Wait for “Resource information” from TaskManager; 
Create platform and common memory; 
Send Respond “Status of creating Platform and common memory” to TaskManager; 
If (Status=failure) Then Stop; 
Create 1DCSP-Solvers ; 
While (True) 
 Do 
 { 
 Wait for Request from TaskManager; 
 If (Request=“to allocate common memory space for new problem”) 
 Then 
 { 
 Check « fee space in common memory » ; 
 If (« free space is enouth for new problem ») 
 Then 
 Send Respond “success allocation respond” to TaskManager 
 Else 
 Send Respond “failure allocation respond” to TaskManager; 
 } ; 
 If (Request=“to free the common memory space for the solved problem”) 
 Then 
 { 
 Update “common memory management data”; 
 Remove 1DMCSP-Solvers corresponding to the solved problem from 
platform 
 }; 
 If (Request=« Instruct the agents to move to new locations ») 
 Then 
 Reallocate « 1DMCSP-Solvers and 1DCSP-Solvers to new resources » ; 
 If (Request=”Stop Request”) 
 Then Stop 
 }; 
 57
C. Giả mã đặc tả chức năng của tác tử 1DMCSP-Solver 
Start ; 
Initiate « first feasible solution population in FS» ; 
While (« Stop conditions are not satisfied ») 
 Do 
 { 
 While (some feasible solution’s Status Variable in FS and Offspring is not equal 
to F) 
 Do 
 { 
 Check all Status variables of its 1DCSP subproblems ; 
 If (all Status Variables of its 1DCSP subproblems are F) 
 Then 
 Set feasible solution’s Status Variable=F 
 } ; 
 If (Offspring is empty) 
 Then 
 { 
 Perform operations in Step 2, Step 3 and of GA-CG ; 
 Store Results in Offspring ; 
 While (some feasible solution’s Status Variable in Offspring is not 
equal to F) 
 Do 
 { 
 Check all Status variables of its 1DCSP subproblems ; 
 If (all Status Variables of its 1DCSP subproblems are F) 
 Then 
 Set feasible solution’s Status Variable=F ; 
 } ; 
 Perform Step 4 of GA-CG 
 } 
 Else 
 { 
 Peform Step 5 of GA-CG ; 
 Erase Offspring 
 } 
 } ; 
Set Problem’s Status Variable=F ; 
Stop 
 58
D. Giả mã đặc tả chức năng của tác tử 1DCSP-Solver 
Start ; 
While (TRUE) 
 Do 
 { 
 Find « Unsolved 1DCSP subproblem in common memory » ; 
 If (« Unsolved 1DCSP subproblem found ») 
 Then 
 { 
 Set 1DCSP subproblem’s Status Variable=P ; 
 Perform Step 1 of GA-CG with unsolved 1DCSP subproblem ; 
 Store Results in common memory ; 
 Set 1DCSP subproblem’s Status Variable=F 
 } 
 } 
SUMMARY 
GMAS-1DMCSP: GENETIC MULTI-AGENT SYSTEM FOR SOLVING 
ONE-DIMENSIONAL CUTTING STOCK PROBLEM WITH MULTIPLE STOCK SIZES 
Multi-agent systems (MASs) as an emerging sub-field of artificial intelligence concern 
with interaction of agents to solve a common problem. This paradigm has become more and 
more important in many aspects of computer science by introducing the issues of distributed 
intelligence and interaction. They represent a new way of analyzing, designing, and 
implementing complex software systems. This paper introduces a JADE-Based distributed 
Multi-agents system for solving One-Dimensional Cutting Stock Problem with Multiple Stock 
Sizes on the basis of the theoretical results presented in [1]. The system has effectively been 
operating in the industrial environment. 
Địa chỉ: Nhận bài ngày 25 tháng 7 năm 2009 
Phan Thị Hoài Phương, 
Học viện Công nghệ Bưu chính viễn thông. 
Lương Chi Mai, 
Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Việt Nam.