【作者】 黄红兵；

【导师】 崔耀东；

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

【摘要】 随着中国加入WTO,制造行业的企业面临着更为激烈的市场竞争。为了在竞争中立于不败之地,企业必须想方设法提高经济效益,而提高经济效益的重要途径之一就是通过提高材料的利用率来降低成本。矩形件排样在工业上有广泛的应用,目标是使下料过程中的切割损失减少到最少,使得原材料的利用率最高。优化排样算法的研究既有实际应用价值,又有理论意义。矩形排样问题属于组合最优化问题和NP完全问题,因为存在计算上的复杂性,在一定时间内求其精确全局最优解是相当困难的。对于矩形排样问题,任何算法都难以保证总能得到最优解,目前解决的方法多为各种启发式算法。提高原材料利用率问题是一个系统工程问题,需要从生产管理、优化下料、支持决策等方面提供完备的一体化解决方案。其中优化下料环节中,构造有效的优化算法是关键。矩形件排样不仅适用于矩形零件的排放,而且也是不规则零件排放的基础。本文研究的问题是无约束非剪切单一卷材矩形件的优化下料,其中卷材为定宽无限长,要排放的矩形件数量和规格都是已知的,要求在排放完所有给定矩形件的前提下使所消耗的卷材长度最小。遗传算法是借鉴生物的自然选择和进化机制的一种全局优化自适应概率搜索算法,具有快速随机的全局搜索能力。对于非常复杂、高度非线性问题的优化求解,表现出比其它传统优化方法更优越的性能,是21 世纪智能计算中的核心技术之一。本文对遗传算法做了系统介绍,包括遗传算法的特点、基本实现技术等。对求解矩形件优化排样问题的遗传算法的设计及具体实现进行了详细讨论。本文所做的主要工作如下: 分析了排样问题的研究现状,对中外学者在矩形件优化排样方面提出的多种算法进行了认真的比较,在矩形件排放算法-“基于最低水平线的搜索算法”基础上,提出了一种改进算法:“基于最低水平线的空闲区域可再利用搜索算法”,它克服了其它排放算法对某些排样图不能给出的缺点,满足“最左最下”条件。改进算法和原算法相比,改进之处表现在:能够对最低水平线发生提升时产生的废弃空闲区域进行回收利用,通过对矩形件排放过程中动态产生的空闲区域的位置关系进行判断,改进算法能够对相邻的空闲区域进行有效合并,通过对空闲区域进行适当的填充从而实现对空闲区域的再利用,因此能够在一定程度上提高卷材的利用率。通过比较要排放矩形件的长宽与空闲区域的尺寸大小,最终确定矩形件的较优排放次序及矩形件在卷材上的确切排放位置。本文把“基于最低水平线的空闲区域可再利用搜索算法”和遗传算法结合起来,共同求解矩形件优化排样问题:先通过遗传算法确定矩形件较优的排放顺序和排放方式,然后按照“基于最低水平线的空闲区域可再利用搜索算法”生成排样图,通过比较不同的矩形件排放序列对应的卷材利用率,最终得到较优的排样方案。根据提出的改进算法,开发出了计算机辅助优化排样系统,测试数据表明了改更多还原

【Abstract】 After China’s accession to the World Trade Organization ,manufacturing enterprise face more intensive market competition. In order to win the market ,one important task is to increase economic income ,which can be realized by decreasing production cost. Improving material usage may reduce the costs of production and thus it is an efficient way to increase the profits of the enterprises. Layout of rectangle parts has been widely used in various industries . Cutting of two-dimensional(2-D) shaped parts from 2-D sheets ,with a minimum wastage of materials is an important task. The research of optimizing cutting stock problem is to study how to generate cutting patterns to improve material usage .So research on the problem is of importance in theory and practice. Rectangular packing problem(RPP) is a combinatorial optimization and NP-complete problem. It is difficult to find its exact global optimum for such a problem because of the high complexity of computation. The traditional goal of RPP is to minimize the trim loss. For the rectangular packing problem ,no algorithm is sufficient to solve the problem . Up to now there are varieties of heuristic algorithms to solve the rectangular packing problem because of its high complication. Many factors should be considered to get a good solution, such as production management, cutting stock process, and decision support. For the cutting stock process, the key problem is to construct an efficient algorithm . Research on the rectangular packing problem not only deals with the layout problem of a set of 2D rectangular parts onto a rectangular object but also plays important role in solving of irregular cutting stock problem . The unconstrained two-dimensional non-guillotine cutting problem consists of packing rectangular pieces of predetermined sizes into a sheet ,which is restricted in width but infinite in length, where any cuts that are made are unrestricted . The objective of most solution techniques is to find ‘cutting pattern ’that minimize the unused area(trim loss) .This paper discussed this problem in detail. Genetic Algorithm (GA) is a method for searching for the optimum solution to a complex problem , based on the mechanics of natural selection, the process of evolution .It has the ability of doing a global searching quickly and randomly . It is flexible and robust. In the aspect of solving large, non-linear and poorly understood problems where expert knowledge is scarce or difficult to encode and traditional methods fail, GA has great advantages. It is one of kernel techniques related with intelligent computing in 21 century. This paper introduced genetic algorithm systematically, which include the relationship between GA and natural evolution and the characteristics of genetic algorithm , basic implement techniques of GA and so on .The design and implement of GA used to solve the rectangular packing problem are also discussed in detail. The primary work of this paper as follows:First ,we analyze the actuality of the packing problem ,the algorithms of layout of rectangle parts mostly in use were compared . On the basis of the Lowest Horizontal Line –Search Algorithm(LHL-SA) , an improved algorithm for rectangular packing problem is proposed in this paper , that is, Lowest Horizontal Line-Waste Area Can Reused Searching Algorithm(LHL-WARSA),which meets the BL condition and overcome the shortcomings of other algorithm for some patterns . The proposed algorithm can combine small waste areas that produced during the process of packing to large areas ,then use them again,so it can improve the using ratio of material more efficiently . The size of each rectangle is compared with that of waste area , therefore better sequence and better location of each rectangle on the sheet can be obtained . We solve the rectangular packing problem by applying the genetic algorithm .The most important is that we use the genetic algorithm to find the sequence in which the small rectangles are packed ,then we used the improved algorithm advanced in this paper to pack the rectangular pieces .By comparison ,the best cutting pattern was obtained. Based on the proposed algorithm , a system of computer-aided optimizing nesting was realized .The experimental results indicate that the improved algorithm is flexible and effective. Research in this dissertation will contribute to economize raw materials , reduce operating costs and improve the enterprise’s economic efficiency. In the end , author summarizes the research on rectangular packing problem and puts forward the orientation of the next work in the future.更多还原