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ích cỡ vật liệu thô

Luận án được thực hiện và hoàn thành dưới sự hướng dẫn của PGS.TS Lương ChiMai và TS. Nguyễn Văn Hùng. Tr ước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến côLương Chi 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....
Nội dung trích xuất từ tài liệu:
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ích cỡ vật liệu thôBỘ GIÁO DỤC & ĐÀO TẠO VIỆN KH & CN VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN PHAN THỊ HOÀI PHƯƠNG 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Ô LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội – 2011BỘ GIÁO DỤC & ĐÀO TẠO VIỆN KH & CN VIỆT NAM VIỆN CÔNG NGHỆ THÔNG TIN PHAN THỊ HOÀI PHƯƠNG 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Ô Chuyên ngành: Đảm bảo toán học cho máy tính và hệ thống tính toán Mã số : 62 46 35 01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC : 1. PGS.TS. LƯƠNG CHI MAI 2. TS. NGUYỄN 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ếtchung 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 Lương ChiMai và TS. Nguyễn Văn Hùng. Tr ước hết, tôi xin bày tỏ lòng biết ơn sâu sắc đến côLương Chi 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ôithu 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 dà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. i MỤC LỤCMỞ ĐẦU ........................................................................................................................ 1 CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN ............................................... 9Chương 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.1.1. Mô hình Gilmore-Gomory ..................................................................... 10 Mô hình Arc-flow của Valerio de Carvalho .......................................... 13 1.1.2. Giải thuật di truyền ........................................................................................ 19 1.2. Kết luận ......................................................................................................... 25 1.3. BÀI TOÁN CẮT VẬT TƯ MỘT CHIỀU VỚI NHIỀU KÍCH THƯỚCChương 2.VẬT LIỆU THÔ: MÔ HÌNH VÀ GIẢI PHÁP ........................................................... 26 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 2.1. Gilmore và Gomory .................................................................................................. 26 Phát biểu mới của bài toán OneDCSP_M ..................................................... 28 2.2. Giải thuật di truyền lai ghép giải bài toán OneDCSP_M .............................. 32 2.3. Kết quả tính toán ........................................................................................... 40 2.4. Kết luận ......................................................................................................... 50 2.5. HỆ THỐNG ĐA TÁC TỬ GMAS -OneDCSP_M GIẢI BÀI TOÁNChương 3.OneDCSP_M . ......................................................................................................... 52 Yêu cầu của hệ thống GMAS -OneDCSP_M ................................................ 54 3.1. Thiết kế ...