生成最优同形块两阶段布局方式的确定型算法

为解决大规模二维布局问题,提出一种生成同形块两阶段布局方式的确定型算法。首先通过动态规划确定最优同形块;然后求解背包问题确定同形块在同形级中的布局方式和同形级在同形段中的最优布局方式;最后选择两个同形段生成最优同形块布局方式。通过43道基准测题,将该算法与经典两阶段和三块算法进行比较。实验结果表明,该算法不仅能满足剪切工艺,在计算时间和板材利用率上优于以上算法,而且能在合理时间内取得好的优化结果。     

基于匀质条带的矩形件最优三块布局算法

为解决大规模矩形件布局问题,提出一种动态规划算法生成基于匀质条带的矩形件最优三块布局方式。这种算法将板材分为三个块,同一块中只包含方向和长度均相同的匀质条带。通过求解背包模型生成块中的条带最优布局,隐枚举的讨论所有可能尺寸的块,确定所有三块组合的布局价值,选择布局价值最大的一个组合作为最优解。通过文献中的测题,将该算法与经典两段布局算法和启发式布局算法TABU500进行比较。实验结果表明:该算法在计算时间和材料利用率两方面都有效,且生成的布局方式简化了下料切割工艺。     

双排多段排样方式及其生成算法

为解决大规模矩形毛坯无约束的二维剪切排样问题,提出双排多段排样方式及其 生成算法。排样时采用一条剪切线将板材切分为两段,用一组剪切线将每段切分成一系列的块, 每个块由一组水平方向的同质条带构成。采用枚举法确定两段分界线的最优位置,通过求解背 包模型确定所有可能尺寸的块的最大价值和块在段中的最优布局。利用文献中的2 组基准测题 对所述算法进行测试,实验结果表明,该算法能在合理的计算时间内取得较好的优化结果。     

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

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

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

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

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

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

同尺寸矩形毛坯排样的连分数分支定界算法

在确定同尺寸矩形毛坯最优排样方式的算法中，连分数算法的时间效率最高，但所生成排样方式的切割工艺复杂．提出连分数分支定界算法，该算法应用连分数法确定毛坯数最优值，采用贴切的上界估计方法；在搜索过程中只保留上界不小于最优值的分支，遇到下界等于最优值的分支时结束搜索．实验结果表明，该算法的时间效率和连分数算法接近，并可以有效地简化切割工艺，生成切割工艺最简单的排样方式．最后，通过实例分析说明该算法的节约材料潜力。     

生成冲裁条带四块排样方式的最优算法

提出一个生成冲裁条带四块布局方式的最优算法,用于解决冲裁件无约束排样问题。该算法用三条剪切线把板材划分成四个块,每个块里面只包含方向和长度都相同的冲裁条带。首先生成所有可能长度的冲裁条带,然后求解背包问题生成冲裁条带在块里面的最优布局,最后通过枚举三条剪切线位置得到不同的四块组合,选择使排样价值最大的四块组合生成最优的四块排样方式。实验结果表明,该算法不仅可以提高材料利用率,而且计算时间合理。     

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

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

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

目的 针对矩形件无约束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道例题未求出精确解。结论 本文算法计算时间远小于精确算法,优化效果接近精确算法;本文算法计算时间与多种启发式算法接近,但优化效果好于多种启发式算法。     

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.     

Multi-level graph layout on the GPU

This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented.     

一种基于目标特征挖掘的带钢缺陷图像分割方法

通过分析带钢图像,挖掘缺陷图像的特征,提出一种基于目标特征挖掘的带钢缺陷图像分割方法。首先,将采集的带钢缺陷图像进行中值滤波处理;然后,通过等分图像灰度范围所确定的一系列阈值对带钢图像进行预分割,通过挖掘带钢缺陷图像的特征,以特征因子作为任务驱动,找出特征值发生突变的区间;在此突变的区间内,再按照上述方法对带钢图像缺陷存在的区域进行细分,找出面积突变点,以此确定最佳阈值,通过最佳阈值进行带钢缺陷图像分割,得到特征子图;最后将若干特征子图融合,得到带钢缺陷图像分割结果。实验结果表明,将此方法应用于带钢缺陷图像分割过程中,能够完整有效地分割出带钢缺陷区域,为带钢缺陷的视觉在线检测提供了可能性。     

Automated optimal design of a two-stage helical gear reducer

The design space of multi-stage transmissions is usually very large and heavily constrained. This places significant demands on the algorithm employed to search it, but successful optimization has the potential to yield considerably better designs than conventional heuristics, at the same time enabling a better understanding of the trade-offs between various objectives (such as service life and overall weight). Here we tackle a two-stage helical gear transmission design problem (complete with the sizing and selection of shafts, bearings, housing, etc.) using a two-phase evolutionary algorithm in a formulation that can be extended to include additional stages or different layouts.     

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

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

Conjugate conflict continuation graphs for multi-layer constrained via minimization

A graph model for describing the relationships among wire segments is crucial to constrained via minimization (CVM) in a VLSI design. In this paper we present a new graph model, called the conjugate conflict continuation graph, for multi-layer CVM with stacked vias. This graph model eases the handling of stacked via problems. An integer linear programming (ILP) formulation and a simulated annealing (SA) algorithm based on this graph model are developed to solve multi-layer CVM. The ILP model is too complicated to solve efficiently. The SA algorithm on average achieves 6.4% via reduction for layouts obtained using a commercial tool under a set of practical constraints in which the metal wires (including pins) used in cell layouts, power rails and rings, and clock routing are treated as obstacles or fixed-layer objects to a multi-layer CVM.     

Parallel Complexity of Matrix Multiplication1

Effective design of parallel matrix multiplication algorithms relies on the consideration of many interdependent issues based on the underlying parallel machine or network upon which such algorithms will be implemented, as well as, the type of methodology utilized by an algorithm. In this paper, we determine the parallel complexity of multiplying two (not necessarily square) matrices on parallel distributed-memory machines and/or networks. In other words, we provided an achievable parallel run-time that can not be beaten by any algorithm (known or unknown) for solving this problem. In addition, any algorithm that claims to be optimal must attain this run-time. In order to obtain results that are general and useful throughout a span of machines, we base our results on the well-known LogP model. Furthermore, three important criteria must be considered in order to determine the running time of a parallel algorithm; namely, (i) local computational tasks, (ii) the initial data layout, and (iii) the communication schedule. We provide optimality results by first proving general lower bounds on parallel run-time. These lower bounds lead to significant insights on (i)–(iii) above. In particular, we present what types of data layouts and communication schedules are needed in order to obtain optimal run-times. We prove that no one data layout can achieve optimal running times for all cases. Instead, optimal layouts depend on the dimensions of each matrix, and on the number of processors. Lastly, optimal algorithms are provided.