Dynamic programming algorithms for the cutting problem of equal circles

摘要

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.