Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một phương pháp tiếp cận dựa trên lập trình động và heuristics cho bài toán cắt hai chiều với các khiếm khuyết
Tóm tắt
Bài báo này đề cập đến một bài toán cắt hai chiều, trong đó các vật phẩm hình chữ nhật nhỏ được cắt ra từ một vật thể lớn hình chữ nhật, trong đó có nhiều khiếm khuyết. Giả định rằng số lượng các mảnh của mỗi loại vật phẩm nhỏ có thể được cắt ra từ vật thể lớn là không giới hạn. Ngoài ra, tất cả các đường cắt đều bị hạn chế theo kiểu guillotine và số giai đoạn cần thiết để thực hiện tất cả các đường cắt là không giới hạn. Hơn nữa, không có vật phẩm nhỏ nào được phép chồng lắp lên một khu vực bị khiếm khuyết. Mục tiêu là tối đa hóa giá trị của các vật phẩm nhỏ đã được cắt. Để giải quyết vấn đề đã được mô tả ở trên, một phương pháp tiếp cận dựa trên lập trình động kết hợp với heuristic được trình bày, nhằm khắc phục những hạn chế về cấu trúc và tính toán của các phương pháp đã được đề xuất trước đó. Trong sự hiện diện của các khiếm khuyết, việc đại diện cho các khu vực khiếm khuyết và định nghĩa các tập phân rã được xem xét lại. Điều này cho phép cải thiện tính hiệu quả tính toán cũng như yêu cầu về không gian lưu trữ để giải quyết vấn đề đã cho với bất kỳ số lượng khiếm khuyết nào trong phương pháp này. Chúng tôi cũng phân tích độ phức tạp tính toán của thuật toán và xác định những yếu tố ảnh hưởng đến thời gian chạy của nó. Phương pháp được đề xuất được đánh giá thông qua một loạt các thí nghiệm số chi tiết được thực hiện trên các trường hợp bài toán trích xuất từ tài liệu, cũng như trên các trường hợp được tạo ngẫu nhiên. Các thí nghiệm không chỉ minh họa cách mà phương pháp đã được đề xuất có thể xác định các giải pháp tối ưu cho các trường hợp bài toán thử nghiệm, mà còn giải thích lý do tại sao các phương pháp hiện có không làm được điều đó. Hơn nữa, các kết quả tính toán chỉ ra rằng phương pháp được đề xuất, được trang bị với các tập phân rã mới được đề xuất, có khả năng tạo ra một tỷ lệ cao các giải pháp tối ưu cho bài toán tương ứng với các khiếm khuyết.
Từ khóa
#cắt hai chiều #khiếm khuyết #lập trình động #phương pháp heuristic #tối ưu hóaTài liệu tham khảo
Aboudi R, Barcia P (1998) Determining cutting stock patterns when defects are present. Ann Oper Res 82:343–354
Afsharian M (2013) The two-dimensional, rectangular, guillotineable-layout cutting problem with defects. Shaker Verlag, Aachen
Alvarez-Valdes R, Parreño F, Tamarit JM (2002) A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems. Comput Oper Res 56:414–425
Beasley JE (1985a) Algorithms for unconstrained two-dimensional guillotine cutting. J Oper Res Soc 36:297–306
Beasley JE (1985b) An exact two-dimensional non-guillotine cutting tree search procedure. Oper Res 33:49–64
Beasley JE (2004) A population heuristic for constrained two-dimensional non-guillotine cutting. Eur J Oper Res 156:601–627
Birgin EG, Lobato RD, Morabito R (2012) Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm. J Oper Res Soc 63:183–200
Carnieri C, Mendoza GA, Luppold WG (1993) Optimal cutting of dimension parts from lumber with a defect: a heuristic solution procedure. For Prod J 43:66–72
Christofides N, Whitlock C (1977) An algorithm for two-dimensional cutting problems. Oper Res 25:30–44
Fayard D, Hifi M, Zissimopoulos V (1998) An efficient approach for large-scale two-dimensional guillotine cutting stock problems. J Oper Res Soc 49:1270–1277
Fayard D, Zissimopoulos V (1995) An approximation algorithm for solving unconstrained two-dimensional knapsack problems. Eur J Oper Res 84:618–632
G YG, Kang MK (2002) A new upper bound for unconstrained two-dimensional cutting and packing. J Oper Res Soc 53:587–591
G YG, Seong YJ, Kang MK (2003) A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems. Oper Res Lett 31:301–307
Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper Res 9:849–859
Gilmore PC, Gomory RE (1965) Multistage cutting stock problems of two and more dimensions. Oper Res 13:94–120
Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper Res 14:1045–1074
Hahn SG (1968) On the optimal cutting of defective sheets. Oper Res 16:1100–1114
Herz JC (1972) Recursive computational procedure for two-dimensional stock cutting. IBM J Res Dev 16:462–469
Hifi M (1997) The DH/KD algorithm: a hybrid approach for unconstrained two-dimensional cutting problems. Eur J Oper Res 97:41–52
Hifi M (2004) Dynamic programming and hill-climbing techniques for constrained two dimensional cutting stock problems. J Comb Optim 8:65–84
Hifi M, Zissimopoulos V (1996) A recursive exact algorithm for weighted two-dimensional cutting. Eur J Oper Res 91:553–564
Kang MK, Yoon K (2011) An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems. Int J Prod Res 49(15):4437–4455
Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85–103
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin
Morabito R, Arenales MN (1996) Staged and constrained two-dimensional guillotine cutting problems: an AND-OR graph approach. Eur J Oper Res 94:548–560
Morabito RN, Arenales MN, Arcaro VF (1992) An And-Or-Graph approach for two-dimensional cutting problems. Eur J Oper Res 58:263–271
Morabito R, Pureza V (2010) A heuristic approach based on dynamic programming and AND-OR graph search for the constrained two-dimensional guillotine cutting problem. Ann Oper Res 179:297–315
Neidlein V, Vianna ACG, Arenales MN, Wäscher G (2008) The two-dimensional, rectangular, guillotineable-layout cutting problem with a single defect. Working Paper No. 35, Faculty of Economics and Management, Otto-von-Guericke-University Magdeburg.
Neidlein V, Wäscher G (2008) SLOPPGEN: a problem generator for the two-dimensional rectangular single large object placement problem. Working Paper No. 15, Faculty of Economics and Management, Otto-von-Guericke-University Magdeburg.
Özdamar L (2000) The cutting-wrapping problem in the textile industry: optimal overlap of fabric lengths and defects for maximizing return based on quality. Int J Prod Res 38:1287–1309
Rönnqvist M, Astrand E (1998) Integrated defect detection and optimization for cross cutting of wooden boards. Eur J Oper Res 108:490–508
Sarker BR (1988) An optimum solution for one-dimensional slitting problems: a dynamic programming approach. J Oper Res Soc 39:749–755
Scheithauer G, Terno J (1988) Guillotine cutting of defective boards. Optimization 19:111–121
Song X, Chu CB, Lewis R, Nie YY, Thompson J (2010) A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting. Eur J Oper Res 202:368–378
Twisselmann U (1999) Cutting rectangles avoiding rectangular defects. Appl Math Lett 12:135–138
Vianna ACG, Arenales MN (2006) Problema de corte de placas defeituosas. Pesqui Operacional 26:185–202
Wäscher G, Haußner H, Schumann H (2007) An improved typology of cutting and packing problems. Eur J Oper Res 183:1109–1130