A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size

We consider a two-dimensional cutting stock problem where stock of different sizes is available, and a set of rectangular items has to be obtained through two-staged guillotine cuts. We propose a heuristic algorithm, based on column generation, which requires as its subproblem the solution of a two-dimensional knapsack problem with two-staged guillotines cuts. A further contribution of the paper consists in the definition of a mixed integer linear programming model for the solution of this knapsack problem, as well as a heuristic procedure based on dynamic programming. Computational experiments show the effectiveness of the proposed approach, which obtains very small optimality gaps and outperforms the heuristic algorithm proposed by Cintra et al. [3].     

The two-dimensional cutting stock problem revisited

In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k=2 stages cannot guarantee any bounded asymptotic performance ratio. k=3 stages lead to asymptotic performance ratios arbitrarily close to 1.69103; this bound is tight. Finally, k=4 stages yield asymptotic performance ratios arbitrarily close to 1.Steve Seiden died in a tragic accident on June 11, 2002. This paper resulted from a number of email discussions between the authors in spring 2002.     

An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

The irregular strip packing problem is a combinatorial optimization problem that requires to place a given set of two-dimensional polygons within a rectangular container so that no polygon overlaps with other polygons or protrudes from the container, where each polygon is not necessarily convex. The container has a fixed width, while its length can change so that all polygons are placed in it. The objective is to find a layout of the set of polygons that minimizes the length of the container.We propose an algorithm that separates overlapping polygons based on nonlinear programming, and an algorithm that swaps two polygons in a layout so as to find their new positions in the layout with the least overlap. We incorporate these algorithms as components into an iterated local search algorithm for the overlap minimization problem and then develop an algorithm for the irregular strip packing problem using the iterated local search algorithm. Computational comparisons on representative instances disclose that our algorithm is competitive with other existing algorithms. Moreover, our algorithm updates several best known results.     

A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering

The nesting problem is commonly encountered in sheet metal, clothing and shoe-making industries. The nesting problem is a combinatorial optimization problem in which a given set of irregular polygons is required to be placed on a rectangular sheet. The objective is to minimize the length of the sheet while having all polygons inside the sheet without overlap. In this study, a methodology that hybridizes cuckoo search and guided local search optimization techniques is proposed.     

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.     

The cutting stock problem and integer rounding

An integer programming problem is said to have the integer round-up property if its optimal value is given by the least integer greater than or equal to the optimal value of its linear programming relaxation. In this paper we prove that certain classes of cutting stock problems have the integer round-up property. The proof of these results relies upon the decomposition properties of certain knapsack polyhedra.This research was partially supported by National Science Foundation grants ECS-8005350 and 81-13534 to Cornell University.     

An integrated cutting stock and sequencing problem

In this paper an integrated problem formulated as an integer linear programming problem is presented to find an optimal solution to the cutting stock problem under particular pattern sequencing constraints. The solution uses a Lagrangian approach. The dual problem is solved using a modified subgradient method. A heuristic for the integrated problem is also presented. The computational results obtained from a set of unidimensional instances that use these procedures are reported.     

The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.     

Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns

Two-staged patterns are often used in manufacturing industries to divide stock plates into rectangular items. A heuristic algorithm is presented to solve the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. It uses the column-generation method to solve the residual problems repeatedly, until the demands of all items are satisfied. Each pattern is generated using a procedure for the constrained single large object placement problem to guarantee the convergence of the algorithm. The computational results of benchmark and practical instances indicate the following: (1) the algorithm can solve most instances to optimality, with the gap to optimality being at most one plate for those solutions whose optimality is not proven and (2) for the instances tested, the algorithm is more efficient (on average) in reducing the number of plates used than a published algorithm and a commercial stock cutting software package.     

The cutting stock problem for large sections in the iron and steel industries

The characteristics of a cutting stock problem for large sections in the iron and steel industries are as follows:(1) There is a variety of criterions such as maximizing yield and increasing effeciency of production lines. (2) A cutting stock problem is accompanied by an optimal stock selection problem. A two-phase algorithm is developed, using an heuristic method. This algorithm gives nearly optimal solutions in real time. It is applied to both batch-solving and on-line solving of one-dimensional cutting of large section. The new algorithm has played an important role in a large-section production system to increase the yield by approximately 2.5%.     

A heuristic for the one-dimensional cutting stock problem with usable leftover

A heuristic algorithm for the one-dimensional cutting stock problem with usable leftover (residual length) is presented. The algorithm consists of two procedures. The first is a linear programming procedure that fulfills the major portion of the item demand. The second is a sequential heuristic procedure that fulfills the remaining portion of the item demand. The algorithm can balance the cost of the consumed bars, the profit from leftovers and the profit from shorter stocks reduction. The computational results show that the algorithm performs better than a recently published algorithm.     

An improved typology of cutting and packing problems

The number of publications in the area of Cutting and Packing (C&P) has increased considerably over the last two decades. The typology of C&P problems introduced by Dyckhoff [Dyckhoff, H., 1990. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159] initially provided an excellent instrument for the organisation and categorisation of existing and new literature. However, over the years also some deficiencies of this typology became evident, which created problems in dealing with recent developments and prevented it from being accepted more generally. In this paper, the authors present an improved typology, which is partially based on Dyckhoff’s original ideas, but introduces new categorisation criteria, which define problem categories different from those of Dyckhoff. Furthermore, a new, consistent system of names is suggested for these problem categories. Finally, the practicability of the new scheme is demonstrated by using it as a basis for a categorisation of the C&P literature from the years between 1995 and 2004.     

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.     

Optimising the cutting of wood fibre plates in the hardboard industry

Hardboard companies transform eucalyptus trunks into rectangular wood fibre plates basically by means of processes of disintegration and reconstitution of wood fibres. Such plates called hardboards are then cut into ordered items (smaller rectangles) to satisfy customer demands. In this paper, we present approaches to generate cutting patterns that minimize the cost or waste of material, considering different particular constraints associated with longitudinal and transversal saws, head cuts, book rotation and item unloading stations of the cutting machine. The methods are based on dynamic programming recursive formulas combined with greedy constructive heuristics and the primal simplex algorithm. To illustrate the application of these approaches, a case study was carried out in a Brazilian hardboard company. The results show that the approaches are able to produce better solutions than the ones currently used by the company.     

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.     

Exact algorithm for generating two-segment cutting patterns of punched strips

Metal plates are often divided into items in two stages. First a guillotine shear cuts the plate into strips at the shearing stage, and then a stamping press punches out the items from the strips at the punching stage. This paper presents an algorithm for generating optimal two-segment cutting patterns of strips at the shearing stage. An orthogonal cut divides the plate into two segments, each of which contains strips of the same direction and length. The algorithm uses dynamic programming techniques to determine the optimal strip layouts on segments of various lengths, and selects two segments to appear in the optimal pattern. The segments are considered in increasing order of their lengths, so that dominant properties can be used to shorten the computation time. The computational results indicate that the algorithm is efficient in both material utilization and computation time.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

A BRANCH-AND-PRICE ALGORITHM FOR SOLVING THE CUTTING STRIPS PROBLEM

After giving a suitable model for the cutting strips problem, we present a branch-and-price algorithm for it by combining the column generation technique and the branch-and-hound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computarional experience is reported.     

A note on the approximability of cutting stock problems

Cutting stock problems and bin packing problems are basically the same problems. They differ essentially on the variability of the input items. In the first, we have a set of items, each item with a given multiplicity; in the second, we have simply a list of items (each of which we may assume to have multiplicity 1). Many approximation algorithms have been designed for packing problems; a natural question is whether some of these algorithms can be extended to cutting stock problems. We define the notion of “well-behaved” algorithms and show that well-behaved approximation algorithms for one, two and higher dimensional bin packing problems can be translated to approximation algorithms for cutting stock problems with the same approximation ratios.