下料问题的研究与应用
文献类型：学位论文
| 作者 | 宋翔 |
| 学位类别 | 博士 |
| 答辩日期 | 2004-12-20 |
| 授予单位 | 中国科学院沈阳自动化研究所 |
| 授予地点 | 中国科学院沈阳自动化研究所 |
| 导师 | 聂义勇 ; 储诚斌 |
| 关键词 | 下料 动态规划 爬山 顺序启发式 不完全枚举 |
| 其他题名 | Cutting Stock Problems: Research and Application |
| 学位专业 | 机械电子工程 |
| 中文摘要 | 本文中共求解了四类下料问题。它们为1维，2维背包问题，1维和1.5维下料问题。在1维背包问题中，本文给出了一个爬山算法来解决这类问题。实验结果和理论分析表明，该算法在解决这类特殊数据结构的背包问题时具有很高的近优率，较低的计算复杂度。在2维背包（下料）问题中，本文提出一个启发式动态规划方法来解决这一2维背包问题。与传统的动态规划方法相比，该方法大大降低了计算复杂度，同时以较高的比率(93%)得到最优解。在理论上，本文对该算法的最坏情形进行了分析，并给出了相关理论结果。通过对中小型下料问题的数值实验对该算法的优越性进行了验证。本文给出不完全枚举方法对经典的1维下料问题进行求解。对问题的算法进行了理论上的论证，论证结果表明，采用该算法可以得到某些特殊情形下原问题的最优解。理论分析和数值实验均表明该不完全枚举解法是一种近隐式枚举方法。文中所研究的1.5维下料问题具有多目标，多约束的特性，在所获得的文献中尚没有现成的算法可以遵循。本文根据问题特点首先采用顺序启发式解法(SHP)得到问题的较好的可行解。然后通过改变SHP方法中引入的四个可调整参数的取值，将SHP方法改进为迭代启发式解法，使问题的搜索空间扩大，提高了得到问题最优解的概率。 |
| 索取号 | F406.5/S88/2005 |
| 英文摘要 | 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. |
| 语种 | 中文 |
| 公开日期 | 2012-08-29 |
| 产权排序 | 1 |
| 分类号 | F406.5 |
| 源URL | [http://ir.sia.ac.cn/handle/173321/9477]  |
| 专题 | 沈阳自动化研究所_工业信息学研究室_工业控制系统研究室 |
| 推荐引用方式 GB/T 7714 | 宋翔. 下料问题的研究与应用[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2004. |
入库方式： OAI收割
来源：沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。