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.     

Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size.     

Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths

This paper deals with the classical one-dimensional integer cutting stock problem, which consists of cutting a set of available stock lengths in order to produce smaller ordered items. This process is carried out in order to optimize a given objective function (e.g., minimizing waste). Our study deals with a case in which there are several stock lengths available in limited quantities. Moreover, we have focused on problems of low demand. Some heuristic methods are proposed in order to obtain an integer solution and compared with others. The heuristic methods are empirically analyzed by solving a set of randomly generated instances and a set of instances from the literature. Concerning the latter, most of the optimal solutions of these instances are known, therefore it was possible to compare the solutions. The proposed methods presented very small objective function value gaps.     

Waste minimization in irregular stock cutting

This paper addresses a category of two dimensional NP-hard knapsack problem in which a given convex/non-convex planner items (polygons) have to be cut out of a single convex/non-convex master surface (stock). This cutting process is found in many industrial applications such as sheet metal processes, home-textile, garment, wood, leather and paper industries. An approach is proposed to solve this problem, which depends on the concept of the difference between the area of a collection of polygons and the area of their convex hull. The polygon assignment inside the stock is subjected to feasibility tests to avoid overlapping, namely, angle test, bound test, point inclusion and polygon intersection test. An iterative scheme is used to generate different polygon placements while optimizing the objective function. Computer software is developed to solve and optimize the problem under consideration. Few examples are conducted for different combinations of convex, non-convex items and stocks. Well-known benchmark problems from the literature are tested and compared with our approach. The results of our algorithm have an interesting computational time and can compete with the results of previous work in some particular problems. The computational performance of the developed software indicates the efficiency of the algorithm for solving 2-D irregular cutting of non-convex polygons out of non-convex stock.     

Models for the two-dimensional two-stage cutting stock problem with multiple stock size

We consider a Two-Dimensional Cutting Stock Problem (2DCSP) where stock of different sizes is available, and a set of rectangular items has to be obtained through two-stage guillotine cuts. We propose and computationally compare three Mixed-Integer Programming models for the 2DCSP developing formulations from the literature. The first two models have a polynomial and pseudo-polynomial number of variables, respectively, and can be solved with a general-purpose MIP solver. The third model, having an exponential number of variables, is solved via branch-and-price techniques. We conclude the paper describing the results of extensive computational experiments on a set of benchmark instances from the literature.     

Using Wang's two-dimensional cutting stock algorithm to optimally solve difficult problems

P. Y. Wang's classic bottom-up two-dimensional cutting stock algorithm generates cutting patterns by building rectangles both horizontally and vertically. This algorithm uses a parameter β ₁ to tradeoff the number of rectangles generated by the algorithm and hence the quality of the cutting pattern solution obtained versus the amount of computer resources required. Several researchers have made relatively straightforward modifications to Wang's basic algorithm resulting in improved computational times. However, even with these modifications, Wang's approach tends to require large amounts of computer resources in order to optimally or near-optimally solve difficult two-dimensional guillotine cutting stock problems. In this paper, we present an iterative approach that judiciously uses Wang's basic algorithm (with some previously defined modifications) to obtain optimal cutting patterns to difficult two-dimensional cutting stock problems in reasonable computer run times.     

改进的遗传算法优化二维不规则图形排样

针对大规模零件和不规则石材下料优化排样问题,提出了改进的遗传算法优化排样方法.采取二进制与十进制混合编码的策略,既克服了单独使用二进制编码时,编码串太长且操作不方便的不足,又解决了十进制编码中相近的编码方案获得的材料利用率却相去甚远的问题;通过计算矢量图形的相似度,从而对图形群体进行分类,降低了遗传算法的时间复杂度.实验结果表明,该优化排样算法在时间复杂度和空间占有率上均优于传统的遗传算法优化排样.     

Arc-flow model for the two-dimensional guillotine cutting stock problem

We describe an exact model for the two-dimensional cutting stock problem with two stages and the guillotine constraint. It is an integer linear programming (ILP) arc-flow model, formulated as a minimum flow problem, which is an extension of a model proposed by Valério de Carvalho for the one dimensional case. In this paper, we explore the behavior of this model when it is solved with a commercial software, explicitly considering all its variables and constraints. We also derive a new family of cutting planes and a new lower bound, and consider some variants of the original problem. The model was tested on a set of real instances from the wood industry, with very good results. Furthermore the lower bounds provided by the linear programming relaxation of the model compare favorably with the lower bounds provided by models based on assignment variables.     

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.     

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.     

A parallel algorithm for constrained two-staged two-dimensional cutting problems

In this paper, we solve the two-staged two-dimensional cutting problem using a parallel algorithm. The proposed approach combines two main features: beam search (BS) and strip generation solution procedures (SGSP). BS employs a truncated tree-search, where a selected subset of generated nodes are retuned for further search. SGSP, a constructive procedure, combines a (sub)set of strips for providing both partial lower and complementary upper bounds. The algorithm explores in parallel a subset of selected nodes following the master-slave paradigm. The master processor serves to guide the search-resolution and each slave processor develops its proper way, trying a global convergence. The aim of such an approach is to show how the parallelism is able to efficiently solve large-scale instances, by providing new solutions within a consistently reduced runtime. Extensive computational testing on instances, taken from the literature, shows the effectiveness of the proposed approach.     

Heuristics for capacity planning problems with congestion

Motivated by a problem in the semiconductor industry, we develop improved formulations for the problem of planning capacity acquisition and deletion over time when resources are subject to congestion, motivated by a problem in the semiconductor industry. We use nonlinear clearing functions to relate the expected output of a production resource in a planning period to the expected work in process (WIP) inventory level. Exploiting the properties of the clearing function allows us to formulate the single workcenter problem as a shortest path problem. This forms the basis for two greedy constructive heuristics and a Lagrangian heuristic for the multistage problem. The latter procedure also provides lower bounds on the optimal value. We present computational experiments showing that the proposed heuristics obtain high-quality solutions in modest CPU times.     

A cutting plane method for knapsack polytope

A separation algorithm for knapsack polytope is proposed. This algorithm has been used in the branch-and-cut method for solving the generalized assignment problem and the capacitated p-median problem. The computational experiment on the test instances has shown that this method is highly competitive in comparison with the existing approaches.     

Solving two-dimensional cutting stock problem via a DNA computing algorithm

Two-dimensional cutting stock problem (TDCSP) is a well-known combinatorial optimization problem in which a given set of two-dimensional small pieces with different shapes should be cut from a given main board so that the demand of each small piece is satisfied and the total waste is minimized. Since TDCSP is an NP-complete problem, it is unsolvable in polynomial time on electronic computers. However, using the structure of DNA molecules, DNA computing algorithms are capable to solve NP-complete problems in polynomial time. In this paper, a DNA computing algorithm based on the sticker model is presented to find the optimal solution to TDCSP. It is proved that the time complexity of this algorithm on DNA computers is polynomial considering the number of small pieces and the length and width of the main board.

     

An optimization algorithm for cutting stock problems in the TFT-LCD industry

Due to lack of efficient approaches of mixed production, the present production approach of the TFT-LCD industry is batch production that each glass substrate is cut into LCD plates of one size only. This study proposes an optimization algorithm for cutting stock problems of the TFT-LCD industry. The proposed algorithm minimizes the number of glass substrates required to satisfy the orders, therefore reducing the production costs. Additionally, the solution of the proposed algorithm is a global optimum which is different from a local optimum or a feasible solution that is found by the heuristic algorithm. Numerical examples are also presented to illustrate the usefulness of the proposed algorithm.     

There is no EPTAS for two-dimensional knapsack

In the d-dimensional (vector) knapsack problem given is a set of items, each having a d-dimensional size vector and a profit, and a d-dimensional bin. The goal is to select a subset of the items of maximum total profit such that the sum of all vectors is bounded by the bin capacity in each dimension. It is well known that, unless P=NP, there is no fully polynomial-time approximation scheme for d-dimensional knapsack, already for d=2. The best known result is a polynomial-time approximation scheme (PTAS) due to Frieze and Clarke [A.M. Frieze, M. Clarke, Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European J. Operat. Res. 15 (1) (1984) 100-109] for the case where d?2 is some fixed constant. A fundamental open question is whether the problem admits an efficient PTAS (EPTAS).In this paper we resolve this question by showing that there is no EPTAS for d-dimensional knapsack, already for d=2, unless W[1]=FPT. Furthermore, we show that unless all problems in SNP are solvable in sub-exponential time, there is no approximation scheme for two-dimensional knapsack whose running time is , for any function f. Together, the two results suggest that a significant improvement over the running time of the scheme of Frieze and Clarke is unlikely to exist.     

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.     

A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces

Given a set of rectangular pieces and a rectangular container, the two-dimensional knapsack problem (2D-KP) consists of orthogonally packing a subset of the pieces within the container such that the sum of the values of the packed pieces is maximized. If the value of a piece is given by its area, the objective is to maximize the covered area of the container. A genetic algorithm (GA) is proposed addressing the guillotine case of the 2D-KP as well as the non-guillotine case. Moreover, an orientation constraint may optionally be taken into account and the given piece set may be constrained or unconstrained. The GA is subjected to an extensive test using well-known benchmark instances. Compared with recently published methods, the GA yields competitive results.     

Bi-dimensional knapsack problems with one soft constraint

In this paper, we consider bi-dimensional knapsack problems with a soft constraint, i.e., a constraint for which the right-hand side is not precisely fixed or uncertain. We reformulate these problems as bi-objective knapsack problems, where the soft constraint is relaxed and interpreted as an additional objective function. In this way, a sensitivity analysis for the bi-dimensional knapsack problem can be performed: The trade-off between constraint satisfaction, on the one hand, and the original objective value, on the other hand, can be analyzed. It is shown that a dynamic programming based solution approach for the bi-objective knapsack problem can be adapted in such a way that a representation of the nondominated set is obtained at moderate extra cost. In this context, we are particularly interested in representations of that part of the nondominated set that is in a certain sense close to the constrained optimum in the objective space. We discuss strategies for bound computations and for handling negative cost coefficients, which occur through the transformation. Numerical results comparing the bi-dimensional and bi-objective approaches are presented.     

Efficient stock cutting for laminated manufacturing

When an object is made using Laminated Manufacturing (LM), the output is a rectangular block with the required object trapped inside. In order to enable extraction of the object, the remaining sheet in each layer is cut into square grids that grow into tiny tiles. Thus, the remaining stock inside and surrounding the object is in the form of tiled fragments. The operator ‘decubes’ or removes these tiles using sharp tools and extracts the object. Making use of the remaining stock as support structure and grid cutting to enable extraction of the object are very innovative ideas in the ‘paste-and-cut’ LM approach. However, this method is very inefficient for two reasons: firstly, cutting efficiency is poor since laser spends most of its time in grid cutting; secondly, decubing takes several hours. In this paper, an efficient method of cutting the remaining stock to extract the object is presented.Extraction of the object from the stock block has analogy with the extraction of casting from its mold—the present and proposed methods respectively being analogous to sand casting and permanent mold casting processes. In the proposed method, rather than fragmenting the remaining stock into tiny tiles, it is segmented into two stock halves that open about a parting surface of minimum area. This optimal parting surface is obtained for the convex hull of the object, rather than for the object itself, due to its complete visibility along any pair opposite directions. The convex hull is further segmented into the object and plugs. The plugs are so shaped that they do not get entangled inside the concave portions of the object. The plugs whose drawing directions coincide with the opening direction of the stock halves are merged with the corresponding stock halves. The object, all the plugs and both the stock halves form the stock block. All these pieces are made together in the LM machine. For disassembly, first the convex hull will be extracted by opening the stock halves. Subsequently the plugs that fill the concave portions of the object will be extracted from the convex hull. Thus, grid cutting and decubing are eliminated in the proposed method resulting in drastic reduction in prototyping time and improved quality of the prototype.