Tiến Sĩ 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ô

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 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 ắ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 quan tâm của cộng đồng nghiên cứu dành cho 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.

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