基于离散化和遗传算法的皮革制造中的排样问题

采用离散化处理使排样优化过程与皮料和样片的几何信息无关，解决了不规则几何轮廓约束的困扰，研究方法特别适用于二维不规则形体在多个二维不规则平面上的优化排样。     

普通冲裁模、引伸模CAD系统的二维优化排样

本文介绍了二维优化排样的定义和单个冲裁体、引伸件二维优化排样的数学模型,讨论了原有各种排样算法的优缺点,提出并详细阐述了四种二维优化排样的新算法:DS算法、Sort算法、联接算法、变步长搜索最优方案算法,给出了新算法用于普通冲裁模、引伸模CAD系统二维优化排样的图例及数据结果。     

用于二维不规则排样的离散临界多边形模型

提出了一个用于求解二维不规则排样问题的离散临界多边形模型.Burke等人的BLF算法是求解排样问题的一种有效算法,但其算法对一些特殊实例会产生非法的解.为了解决这个问题,提出了一种基于离散临界多边形模型,并对其正确性作了严格证明.新模型是只含有点和区间的简单模型,在大大降低原问题几何复杂性的同时,也使许多启发式策略可以更容易地求解该问题.计算结果表明,基于离散临界多边型模型的排样算法是很有效的.     

二维板材圆形下料的邻居关系算法

二维圆形排样问题是工业设计与生产中经常遇到的问题.常规下料问题主要针对矩形或圆形等规则板材,常用算法包括模拟退火、遗传算法等.本文在分析规则板材下料算法的基础上,针对实际生产应用中更为复杂的、具有不规则边界板材下料问题,提出了一种基于人工下料思维的仿生下料算法--邻居关系算法.该算法具有很好的利用率和时效性,较好地满足了实际应用的需要.实际板材下料结果表明,平均面积利用率为75.56％,平均计算时间为13.84s.所得排样利用率与模拟退火算法相当,但排样运算时间大大缩小,适应了实际下料需求,已应用于某跨国企业优化下料中.     

基于遗传模拟退火算法的不规则多边形排样

将遗传授拟退火算法应用于计算机辅助排样领域，设计了一种基于遗传模拟退火技术的启发式排样算法．该算法能够处理不规则多边形的排样问题；同时，给出一种对象的几何表达方式，可以忽略高度不规则形状带来的复杂性影响．该算法通过基于遗传模拟退火算法的全局优化概率搜索，寻找排样件在排样时的最优次序及各自的旋转角度，然后采用基于左下角(BL)策略的启发式排样算法实现自动排样．     

解决二维下料问题的顺序启发式算法

求解二维下料问题即求解如何用最少的板材排入所需的全部毛坯的问题。一种基于价值修正策略的顺序启发式算法被用来生成排样方案,方案中的排样方式按单位面积价值最大生成,在各排样方式顺序生成的过程中不断修正方式中使用到的毛坯的价值。迭代调用该过程多次生成多个排样方案,从中选择最优的排样方案。通过实验证明算法的有效性。     

一种求解圆形件下料问题的启发式算法

针对二维圆形件下料问题,提出一种改进的顺序启发式算法。在生成排样方式的过程中,采用价值修正策略不断修正当前排入圆片的价值,使之趋于合理,选取价值最大的排样方式组成当前排样方案,迭代调用该过程多次,从中选取最优的排样方案。实验结果证明,与线性规划算法相比,该算法更有效。     

应用精确两阶段排样图的板材下料算法

求解基于精确两阶段排样图的二维下料问题,用最小的板材成本,生产出所需要的全部毛坯。将顺序启发式算法和排样图生成算法相结合,顺序生成排样方案中的各个排样图;采用顺序价值修正策略,在生成每个排样图后修正其中所含各种毛坯的价值。经过多次迭代生成多个排样方案,从中选择最好者。实验计算时与商业软件和文献算法相比较,结果表明所述算法可以更为有效地减少板材消耗。     

基于最优子段的矩形优化排样

为有效解决企业实际生产中的矩形优化排样问题,对矩形优化排样算法进行研究, 给出基于最优子段的矩形优化排样算法,有效解决了企业实际生产中的长板矩形优化排样问题。 首先基于动态规划算法求出所有小于剪床刀刃长度的最优子段的最佳排样方式,然后以所求的最 优子段作为可用子段在长板上进行优化排样,并将矩形优化排样问题转化为完全背包问题。最后 基于分支定界技术的整数规划算法对其进行求解。企业应用实例表明该算法在解决长板矩形优化 问题方面优于其他算法。     

基于曲率匹配和递归排序的自适应排样算法

为提高盘状毛坯的使用率,提出一种口腔修复加工中模型边界在盘状毛坯中的排样算法,主要包括边界匹配、多边形定位及递归排序.首先基于协方差矩阵及矩阵SVD分解算法对模型多边形进行分段,并采用等弧长曲线采样曲率匹配确定待匹配模型边界;然后依毛坯边界角度分布及沿圆周排样的思想确定模型轮廓的旋转和平移定位;最后提出一种基于包络率的递归排序算法,对在排样过程中发现的大孔洞可动态地调整排样顺序.实验结果表明,该算法可以处理不规则模型边界在任意形状毛坯中的排样,能有效地降低加工成本.     

Genetic Algorithm Coding Methods for Leather Nesting

The problem of placing a number of specific shapes in order to minimise waste is commonly encountered in the sheet metal, clothing and shoe-making industries. The paper presents genetic algorithm coding methodologies for the leather nesting problem which involves cutting shoe upper components from hides so as to maximise material utilisation. Algorithmic methods for computer-aided nesting can be either packing or connectivity driven. The paper discusses approaches to how both types of method can be realised using a local placement strategy whereby one shape at a time is placed on the surface. In each case the underlying coding method is based on the use of the no-fit polygon (NFP) that allows the genetic algorithm to evolve non-overlapping configurations. The packing approach requires that a local space utilisation measure is developed. The connectivity approach is based on an adaptive graph method. Coding techniques for dealing with some of the more intractable aspects of the leather nesting problem such as directionality constraints and surface grading quality constraints are also discussed. The benefits and drawbacks of the two approaches are presented.     

Image processing techniques for leather hide ranking in the footwear industry

The subjective assessment of finished leather hide has resulted in much argument, wasted costs and disruption of production schedules in both the tannery and leather footwear industry. Leather has attracted much research work worldwide; however, to date no objective quality assessment methodology is available, let alone an automatic assessment system. In this project, a machine-vision-based approach to grading leather hide has been developed. The image of a given castle hide was acquired using the developed machine vision system. A map of the different types of defect contours contained in the hide was extracted. Algorithms were then formulated enabling the computerization of the quarter rule, a standard method for grading leather hide in the footwear industry. Typical results from the developed grading process include the leather cuttable areas within a given hide, taking into account various types of defects, and the contour map of defects, which in fact is a vital input to any computerized shoe-part nesting system. The success of automatically grading leather hide in this project will not only provide the tanner with a means of accurately defining the price of a leather hide but also greatly assist the footwear manufacturer in the optimal nesting of irregular shoe parts within a given hide.     

Two-dimensional cutting stock problem research: A review and a new rectangular layout algorithm

The two-dimensional cutting stock problem addresses the allocation of a required bill of materials onto stock sheets in a manner that minimizes the trim losses. This paper surveys the progress made on the study of the problem from the original contributions by Gilmore and Gomory in the mid-1960s to the present. Conclusions are for these algorithms to find greater application in industry, one must consider the allocation of both regular and irregular shapes. Moreover, the objective of minimizing the trim losses is not an adequate performance measure when the cutting department is placed in the perspective of the entire manufacturing system. The costs of inventory and production have to be included in the objective to be minimized in order to ensure maximum production efficiency. In addition, an algorithm based on the first fit decreasing heuristic¹ is presented to achieve layouts of rectangular bills of material on rectangular stock sheets, and its performance is examined. A number of nesting algorithms are currently in use in industry, but virtually all of these systems are considered to be highly proprietary and specific. The cutting stock problem has been variously adapted to applications in numerous industries. From its original form described later, it has been modified for use in paper, lumber, cloth, metal, leather stamping and other industries. In each case, the problem has been reformulated to suit the needs of the specific industry.     

基于样图的排样及其样图检索方法

为解决不规则图形排样问题,讨论了基于实例(样图)的推理方法在零件排样问题中的应用,给出了基于样图的排样系统结构.此方法的一个关键问题是在已知待排的零件组和板料的前提下,如何从样图库中检索出相应样图的图形匹配方法.为此提出了基于图形(组)简化骨架的模式编码的串间Findler距离的图形(组)之间相似性检索算法,并给出了算例验证.     

A heuristic for nesting problems of irregular shapes

Layout has a close relationship with product cost in the vein of how to most efficiently cut product patterns from raw materials. This is the so-called “nesting problem”, which occurs frequently in sheet metal and furniture industries, wherein material utilization needs to be maximized. In this paper, a quick location and movement (QLM) algorithm is proposed to solve the situation of irregular shapes nested on multiple irregular sheets. This approach includes two major parts: it first approximates irregular shapes to a polygon with the use of a cluster of straight lines, and second, it arranges the approximated shapes one-by-one with the proposed step-by-step rule. Finally, this study investigates and compares examples presented by other authors. The results show that the QLM algorithm takes less time to calculate a layout and the material utilization efficiency is higher compared to other methods.     

改进临界多边形生成算法

在Burke等人提出的用于求解临界多边形的移动碰撞算法基础之上,提出了一种更加高效的求取NFP的改进算法。该算法大大降低了问题的几何复杂性,简化了计算最小移动距离的方法,使许多启发式策略可以更加容易地与该算法结合来求解二维排样问题。实例验证了改进算法是有效且可行的,已应用于皮革自动排样软件中。     

A Hybrid Circular Queue Method for Iterative Stencil Computations on GPUs

In this paper,we present a hybrid circular queue method that can significantly boost the performance of stencil computations on GPU by carefully balancing usage of registers and shared-memory.Unlike ea...     

New constructive algorithms for leather nesting in the automotive industry

In this paper, we address one of the hardest two-dimensional cutting stock problems that can be found in industry. The problem is called the Leather Nesting Problem, and it consists in finding the best layouts for a set of irregular shapes within large natural leather hides with highly irregular contours, and which may have holes and quality zones. Here, we focus on a real case from the automotive industry, and in particular on the production of car seats. In this case, the irregular shapes that have to be cut from the hides are pieces of the car seats.The practical relevance of this problem, and the potential value of the savings that good solutions may generate, contrasts with the very small number of contributions that have been reported in the literature. In this paper, we aim to contribute to the efficient resolution of this problem by exploring in depth many new different constructive procedures. Our approaches rely on the computation of no-fit polygons, and try to use the information provided by these polygons as much as possible. Different strategies for sorting, selecting and placing the pieces, and for evaluating the placement of these pieces are proposed and discussed. We also report on an extensive set of computational experiments using real instances. To evaluate our approaches, we applied the real criteria used by companies operating in this sector. These experiments show that our approaches can generate very high quality layouts within the same time limits as those needed by human operators.     

多方向模板变分模型的单幅图像超分辨率重建

目的 为了增强图像超分辨率重建的准确性,克服传统插值所产生的边缘模糊与边缘锯齿等负面效果,提出一种基于多方向模板变分模型的单幅图像超分辨率重建方法。方法 首先构建体现28个方向的多方向模板对输入图像的轮廓方向进行计算,同时通过将TV模型引入到图像轮廓的估计中来确定边缘轮廓的最优方向;在此基础上通过进行基于所提出的多方向模板的图像插值来实现图像的超分辨率重建。结果 对比基于活动轮廓的图像边缘插值方法重建的经典高分辨率测试图像,本文方法在平均峰值信噪比和平均结构相似度方面分别提高了1.578 dB和 0.030 02 dB。结论 本文方法可以有效地克服传统插值方法所产生的边缘模糊和边缘锯齿化等负面效果,也避免了较少方向模板所带来的边缘和纹理丰富区域的纹理失真现象,可以取得较好的重建效果。