Luận án 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í

BỘ GIÁO DỤC & ĐÀO TẠO VIEN KH & CN VIET NAM VIEN CONG NGHE THONG TIN PHAN THI HOAI PHUONG MOT GIAI THUAT DI TRUYEN GIAI BAI TOAN CAT VAT TU MOT CHIEU VỚI NHIÊU KÍCH CỠ VẬT LIỆU THO LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội — 2011 BỘ GIÁO DỤC & ĐÀO TẠO VIEN KH & CN VIET NAM VIEN CONG NGHE THONG TIN PHAN THI HOAI PHUONG MOT GIAI THUAT DI TRUYEN GIAI BAI TOAN CAT VAT TU MOT CHIEU VOI NHIEU KICH CO VAT LIEU THO Chuyén nganh: Dam bao toan học cho máy tính và hệ thống tính toán Mã số: 62 46 35 (I1 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. LƯƠNG CHI MAI 2. NGUYEN VĂN HÙNG Hà Nội - 2011 LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả được viết chung với các tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận án.

Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào. Tác giả Phan Thị Hoài Phương LỜI CẢM ƠN Luận án được thực hiện và hoàn thành dưới sự hướng dẫn của PGS.TS Luong Chi Mai và TS. Trước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến cô Lương Chỉ Mai và thầy Nguyễn Văn Hùng, những ng ười thầy đã tận tình hướng dẫn, chỉ bảo, giúp đỡ tôi học tập và nghiên cứu. Xin trân trọng cảm ơn Ban lãnh đạo Viện Công nghệ thông tin và bộ phận quản lý nghiên cứu sinh đã nhiệt tình giúp đỡ và tạo điều kiện thuận lợi đề tôi hoàn thành luận án này.

Tôi xin trân trọng cảm ơn Ban lãnh đạo Học Viện Công nghệ Bưu chính viễn th ông đã tạo điều kiện cho tôi học tập, nghiên cứu và thực hiện luận án. Tôi cũng xin cảm ơn Bộ phận kỹ thuật Nhà máy ống thép Việt -Đức đã cho phép tôi thu thập số liệu và triển khai mô hình thử nghiệm ứng dụng giải bài toán cắt vật tư. Cuối cùng tôi xin đành tặng luận án này cho những người thân yêu: bố mẹ, chồng, con gái và con trai của tôi như muốn nói một lời cảm ơn chân thành nhất vì sự giúp đỡ, sự động viên không giới hạn đối với tôi. Họ chính là nơi khơi nguồn và cũng là đích hướng tới trong học tập và nghiên cứu của tôi.

CÁC KIÊN THỨC CƠ SỞ LIÊN QUAN. 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. Mô hình Gilmore-GOIOYFV. Mô hình Arc-flow của Valerio de Carvalho.2, Giải thuật di truyền,.

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,. __ 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 6110. Phát biểu mới của bài toán OneCSP _ÌM. Giải thuật di truyền lai ghép giải bài toán OseDCSP_M.

Kết quả tính toán,. KROQ Man sa. HE THONG DA TAC TU GMAS-OneDCSP_M GIẢI BÀI TOÁN OneDCSP_M 3. Yêu cầu cua hé thong GMAS-OneDCSP_M.

Thiét ké hé thong GMAS-OneDCSP_M. Kiến trúc hệ thống GMAS-OneDCSP_M. Thiết kế chỉ tiết hệ thống GMAS-OneDCSP_M. Đánh giá tính hiệu quả của hệ thống GMAS-OneDŒSP_M., 67 KET LUAN VA HUGNG NGHIEN CUU TIEP THEO.-2222222222222222252222 68 DANH MUC CAC CONG TRINH CUA TAC GIA.

cccsssesssssssessssesesssessssssessssseesesiee 70 TÀI LIỆU THAM KHẢO,,.,ÔỎ 78 i DANH MUC THUAT NGU Thuật ngữ tiếng Việt Thuật ngữ tiếng Anh Bài toán chủ Master Problem — MP Bài toán chủ giới hạn Restricted Master Problem — RMP Bai toan con dinh gia Subproblem — pricing problem Điêm cực Extreme point Giải thuật di truyền Genetic Algorithm — GA Giá suy giảm Reduced cost Lập trình tiễn hóa Evolutionary Programming-EP Nới lỏng tuyến tính liên tục Linear continuous relaxation Noi long tuyén tính liên tục mạnh Strong linear continuous relaxation Nới lỏng tuyến tính liên tục yêu Weak linear continuous relaxation Phuong phap nhanh can Branch and Bound —- B&B Phương pháp phân nhánh và định giá Branch and Price - B&P Phương pháp phân nhánh, định giá và cắt Branch and Price and Cut Phương pháp tạo sinh cột Column Generation Tia cực Extreme ray Tính chất làm tròn nguyên Integer Round-Up Property - IRUP Tính chất làm tròn nguyên cải biên Modified Integer Round-Up Property — MIRUP Tinh toán tiễn hóa Evolutionary Computation Thuật toán tiên hóa Evolutionary Algorithm- EA đi DANH MUC CAC KY HIEU, CUM TU VIET TAT Ký hiệu Thuật ngữ AF Thuật toán dựa trên mô hình luồng cung (Arc-Flow model) của Carvalho giải bài toán OneDCSP_S A-Team Asynchronous Team- Kiến trúc không đồng bộ sử dụng trong hệ đa tác tử C&P Cutting and Packing — Cắt vật tư và đóng hàng CSP Cutting Stock Problem -Bài toán cắt vật tư FIPA Foundation for Intelligent Physical Agents GA-AF Genetic Algorithm- Arc-Flow Model — Thuat toán lai ghép giải thuật di truyền và thuật toán AF GMAS- Genetic Multi Agent System- Hệ thống gen đa tác tử giải bài toán OneDCSP_M | OneDCSP_M JADE Java Agent DEvelopment Framework LP Linear Programming — Quy hoach tuyén tinh OneDCSP One Dimension Cutting Stock Problem-Bai toan cat vat tư một chiêu OneDCSP_M | One Dimensional Cutting Stock, Problem with Multiple Stock Sizes -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ô OneDCSP_M- | Tác từ giải bài toán OneDCSP_M Solver OneDCSP_S | One Dimensional Cutting Stock Problem with Single Stock Sizes -Bài toán cắt vật tư một chiêu với một loại kích thước vật liệu thô OneDCSP_S'? Nới lỏng tuyén tinh cua bai toan OneDCSP_S OneDCSP_S- Solver Tac tir giai bai toan OneDCSP_S iv DANH MUC CAC BANG BIEU Bang 2.1 Téng két chất lượng nghiệm so với kết qua cua Belov -Scheithauer.2 Kết qua tinh toán của Silvio A. Araujo và đồng sự.3 Phân bó độ chênh lệch nghiệm so với kết quả của Belov -Scheithauer.4 Thống ké thoi gian tinh toan ng .5 Thống kê phân bó thời gian tính toán .---2-- 22222 +E+e+2Exserrserrrxee 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__§.---cccccrcerrreee 10 Hình 1-2 Ví dụ về mạng lưới và phương án cắt với =9 và các j¡ c{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 OneCSP _M.cccccccccrerriee 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. on) Hình 3-2 Biểu đồ tương tác giữa người dùng va hé thong GMAS -OneDCSP_M.55 Hình 3-3 Kiến trúc hệ thống GMAS-O»eDCSP_M. Hình 3-4 Cấu trúc bộ nhớ chung tương ứng với mỗi bài toán OneDCSP_M.

Hình 3-5 Biêu đồ Use Case của hệ thông GMAS-OnelDCSP_M.--- 63 MO DAU Dan 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ủ dé này: Cắt vật tư và bài toán phế thải, xếp thung (bin packing), bai toan sip ba 16 (knapsack), can bằng luồng (line balancing), bài toán phân phối bộ nhớ và lap lich cho bé da xt ly (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 va van tru 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à hau can. 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 cha dé nay do L.Kantorovich đưa ra năm 1939 khi ông đề xuất áp dụng các mô hình toán học dé 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ướ ¡ 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 duge Gilmore va Gomory dé xuat 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 dé 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 toá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. Do tính khoa học cũng như thực tiễn cao của chủ đề c at vat tw và đóng hàng nên vào năm 1988 H. Waescher đã thành lập Special Interest Group on Cutting and Packing (SICUP), bước quan trong đề hỗ trợ nghiên cứu quốc tế về chủ đề này.

Một trong những đóng góp nổi bật của H. vào năm 1990 cho việc phát triển các nghiên cứu lý thuyết cũng như ứng dụng trong lĩnh vực này là việc đưa ra phân loại (Typology) các bài toán cắt vật tư và đóng hàng dựa trên điều tra các đặc tính của cấu trúc hình học, cấu trúc logic và ngữ cảnh xuất hiện của chúng trong thực tế. Sự phân loại này được G. Waescher và các đồng nghiệp tiếp tục hoàn thiện vào năm 2007.

Việc phân loại được thực hiện dựa trên bốn tiêu chí: 1.