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

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

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.     

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

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

考虑多目标优化的一维排样系统

对于常见的一维下料问题,采用顺序启发式算法设计排样系统。在保证较高材料利用率的同时,考虑多个优化目标的实现,如减少排样方式数,优先使用短材料,增加最后一根原材料上的余料长度等。通过对各个目标设定不同的优先级,可生成满足实际生产环境需要的排样方案。经过与其他多种优化算法的实验结果比较,证实本文排样系统的优越性。     

The usable leftover one‐dimensional cutting stock problem—a priority‐in‐use heuristic

We consider a one‐dimensional cutting stock problem in which the material not used in the cutting patterns, if large enough, is kept for use in the future. Moreover, it is assumed that leftovers should not remain in stock for a long time, hence, such leftovers have priority‐in‐use compared to standard objects (objects bought by the industry) in stock. A heuristic procedure is proposed for this problem, and its performance is analyzed by solving randomly generated dynamic instances where successive problems are solved in a time horizon. For each period, new demands arise and a new problem is solved on the basis of the information about the stock of the previous periods (remaining standard objects in the stock) and usable leftovers generated during those previous periods. The computational experiments show that the solutions presented by the proposed heuristic are better than the solutions obtained by other heuristics from the literature.     

Near-optimal solutions to one-dimensional cutting stock problems

This paper describes a set of heuristic procedures for efficiently generating good solutions to one-dimensional cutting stock problems in which (i) there are multiple stock lengths with constraints on their availability, (ii) it is desirable to cut the trim into as few pieces as possible and (iii) it is difficult because of the problem's structure, to round fractional, LP solutions to good feasible cutting plans. The point of departure for the procedures is the column generation technique of Gilmore and Gomory. The computational experience reported here suggests that the heuristics are both effective and efficient.     

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

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

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

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

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.     

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.     

多尺寸圆木二维下料问题研究

圆木二维下料问题是木材企业中常见问题,针对一些头部与尾部直径相差不大的木材,可以将这些木材看作是圆柱体,下料时将其切成和圆木长度相等的多个长方体毛坯,该问题可转化为二维下料问题。采用顺序价值校正框架和动态规划算法求解该下料问题。顺序生成排样图,每生成一个排样图便调整毛坯的价值,重复该过程直到满足毛坯需求为止。通过迭代生成多个下料方案以便优选。圆木下料的研究对减少木材企业的成本很有意义。     

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.     

An evolutionary algorithm for the one‐dimensional cutting stock problem

This paper deals with the one‐dimensional integer cutting stock problem, which consists of cutting a set of available objects in stock in order to produce ordered smaller items in such a way as to minimize the waste of material. The case in which there are various types of objects available in stock in limited quantities is studied. A new heuristic method based on the evolutionary algorithm concept is proposed to solve the problem. This heuristic is empirically analyzed by solving randomly generated instances and the results are compared with other methods from the literature.     

A genetic algorithm approach for the cutting stock problem

In this paper, a genetic algorithm approach is developed for solving the rectangular cutting stock problem. The performance measure is the minimization of the waste. Simulation results obtained from the genetic algorithm-based approach are compared with one heuristic based on partial enumeration of all feasible patterns, and another heuristic based on a genetic neuro-nesting approach. Some test problems taken from the literature were used for the experimentation. Finally, the genetic algorithm approach was applied to test problems generated randomly. The simulation results of the proposed approach in terms of solution quality are encouraging when compared to the partial enumeration-based heuristic and the genetic neuro-nesting approach.     

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.     

有限制二维板材启发式下料算法研究

橱柜及板式家具生产都涉及二维板材下料,材料利用率的最大化一直是该类企业追求的目标。本文提出了基于启发式规则的有限制二维板材下料算法。通过在橱柜生产过程中自动下料系统的实施和理论分析,该算法是实用有效的。     

Solving a combined cutting-stock and lot-sizing problem with a column generating procedure

In NonÅs and Thorstenson [A combined cutting stock and lot sizing problem. European Journal of Operational Research 120(2) (2000) 327–42] a combined cutting-stock and lot-sizing problem is outlined under static and deterministic conditions. In this paper we suggest a new column generating solution procedure for this problem that works well on both small and large-sized problems. The procedure includes characteristics from both the column generating procedure in NonÅs and Thorstenson, which works well on small-sized problems, and from the sequential heuristic due to Haessler [A heuristic programming solution to a nonlinear cutting stock problem, Management Science 17(12) (1971) 793–802], which works well on large-sized problems. Numerical results are presented that show that the new heuristic performs better than both of the earlier procedures. Comparisons with results obtained by other authors indicate that the procedure works well also for the extended cutting-stock problem with only a setup cost for each pattern change.     

A microcomputer cutting stock analysis and planning system

The system described herein solves cutting stock problems encountered in the flat glass and related industries. Cutting patterns with relatively high but not necessarily optimal utilization are generated by first selecting a strip width either automatically (via a heuristic) or manually (via user intervention). The related knapsack problem which results is then solved to determine how to pack pieces into the strip. A graphical display of the resulting cutting pattern allows the user to evaluate it in consideration of his expertise in the overall manufacturing environment in addition to its utilization.     

A New PSO-based Algorithm for Two-Dimensional Non-Guillotine Non-Oriented Cutting Stock Problem

In this paper, a new algorithm is proposed for the two-dimensional non-guillotine non-oriented cutting stock problem. The considered problem consists of cutting small rectangular pieces of predetermined sizes from large but finite rectangular plates. The objective is to generate cutting patterns that minimize the unused area and fulfill customer orders. The proposed algorithm is a combination of a new particle swarm optimization approach with a heuristic criterion inspired from the literature. The algorithm is tested on twenty-two instances divided into two sets. Corresponding results show the algorithm efficiency in optimizing the trim loss that is comprised between 2.6% and 7.8% for all considered instances.     

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.