Xem mẫu
- 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)
nguon tai.lieu . vn