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

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

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à

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

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ữ

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 – Thuật toán lai ghép giải

thuật di truyền và thuật toán AF

GMAS- OneDCSP_M

Genetic Multi Agent System- Hệ thống gen đa tác tử giải bài toán

OneDCSP_M

JADE Java Agent DEvelopment Framework

LP Linear Programming – Quy hoạch tuyến tính

OneDCSP One Dimension Cutting Stock Problem-Bài toán cắt vật 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- Solver

Tác tử giải bài toán OneDCSP_M

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

LP Nới lỏng tuyến tính của bài toán OneDCSP_S

OneDCSP_S- Solver

Tác tử giải bài toán OneDCSP_S

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