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.     

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

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

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

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

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

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

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.     

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.     

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

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

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.     

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

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

New lower bounds based on column generation and constraint programming for the pattern minimization problem

The pattern minimization problem is a cutting and packing problem that consists in finding a cutting plan with the minimum number of different patterns. This objective may be relevant when changing from one pattern to another involves a cost for setting up the cutting machine. When the minimization of the number of different patterns is done by assuming that no more than the minimum number of rolls can be used, the problem is also referred to as the cutting stock problem with setup costs.     

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

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

A hybrid heuristic to reduce the number of different patterns in cutting stock problems

We propose a hybrid procedure to obtain a reduced number of different patterns in cutting stock problems. Initially, we generate patterns with limited waste that fulfill the demands of at least two items when the patterns are repeatedly cut as much as possible but without overproducing any of the items. The problem is reduced and the residual problem is solved. Then, pattern reduction techniques (local search) are applied starting with the generated solution. The scheme is straightforward and can be used in cutting stock problems of any dimension. Variations of the procedure are also indicated. Computational tests performed indicated that the proposed scheme provides alternative solutions to the pattern reduction problem which are not dominated by other solutions obtained using procedures previously suggested in the literature.     

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

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

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.     

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

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

Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns

A sequential value correction heuristic is presented for the two-dimensional cutting stock problem with three-staged homogenous patterns, considering both input-minimization and simplicity of the cutting process. The heuristic constructs many cutting plans iteratively and selects the best one as the solution. The patterns in each cutting plan are generated sequentially using simple recursive techniques. The values of the item types are corrected after the generation of each pattern to diversify the cutting plans. Computational results indicate that the proposed heuristic is more effective in input minimization than published algorithms and commercial stock cutting software packages that use three-staged general or exact patterns.     

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

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

基于两阶段的分段单一矩形优化排样

为有效解决分段单一矩形优化排样问题,给出一个求解分段单一矩形优化排样问题的两阶段方法。第一阶段完成标准子段最佳排样方式求解,并将二维排样问题转化为一维下料问题,第二阶段使用适合于一维下料问题求解的算法完成板材最佳排样方式求解。使用该方法开发了一个单一矩形优化排样系统,该系统既可以解决分段单一矩形排样问题也可以解决其他类型的单一矩形优化排样问题。企业应用实例表明该方法是求解分段单一矩形优化排样问题的一个较为有效的方法。     

On the one-dimensional stock cutting problem in the paper tube industry

The one-dimensional cutting stock problem (1D-CSP) is one of the representative combinatorial optimization problems which arises in many industrial applications. Although the primary objective of 1D-CSP is to minimize the total length of used stock rolls, the efficiency of cutting processes has become more important in recent years. The crucial bottleneck of the cutting process often occurs at handling operations in semiautomated manufacturers such as those in the paper tube industry. To reduce interruptions and errors at handling operations in the paper tube industry, we consider a variant of 1D-CSP that minimizes the total length of used stock rolls while constraining (C1) the number of setups of each stock roll type, (C2) the combination of piece lengths occurring in open stacks simultaneously, and (C3) the number of open stacks. For this problem, we propose a generalization of the cutting pattern called the “cutting group,” which is a sequence of cutting patterns that satisfies the given upper bounds of setups of each stock roll type and open stacks. To generate good cutting groups, we decompose the 1D-CSP into a number of auxiliary bin packing problems. We develop a tabu search algorithm based on a shift neighborhood that solves the auxiliary bin packing problems by the first-fit decreasing heuristic algorithm. Experimental results show that our algorithm improves the quality of solutions compared to the existing algorithm used in a paper tube factory.     

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

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