Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Mathematical Solution of a Two Dimensional Cutting Problem

IP.com Disclosure Number: IPCOM000075295D
Original Publication Date: 1971-Aug-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 26K

Publishing Venue

IBM

Related People

Marconi, R: AUTHOR

Abstract

Given rectangular stock sheets of set sizes whose unit cost varies according to size, smaller rectangles should be cut in the sizes and quantities to meet production orders with the minimum waste. The classic approach is: (Image Omitted)

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 57% of the total text.

Page 1 of 3

Mathematical Solution of a Two Dimensional Cutting Problem

Given rectangular stock sheets of set sizes whose unit cost varies according to size, smaller rectangles should be cut in the sizes and quantities to meet production orders with the minimum waste. The classic approach is:

(Image Omitted)

The problem of the prohibitive number of possible cutting patterns is solved by generating only one pattern at a time, by a "knapsack" type dynamic programming method, to generate the best column vector at each "LP pricing" stage.

In determining a two-dimensional cutting pattern, the dynamic programming is used in two steps.

Step 1 is to calculate the best value (expressed in terms of the shadow prices b(i) of the current nonoptimal solution) of a longitudinal strip containing pieces of the orders whose width is not greater than the width of the strip. The number of different strips is equal to the number m of orders.

Step 2 is to determine the best fit of the strips in each of the stock sheets to be cut.

Four points must be underlined:
1) The cutting patterns actually may involve a three-stage

cutting, rather

than a two-stage, because the requirement on the width

expressed in step 1 to determine the cutting patterns.
2) The stock should be available in unlimited quantities, in the

various sizes.
3) Optimization should be, on choice, one or two-dimensional, to

save machine time when it is proper.
4) There is no limit on the maximum number of available knives.

The classic approach has been modified:
1) Substitute the condition, used in step 1

(Image Omitted)

The various types of stock are virtually regarded as fictitious orders having zero sizes and required in maximum quantity g(1). The...