二维剪切下料问题的三阶段排样方案优化算法研究

发布时间：2018-08-28 07:55

【摘要】：下料问题是一种计算复杂度很高的组合优化问题,具有很深的工程应用背景,如机械制造的金属切割、家具业的木材切割、建筑业的玻璃切割、印刷业的排版、化工业的塑料加工、服装业的布料剪裁等都属于此类应用。优化算法可以为下料问题提供合理的排样方案,降低材料成本,简化切割操作,从而降低生产成本,提高企业竞争力。本文以二维剪切下料问题为研究对象,从以消耗的板材数量最少为目标的三阶段同质(3H)排样方案开始,扩展到考虑余料标准化的排样方案,最后研究了考虑余料标准化的余料下料问题。达到板材用量最少的同时,提高余料的二次利用价值和可用性。并在后继生产周期中合理优先使用余料,进一步减少板材用量和材料浪费,减少废料对环境的污染。本文从以下三个方面研究二维剪切下料问题,主要的工作和创新点包括:(1)针对普通的二维剪切下料问题,采用迭代顺序价值修正算法,迭代生成多个3H排样方案,从中选择板材用量最少者作为剪切下料问题的解。将排样方案分解成多个3H排样方式的顺序求解。采用递推过程快速生成排样方式,通过毛坯初始价值调整、排样方式毛坯价值修正和代际价值修正,改变毛坯在排样过程中的优先顺序,引导不同种类毛坯在不同排样方式中均衡分布。多个系列、大量算例的实验结果表明,迭代顺序价值修正算法特别适用于中大规模的应用场合,生成的三阶段排样方案优于文献算法和商业软件的同类三阶段排样方案,其效果不仅体现在节省板材用量和节省计算时间上,而且体现在剪切切割操作的简化上。(2)针对考虑余料标准化的二维剪切下料问题,采用基于束搜索的余料聚集算法,将余料汇集于板材的右侧,形成与板材同宽的标准余料。束搜索节点的评价算子包含已填充子板的局部排样方式价值、剩余子板的估计价值或余料的二次利用价值,以递推生成的初始排样方式作为过滤器删除部分差节点。实验结果表明,束搜索算法可以快速聚集余料碎片形成大的标准余料,生成的3HL排样方式在毛坯价值上比其他启发式算法生成的同类排样方式高。而在相同毛坯价值下,3HL排样方式与文献中的其他剪切排样方式相比,废料碎片少,可用标准余料的面积更大,有利于余料的管理和使用。(3)针对考虑余料标准化的余料下料问题,阐述两种启发式算法:ISVCL算法和ISVC-BS算法。ISVCL算法以材料成本(板材总面积-余料总面积)最少为目标,在迭代顺序价值修正算法的基础上增加了标准余料生成和优先使用。ISVC-BS算法结合了迭代顺序价值修正算法和束搜索算法,先通过束搜索算法试排样部分毛坯,再利用迭代顺序价值修正算法搜索剩余毛坯的板材用量最少排样方案,并由束搜索算法对材料利用率低的排样方式进行余料聚集。按最大板长生成虚拟排样方式,按性价比最高的原则选择排样方式。通过设置余料的使用系数,使余料比板材具有更高的使用优先权。单周期的实验结果表明,两种启发式算法在生成标准可用余料的同时,排样方案的板材用量并没有增加。ISVC-BS算法达到最少板材用量的迭代次数比ISVCL算法要少,相同迭代次数下生成的标准余料更大。多周期的实验结果表明,ISVC-BS算法可有效用于余料下料问题,将标准余料用于后继生产周期,减少板材的用量,降低长期生产成本。
[Abstract]:Cutting stock problem is a kind of combinatorial optimization problem with high computational complexity. It has a deep engineering application background, such as metal cutting in mechanical manufacturing, wood cutting in furniture industry, glass cutting in construction industry, typesetting in printing industry, plastic processing in chemical industry, cloth cutting in garment industry, etc. In this paper, the two-dimensional shearing blanking problem is studied, starting with the three-stage homogeneous (3H) blanking scheme aiming at minimizing the number of consumed sheets, and extending to the blanking scheme considering the standardization of surplus materials. Finally, the problem of blanking leftovers considering the standardization of leftovers is studied. The minimum amount of leftovers is achieved, and the secondary utilization value and usability of leftovers are improved. The main work and innovations of the two-dimensional shearing blanking problem include: (1) Aiming at the ordinary two-dimensional shearing blanking problem, the iterative sequential value correction algorithm is used to iteratively generate several 3H layout schemes, from which the least amount of sheet metal is selected as the solution of the shearing blanking problem. Through adjusting the initial value of the blank, modifying the value of the blank and intergenerational value of the blank, changing the priority order of the blank in the layout process, guiding the balanced distribution of different kinds of blanks in different layout methods. Positive algorithm is especially suitable for medium and large-scale applications. The generated three-stage layout scheme is superior to the similar three-stage layout scheme of literature algorithm and commercial software. Its effect is not only reflected in saving sheet metal consumption and computing time, but also in the simplification of cutting operation. (2) Two-dimensional layout considering the standardization of residual materials. For the shearing blanking problem, the residue aggregation algorithm based on bundle search is used to aggregate the residue on the right side of the sheet to form the standard residue of the same width as the sheet. The experimental results show that the bundle search algorithm can quickly aggregate the residual fragments to form large standard residues, and the generated 3HL layout method has higher blank value than other heuristic algorithms. However, under the same blank value, the 3HL layout method is compared with other cutting methods in the literature. Compared with the cutting layout method, the scrap fragments are less and the usable area of standard scrap is larger, which is conducive to the management and use of scrap. (3) Aiming at the problem of scrap blanking considering the standardization of scrap, two heuristic algorithms are presented: ISVCL algorithm and ISVC-BS algorithm. ISVC-BS algorithm combines iterative sequential value correction algorithm and bundle search algorithm. First, the bundle search algorithm is used to try out part of the blank layout, and then the iterative sequential value correction algorithm is used to search the least amount of blank layout scheme for the remaining blank. By setting the coefficient of usage of the surplus material, the surplus material has a higher usage priority than the plate material. One-cycle experimental results show that the two heuristic algorithms are in the process of generating the standard. The ISVC-BS algorithm has fewer iterations than ISVCL algorithm, and the standard residue generated under the same iterations is larger. The multi-period experimental results show that ISVC-BS algorithm can be effectively used for the blanking problem of the residue, and the standard residue is used for the subsequent generation. Production cycle, reduce plate consumption, reduce long-term production costs.
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TB497

【相似文献】