Research on and Application of Cutting Stock Problems
文献类型：学位论文
| 作者 | Song X(宋翔) |
| 学位类别 | 博士 |
| 答辩日期 | 2004-12-20 |
| 授予单位 | 中国科学院沈阳自动化研究所 |
| 授予地点 | 中国科学院沈阳自动化研究所 |
| 导师 | 聂义勇 ; 储诚斌 |
| 关键词 | cutting stock problem dynamic programming hill climbing sequential heuristic procedure incompletely enumerative |
| 其他题名 | 下料问题的研究与应用 |
| 学位专业 | 机械电子工程 |
| 中文摘要 | This thesis develops and investigates heuristic approaches to the classical and practical Cutting Stock problems. In particular, we concentrate on hill climbing and dynamic programming techniques, incompletely enumerative and sequential heuristic procedures.There are in total four cutting problems to be solved in this thesis. They are 1D and 2D Knapsack Problems, 1D and 1.5D Cutting Stock Problems. In 1DKP, we develop a hill climbing method, with high approximation ratio and relatively low computational complexity in solving the 1DKP of special data structure as we have described. In 2DKP, a heuristic dynamic-programming method is proposed for solving efficiently an unconstrained non-staged 2D knapsack problem. Compared with the traditional dynamic programming, the algorithm gives a high percentage of optimal solutions (93%) with a much lower computational complexity. The worst-case performance of the algorithm is evaluated. Some theoretical analyses for the algorithm are performed. Computational results are given for small and medium-sized problems. After solving the 1D and 2D Knapsack Problems, we focus our attention on a kind of 1DCSP proposed by a factory in Macao. Although this is a classical 1DCSP, the problem has so large a size that tradition Column Generation technique is no longer applicable. Thus we developed an incompletely enumerative algorithm to solve the problem. Theoretical analyses and numerical experiments show that this incompletely enumerative algorithm is an approximate implicitly enumerative solution.Finally, an iterative sequential heuristic procedure is developed to solve the general real-life 1.5DCSP. An SHP algorithm is used firstly to generate a feasible solution to the general problem. Then the SHP is improved into an iterative SHP, in which different strucures for a single cutting pattern are found by adjusting four adjustable parameters given in the SHP. With this method, the search space is enlarged and the probability that an optimal solution is found is highly improved. |
| 索取号 | F406.5/S88/2005 |
| 公开日期 | 2012-08-29 |
| 产权排序 | 1 |
| 分类号 | F406.5 |
| 源URL | [http://ir.sia.ac.cn/handle/173321/9451]  |
| 专题 | 沈阳自动化研究所_工业信息学研究室_工业控制系统研究室 |
| 推荐引用方式 GB/T 7714 | Song X. Research on and Application of Cutting Stock Problems[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2004. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。