A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting
文献类型：期刊论文
| 作者 | Song X(宋翔); Chu CB(储诚斌); R. Lewis; Nie YY(聂义勇); J. Thompson |
| 刊名 | European Journal of Operational Research
 |
| 出版日期 | 2010 |
| 卷号 | 202期号:2页码:368-378 |
| 关键词 | Heuristic Dynamic programming 2D cutting |
| ISSN号 | 0377-2217 |
| 产权排序 | 1 |
| 中文摘要 | In this paper, a dynamic programming-based recursive method is proposed for solving an unconstrained 2D rectangular cutting problem. The algorithm is an incomplete method, in which some intricate cutting patterns may not be obtained. The worst case performance of the algorithm is evaluated and some theoretical analyses for the algorithm are performed. Compared to traditional dynamic programming, this algorithm gives a high percentage of optimal solutions (94.84%, 86.67% and 77.83% for small, medium and large sized unweighted instances, 99.67%, 99.50% and 97.00% for small, medium and large sized weighted instances) but features a far lower computational complexity. Computational results are also presented for some known benchmarks. |
| WOS标题词 | Social Sciences ; Science & Technology ; Technology |
| 类目[WOS] | Management ; Operations Research & Management Science |
| 研究领域[WOS] | Business & Economics ; Operations Research & Management Science |
| 关键词[WOS] | 2-DIMENSIONAL KNAPSACK-PROBLEMS ; TABU SEARCH ALGORITHM ; PACKING PROBLEMS ; STOCK PROBLEMS ; BLOCK PATTERNS ; GRAPH APPROACH ; GENERATION ; TYPOLOGY |
| 收录类别 | SCI ; EI |
| 语种 | 英语 |
| WOS记录号 | WOS:000271936000007 |
| 公开日期 | 2012-05-29 |
| 源URL | [http://ir.sia.cn/handle/173321/7293]  |
| 专题 | 沈阳自动化研究所_机器人学研究室 |
| 推荐引用方式 GB/T 7714 | Song X,Chu CB,R. Lewis,et al. A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting[J]. European Journal of Operational Research,2010,202(2):368-378. |
| APA | Song X,Chu CB,R. Lewis,Nie YY,&J. Thompson.(2010).A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting.European Journal of Operational Research,202(2),368-378. |
| MLA | Song X,et al."A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting".European Journal of Operational Research 202.2(2010):368-378. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。