:::

詳目顯示

回上一頁
題名:An Exact Algorithm for Large-scale Unconstrained Three Staged Cutting Problems with Same-size Block Requirement
書刊名:International Journal of Information and Management Sciences
作者:Ji, JunLu, Yi-pingCha, Jian-zhongYu, Jia-qingCui, Yao-dong
出版日期:2012
卷期:23:1
頁次:頁59-78
主題關鍵詞:Cutting problemsDynamic programmingKnapsack problemSame-size block
原始連結:連回原系統網址new window
相關次數:
  • 被引用次數被引用次數:期刊(1) 博士論文(0) 專書(0) 專書論文(0)
  • 排除自我引用排除自我引用:0
  • 共同引用共同引用:0
  • 點閱點閱:32
Abstract This paper deals with the two-dimensional cutting problem, in which a set of small rectangular pieces are cut from a large rectangle for the purpose of maximizing the total value of the pieces included. The two-dimensional cutting problem is a very hard problem to solve, for which optimal algorithms exist but tackle large-scale problems inefficiently. Cutting patterns usually not only come from real-world production demands, but also can simplify a problem into some sub-problems. The pattern algorithm for each sub-problem can be constituted with much higher running speed, and serve as approximate algorithms to the optimal algorithms. This paper proposes an exact algorithm for generating three staged same-size block cutting pattern. This algorithm uses knapsack approach combined with a dynamic programming recursion. The algorithm is compared with the well-known three-stage algorithm and the T-shape homogenous block algorithm through large-scale instances. The experiment results illustrate that the material usage of this paper's algorithm is higher than above algorithms within reasonable computational time.
期刊論文
1.Alvarez-Valdés, Ramón、Parajón, Antonio、Tamarit, José Manuel(2002)。A Tabu Search Algorithm for Large-scale Guillotine (Un)Constrained Two-Dimensional Cutting Problems。Computers & Operations Research,29(7),925-947。  new window
2.Agrawal, P. K.(1993)。Minimizing Trim Loss in Cutting Rectangular Blanks of a Single Size Form a Rectangular Sheet Using Orthogonal Guillotine Cuts。European Journal of Operational Research,64(3),410-422。  new window
3.Arslanov, M. Z.(2000)。Continued Fractions in Optimal Cutting of a Rectangular Sheet into Equal Small Rectangles。European Journal of Operational Research,125(2),239-248。  new window
4.Cintra, G. F.、Miyazawa, F. K.、Wakabayashi, Y.、Xavier, E.C.(200811)。Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation。European Journal of Operational Research,191(1),61-85。  new window
5.Cui, Y.、Zhao X.、Yang Y.、Yu, P.(2009)。Uniform block patterns for constrained guillotine cutting of rectangular items。International Journal of Information and Management Sciences,20(1),89-101。  new window
6.Cui, Y.(20040801)。Generating optimal T-shape cutting patterns for rectangular blanks, Proceedings of the Institution of Mechanical Engineers。Journal of Engineering Manufacture,218(8),857-866。  new window
7.Cui, Y.、Liu Z.(200806)。T-shape homogenous block patterns for the two-dimensional cut-ting problem。Journal of Global Optimization,41(2),267-281。  new window
8.Cui, Y.(200511)。Dynamic programming algorithms for the optimal cutting of equal rectangles。Applied Mathematical Modeling,29(11),1040-1053。  new window
9.Cui, Y.(200502)。Exact and heuristic algorithms for staged cutting problems, Proceedings of the Institution of Mechanical Engineers。Journal of Engineering Manufacture,219(2),201-208。  new window
10.Elsa S.、Filipe, A.、J. M. Val?rio de Carvalho(201009)。An integer programming model for two-and three-stage two-dimensional cutting stock problems。European Journal of Operational Research,205(3),699-708。  new window
11.Gilnore, P.C.、Gomory, R. E.(19650201)。Multistage cutting problems of two and more dimensions。Computers & Operations Research,13(1),94-120。  new window
12.Hifi, M.、Saadi, T.(2010)。A cooperative algorithm for constrained two-staged two-dimensional cutting problems。Journal of Operational Research,9(1),104-124。  new window
13.Hifi, M.、Zissimopoulos, V.(199606)。A recursive exact algorithm for weighted two-dimensional cutting。Journal of Operational Research,91(3),553-564。  new window
14.Hifi, M.(200101)。Exact algorithms for large-scale unconstrained two and three staged cutting problems。Computational Optimization and Applications,18(1),63-88。  new window
15.Seong, G. G.、Kang, M. K.(200307)。A best-first branch and bound algorithm for unconstrained two dimensional cutting problems。Operations Research Letters,31(4),301-307。  new window
16.Tarnowski, A. G.、Terno, J.、Scheithauer, G.(1994)。Apolynornial time algorithm for the guillotine pallet-loading Problem。Information Systems Research,32(4),275-287。  new window
圖書
1.Kellerer, H.、Pferschy, U.、Pisinger, D.(2004)。Knapsack Problems。Berlin:Springer。  new window
 
 
 
 
第一頁 上一頁 下一頁 最後一頁 top
QR Code
QRCODE