Abstract
A method is developed for cutting up sheets with defective areas into given pieces while minimizing waste. The sheets, the pieces, and the defects are all rectangles, these latter to be identified by the coordinates of two opposite corners in a coordinate system attached to the sheet. The cutting is done in in three stages. If the length of the sheet is along the x-axis, the first cuts are made parallel to the y-axis, obtaining “sections.” The sections are then cut into “strips” parallel to the x-axis, and, finally, the strips into “pieces” parallel to the y-axis. The procedure uses dynamic programming, which requires a value to be attached to each size. The computer program senses the defects and fits pieces into the clear portion of the sheet in such a way that the total value is a maximum. In order to shorten machine time, some simplifying shortcuts are made.