Sage Journals: Discover world-class research

Abstract

The current paper presents an approach for generating cutting patterns of equal circular blanks processed with the shearing and punching process, which includes two stages. A guillotine machine divides the sheet into strips at the first stage. A stamping press punches out the blanks from the strips at the second stage. Normal patterns consisting of orthogonal strips are proposed and four dynamic programming algorithms for generating them are presented. The first two algorithms deal with the unconstrained problem in which there is no constraint on the number of blanks included in a pattern, and the last two deal with the constrained problem in which the blank demand must be met exactly. The computational results indicate that the algorithms are efficient in both computation time and material utilization.

Keywords

algorithms dynamic programming two-dimensional cutting circles CAD

References

Stoyan

Y. G.

Yaskov

G. N.

Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. Int. Trans. Opl Res., 1998, 5, 45–57.

Dowsland

Optimizing the palletization of cylinders in cases. OR Spektrum, 1991, 13, 204–212.

George

J. A.

George

J. M.

Lamar

B. W.

Packing different-sized circles into a rectangular container. Eur. J. Opl Res., 1995, 84, 693–712.

Hifi

Rym

M. H.

Approximate algorithms for constrained circular cutting problems. Computers Ops Res., 2004, 31, 675–694.

Stoyan

Y. G.

Yaskov

A mathematical model and a solution method for the problem of placing various-sized circles into a strip. Eur. J. Opl Res., 2004, 156, 590–600.

Locatelli

Raber

Packing equal circles in a square: A deterministic global optimization approach. Discrete Appl. Math., 2002, 122, 139–166.

Cui

Generating optimal T-shape cutting patterns for circular blanks. Computers Ops Res., 2005, 32, 143–152.

Birgin

E. G.

Martínez

J. M.

Ronconi

D. P.

Optimizing the packing of cylinders into a rectangular container: A nonlinear approach. Eur. J. Opl Res., 2005, 160, 19–33.

Agrawal

P. K.

Minimizing trim loss in cutting rectangular blanks of a single size form a rectangular sheet using orthogonal guillotine cuts. Eur. J. Opl Res., 1993, 64, 410–422.

10.

Cui

Zhou

Generating optimal cutting patterns for rectangular blanks of a single size. J. Opl Res. Soc., 2002, 53, 1338–1346.

11.

Tarnowski

A. G.

Terno

Scheithauer

A polynomial time algorithm for the guillotine palletloading problem. INFOR, 1994, 32, 275–287.

12.

Arslanov

M. Z.

Continued fractions in optimal cutting of a rectangular sheet into equal small rectangles. Eur. J. Opl Res., 2000, 125, 239–248.

13.

Cui

Dynamic programming algorithms for the optimal cutting of equal rectangles. Appl. Math. Modelling, 2005, 29, 1040–1053.

14.

Cui

Huang

Dynamic programming algorithms for generating optimal strip layouts. Comp. Optimization Applic., 2006, 33, 287–301.

15.

Wascher

Haussner

Schumann

An improved typology of cutting and packing problems. Eur. J. Opl Res., 2005. DOI:10.1016.j.ejor.2005.12.047.

16.

Cheng

C. H.

Feiring

B. R.

Cheng

T. C. E.

Cutting stock problem - a survey. Int. J. Prod. Econ., 1994, 36, 291–305.

17.

Lodi

Martello

Monaci

Two-dimensional packing problems: A survey. Eur. J. Opl Res., 2002, 141, 241–252.

Dynamic programming algorithms for the cutting problem of equal circles

Abstract

Abstract

Keywords

References