Heuristic and exact algorithms for generating homogenous constrained three-staged cutting patterns

An approach is proposed for generating homogenous three-staged cutting patterns for the constrained two-dimensional guillotine-cutting problems of rectangles. It is based on branch-and-bound procedure combined with dynamic programming techniques. The stock plate is divided into segments. Each segment consists of strips with the same direction. Only homogenous strips are allowed, each of which contains rectangles of the same size. The approach uses a tree-search procedure. It starts from an initial lower bound, implicitly generates all possible segments through the builds of strips, and constructs all possible patterns through the builds of segments. Tighter bounds are established to discard non-promising segments and patterns. Both heuristic and exact algorithms are proposed. The computational results indicate that the algorithms are capable of dealing with problems of larger scale. Finally, the solution to a cutting problem taken from a factory that makes passenger cars is given.     

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

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

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.     

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

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

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.     

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

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

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

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

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

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

Generating optimal T-shape cutting patterns for circular blanks

Circular blanks are often used in the manufacturing of the stators and rotors of electric motors. Some factories in China use T-shape cutting patterns to improve material usage. The author presents an algorithm to generate optimal T-shape cutting patterns for circular blanks. 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 direction 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 principles and steps of the algorithm are described in detail. The computational results indicate that the algorithm is efficient both in computation time and in material usage. Finally, the solution to an example is given.     

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.     

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.     

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

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

A simple algorithm for generating optimal equal circle cutting patterns with minimum sections

The cutting and stamping process is often used to divide stock plates into circular items. A guillotine machine cuts the plates into strips at the cutting phase. A stamping press stamps out the items from strips at the stamping phase. Normal patterns have been proposed for the case of equal circles. They consist of sections that contain strips of the same direction. The cutting process can be simplified if the number of sections is reduced. This short communication presents a simple algorithm for selecting from the optimal patterns the one that has the minimum number of sections. It assumes that the pattern value equals the value of the produced items minus the cost of the sections. The expected solution can be obtained by using an adequate section cost. The algorithm is faster and much simpler to design than a recently published algorithm.     

Genotype–phenotype heuristic approaches for a cutting stock problem with circular patterns

The cutting stock problem has been studied in the context of different industrial applications inducing NP-hard problems in most instances. However, the application in sawmill has not received the same attention. In this paper, we deal with the problem of determining the number of logs to cut over a period of several days and the geometry of sawmill patterns in order to satisfy the demand while minimizing the loss of material. First, the problem is formulated as an integer programming problem of the form of a constrained set covering problem where the knowledge of a priori cutting patterns is necessary to generate its columns. In our implementation, these patterns are obtained using a genetic algorithm (GA) or a simulated annealing method (SA). Then, two different approaches are introduced to solve the problem. The first approach includes two methods that combine a metaheuristic to generate the number of logs and a constructive heuristic to generate the cutting patterns for each of the logs. In the second approach, we use an exact procedure CPLEX to solve the integer programming model where the cutting patterns are generated with the GA method (GA+CPLEX) or the SA method (SA+CPLEX). These four methods are compared numerically on 11 semi-randomly generated problems similar to those found in real life. The best results for the loss are obtained with the two-stage GA+CPLEX approach that finds the best values for 7 problems.     

一种求解圆形下料问题的快速算法

本文研究圆形件优化排样算法,目的是提高材料利用率。本文提出了一种新的放置算法(圆弧搜索算法,ASA),与文献中算法相比,ASA在较短的时间内产生了可以和排样领域著名的法国学者Hifi在SCI和EI检索刊物中提出的较复杂方法GA-BH在利用率方面相媲美的效果;对随机生成例题的计算结果表明,本文算法的计算时间可以满足一般实践应用的要求,所得排样方案的材料利用率较高。     

一种求解圆形下料问题的快速算法

本文研究圆形件优化排样算法,目的是提高材料利用率。本文提出了一种新的放置算法(圆弧搜索算法,ASA),与文献中算法相比,ASA在较短的时间内产生了可以和排样领域著名的法国学者Hifi在SCI和EI检索刊物中提出的较复杂方法GA-BH在利用率方面相媲美的效果;对随机生成例题的计算结果表明,本文算法的计算时间可以满足一般实践应用的要求,所得排样方案的材料利用率较高。     

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

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

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

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

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

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

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

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