Đồ Án Luận Án TS Toán học: 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

VIỆN CÔNG NGHỆ THÔNG TIN
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Hà Nội – 2011

MỤC LỤC (Luận án dài 92 trang)

MỞ ĐẦU 1

Chương 1. CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN . 9

1.1. Bài toán cắt vật tư một chiều với một loại vật liệu thô và thuật giải 9
1.1.1. Mô hình Gilmore-Gomory . 10
1.1.2. Mô hình Arc-flow của Valerio de Carvalho 13
1.2. Giải thuật di truyền 19
1.3. Kết luận . 25

Chương 2. 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Ô: MÔ HÌNH VÀ GIẢI PHÁP . 26
2.1. Phát biể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ô theo
Gilmore và Gomory 26
2.2. Phát biểu mới của bài toán OneDCSP_M . 28
2.3. Giải thuật di truyền lai ghép giải bài toán OneDCSP_M 32
2.4. Kết quả tính toán . 40
2.5. Kết luận . 50

Chương 3. HỆ THỐNG ĐA TÁC TỬ GMAS -OneDCSP_M GIẢI BÀI TOÁN
OneDCSP_M . 52

3.1. Yêu cầu của hệ thống GMAS -OneDCSP_M 54
3.2. Thiết kế hệ thống GMAS-OneDCSP_M . 55
3.2.1. Kiến trúc hệ thống GMAS-OneDCSP_M . 55
3.2.2. Thiết kế chi tiết hệ thống GMAS-OneDCSP_M . 58
3.3. Đánh giá tính hiệu quả của hệ thống GMAS-OneDCSP_M . 65
3.4. Kết luận . 67

KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO 68
DANH MỤC CÁC CÔNG TRÌNH CỦA TÁC GIẢ . 70
TÀI LIỆU THAM KHẢO 71
PHỤ LỤC . 78



DANH MỤC CÁC BẢNG BIỂU

Bảng 2.1 Tổng kết chất lượng nghiệm so với kết quả của Belov -Scheithauer 44
Bảng 2.2 Kết quả tính toán của Silvio A. Araujo và đồng sự 45
Bảng 2.3 Phân bố độ chênh lệch nghiệm so với kết quả của Belov -Scheithauer 46
Bảng 2.4 Thống kê thời gian tính toán . 48
Bảng 2.5 Thống kê phân bố thời gian tính toán . 49



DANH MỤC CÁC HÌNH VẼ

Hình 0.1 Sơ đồ các cách tiếp cận giải bài toán cắt vật tư một chiều . 6
Hình 1-1 Các phương án cắt trong bài toán OneDCSP_S . 10
Hình 1-2 Ví dụ về mạng lưới và phương án cắt với L=9 và các li Î{4,3,2} . 13
Hình 1-3 Một thế hệ mới được hình thành qua pha chọn lọc và pha tái tổ hợp. . 22
Hình 2-1 Các phương án cắt trong bài toán OneDCSP_M 27
Hình 2-2 Biểu đồ thống kê độ chênh lệch so với kết quả của Belov -Scheithauer . 47
Hình 2-3 Biểu đồ thống kê phân bổ thời gian tính toán . 50
Hình 3-1 Kiến trúc của A-Team . 53
Hình 3-2 Biểu đồ tương tác giữa người dùng và hệ thống GMAS -OneDCSP_M . 55
Hình 3-3 Kiến trúc hệ thống GMAS-OneDCSP_M . 56
Hình 3-4 Cấu trúc bộ nhớ chung tương ứng với mỗi bài toán OneDCSP_M 59
Hình 3-5 Biểu đồ Use Case của hệ thống GMAS -OneDCSP_M 63

MỞ ĐẦU


Dân số thế giới tăng nhanh và đời sống vật chất của con người không ngừng nâng cao. Điều đó dẫn tới nhu cầu về tài nguyên thiên nhiên ngày càng lớn. Chúng ta đã và đang chứng kiến sự cạn kiệt của tài nguyên thiên nhiên, nhất là những nguồn tài nguyên không tái tạo được như khoáng sản. Để phát triển bền vững, việc sử dụng tài nguyên một cách hiệu quả luôn là vấn đề thời sự của toàn nhân loại. Trong các ngành kinh tế như chế tạo máy, xây dựng, dệt may việc sử dụng hiệu quả tài nguyên thể hiện bởi việc sử dụng hiệu quả các loại vật liệu thô phục vụ cho mục đích kinh tế.

Lĩnh vực cắt vật tư và đóng hàng (Cutting & Packing -C&P) bao gồm nhiều bài toán tổ hợp, hình học, các mô hình và thuật toán lý thuyết cũng như thực tiễn liên kết với nhau. Mục tiêu chính của lĩnh vực này là sắp xếp một cách hiệu quả các đối tượng được mô tả bằng ngôn ngữ hình học trong một miền lớn hơn. Các bài toán sau đây là các bài toán điển hình cho chủ đề này: Cắt vật tư và bài toán phế thải, xếp thùng (bin packing), bài toán sắp ba lô (knapsack), cân bằng luồng (line balancing), bài toán phân phối bộ nhớ và lập lịch cho bộ đa xử lý ( memory allocation and multiprocessor scheduling problem) Các bài toán cắt vật tư và đóng hàng được phát biểu và xử lý trong nhiều ngành khoa học khác nhau như khoa học quản lý, khoa học kỹ thuật, khoa học máy tính và công nghệ thông tin, toán học và vận trù học. Chúng là các bài toán thực tế đặt ra cho các ngành công nghiệp như công nghiệp kính, thép, giấy, da, may mặc, vận tải và hậu cần.

Từ giữa thế kỷ trước đã có nhiều cá ch tiếp cận giải các bài toán cắt vật tư và đóng hàng được đề xuất. Công trình khởi nguồn cho chủ đề này do L.V.Kantorovich đưa ra năm 1939 khi ông đề xuất áp dụng các mô hình toán học để tổ chức và lập kế hoạch sản xuất. Các mô hình này được phát biểu dướ i dạng các bài toán Quy hoạch nguyên và được chỉ ra thuộc lớp các bài toán NP -hard. Mô hình có một số nhược điểm như có nới lỏng liên tục yếu và tính đối xứng nên việc áp dụng nó trong các bài toán thực tiễn tỏ ra không hiệu quả.

Để khắc phục nhược điểm củ a mô hình trên, một mô hình khác cùng với kỹ thuật giải hiệu quả bài toán cắt vật tư một chiều được Gilmore và Gomory đề xuất vào những năm 60 thế k ỷ trước. Trong kỹ thuật này, các tác giả sử dụng công cụ quy hoạch tuyến tính để giải bài toán nới lỏng liên tục dẫn xuất từ bài toán quy hoạch nguyên. Nghiệm của bài toán quy hoạch nguyên ban đầu sẽ nhận được bằng các kỹ thuật làm tròn nghiệm của bài toán nới lỏng liên tục khi bài toán đảm bảo tính chất làm tròn nguyên (Integer Round-Up Property-IRUP). Đề xuất của Gilmore và Gomory đặc biệt hiệu quả khi giải các bài toán cắt vật tư nhờ kỹ thuật tạo sinh cột với việc giải Bài t oán xếp ba lô như một bài toán con. Sau này kỹ thuật tạo sinh cột trở thành kỹ thuật được ưa chuộng nhất khi người ta đề cập tới việc giải các bài toán quy hoạch cỡ lớn.