ON THE OPTIMUM TWO-DIMENSIONAL ALLOCATION PROBLEM.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1966
- Accession Number
- AD0642761
Entities
People
- Murray J. Haims
Organizations
- New York University