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