Accession Number : AD0642761

Title :   ON THE OPTIMUM TWO-DIMENSIONAL 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 two-dimensional allocation problem is the problem of deciding how to cut two-dimensional 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 template-layout problems, require that one cut as many pieces as possible from a single sheet of material. The second, known as cutting-stock 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 template-layout problem is divided into two phases. First, the irregular-shaped 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, L-shaped, and right-triangular 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 template-layout 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