查詢結果分析
相關文獻
頁籤選單縮合
題名 | An Exact Algorithm for Large-scale Unconstrained Three Staged Cutting Problems with Same-size Block Requirement= |
---|---|
作者 | Ji, Jun; Lu, Yi-ping; Cha, Jian-zhong; Yu, Jia-qing; Cui, Yao-dong; |
期刊 | International Journal of Information and Management Sciences |
出版日期 | 20120300 |
卷期 | 23:1 2012.03[民101.03] |
頁次 | 頁59-78 |
分類號 | 494.542 |
語文 | eng |
關鍵詞 | Cutting problems; Dynamic programming; Knapsack problem; Same-size block; |
英文摘要 | 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. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。