A Multistage Solution of the Template-Layout Problem

Abstract

The template-layout problem is to determine how to cut irregular-shaped two-dimensional pieces out of given stock sheets in an optimum manner without making an exhaustive search of all possible arrangements of the pieces. An algorithm is described for solving template-layout problems with a digital computer. The method of solution requires that the irregular shapes be enclosed, singly or in combination, in minimum area rectangles called modules. Individual modules will contain from one to perhaps eight optimally fitted irregular pieces. The modules are then packed into the given stock sheet(s) so as to optimize a specified objective function. The packing is carried out with a dynamic programming algorithm, which converts the multivariable problem into a multistage one. Successive iterations of the algorithm are used to determine whether higher order modules (containing more irregular-shaped pieces) improve the solution. A detailed description of the algorithm is given. An illustrative example is included and its computer solution is described. The paper concludes with an extension of the algorithm to an improved version which can be expected to yield solutions more closely approaching the true optimum.