Một giải thuật di truyền giải bài toán cắt vật tư một chiều với nhiều kích cỡ vật liệu thô

Phạm Thị Hoài Phương
_, Học Viện Công nghệ Bưu chính viến thông
January, 2012
Full text (external site)
 

Abstract

Nội dung chính của luận án là nghiên cứu xây dựng thuật toán hiệu quả 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ô, trong đó nguồn nguyên liệu là không bị giới hạn.

Cụ thể, luận án đạt được các kết quả mới sau:
1. Tiến hành phân tích mối liên quan ngữ nghĩa của 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ô với bài toán cắt trên một loại vật liệu thô. Từ đó, tác giả đưa ra một cách phát biểu mới của bài toán cắt vật tư với nhiều kích cỡ vật liệu thô.

2. Đề xuất lai ghép giải thuật di truyền với kỹ thuật phân nhánh và định giá theo mô hình Arc-Flow tạo nên thuật toán GA-AF giải hiệu quả 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ính đúng đắn của thuật toán được chứng minh bằng lý thuyết. Tính hiệu quả được kiểm chứng trên một số lượng tương đối lớn các bài toán mẫu.

3. Dựa trên thuật toán GA-AF, đề xuất cài đặt phân tán thuật toán dưới dạng một hệ đa tác tử di động GMAS-OneDCSP_M nhằm nâng cao hiệu quả tính toán. Tính đúng đắn của hệ thống được chứng minh. Tính hiệu quả của hệ thống được phân tích bằng toán học cũng như trong môi trường triển khai thực tiễn.


Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology