改进的矩形毛坯三块排样方式及其算法

致力于改进矩形毛坯三块排样方式的生成算法,采用三种策略缩小解的搜索范围,并将该算法与线性规划相结合形成排样方案生成算法,用于求解大规模矩形毛坯排样问题.通过实验证明,与二阶段、T形、两段、三阶段排样算法相比,排样方案生成算法生成的排样方案虽然板材利用率稍低,但排样方案简单,能够简化切割工艺.     

简化同尺寸矩形毛坯排样方式的动态规划算法

同尺寸矩形毛坯排样方式的最优性包括毛坯数量最优性和切割工艺最优性。前者是指排样方式中所含毛坯数最大;后者是指在所有实现毛坯数量最优性的排样方式中,切割工艺最为简单。采用条带数衡量排样方式的复杂性,用动态规划算法生成条带数最少的最优排样方式。实验计算结果表明,所述算法能够明显简化下料工艺,对指导生产实践具有较重要的意义。     

一种高效的矩形套裁排样的带填充排样算法

提出一种带填充排样算法,实现矩形毛坯套裁排样。该算法首先用水平剪切线将板材分层,每层的宽度和板材宽度相同,高度和层最左端的主毛坯高度相同;通过调用两个递归过程确定最优排样方式,第一个过程确定每层左端的主毛坯,第二个过程确定层右端区域的毛坯排列方式。采用分支定界技术缩小搜索空间。实验计算结果说明所述算法比文献中最近报道的几种算法都有效。     

生成矩形毛坯最优T形排样方式的递归算法

讨论矩形毛坯无约束两维剪切排样问题．采用由条带组成的T形排样方式，切割工艺简单．排样时用一条分界线将板材分成2段，同一段中所有条带的方向和长度都相同．一段含水平条带．另一段含竖直条带．采用递归算法确定分界线的最优位置以及每段中条带的最优组合．以便使下料利用率达到最高．采用大量随机生成的例题进行实验，结果表明该算法在计算时间和提高材料利用率2方面都较有效．     

生成最优单毛坯条带T型布局方式的精确算法

为解决大规模矩形件布局问题,提出一个生成单毛坯条带T型布局方式的精确算法。该算法不仅可在合理时间内取得好的优化结果,而且在满足实际下料工艺的同时化简了切割工艺。该算法首先确定最优单毛坯条带,然后通过求解一维背包问题确定单毛坯条带在级中的布局方式和级在段中的最优布局方式,最后选择两个最优段生成布局方式。通过文献中的63道基准测题,将该算法与5种著名算法(经典两阶段、普通T型、同质块两阶段、普通布局算法和启发式算法TABU500)进行了比较。实验结果表明,该算法在计算时间和材料利用率两方面都有效。     

矩形毛坯最优三块排样的新算法

针对矩形毛坯二维下料问题,提出采用三块排样的下料算法,以达到最小化板材消耗量和简化切割工艺的目标。该算法将列生成法和排样方式生成算法相结合,生成一个含多个排样方式(排样图)的集合,然后通过解整数规划问题获得各个排样方式的使用次数。排样方式生成算法通过构造并求解整数规划模型,求出最优三块排样。采用的三块排样,切割工艺简单,能有效提高切割效率。实验结果表明,该算法可以明显减少板材消耗。     

考虑切割刀数的T形排样算法研究

讨论无约束二维板材切割问题,采用T形排样方式以简化切割工艺。优化目标是使排样方式的价值最大,而排样方式的价值等于其中所含毛坯的总价值与切割成本之差。假定切割成本与切割刀数成正比,采用基于动态规划的算法生成排样方式。实验结果表明该算法可有效地减少切割刀数,计算时间合理。     

一种卷板填充分层递归排样的优化算法

研究了卷板填充排样问题,提出了一种分层递归排样的优化算法。算法使用水平剪切线将卷板分层,每层的宽度和卷板宽度相同,高度和层最左端的主毛坯高度相同;通过调用递归过程确定卷板中层的排列,为各层选定主毛坯,并确定毛坯的排列方式;采用分支定界技术缩小搜索空间。实验结果说明该算法比文献中最近报道的几种算法都有效。     

生成矩形毛坯最优两段排样方式的确定型算法

排样价值、切割工艺和计算时间是排样问题主要考虑的3个因素.文中提出一个新的基于排样模式的确定型排样算法——同质块两段排样算法,此算法适合剪冲下料工艺,在实现工艺简化的同时提高了排样价值时间比.首先通过动态规划算法生成最优同质块,然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式,最后选择两个段生成最优的两段排样方式.通过3组经典测题对该文算法进行了测试,将算法与4种著名算法进行了比较.实验结果表明,该文算法的优化结果好于以上4种著名算法,有效地提高了板材利用率,并且计算时间合理.     

二维剪切排样的束搜索启发式算法

针对约束二维矩形剪切排样问题,提出了一种基于束搜索的三阶段剪切排样算法。其切割过程包括三个阶段：板材剪切成段,段剪切成条带,条带切割成准确尺寸毛坯。采用动态规划确定段的价值,复杂度低的拼接递推不同长度子板的初始价值和板材的初始可行解,束搜索优化板材的排样方式。束搜索的节点用矩形对表示,分别是段组合而成的局部方式和未填充的剩余子板。以局部方式价值与剩余子板的初始价值之和作为节点的估计值。按估计值选择精英节点继续分支,其他节点直接删除不再回溯。实验结果表明该算法可缩短三阶段同质排样的计算时间,且所获得的余料大,利于余料的回收管理和再利用。     

An exact algorithm for generating homogenous T-shape cutting patterns

Both the material usage and the complexity of the cutting process should be considered in generating cutting patterns. This paper presents an exact algorithm for constrained two-dimensional guillotine-cutting problems of rectangles. It uses homogenous T-shape patterns to simplify the cutting process. Only homogenous strips are allowed, each of which contains rectangular blanks of the same size and direction. The sheet is divided into two segments. Each segment consists of strips of the same length and direction. The strip directions of the two segments are perpendicular to each other. The algorithm is based on branch and bound procedure combined with dynamic programming techniques. It is a bottom-up tree-search approach that searches the solution tree from the branches to the root. Tighter bounds are established to shorten the searching space. The computational results indicate that the algorithm is efficient both in computation time and in material usage.     

矩形件简单块占角排样方式的动态规划

目的 针对矩形件无约束2维剪切排样问题,提出一种可简化板材切割工艺的简单块占角排样方式,并构造这种排样方式的动态规划生成算法。方法 该排样方式在板材左下角按照简单块方式排样若干行若干列同种矩形件,将板材剩余部分划分为两个子板;将子板按照上述方法继续递归排样和划分,直至子板排满矩形件为止。采用动态规划确定所有可能尺寸的板材左下角排样的最优矩形件、矩形件的最优行列数和板材剩余部分的最优子板划分。运用规范尺寸排除不必要的计算。结果 将本文算法与目前常见的算法进行比较,实验结果表明本文算法计算时间合理,排样价值较高。在第1组41道基准例题中,本文算法所有例题均求出了精确解,同质块T型算法、同质块两段算法和复合条带两段算法分别有7道、5道和4道例题未求出精确解。在第2组20道基准例题中,本文算法只有1道例题未求出精确解,普通三阶段算法、同质块T型算法、同质块两段算法和匀质条带三块算法分别有18道、15道、15道和20道例题未求出精确解。在第3组50道随机例题中,本文算法、普通两段算法和同质块两段算法板材利用率分别为99.913 7%、99.862 3%和99.796 1%。在第4组31道基准例题中,本文算法所有例题均求出了精确解,普通占角排样算法有2道例题未求出精确解。结论 本文算法计算时间远小于精确算法,优化效果接近精确算法;本文算法计算时间与多种启发式算法接近,但优化效果好于多种启发式算法。     

Revisiting Multiple Pattern Matching Algorithms for Multi-Core Architecture

Due to the huge size of patterns to be searched,multiple pattern searching remains a challenge to several newly-arising applications like network intrusion detection.In this paper,we present an attempt to design efficient multiple pattern searching algorithms on multi-core architectures.We observe an important feature which indicates that the multiple pattern matching time mainly depends on the number and minimal length of patterns.The multi-core algorithm proposed in this paper leverages this feature to decompose pattern set so that the parallel execution time is minimized.We formulate the problem as an optimal decomposition and scheduling of a pattern set,then propose a heuristic algorithm,which takes advantage of dynamic programming and greedy algorithmic techniques,to solve the optimization problem.Experimental results suggest that our decomposition approach can increase the searching speed by more than 200% on a 4-core AMD Barcelona system.     

二维板材切割下料问题的一种确定性算法

研究二维板材切割下料问题,即使用最少板材切割出一定数量的若干种矩形件。 提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方 式的背包算法;然后采用线性规划算法迭代调用上述背包算法,每次均根据生产成本最小原则 改善目标函数并修正各种矩形件的当前价值,按照当前价值生成新的排样方式;最后选择最优 的一组排样方式组成排样方案。采用基准测题,将该算法与著名的T 型下料算法进行比较,实 验结果表明,该算法比T 型下料算法更能节省板材,计算时间能够满足实际应用需要。     

基于价值修正的圆片下料顺序启发式算法

讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T 型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T 型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。     

Using Wang's two-dimensional cutting stock algorithm to optimally solve difficult problems

P. Y. Wang's classic bottom-up two-dimensional cutting stock algorithm generates cutting patterns by building rectangles both horizontally and vertically. This algorithm uses a parameter β ₁ to tradeoff the number of rectangles generated by the algorithm and hence the quality of the cutting pattern solution obtained versus the amount of computer resources required. Several researchers have made relatively straightforward modifications to Wang's basic algorithm resulting in improved computational times. However, even with these modifications, Wang's approach tends to require large amounts of computer resources in order to optimally or near-optimally solve difficult two-dimensional guillotine cutting stock problems. In this paper, we present an iterative approach that judiciously uses Wang's basic algorithm (with some previously defined modifications) to obtain optimal cutting patterns to difficult two-dimensional cutting stock problems in reasonable computer run times.     

Heuristic and genetic approach for nesting of two-dimensional rectangular shaped parts with common cutting edge concept for laser cutting and profile blanking processes

This paper presents a novel two-dimensional nesting strategy suitable for sheet metal industries employing laser cutting and profile blanking processes. The proposed nesting approach is developed by the combination of heuristic and genetic algorithms in order to generate an effective nested pattern, in such a way that, it minimizes the sheet material wastage and also the cutting tool path distance, while arranging a set of rectangular parts in a rectangular sheet. With the proposed bottom–left heuristic method, at first, the parts are considered in a specific sequence and orientation, and each part is translated to the feasible bottom left most position on the previously placed parts and then adjusted to form the common cutting edges with adjacent parts. Further, the heuristic algorithm ensures the formation of clusters, in which a group of parts share the cutting edges, for effective handling of parts while cutting. Finally the optimal and effective nested pattern is generated by the genetic evaluation process which reproduces several sets of nested patterns, before converging to the optimality. The effectiveness of the proposed work, in terms of utilization of sheet material, is demonstrated by comparing the results obtained from the literature. Furthermore the uniqueness of the present approach in enhancing the nested pattern efficiency and minimizing the tool path distance with common cutting edge concept is illustrated.