【作者】 宋晓霞；

【导师】 崔耀东；

【作者基本信息】 广西师范大学 ， 计算机软件与理论， 2005， 硕士

【摘要】 优化排样是研究如何下料使得原材料利用率最高,在实际生产中应用广泛。服装制造业、皮革制品制造业、体育用品制造业、机械制造业等行业中存在大量的下料问题。国内有成千上万家这样的企业,绝大部分企业仍处于手工下料阶段,下料利用率较低,造成原材料的浪费。因此有效提高原材料的利用率,降低生产成本,是增加企业效益的有效途径之一。提高原材料利用率问题是一个系统工程问题,需要从生产管理、优化下料、决策支持等方面提供完备的一体化解决方案。这些环节中优化下料方案是提高原材料利用率最直接的方法,而优化下料方案的关键是构造有效的优化排样算法。本文研究的是圆形件排样问题,是二维下料问题的一个分支。国内外对二维下料问题研究给予了足够的重视,多为矩形毛坯和二维不规则性毛坯的排样问题,而对圆形排样问题的研究较少。实际当中遇到圆形件排样问题时,常采用手工排样方案下料,这样的下料方法容易造成原材料的浪费。因此本文在借鉴其它二维下料问题算法的基础上,提出适合圆形件排样的算法。理论上可以采用传统的动态规划、线性整数规划方法、爬山法、分枝定界法等排样算法;也可以采用禁忌搜索、模拟退火算法、遗传算法、神经网络算法等现代优化算法。而传统的寻优方法只能解决实际应用当中的简单问题,对于稍微复杂的问题就需要向启发式的优化方法寻求解决方案。本文研究的圆形件排样问题,是指将卷材切成若干圆形毛坯,使所产生的废料尽可能地少。由于卷材长度远远大于毛坯直径,在算法设计时可以将其作为无限长处理。所排零件包括多种尺寸的圆形件,其需求必须精确满足。该问题已经被证明属于相当困难的NP 完全问题。本文提出一种排样算法(简称ASA),按指定的顺序,依次将圆形毛坯排列到卷材上。对于当前要排入卷材的毛坯,ASA 首先将可行位置的搜索范围进行离散,也就是选择搜索范围的一个子集进行搜索。这个子集比文献中的算法所考虑的搜索范围大,有利于提高解的质量。然后利用圆形件的形状特性,排样方式的性质等,避免对搜索范围中部分不可行区域的搜索,以缩短求解时间。ASA按指定的顺序将圆形毛坯排入卷材,因此所得排样方案的材料利用率,取决于给定的毛坯顺序。本文采用混合遗传算法(简称HGA)指导搜索,以考虑多种毛坯顺序。每种顺序对应一个排样方案,从中可选出材料利用率高的排样方案。基于毛坯编号进行编码;将随机技术与经验相结合生成初始群体;在进化更多还原

【Abstract】 The research on the cutting stock problems is to study how to generate cutting patterns to maximize material usage. Cutting stock problems appear in many industries, such as the industries of rag trade, leather, sports goods, mechanical manufacturing, and so on. There are thousands of enterprises which have cutting stock problems in our country, but the majority of them use hand-generated cutting patterns in the cutting process. As a result, the material usage is low and the amount of waste is large. Improving material usage may reduce the costs of production and it is an efficient way to increase the profits of the enterprises. Improving material usage is a systematic engineering. Many factors should be considered to get a good solution, such as production management, optimizing the cutting process, and decision support. The most direct method to improve material usage is to optimize the cutting scheme, and the key is to develop efficient algorithms. The two-dimensional cutting problems of rectangular and irregular blanks have been studied intensively, but the cutting problems of circular blanks have drawn little attention. So this paper focuses on the cutting problem of circular blanks, which is a branch of two-dimensional cutting problems. Hand-generated cutting patterns are often used in the cutting process of circular blanks in practice, which produce more waste. This paper presents an algorithm for the cutting problem of circular blanks. In theory, both conventional layout algorithms, such as dynamic programming, integer programming, linear programming, hill-climbing approach, branch and bound approach, and modern optimization algorithms such as tabu search, simulated annealing, genetic algorithms and neural networks, may be adopted. Conventional optimizing approaches can merely solve some simple problems in practice. As to the more complicated problems, heuristic algorithms should be adopted. The cutting problem of circular blanks (CPCB for short) discussed is to cut a roll into many demanded circular blanks, so as to minimize waste. The roll length is much larger than the sizes of the blanks. It may be taken as infinite in developing the algorithms. The blanks may be of different sizes, and the demand for each type must be meet exactly. This problem has been shown to be NP complete. This paper presents an algorithm (ASA for short) for the CPCB. It arranges the blanks one after the other according to a given order. A feasible position must be determined for each blank. The searching space consists of only discrete positions that form a subset of the space that should be searched. This searching space is larger than that used by the algorithms reported in the literature. This is helpful for improving the solution. The characteristics of the blank shape and the cutting pattern are analyzed to avoid considering some regions of the searching space that do not contain feasible positions. This may shorten the time required to solve a problem. ASA arranges the blanks in the roll according to a fixed order. Therefore, the material usage of the solution depends on the given order. A hybrid genetic algorithm (HGA for short) is used to generate different orders, each of which relates to a cutting pattern. The one of the highest material usage is selected from these patterns. The coding of the string is based on the integer indexes of the blanks. The initial population is generated both randomly and empirically. The best one of the strings considered so far is kept as the current best solution. The tournament selection process that chooses the strings considering their actual fitness values is used. The widely used sequencing cross operator and the swapping mutation operator are used. When the evaluation process is about to be terminated, the hill-climbing approach is used to consider new strings that are generated from the current best string, so as to improve the solution further. Both benchmark and random problems are used to test the algorithms. The computational results of the benchmark problems indicate that the algorithms can generate cutting patterns of higher material usage in shorter times, and are comparable to those presented by Hifi who is a famous French scholar in the domain of cutting and packing. The computational results of the random problems indicate that the algorithms of this paper can generate cutting patterns of higher material usage, and the computation time is reasonable for most practical cutting problems.更多还原