Strip generation algorithms for constrained two-dimensional two-staged cutting problems

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, …, n, is characterized by a length l_i, a width w_i, a profit (or weight) c_i and an upper demand value b_i. The upper demand value is the maximum number of pieces of type i which can be cut on rectangle (L, W). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure. We evaluate the performance of these algorithms on instances extracted from the literature.     

Roll cutting in the curtain industry,or: A well-solvable allocation problem

We study the problem of cutting a number of pieces of the same length from n rolls of different lengths so that the remaining part of each utilized roll is either sufficiently short or sufficiently long. A piece is ‘sufficiently short’, if it is shorter than a pre-specified threshold value δ_min, so that it can be thrown away as it cannot be used again for cutting future orders. And a piece is ‘sufficiently long’, if it is longer than a pre-specified threshold value δ_max (with δ_max > δ_min), so that it can reasonably be expected to be usable for cutting future orders of almost any length. We show that this problem, faced by a curtaining wholesaler, is solvable in O(nlogn) time by analyzing a non-trivial class of allocation problems.     

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.     

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.     

Dynamic programming algorithms for the optimal cutting of equal rectangles

This paper presents dynamic programming algorithms for generating optimal guillotine-cutting patterns of equal rectangles. The algorithms are applicable for solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. The algorithms are able to generate the simplest optimal patterns to simplify the cutting process. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths no longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. The computational results indicate that the algorithms presented are more efficient than the branch-and-bound algorithms, which are the best algorithms so far that can guarantee the simplest patterns.     

Algorithms for Unconstrained Two-Dimensional Guillotine Cutting

In this paper we consider the unconstrained, two-dimensional, guillotine cutting problem. This is the problem that occurs in the cutting of a number of rectangular pieces from a single large rectangle, so as to maximize the value of the pieces cut, where any cuts that are made are restricted to be guillotine cuts.We consider both the staged version of the problem (where the cutting is performed in a number of distinct stages) and the general (non-staged) version of the problem.A number of algorithms, both heuristic and optimal, based upon dynamic programming are presented. Computational results are given for large problems.     

Simple block patterns for the two-dimensional cutting problem

This paper presents an algorithm for the unconstrained two-dimensional cutting problem of rectangular pieces. It proposes the simple block (SB) pattern consisting of simple blocks. The SB pattern is defined recursively. Each cut on the stock plate produces just one simple block. A horizontal cut produces a horizontal block with width equal to that of the leftmost piece in the block. A vertical cut produces a vertical block with length equal to that of the bottommost piece in the block. The algorithm generates the optimal SB pattern recursively, and selects optimally the first piece in each block. It uses upper bound to prune some unpromising branches during the searching process. The computational results indicate that the algorithm is highly efficient in improving material utilization, and the computation time is reasonable.     

A hybrid approach for optimization of one-dimensional cutting

The article examines a hybrid approach for optimizing one-dimensional stock cutting. The proposed approach combines two methods: the pattern-oriented LP-based method, and the item-oriented sequential heuristic procedure. The purpose of such a combined method is its ability to cut order lengths in exactly required number of pieces and to cumulate consecutive residual lengths in one piece which could be used later. The sample problem is presented and solved.     

Generating optimal cutting patterns for rectangular blanks of a single size

This paper deals with the problem of minimizing trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts. First we prove that we can obtain the unconstrained optimal layout by searching among normal multi-section layouts. Next we present an unconstrained algorithm to search for it. The unconstrained algorithm uses a branch-and-bound method with a tight upper bound. Later we discuss the algorithm for the constrained problem where the blank demand must be met exactly. Finally, the unconstrained algorithm is extended to cope with the blade length constraint. Experimental computations show that the algorithms are extremely efficient.     

Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

In this paper the problem of optimally guillotine cutting a rectangle (A, B  ) into small rectangles of two kinds is considered. Rectangles of the first kind (c,_ai),i∈I$(c\text{,}{a}_i)\text{,}i\in I$ have the same width, and their heights can be various. Rectangles of the second kind (_bj,d),j∈J$(b_j\text{,}d)\text{,}j\in J$ have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27–51; A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93–124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds.     

Dynamic Programming Algorithms for Generating Optimal Strip Layouts

This paper presents dynamic programming algorithms for generating optimal strip layouts of equal blanks processed by shearing and punching. The shearing and punching process includes two stages. The sheet is cut into strips using orthogonal guillotine cuts at the first stage. The blanks are punched from the strips at the second stage. The algorithms are applicable in solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths not longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. Experimental computations show that the algorithms are efficient.     

A tree search algorithm for solving the multi-dimensional strip packing problem with guillotine cutting constraint

The article presents a tree search algorithm (TRSA) for the strip packing problem in two and three dimensions with guillotine cutting constraint. In the 3D-SPP a set of rectangular items (boxes) and a container with fixed width and height but variable length are given. An arrangement of all boxes within the container has to be determined so that the required length is minimised. The 2D-SPP is analogously defined. The proposed TRSA is based on a tree search algorithm for the container loading problem by Fanslau and Bortfeldt (INFORMS J. Comput. 22:222?C235, 2010). The TRSA generates guillotine packing patterns throughout. In a comparison with all recently proposed 3D-SPP methods the TRSA performs very competitive. Fine results are also achieved for the 2D-SPP.     

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.     

Network flows and non-guillotine cutting patterns

Up till now there has been no exact and effective algorithm for the problem of finding optimal cutting patterns of rectangles which are not restricted to those with the ‘guillotine’ property. This problem can be interpreted in a resource constrained scheduling context. The contribution of this paper to this topic is a good characterization of the flow functions and graphs corresponding to cutting patterns.     

Complexity of Linear Problems with a Fixed Output Basis

We use an information-based complexity approach to study the complexity of approximation of linear operators. We assume that the values of a linear operator may be elements of an infinite dimensional space G. It seems reasonable to look for an approximation as a linear combination of some elements g_i from the space G and compute only the coefficients c_i of this linear combination. We study the case when the elements g_i are fixed and compare it with the case where the g_i can be chosen arbitrarily. We show examples of linear problems where a significant output data compression is possible by the use of a nonlinear algorithm, and this nonlinear algorithm is much better than all linear algorithms. We also provide an example of a linear problem for which one piece of information is enough whereas an optimal (minimal cost) algorithm must use information of much higher cardinality.     

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.     

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method.     

Sharp converse theorem ofL p -polynomial approximation

For algebraic polynomial approximation on [?1,1] the analogue of the Zygmund-Timan type converse Marchaud inequality is proved. These are the exact converse estimates inL ^p spaces when 1<p<∞. The proof forp>2 uses Hirschman's multiplier theory, while forp相似文献   

An arc flow-based optimization approach for the two-stage guillotine strip cutting problem

Despite its broad range of industrial applications, the two-stage guillotine restriction has received very scant attention in the strip cutting literature. An integer linear programming model that is based on a special graph structure is devised for this strongly NP-hard problem. In addition to being easy to implement, the empirical study on a large set of instances from the literature and from real industrial world cases shows the efficiency of the proposed method while solving instances with high multiplicity factor.