Strips minimization in two-dimensional cutting stock of circular items

Circular items are often produced from stock plates using the cutting and stamping process that consists of two stages. A guillotine machine divides the plate into strips at the cutting stage, and then a press punches out the items from the strips at the stamping stage. The cutting cost at the first stage often increases with the number of strips in the cutting plan. An approach is presented for the two-dimensional cutting stock problem of the strips at the cutting stage. The objective is to minimize the sum of the material and the cutting costs. The approach formulates the problem as an integer linear programming, and uses a column generation method for generating the cutting patterns. The cutting patterns have the feature that each cut on the plate produces just one strip. The computational results indicate that the approach can greatly reduce the number of strips in the cutting plan.     

冲裁件条料最优四块剪切下料方案的生成算法

讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较,实验计算结果表明,该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解,可以看出该算法解决实际下料问题是有效的。     

面向可加工性的矩形件优化下料算法

针对目前矩形件优化下料算法侧重追求高材料利用率,而对实际切割成本考虑不足的现状,提出一种既维持高材料利用率,又使下料方案具有较低切割成本的矩形件优化下料算法。算法采用SVC框架和同质条带多级规范方式求解矩形件下料问题。利用条带共边排样的路径优化设计进行切割路径长度的计算,以生产成本（材料成本与切割成本之和）为优化目标得到高材料利用率、低切割成本的下料方案,最后通过实验证实该算法的可行性与有效性。     

Heuristic for the two-dimensional arbitrary stock-size cutting stock problem

A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier’s provisions, such that the plate cost is minimized. The supplier’s provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.     

Heuristic for constrained T-shape cutting patterns of rectangular pieces

T-shape patterns are often used in dividing stock plates into rectangular pieces, because they make good balance between plate cost and cutting complexity. A dividing cut separates the plate into two segments, each of which contains parallel strips, and the strip orientations of the two segments are perpendicular to each other. This paper presents a heuristic algorithm for constrained T-shape patterns, where the optimization objective is to maximize the pattern value, and the frequency of each piece type does not exceed the demand. The algorithm considers many dividing-cut positions, determines the pattern value associated to each position using a layout-generation procedure, and selects the one with the maximum pattern value as the solution. Pseudo upper bounds are used to skip some non-promising positions. The computational results show that the algorithm is fast and able to get solutions better than those of the optimal two-staged patterns in terms of material utilization.     

矩形毛坯排样中条带长度的约束处理

该文的排样问题是根据剪冲工艺的要求抽象出来的。剪冲工艺是指分两步将板材分割成毛坯:第一步用平剪床将板材切成条带;第二步采用剪或冲的方式,将条带切成毛坯。所考虑的工艺约束包括最小条带长度约束和最大条带长度约束,排样方式中条带的长度,必须在最小和最大条带长度约束值之间。该文对基本的动态规划算法加以改造,使之能够处理最小和最大条带长度约束,并在C++环境下,开发出同尺寸矩形毛坯排样系统UR。利用这个软件,进行了大量的例题测试,得出对生产实践具有指导意义的结论。     

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

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

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

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

Heuristic algorithm for a cutting stock problem in the steel bridge construction

A rectangular two-dimensional cutting stock problem in the steel bridge construction is discussed. It is the problem of cutting a set of rectangular items from plates with arbitrary sizes that lie in the supplier specified ranges, such that the necessary plate area is minimized. Several types of cutting patterns are used to compose the cutting plan. All of them are easy to generate and cut except the last one. The algorithm uses both recursive and dynamic programming techniques to generate patterns of the last type. The computational results of 22 practical instances indicate that the algorithm can produce solutions close to optimal, and the computation time is reasonable for practical use.     

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

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

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.     

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

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

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

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

冲裁条带最优多段排样方式的动态规划算法

讨论冲裁件无约束剪冲排样问题,用动态规划算法生成冲裁条带多段排样方式。采用一组相互平行的分割线将板材分成多个段,每段含一组方向和长度都相同的条带。通过动态规划算法确定所有可能尺寸段的最优价值以及板材中段的最优组合,使整张板材价值达到最大。实验结果表明该算法能够提高材料利用率,计算时间能满足实际应用的需要。     

A cutting stock problem and its solution in the manufacturing industry of large electric generators

T-shape cutting patterns are applied in the manufacturing of circular and sectorial blanks for stators and rotors of large electric generators. The author presents an algorithm to generate them. In the patterns more than one row of identical blanks can appear in a strip. A strip is in one of the two perpendicular directions, namely X- or Y-direction. The algorithm uses the knapsack algorithm and an implicit enumeration method to determine the optimal combination of blank rows in the strips, the strip numbers and directions in the pattern. The algorithm is applied to the real cutting stock data of a factory that makes large electric generators. The results indicate that the algorithm is efficient both in computation time and in material usage.     

Generating optimal two-section cutting patterns for rectangular blanks

This paper presents an algorithm for generating unconstrained guillotine-cutting patterns for rectangular blanks. A pattern includes at most two sections, each of which consists of strips of the same length and direction. The sizes and strip directions of the sections must be determined optimally to maximize the value of the blanks cut. The algorithm uses an implicit enumeration method to consider all possible section sizes, from which the optimal sizes are selected. It may solve all the benchmark problems listed in the OR-Library to optimality. The computational results indicate that the algorithm is efficient both in computation time and in material utilization. Finally, solutions to some problems are given.     

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

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

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

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

基于两段排样方式的矩形件优化下料算法

针对矩形件下料问题,提出一种基于两段排样方式的优化下料算法。首先构造一 种约束排样算法,生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余 需求量迭代调用上述约束排样算法生成一个虚拟下料方案,按照不产生多余矩形件原则选取虚 拟下料方案中的部分排样方式加入到实际下料方案中,更新矩形件剩余需求量;重复上述步骤 直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2 种文献算法进行比较,数值实 验结果表明该算法下料利用率比2 种文献算法分别高1.61%和0.78%。     

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

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