Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape

In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time.     

Logic based Benders' decomposition for orthogonal stock cutting problems

We consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90° is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading.     

The skiving stock problem as a counterpart of the cutting stock problem

The cutting stock problem (CSP) is a particular case of the set‐covering problem. Similarly we introduce another class of combinatorial optimization problems called the skiving stock problem (SSP) as a particular case of the set‐packing problem. The SSP shares many properties and solving techniques with the CSP. When these two problem spaces are contrasted they illuminate one another in that they form a ‘dual’ relationship where techniques once thought to be applicable in one domain can be applied in the other. Furthermore the SSP, like the CSP, may have numerous applications in business and industry.     

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.     

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.     

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.     

Approximate algorithms for the container loading problem

In this paper we develop several algorithms for solving three–dimensional cutting/packing problems. We begin by proposing an adaptation of the approach proposed in Hifi and Ouafi (1997) for solving two–staged unconstrained two–dimensional cutting problems. We show how the algorithm can be polynomially solved for producing a constant approximation ratio. We then extend this algorithm for developing better approximate algorithms. By using hill–climbing strategies, we construct some heuristics which produce a good trade–off between the computational time and the solution quality. The performance of the proposed algorithms is evaluated on different problem instances of the literature, with different sizes and densities (a total of 144 problem instances).     

Exact algorithms for the two-dimensional guillotine knapsack

The two-dimensional knapsack problem requires to pack a maximum profit subset of “small” rectangular items into a unique “large” rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem.In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are computationally evaluated on well-known benchmark instances from the literature.The C++ source code of the recursive procedure is available upon request from the authors.     

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

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

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

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

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

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

Bin packing and related problems: General arc-flow formulation with graph compression

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems—including multi-constraint variants—by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model.Our formulation is equivalent to Gilmore and Gomory׳s, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern.The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.     

Evaluation of algorithms for one-dimensional cutting

The paper deals with the problem of evaluating and comparing different one-dimensional stock cutting algorithms regarding trim loss. Different types of problems are identified. An evaluation method is developed which enables a comparison of solutions of all types of problems. A practical example of this methods implementation is presented.Scope and purposeThere are many algorithms and methods for one-dimensional stock cutting with different factors that need to be taken into account. Therefore a general comparison between them is very difficult if not impossible. However, if we assume that trim loss is the most important factor common to different methods, we can overcome this problem by limiting the comparison to trim loss. In different cutting stock problems and in different approaches to them trim loss is defined differently. For the comparison of different solutions to be possible, we need to find a common definition to the trim loss. Such a general definition is introduced by the General One-Dimensional Cutting Stock Problem type (G1D-CSP). In this paper, a problem generator algorithm PGEN for G1D-CSP is presented and the method for evaluation and comparison of different one-dimensional cutting stock algorithms is proposed.     

Two-dimensional cutting stock problem research: A review and a new rectangular layout algorithm

The two-dimensional cutting stock problem addresses the allocation of a required bill of materials onto stock sheets in a manner that minimizes the trim losses. This paper surveys the progress made on the study of the problem from the original contributions by Gilmore and Gomory in the mid-1960s to the present. Conclusions are for these algorithms to find greater application in industry, one must consider the allocation of both regular and irregular shapes. Moreover, the objective of minimizing the trim losses is not an adequate performance measure when the cutting department is placed in the perspective of the entire manufacturing system. The costs of inventory and production have to be included in the objective to be minimized in order to ensure maximum production efficiency. In addition, an algorithm based on the first fit decreasing heuristic¹ is presented to achieve layouts of rectangular bills of material on rectangular stock sheets, and its performance is examined. A number of nesting algorithms are currently in use in industry, but virtually all of these systems are considered to be highly proprietary and specific. The cutting stock problem has been variously adapted to applications in numerous industries. From its original form described later, it has been modified for use in paper, lumber, cloth, metal, leather stamping and other industries. In each case, the problem has been reformulated to suit the needs of the specific industry.     

一种卷板填充分层递归排样的优化算法

研究了卷板填充排样问题,提出了一种分层递归排样的优化算法。算法使用水平剪切线将卷板分层,每层的宽度和卷板宽度相同,高度和层最左端的主毛坯高度相同;通过调用递归过程确定卷板中层的排列,为各层选定主毛坯,并确定毛坯的排列方式;采用分支定界技术缩小搜索空间。实验结果说明该算法比文献中最近报道的几种算法都有效。     

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

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

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

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

Exhaustive approaches to 2D rectangular perfect packings

In this paper, we consider the two-dimensional rectangular strip packing problem, in the case where there is a perfect packing; that is, there is no wasted space. One can think of the problem as a jigsaw puzzle with oriented rectangular pieces. Although this comprises a quite special case for strip packing, we have found it useful as a subroutine in related work. We demonstrate a simple pruning approach that makes a branch-and-bound-based exhaustive search extremely effective for problems with less than 30 rectangles.     

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.     

一种有效的求解一维下料问题的启发式算法

使用了一种改进的顺序启发式算法,在排样方式的生成过程中不断修正当前排入毛坯的价值,使之趋于合理,依次选取求解背包函数获得的最大单位价值的排样方式组成当前排样方案,迭代调用该过程多次,最终选取最优的排样方案。在保证较高材料利用率的同时考虑减少排样方式,增加最后一根材料余料长度等多个优化目标。通过多组实验结果比较,证实了算法的有效性。