Constrained two-dimensional cutting: an improvement of Christofides and Whitlock's exact algorithm
- PDF / 237,177 Bytes
- 8 Pages / 595 x 842 pts (A4) Page_size
- 1 Downloads / 131 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
Constrained two-dimensional cutting: an improvement of Christo®des and Whitlock's exact algorithm M Hi®1 and V Zissimopoulos2 1
Universite de Paris I, France and 2Universite de Paris-Sud, France
Christo®des and Whitlock have developed a top-down algorithm which combines in a nice tree search procedure Gilmore and Gomory's algorithm and a transportation routine called at each node of the tree for solving exactly the constrained two-dimensional cutting problem. Recently, another bottom-up algorithm has been developed and reported as being more ef®cient. In this paper, we propose a modi®cation to the branching strategy and we introduce the onedimensional bounded knapsack in the original Christo®des and Whitlock algorithm. Then, by exploiting dynamic programming properties we obtain good lower and upper bounds which lead to signi®cant branching cuts, resulting in a drastic reduction of calls of the transportation routine. Finally, we propose an incremental solution of the numerous generated transportation problems. The resulting algorithm reveals superior performance to other known algorithms. Keywords: cutting problem; knapsack; dynamic programming; heuristic
Introduction 1±4
The constrained two-dimensional cutting problem (TDC) consists of cutting a rectangular plate of ®xed dimensions into smaller rectangular pieces of given dimensions. Each piece has a utility value and the objective is to maximize the sum of utility values of the produced pieces without violating some ®xed bounds on the number of repetition of a piece in the solution. A set of smaller pieces de®nes a cutting pattern if these pieces can be produced by a sequence of possible cuts on the initial plate. The pieces produced that are not one of the required pieces are considered waste in the cutting pattern. If bounds are not imposed on the number of repetitions of a piece, the problem is known as the unconstrained twodimensional cutting problem5±7. Production of glass, metal sheets, leather or multiprogrammed computer systems, are some obvious examples of applications of these problems. In such applications, the objective is either to minimize the waste or to maximize the total pro®t required to realize some given quantities of rectangular pieces. Frequently, in order to reduce the number of possible cutting patterns, we place two restrictions. The ®rst is to consider only cuts which are of guillotine type, namely horizontal and vertical cuts producing two sub-rectangles. The second one is to suppose that pieces have ®xed orientation, namely a piece of length l and height h is different to a piece of length h and height l. However, these restrictions do not considerably limit the scope of applicaCorrespondence: V Zissimopoulos, LRI, URA 410 CNRS, Universite de Paris Sud, Centre d'Orsay, 91405 Orsay, France.
tions, since a large number of real-word problems naturally have such restrictions. Non-guillotine cases have been treated by Beasley8. Problem formulation The
Data Loading...
