| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1519.1 | is this stated correctly ? | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Thu Nov 07 1991 14:11 | 6 |
|
Why not just cut almost anywhere, parallel to an edge ? That will give you
one piece of size A and one of size B.
|
| 1519.2 | Combinatorial Minimization | CIVAGE::LYNN | Lynn Yarbrough @WNP DTN 427-5663 | Thu Nov 07 1991 15:19 | 15 |
| The general problem space is related to problems in the garment industry,
where you want to cut many suits (e.g.) from a bolt of cloth with minimum
waste (and also with certain other constraints e.g. direction of weave).
The problem in .0 is a simple instance with many of the more complex
constraints removed. As presented, it's a combinatorial minimization
problem [find the minimum number of sheets of plywood to make n pairs of
pieces]. It's also related to the classical Knapsack problem. I think it's
likely to be NP-complete (i.e. the cost of a *complete* solution is likely
to be exponential in the number of pieces), but there may be reasonably
cheap ways of finding near-optimal solutions.
The method of Simulated Annealing has recently been used to attack such
problems with good success. It's not immediately clear how to express this
particular problem in that framework, but the approach is discussed in
"Numerical Recipes".
|
| 1519.3 | | SMOOT::ROTH | The 13th Floor Elevators | Fri Nov 08 1991 12:01 | 10 |
| Re: .1
I should have pointed out that the end goal was to as many shapes as
possible from a single sheet of stock.
Re: .2
Thanks for the reference... I will check into that.
Lee
|
| 1519.4 | some assumptions | CSSE::NEILSEN | Wally Neilsen-Steinhardt | Fri Nov 08 1991 12:21 | 14 |
| I assume that
the sizes of rectanges A and B are given (and that they are
smaller than the 4 x 8 piece you start with)
you are willing to ignore kerf
you are willing to ignore the setup costs of the cuts (cutting plywood
in the real world with a circular saw, I would want all my cuts to
go all the way across the piece being cut. I would also accept some
additional waste to minimize the number of cuts.)
I have no idea how to solve the general problem.
|
| 1519.5 | More details, please | CIVAGE::LYNN | Lynn Yarbrough @WNP DTN 427-5663 | Fri Nov 08 1991 13:14 | 4 |
| What values of 'A' and 'B' are of interest?
Would edge-glued constructions be acceptable (e.g. 1x4 cut in half to make
2x2)?
|
| 1519.6 | DATA | SMOOT::ROTH | The 13th Floor Elevators | Mon Nov 11 1991 10:19 | 16 |
| Re: <<< Note 1519.5 by CIVAGE::LYNN "Lynn Yarbrough @WNP DTN 427-5663" >>>
>What values of 'A' and 'B' are of interest?
Let's say somthing like 8" x 10" for piece "A" and 2" x 12" for piece
"B".
>Would edge-glued constructions be acceptable (e.g. 1x4 cut in half to make
>2x2)?
No gluing allowed.
Disregard kerf widths, assume no cutting loss.
Lee
|
| 1519.7 | My, that's convenient! | CIVAGE::LYNN | Lynn Yarbrough @WNP DTN 427-5663 | Tue Nov 12 1991 10:34 | 23 |
| >Let's say something like 8" x 10" for piece "A" and 2" x 12" for piece
>"B".
You're in luck.
One A piece + 1 B piece is 8*10+2*12 = 104 sqin in area, and the whole
4'x8' sheet is 48"*96" = 4608 sqin. So you can hope for [4608/104] = 44
pairs of {A,B}, with 4608-44*104 = 32 sqin left over.
Cut the first 70" of the sheet into 7 rows of 6 8x10 pieces, 42 in all. Now
cut off 18" of rows of 4 2x12 pieces, 36 in all. Cut the remaining 8x48
piece into 2 8x10 and 8 2*12, e.g.
10 10 12 12 4
+-----+-----+------+------+---+
| | |------+------+ |
8 | | |------+------+ |
| | |------+------+ |
+-----+-----+------+------+---+
So you have 44 8x10, 44 2x12, and one neat 4"x8" chunk left over. On that you
can draw a picture of the layout of the original sheet of 4'x8', to remind
yourself how to do it again the next time :-) !
|