面向多规格板材件的矩形工件排样方法的研究

发布时间：2018-07-03 17:17

本文选题：排样优化 + 一刀切　；参考：《广东工业大学》2015年硕士论文

【摘要】：面向多规格板材件的矩形工件排样问题(2DVSBPP)就是指给出多种规格的矩形工件与板材,要求选出合适的板材组合,将矩形工件逐一排放在板材上,力求板材的总耗损最小,总利用率最高。作为一个经典的NPC问题,2DVSBPP在工件的排样过程中,通常面临两种工艺约束：“一刀切”约束和工件可旋转性约束。本文针对多规格板材件的矩形工件排样问题,提出了一种放宽式搜索算法(Relaxed Search Algorithm, RSA),该算法支持“一刀切”约束和矩形工件可旋转约束,具体包括：1)多规格板材组合的构造算法。依据矩形工件的总面积,选择出可行的板材件组合,并将该组合按面积的增序方式排列。2)单块板材件的排样算法。提出了一种基于组化策略的单板材排样算法,将矩形工件组合成一个单元体代替工件作为排样的基本单元,再设定对工件组的定位规则,在板材件满足“一刀切”约束的条件下,对板材件进行切割；进而,使用一种“排样——切割”的递归排样结构,以利用率是否低于给定的最低利用率作为回溯条件,配合最低利用率的二分遍历式收敛,提高了单块板材件的利用率。3)放宽式搜索算法。在对板材件组合进行选取与单块板材件排样算法生成之后,按初始组合的板材件的顺序尝试排样,并逐步放宽组合的面积,从而逐步更换板材件,并使工件全部排放。4)后处理算法。通过良劣集交换的方式,对已排样板材件上矩形工件的拆分与重组,进一步提高材料利用率。使用国际通用的Benchmark案例进行测试,RSA算法于若干文献报道的算法,求解质量有所提升。基于RSA算法与企业实际生产需求,开发了一套面向多规格板材件矩形工件排样的计算机辅助排样系统。
[Abstract]:The problem of rectangular workpiece layout for multi-specification sheet parts (2DVSBPP) refers to the selection of suitable combination of rectangular workpieces and plates, which requires that the rectangular workpieces be discharged one by one on the plates, so as to minimize the total loss of the plates. The total utilization rate is the highest. As a classical NPC problem, DVSBPP usually faces two kinds of process constraints: "one size fits all" constraint and workpiece rotatability constraint in the process of workpiece layout. In this paper, a relaxed search algorithm (RSA) is proposed to solve the problem of rectangular workpiece layout for multi-specification sheet parts. The algorithm supports "one-size-fits-all" constraints and rotatable constraints for rectangular workpieces. It includes: 1) the construction algorithm of multi-specification plate combination. According to the total area of rectangular workpiece, the feasible combination of sheet parts is selected, and the combination is arranged in order of area. In this paper, a single plate layout algorithm based on histochemical strategy is proposed. The rectangular workpiece is combined into a unit body instead of the workpiece as the basic unit of layout, and then the location rules for the workpiece group are set. Under the condition that the sheet parts meet the "one size fits all" constraint, the sheet parts are cut; furthermore, a recursive layout structure of "layout-cutting" is used, with the backtracking condition of whether the utilization ratio is lower than the given minimum utilization ratio, Combined with the binary traversal convergence of the lowest utilization ratio, the utilization ratio of a single piece of plate is improved by using a 3. 3) relaxed search algorithm. After selecting the combination of sheet parts and generating the algorithm of layout of single piece of sheet, we try to arrange the parts in the order of the initial combination, and gradually relax the area of the combination, so as to replace the parts of the plate step by step. And make all the workpieces discharge 4. 4) post-processing algorithm. In order to improve the material utilization rate, the rectangular workpiece on the plank has been split and reorganized by exchanging the good and bad sets. An international benchmark case is used to test the RSA algorithm, which is reported in several literatures, and the quality of the solution is improved. Based on RSA algorithm and the actual production demand of enterprises, a set of computer aided layout system for rectangular workpiece layout of multi-specification sheet parts is developed.
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TB49

【参考文献】