
Accession Number : AD0642761
Title : ON THE OPTIMUM TWODIMENSIONAL ALLOCATION PROBLEM.
Descriptive Note : Technical rept.,
Corporate Author : NEW YORK UNIV N Y LAB FOR ELECTROSCIENCE RESEARCH
Personal Author(s) : Haims,Murray J.
Report Date : JUN 1966
Pagination or Media Count : 150
Abstract : The general twodimensional allocation problem is the problem of deciding how to cut twodimensional shapes from given sheets of stock material in an optimum manner without having to make an exhaustive search through all possible arrangements. Two categories of problems are studied. The first, known as templatelayout problems, require that one cut as many pieces as possible from a single sheet of material. The second, known as cuttingstock problems, require that pieces be cut from as many sheets as necessary in order that the number of pieces meet a fixed demand. The solution for the templatelayout problem is divided into two phases. First, the irregularshaped pieces are fitted together in clusters and enclosed by modules. Second, the resulting modules are packed into the rectangular sheets so that the arrangements optimize an objective function. The packing methods make it feasible to pack rectangular, Lshaped, and righttriangular modules in rectangular sheets. A test program has been written that can pack ten different rectangular modules into a family of sheets ranging from 1 square unit to 250 square units. The cutting stock problem is formulated as a linear programming problem. It is shown that the solution may be obtained by using the revised simplex method in conjunction with the algorithm for solving the templatelayout problem, at every pivot step, to generate new columns for the linear programming problem. (Author)
Descriptors : (*OPTIMIZATION, *SCHEDULING), MANUFACTURING, TEMPLATES, ECONOMICS, LINEAR PROGRAMMING, ALGORITHMS, DYNAMIC PROGRAMMING
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE