Heuristic and exact methods for the cutting sequencing problem

Cutting stock problems deal with the generation of a set of cutting patterns that minimizes waste. Sometimes it is also important to find the processing sequence of this set of patterns to minimize the maximum queue of partially cut orders. In such instances a cutting sequencing problem has to be solved. This paper presents a new mathematical model and a three-phase approach for the cutting sequencing problem. In the first phase, a greedy algorithm produces a good starting solution that is improved in the second phase by a tabu search, or a generalized local search procedure, while, in the last phase, the problem is optimally solved by an implicit enumeration procedure that uses the best solution previously found as an upper bound. Computing experience, based on 300 randomly generated problems, shows the good performance of the heuristic methods presented.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), items of the current order are cut from stock bars to minimize material cost. Here, stock bars include both standard ones bought commercially and old leftovers generated in processing previous orders, and cutting patterns often include new leftovers that are usable in processing subsequent orders. Leftovers of the same length are considered to be of the same type. The number of types of leftovers should be limited to simplify the cutting process and reduce the storage area. This paper presents an integer programming model for the 1DCSPUL with limited leftover types and describes a heuristic algorithm based on a column-generation procedure to solve it. Computational results show that the proposed approach is more effective than several published algorithms in reducing trim loss, especially when the number of types of leftovers is limited.     

An algorithm for a cutting stock problem on a strip

A cutting stock problem is formulated as follows: a set of rectangular pieces must be cut from a set of sheets, so as to minimize total waste. In our problem the pieces are requested in large quantities and the set of sheets are long rolls of material. For this class of problems we have developed a fast heuristic based on partial enumeration of all feasible patterns. We then tested the effectiveness on a set of test problems ranging from practical to random instances. Finally, the algorithm has been applied to check the asymptotic behaviour of the solution when a continuous stream of pieces is requested and cutting decisions are to be made while orders are still arriving.     

On a pattern sequencing problem to minimize the maximum number of open stacks

Consider a wood cutting setting where different panels have to be cut from large boards. Each cut panel size is put into a stack which remains opened until the last panel of that size is cut. The problem considered here deals with the sequencing of the patterns in order to minimize the maximum number of open stacks during the production run. A branch and bound method for solving this problem is presented which uses a greedy type scheme to select the next node to branch.     

Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem

The research addressing two-dimensional (2D) irregular shape packing has largely focused on the strip packing variant of the problem. However, it can be argued that this is a simplification. The materials from which pieces are required to be cut will ultimately have a fixed length either due to the physical dimensions of the material or through constraints on the cutting machinery. Hence, in order to cut all the pieces, multiple sheets may be required. From this scenario arises the 2D irregular shape cutting stock problem. In this paper, we will present implementations of cutting stock approaches adapted to handle irregular shapes, including two approaches based on column generation (CG) and a sequential heuristic procedure. In many applications, setup costs can be reduced if the same pattern layout is cut from multiple sheets; hence there is a trade-off between material waste and number of patterns. Therefore, we describe the formulation and implementation of an adaptation of the CG method to control the number of different patterns. CG is a common method for the cutting stock problem; however, when the pieces are irregular the sub-problem cannot be solved optimally. Hence we implement CG and solve the sub-problem using the beam search heuristic. Further, we introduce a version of CG for instances where the number of rows is less than the number of columns.     

An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing

This paper presents a two-stage approach for pattern generation and cutting plan determination of the one-dimensional cutting stock problem. Calculation of the total number of patterns that will be cut and generation of the cutting patterns are performed in the first stage. On the other hand, the second stage determines the cutting plan. The proposed approach makes use of two separate integer linear programming models. One of these models is employed by the first stage to generate the cutting patterns through a heuristic procedure with the objective of minimizing trim loss. The cutting patterns obtained from Stage 1 are then fed into the second stage. In this stage, another integer linear programming model is solved to form a cutting plan. The objective of this model is to minimize a generalized total cost function consisting of material inputs, number of setups, labor hours and overdue time; subject to demand requirements, material availability, regular and overtime availability, and due date constraints. The study also demonstrates an implementation of the proposed approach in a coronary stent manufacturer. The case study focuses on the cutting phase of the manufacturing process followed by manual cleaning and quality control activities. The experiments show that the proposed approach is suitable to the conditions and requirements of the company.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

Solving a two-dimensional trim-loss problem with MILP

In this paper a two-dimensional trim-loss problem connected to the paper-converting industry is considered. The problem is to produce a set of product paper rolls from larger raw paper rolls such that the cost for waste and the cutting time is minimized. The problem is generally non-convex due to a bilinear objective function and some bilinear constraints, which give rise to difficulties in finding efficient numerical procedures for the solution. The problem can, however, be solved as a two-step procedure, where the latter step is a mixed integer linear programming (MILP) problem. In the present formulation, both the width and length of the raw paper rolls as well as the lengths of the product paper rolls are considered variables. All feasible cutting patterns are included in the problem and global optimal cutting patterns are obtained as the solution from the corresponding MILP problem. A numerical example is included to illustrate the proposed procedure.     

Solving a bi-criterion cutting stock problem with open-ended demand: a case study

We consider a real-life cutting stock problem with two types of orders. All orders have to be cut from a given number of raws (also known as stock unit, master reel or jumbo). For each order the width of the final (also known as reels or units) and the number of finals is given. An order is called an exact order when the given number of finals must be produced exactly. An order is called an open order when at least the given number of finals must be produced. There is a given maximum on the number of finals that can be produced from a single raw which is determined by the number of knives on the machine. A pattern specifies the number of finals of a given width that will be produced from one raw. A solution consists of specifying a pattern for each raw such that in total the number of finals of exact orders is produced exactly and at least the number of finals of open orders is produced. There are two criteria defined for a solution. One criterion is the cutting loss: the total width of the raws minus the total width of the produced finals. The second criterion is the number of different patterns used in the solution. We describe a branch-and-bound algorithm that produces all Pareto-optimal solutions.     

T-shape homogenous block patterns for the two-dimensional cutting problem

This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction. A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage, and the computation time is reasonable.     

Application of optimization for solving a sawing stock problem with a cant sawing pattern

This paper introduces an optimization approach for solving the sawing stock problem in a sawmill in Brazil using the cant sawing pattern, in which lateral and central pieces are cut from the log surface. As this problem has been proved NP-hard and involves some nonlinearities due to the circular geometry of this pattern, we developed a solution method based on two stages. First, we developed an algorithm to generate all sawing patterns, considering the available log diameters and the demanded lumbers. Next, two integer linear programming models were formulated to optimize the number of sawing patterns to be cut, fulfilling the demand in the planning horizon and attending the amount of logs in inventory. One model minimizes the wood loss, while the other maximizes the sales revenue. The optimization approach was evaluated using real data from the sawmill, obtaining significant reductions in the volume cut, in comparison with the current manual planning process, while completely fulfilling the demand.     

A comparative numerical analysis for the guillotine two-dimensional cutting problem

In this work, the behavior of four algorithms in the resolution of the two-dimensional constrained guillotine cutting problem is analyzed. This problem is concerned about the way a set of pieces should be cut from a plate of greater dimensions, considering guillotine cutting and a constrained number of times a piece can be cut from the plate. In this study three combinatorial and two heuristic methods are considered. In the combinatorial methods from the set of pieces, a minimum loss layout is constructively generated based on Wang's algorithm. In addition, an evolutionary and an annealing type approach are considered. All of these models have been implemented on a high performance Silicon Graphics machine. Performance of each algorithm is analyzed both in terms of percentage waste and running time. In order to do that, a set of 1000 instances are classified according to their combinatorial degree and subsequently evaluated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Two-dimensional Cutting Stock with Multiple Stock Sizes

In this paper an algorithm for a cutting stock problem in the wood industry is presented. Cuts are of guillotine type and requirements have to be met exactly, i.e. no over- or under-production is allowed. There are several different board sizes from which panels can be cut and the problem is to find the best mix of boards and respective cutting patterns that satisfies the demand for panels with minimum wastage. The heuristic algorithm uses a pattern-building procedure combined with an enumeration scheme for the mix of boards.     

Reducing the number of cuts in generating three-staged cutting patterns

Three-staged guillotine patterns are widely used in the manufacturing industry to cut stock plates into rectangular items. The cutting cost often increases with the number of cuts required. This paper focuses on the rectangular two-dimensional cutting stock problem, where three-staged guillotine patterns are used, and the objective is to minimize the sum of plate and cutting costs. The column generation framework is used to solve the problem. It uses a pattern-generation procedure to obtain the patterns. The cutting cost is considered in both the pattern-generation procedure and the objective of the linear programming formulation. The computational results indicate that the approach can reduce the number of cuts, without increasing the plate cost.     

A two-dimensional strip cutting problem with sequencing constraint

We study a strip cutting problem that arises in the production of corrugated cardboard. In this context, rectangular items of different sizes are obtained by machines, called corrugators, that cut strips of large dimensions according to particular schemes containing at most two types of items. Because of buffer restrictions, these schemes have to be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet (sequencing constraint). We show that the problem of finding a set of schemes of minimum trim loss that satisfies an assigned demand for each item size is strongly NP-hard, even if the sequencing constraint is relaxed. Then, we present two heuristics for the problem with the sequencing constraint, both based on a graph characterization of the feasible solutions. The first heuristic is a two-phase procedure based on a mixed integer linear programming model. The second heuristic follows a completely combinatorial approach and consists of solving a suitable sequence of minimum cost matching problems. For both procedures, an upper bound on the number of schemes (setups) is found. Finally, a computational study comparing the quality of the heuristic solutions with respect to an LP lower bound is reported.     

Stock cutting to minimize cutting length

In this paper we investigate the following problem: Given two convex P_in, and P_out where P_in is completely contained in P_out, we wish to find a sequence of ‘guillotine cuts’ to cut out P_in from P_out such that the total length of the cutting sequence is minimized. This problem has applications in stock cutting where a particular shape or design (in this case the polygon P_in) needs to be cut out of a given piece of parent material (the polygon P_out) using only guillotine cuts and where it is desired to minimize the cutting sequence length to improve the cutting time required per piece. We first prove some properties of the optimal solution to the problem and then give an approximation scheme for the problem that, given an error range δ, produces a cutting sequence whose total length is atmost δ more than that of the optimal cutting sequence. Then it is shown that this problem has optimal solutions that lie in the algebraic extension of the field that the input data belongs to — hence due to this algebraic nature of the problem, an approximation scheme is the best that can be achieved. Extensions of these results are also studied in the case where the polygons P_in and P_out are non-convex.     

The stochastic trim-loss problem

The cutting stock problem (CSP) is one of the most fascinating problems in operations research. The problem aims at determining the optimal plan to cut a number of parts of various length from an inventory of standard-size material so to satisfy the customers demands. The deterministic CSP ignores the uncertain nature of the demands thus typically providing recommendations that may result in overproduction or in profit loss. This paper proposes a stochastic version of the CSP which explicitly takes into account uncertainty. Using a scenario-based approach, we develop a two-stage stochastic programming formulation. The highly non-convex nature of the model together with its huge size prevent the application of standard software. We use a solution approach designed to exploit the specific problem structure. Encouraging preliminary computational results are provided.     

A branch-and-price algorithm for the two-stage guillotine cutting stock problem

We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.     

New integer programming formulations and an exact algorithm for the ordered cutting stock problem

Apart from trim loss minimization, there are many other issues concerning cutting processes that arise in real production systems. One of these is related to the number of stacks that need to be opened near the cutting machines. Many researchers have worked in the last years on cutting stock problems with additional constraints on the number of open stacks. In this paper, we address a related problem: the Ordered Cutting Stock Problem (OCSP). In this case, a stack is opened for every new client's order, and it is closed only when all the items of that order are cut. The OSCP has been introduced recently in the literature. Our aim is to provide further insight into this problem. This paper describes three new integer programming formulations for solving it, and an exact algorithm based on column generation, branch-and-bound and cutting planes. We report on computational experiments on a set of random instances. The results show that good lower bounds can be computed quickly, and that optimal solutions can be found in a reasonable amount of time.