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ô

Chia sẻ: Đỗ Huy Quang | Ngày: | Loại File: PDF | Số trang:92

Thêm vào BST

Báo xấu

150
lượt xem 42
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 – 2011
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Ô 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ế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 Lương Chi Mai 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ô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 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ỤC MỞ ĐẦU ........................................................................................................................ 1 CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN ............................................... 9 Chươ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ƯỚC Chươ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ÁN Chương 3. OneDCSP_M . ......................................................................................................... 52 Yêu cầu của hệ thống GMAS -OneDCSP_M ................................................ 54 3.1. Thiết kế hệ thống GMAS-OneDCSP_M ....................................................... 55 3.2. Kiến trúc hệ thống GMAS-OneDCSP_M ............................................. 55 3.2.1. Thiết kế chi tiết hệ thống GMAS -OneDCSP_M ................................... 58 3.2.2. Đánh giá tính hiệu quả của hệ thống GMAS-OneDCSP_M ......................... 65 3.3. Kết luận ......................................................................................................... 67 3.4. 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
ii DANH MỤC THUẬT NGỮ 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 Bài toán con định giá 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 Nới lỏng 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 Phương pháp nhánh cận 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à Branch and Price and Cut cắt 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 Tính toán tiến hóa Evolutionary Computation Thuật toán tiến hóa Evolutionary Algorithm- EA
iii DANH MỤC CÁC KÝ HIỆU, CỤM TỪ VIẾT TẮT Ký hiệu Thuật ngữ Thuật toán dựa trên mô hình luồng cung (Arc-Flow model) của AF Carvalho giải bài toán OneDCSP_S Asynchronous Team- Kiến trúc không đồng bộ sử dụng trong hệ A-Team đa tác tử Cutting and Packing – Cắt vật tư và đóng hàng C&P Cutting Stock Problem -Bài toán cắt vật tư CSP FIPA Foundation for Intelligent Physical Agents Genetic Algorithm- Arc-Flow Model – Thuật toán lai ghép giải GA-AF thuật di truyền và thuật toán AF Genetic Multi Agent System- Hệ thống gen đa tác tử giải bài toán GMAS- OneDCSP_M OneDCSP_M JADE Java Agent DEvelopment Framework Linear Programming – Quy hoạch tuyến tính LP One Dimension Cutting Stock Problem-Bài toán cắt vật tư một OneDCSP 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_SLP Nới lỏng tuyến tính của bài toán OneDCSP_S Tác tử giải bài toán OneDCSP_S OneDCSP_S- Solver
iv 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
v 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
1 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 để
2 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 sin h 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 ắt vật tư và đóng hàng nên vào năm 1988 H. Dyckhoff và G. Waescher đã thành lập Special Interest Group on Cutting and Packing (SICUP), bước quan trọng để 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.Dyckhoff 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 t ra 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í:
3 1. Số chiều của bà i toán: có thể là 1, 2, 3 hoặc lớn hơn 2. Kiểu gán (Kind of assignment) : Có hai kiểu gán là cực đại hóa đầu ra (Output Maximization) hoặc c ực tiểu hóa đầu vào (Input Minimization) 3. Phân loại các đối tượng nhỏ (Assortment of small items) : đồng nhất, tương đố i không thuần nhất (weakly heterogeneous assortment) , hoàn toàn không thuần nhất (Strongly heterogeneous assortment) 4. Phân loại các đối tượng lớn (Assortment of large objects): Một đối tượng lớn (có thể được xem xét chi tiết hơn phụ thuộc vào các - chiều của đối tượng được cố định hay có thể biến đổi ) Một số đối tượng lớn với các chiều cố định. Trường hợp này có thể được - chia thành các bài toán với các đối tượng lớn đồng nhất , tương đối đồng nhất và hoàn toàn không đồng nhất. Trong các kiểu bài toán cắt vật tư thì Bài toán cắt vật tư một chiều (One Dimensional Cutting Stock Problem – OneDCSP) giữ một vị trí quan trọng và chiếm gần một nửa tổng số công trình đã được công bố về chủ đề này. Có nhiều lý do giải thích về mối qua n tâm của cộng đồng nghiên cứu dành ch o bài toán này trong đó có thể dẫn ra nhận xét của Gilmore và Gomory khi nói rằng , nhiều bài toán cắt vật tư nhiều chiều có thể được xử lý bằng một quy trình nhiều công đoạn dựa trên nền tảng bài toán cắt vật tư một chiều. Từ công trình khởi đầu của Gilmor e và Gomory, hàng loạt các biến thể khác nhau của bài toán OneDCSP đã được phát biểu và giải quyết bằng các cách tiếp cận khác nhau. 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 – OneDCSP_M) là mở rộng tự nhiên của bài toán cắt vật tư một chiều với một loại vật tư OneDCSP. Cho đến nay có rất ít công trình nghiên cứu về bài toán này được công bố. Theo phân loại của Waescher, bài toán OneDCSP_M được chia thành hai lớp con: lớp không ràng buộc số lượng của từng loại vật tư đầu vào và lớp có ràng buộc này.
4 Có thể thấy hầu hết các công trình liên quan đến bài toán OneDCSP_M đều hướng tới giải các bài toán thuộc lớp thứ hai . Chúng ta có thể khái quát các cách tiếp cận được đề xuấ t để giải bài toán này như sau. Bài toán cắt vật tư OneDCSP_M là bài toán quy hoạch nguyên và thuộc lớp NP - khó vì vậy không tồn tại thuật toán bảo đảm cho nghiệm tối ưu trong thời gian đa thức. Cho đến nay các phương pháp giải chính xác bài toán quy hoạch nguyên này và các biến thể của nó đều được xây dựng theo lược đồ phân nhánh và định giá (Branch and Price – B&P) dựa trên nới lỏng tuyến tính liên tục của mô hình do Gilmore-Gomory đề xuất vào năm 1963 [26,27] và sau này là mô hình arc-flow của Valerio de Carvalho [55]. Gần đây, Belov [11], Carvalho và đồng nghiệp [ 56] đã đưa vào sử dụng các lát cắt trong lược đồ trên để tạo nên lược đồ phân nhánh định giá và cắt nhằm cải thiện tốc độ tính toán khi giải bài toán. Việc cải biên các lược đồ trên áp dụng giải các biến thể khác nhau của bài toán cũng đã được đề xuất [12,13,14,30,44,58]. Do các phương pháp chính xác giải bài toán cắt vật tư đòi hỏi chi phí thời gian khá tốn kém đối với các bài toán có kích thước trung bình hoặc lớn nên nhiều tác giả đã đề xuất các giải thuật heuristic khác nhau nhằm tìm kiếm nghiệm có chất lượng tốt trong khoảng thời gian chấp nhận được. Các giải thuật heuristic không sử dụng nới lỏng tuyến tính liên tục của bài toán mà dựa vào cấu trúc của bài toán để điều khiển quá trình tìm kiếm. Các giải thuật heuristic đầu tiên được đề xuất để giải các bài toán cắt vật tư thường dựa trên các phương pháp tìm kiếm cục bộ như First -Fit, Next-Fit, Best-Fit và Worst-Fit Decreasing để xây dựng các phương án cắt [52]. Ý tưởng chính của những phương pháp này là sau khi sắp xếp danh sách các thành phẩm theo thứ tự kích thước giảm dần , các phương án cắt được xây dựng theo các chiến lược khác nhau. Phương pháp First-Fit Decreasing tìm thành phẩm phù hợp để xếp vào phương án cắt, còn phương pháp Nex t-Fit tìm chỗ trống trên các phương án cắt để đặt thành phẩm. Phương pháp Best -Fit hạn chế phần dư thừa của mỗi phương án cắt
5 bằng cách tìm không gian nhỏ nhất có thể để đặt các thành phẩm, trong khi phương pháp Worst-Fit thì lại đặt thành phẩm vào không g ian lớn nhất tìm được nhằm để lại nguyên liệu nhiều nhất cho các bước lặp tiếp theo. Một vấn đề nảy sinh là các phương pháp dựa trên tìm kiếm cục bộ như vậy thường rất nhanh chóng rơi vào các cực trị địa phương. Để hạn chế khả năng không mong muốn này, một số tác giả đề xuất áp dụng các Metaheuristic vào việc giải bài toán. Yang dùng giải thuật tham lam trong đó s ử dụng một hàm mục tiêu phụ thuộc vào một số lượng nhỏ các điều ki ện cắt để hỗ tr ợ phát hiện nghiệm tốt nhất trong quá trình tìm kiếm cục bộ tại từng b ướ c của quá trình giải bài toán [60]. Trong [20], Eshghi và cộng sự sử dụng giải thuật đàn kiến với các quy tắc xác suất định nghĩa trước dựa trên đó đàn kiến có thể lựa chọn các phương án cắt để tìm ra phương án cắt tốt nhất. Giải thuật tôi luyện mô phỏng đư ợc sử dụng trong các công trình [33,32]. Một lớp đặc biệt các giải thuật metaheuristic giải bài toán cắt vật tư là lớp các giải thuật di truyền (Genetic Algorithm-GA). Các giải thuật này được xây dựng theo hai cách tiếp cận : cách tiếp cận đơn hàn g và cách tiếp cận dựa trên nhóm. Trong cách tiếp cận đơn hàng, các thành phẩm được sử dụng một cách độc lập khi tạo ra các phương án cắt . Cách tiếp cận này khá gần gũi với định nghĩa của bài toán nhưng ít được áp dụng trong thực tiễn vì các gen mã hóa ng hiệm của bài toán thường bị phá vỡ dưới tác động của các toán tử lai ghép. Toyoda và đồng nghiệp [51,53] đề xuất các toán tử lai ghép khác nhau trong giải thuật di truyền của mình để giải bài toán cắt vật tư. Falkenauer đã đề xuất mô hình dựa trên nhóm [21], trong đó các phương án cắt được xây dựng dựa trên các nhóm thành phẩm đã được phân chia nhằm khắc phục sự ảnh hưởng của các toán tử di truyền đến cấu trúc nghiệm. Yakawa và đồng nghiệp cũng đưa ra toán tử lai ghép đặc biệt gắn vào mô hình giải thuật di truyền dựa trên nhóm do Falkenauer đề xuất [ 59]. Một đề xuất sử dụng ý tưởng lập trình tiến hóa (Evolutionary Programming -EP) giải bài toán cắt vật tư cũng được đề xuất [39]. Trong lập trình tiến hóa , phép tìm kiếm được thực hiện nhờ các toán tử đột biến mà không sử dụng toán tử lai ghép.
6 Liang đã đưa ra hai toán tử đột biến mới và chỉ ra tính ưu việt của các toán tử này. Khác với lập trình tiến hóa, giải thuật di truyền sử dụng cả toán tử lai ghép trong quá trình tìm kiếm. Raymond Chiong và đồng nghiệp [43] đã tiến hành so sánh hai cách tiếp cận EP và GA và kết hợp tính ưu việt của cả hai cách tiếp cận để xây dựng một giải thuật di truyền cho bài toán cắt vật tư. Trong [ 48], Araujo và đồng nghiệp sử dụng giải thuật heuistic First -Fit decreasing để xây dựng các phương án cắt tạo ra các cá thể (nghiệm chấp nhận được) ở mức thấp. Ở mức cao, các tác giả đề xuất thuật toán tiến hóa (Evolutionary Algorithm -EA) với toán tử lựa chọn tham lam ngẫu nhiên. Việc tạo ra các cá thể mới được thực hiện nhờ quá trình trao đổi các phương án cắt giữ a các cá thể trong một pha được đặt tên là co -operation. Mới đây, việc lai ghép giải thuật di truyền với các phương pháp sử dụng nới lỏng tuyến tính liên tục cũng được tác giả luận án đề xuất trong [ 1,2]. Các cách tiếp cận giải bài toán cắt vật tư có thể mô tả theo sơ đồ sau. Các cách tiếp cận giải bài toán OneDCSP Cách tiếp cận chính Cách tiếp cận lai ghép Cách tiếp cận heuristic Dựa trên Metaheuristic xác Dựa trên mô hình nới và tiếp cận chính xác lỏng liên tục Kỹ thuật B&P Metaheuristic Pure-heuristic Sử dụng công cụ Dựa trên tìm toán học để hạn chế kiếm cục b ộ cực trị địa phương - First-Fit - Phương pháp tạo - Giải thuật di truyền Decreasing sinh cột của - Lập trình tiến hóa - Next-Fit Thuật toán Gilmore&Gomory - Thuật toán tiến hóa Decreasing GA-AF - Mô hình arc-flow - Best-Fit - Giải thuật đàn kiến của Carvalho Decreasing - Các thuật toán cải - Mô phỏng tôi luyện - Worst-Fit biên (Belov,…) - Tabu Search Decreasing 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
7 Theo hiểu biết của tác giả, cho đến nay chưa có một công trình nào liên quan đến giải bài toán OneDCSP_M thuộc lớp thứ nhất (không có hạn chế về số lượng vật liệu thô) được công bố. Bài toán này cũng chính là đối tượng nghiên cứu đặt ra cho bản luận án này. Luận án này nhằm đóng g óp một phương pháp hiệu quả để giải bài toán OneDCSP_M xuất phát từ mô hình của Gilmore và Gomory, với điều kiện nguồn nguyên liệu không bị giới hạn. Những đóng góp chính của tác giả trong luận án này bao gồm: Tiến hành phân tích mối liên quan ngữ nghĩa của bài toán OneDCSP_M với - bài toán cắt trên một loại vật liệu thô (One Dimensional Cutting Stock Problem with Single Stock Sizes - OneDCSP_S). Từ đó đư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ô OneDCSP_M Trên cơ sở phát biểu mới của bài toán OneDCSP_M và những mối liên quan - ngữ nghĩa với bài toán OneDCSP_S, đề 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 OneDCSP_M. 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 . - Để nâng cao hiệu quả khi giải các bài toán thực tế, thuật toán GA -AF được cài đặt dưới dạng một hệ thống đa tác tử thực hiện các tính toán song song và phân tán nhằm tận dụng tài nguyên tính toán của mạng cục bộ (LAN). Tính đúng đắn của hệ thống được chứng minh chặt chẽ. 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. Các kết quả được chính được trình bày trong 4 công trình công bố trên tạp chí chuyên ngành và hội thảo quốc tế . Cấu trúc của Luận án như sau:
8 Ngoài phần Mở đầu và Kết luận chung, luận án được chia làm 3 chương. Chương 1 trình bày các công cụ toán học cơ sở nhằm giải quyết bài toán đặt ra ở chương sau. Phần thứ nhất của chương trình bày các mô hình và thuật giải chính xác cho bài toán cắt vật tư với một loại vật liệu thô. Phần thứ hai trình bày tóm tắt một số vấn đề cơ bản của giải thuật di truyền. Trong chương 2, tác giả phân tích mối liên quan ngữ nghĩa giữa bài toán OneDCSP_M và bài toán OneDCSP_S. Kết quả cho thấy việc cắt vật tư với nhiều kích thước vật liệu thô sẽ mang lại hiệu quả hơn so với trường hợp chỉ có một loại vật liệu thô và từ đó đề xuất một mô hình mới cho bài toán OneDCSP_M. Các phân tích đó cũng làm cơ sở cho việc lai ghép giải thuật di truyền (GA) với thuật toán phân nhánh và định giá theo mô hình Arc-Flow (AF) của Carvalho để tạo nên thuật toán mới GA-AF giải bài toán OneDCSP_M. Tính đúng đắn của thuật toán GA-AF được chứng minh chặt chẽ. Tính hiệu quả của thuật toán cũng đượ c kiểm chứng trên tập các bài toán mẫu do Belov [11] đưa ra. Phát biểu mới của bài toán OneDCSP_M trong chương 2 đã phân rã bài toán thành nhiều bài toán con có thể giải quyết một cách độc lập bằng thuật toán phân nhánh và định giá theo mô hình AF. Từ đó , trong chương 3, tác giả đã cài đặt thuật toán dưới dạng một hệ thống đa tác tử GMAS-OneDCSP_M nhằm nâng cao hiệu quả trong ứng dụn g thực tiễn. Tính đúng đắn của hệ thống được chứng minh ; hiệu quả của nó được phân tích chặt chẽ và được kiểm chứng bằng việc triển khai thử nghiệm trong môi trường công nghiệp.
9 Chương 1. CÁC KIẾN THỨC CƠ SỞ LIÊN QUAN Chương này trình bày tóm tắt những công cụ toán học liên quan làm cơ sở cho việc xây dựng giải pháp cho bài toán OneDCSP_M được đưa ra trong các Chương tiếp theo . Phần thứ n hất giới thiệu bài toán cắt vật tư một chiều với một loại vật liệu thô OneDCSP_S với hai mô hình giải bài toán: mô hình của Gilmore -Gomory và mô hình Arc-Flow của Carvalho. Phần tiếp theo của chương đề cập những nội dung cơ bản của thuật toán di truyền. 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 1.1. Bài toán cắt vật tư một chiều kinh điển (bài toán cắt vật tư một chiều với một loại vật liệu thô – One Dimensional Cutting Stock Problem with Single Stock Length OneDCSP_S) được xác định b ởi các dữ liệu sau: (m,L,l=(l1,…,lm),b=(b1,…,bm)), trong đó : - m là số dạng vật liệu thành phẩm được cắt từ vật liệu thô - L là bề rộng của tấm vật liệu thô - Đối với mỗi dạng vật liệu thành phẩm j : + lj là bề rộng + bj là đơn hàng cho loại vật liệu thành phẩm đó. Bài toán đặt ra là tìm cách cắt sao cho số lượng tấm vật liệu thô sử dụng là ít nhất mà vẫn đáp ứng được yêu cầu của đơn hàng. Ở đây, các khái niệm vật liệu thô, vật tư, nguyên liệu đầu vào của bài toán được hiểu với nghĩa tương đương. Tương tự, hai thuật ngữ thành phẩm và sản phẩm cũng mang ý nghĩa tương đương.
10 ai1 aij li Phương án cắt j Phương án cắt 1 li ... ... L L Hình 1-1 Các phương án cắt trong bài toán OneDCSP_S Bài toán OneDCSP lầ n đầu tiên được Kantorovich [35] phát biểu dưới dạng bài toán quy hoạch nguyên và được chứng minh thuộc lớp bài toán NP -Hard. Sau đó nhiều tác giả đã xây dựng các mô hình khác như mô hình của Gilmore -Gomory [26], mô hình Arc-flow của Valerio de Carvalho [ 55], mô hình Node-flow của Belov [14]…nhằm khắc phục tính nới lỏng liên tục yếu cũng như tính đối xứng của mô hình Kantorovich, đồng thời tận dụ ng các thông tin cấu trúc của không gian nghiệm nhằm xây dựng các thuật toán giải chính xác cho bài toán. Sau đây là hai mô hình gốc thường được sử dụng khi nghiên cứu bài toán. 1.1.1. Mô hình Gilmore-Gomory Định nghĩa 1.1 Một phương án cắt là một véc tơ cột a j   a1 j ,..., amj     , j=1,…,n m với aij là số lần thành phẩm thứ i được cắt theo phương án cắt j từ tấm vật liệu thô. Phương án cắt gọi là chấp nhận được nếu nó thỏa mãn đi ều kiện: m l a (1.1) L i ij i 1 Giả sử x j , j  1,..., n là số lần phương án cắt chấp nhận được thứ j được sử dụng trong nghiệm. Khi đó mô hình bài toán cắt vật tư một chiều với một loại vật liệu thô của Gilmore và Gomory được phát biểu như sau: n OneDCSP _ S (m, L, l , b)  min  x j  min x (1.2) j 1
11 trên miền ràng buộc: n a x i=1,…,m (1.3)  bi ij j j 1 j=1,…,n x j   , (1.4) Mô hình (1.1)-(1.4) là bài toán quy hoạch nguyên với số lượng biến n tăng theo hàm mũ của m. Mô hình này khắc phục được tính đối xứng của mô hình Kantorovich và có nới lỏng liên tục mạnh với dự đoá n về tính chất làm tròn nguyên cải biên (Modified Integer Round-Up Property – MIRUP) như sau: “Sự sai khác giữa giá trị tối ưu của bài toán OneDCSP _ S (m, L, l , b) và giá trị tối ưu của bài toán nới lỏng liên tục của nó luôn luôn nhỏ hơn 2” Trong thực tế người ta chưa chỉ ra được các ví dụ có sự sai khác lớn hơn 7/6 [44]. Hơn nữa, những ví dụ có sai khác nhỏ hơn 1 chiếm đa số. Những bài toán như vậy được gọi là các bài toán có tính chất làm tròn nguyên ( Integer Round-Up Property – IRUP). Những bài toán có sai khác lớn hơn hoặc bằng 1 được gọi là những bài toán non-IRUP. Trên cơ sở dự đoán đó, Gilmore và Gomory đề xuất cách tiếp cận giải bài toán (1.1)-(1.4) gồm 2 bước: 1/ giải bài toán nới lỏng liên tục của (1.1)-(1.4); 2/ Làm tròn số nghiệm tối ưu của bài toán nới lỏng liên tục để nhận được nghiệm của bài toán (1.1)-(1.4). Để giải bài toán nới lỏng liên tục của (1.1)-(1.4) với số lượng biến n rất lớn, Gilmore và Gomory lần đầu tiên đề xuất sử dụng kỹ thuật tạo sinh cột , trong đó mỗi biến chỉ được sinh ra khi nó thực sự cần thiết cho việc cải thiện nghiệm tìm được trước đó. Sau khi thêm vào các biến phụ (slacks) ta có thể đưa bài toán (1.1)-(1.4) về dạng chuẩn: OneDCSP _ S (m, L, l , b)  min  x : Ax  b, x   n  (1.5) 