Generating optimal cutting patterns for rectangular blanks of a single size
- PDF / 308,645 Bytes
- 9 Pages / 595 x 794 pts Page_size
- 15 Downloads / 138 Views
#2002 Operational Research Society Ltd. All rights reserved. 0160-5682/02 $15.00 www.palgrave-journals.com/jors
Generating optimal cutting patterns for rectangular blanks of a single size Y Cui* and R Zhou CAD=CAM Engineering Research Center, Nanjing University of Aeronautics and Astronautics, Nanjing, 210016, China 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. Journal of the Operational Research Society (2002) 53, 1338–1346. doi:10.1057/palgrave.jors.2601451 Keywords: cutting stock problem; packing; optimization; pallet loading problem; manufacturing
Introduction The rectangular cutting stock problem occurs when rectangular sheets in stock are to be cut into smaller rectangles, or blanks, to meet a customer’s demand.1–3 Where the blank area must be less than or equal to the sheet area, some trim loss is expected. Some customers may need blanks of different size. Those involved in mass production may want a large number of blanks of the same size. In the former case, nested layouts are often used and blanks of different size may appear in a nested layout. In the latter case, only blanks of the same size can appear in a layout. We refer to the cutting stock problem of rectangular blanks of a single size as the CSPRBSS. This type of cutting stock problem is also identified as the guillotine pallet loading problem4–5 and is denoted 2=B=O=C of guillotine type.6 Although a large number of techniques are available to minimize trim loss when nested layouts are permitted,7 few papers have been published on the CSPRBSS.8–11 Reference 9 proposes a heuristic to generate layouts for the CSPRBSS. These layouts cannot be cut by a guillotine shear. Agrawal presented an exact algorithm to generate optimal guillotine layouts for the CSPRBSS.10 When the algorithm is applied in practice, the following drawbacks might be found: 1. It is inferred through graphics that the optimal layout is included in the normal multi-section layouts. No strict proof is given about the correctness of the optimality.
2. The problem discussed in his work is unconstrained. Since there is no constraint on the blank demand, the algorithm presented cannot be used to solve the constrained cutting stock problem in which the blank demand must be exact. 3. The blade length of the guillotine shear is not considered. If the blade length is shorter than the sheet length, it may be impossible to cut the blanks from the generate
Data Loading...
