calling all Linux hackers...

IMO the developers of OE have never been forced to use it. I've defended this position on MS newsgroups. ;-)

-- Mark

Reply to
Mark Jerde
Loading thread data ...

This will be a simple 'command-line' program; reads all inputs from files,and produces another file as it's output.

It works with a _single_ type of material in any given run.

It assumes all input is: (a)syntactically correct, and (b) rational

INPUTS: 1) Inventory: A list of available material to cut pieces from. Each item consists of W and L dimension, and a quantity. there is a 'special value' for indicating an "infinite" resource. 2) Targets: A numbered (implicitly or explicitly) list of pieces to be cut. Each item is described by a W and L dimension, _and_ a flag as to whether the item can or can *not* be 'rotated' (For simplicity, if there are multiple items of the same dimension, they are listed individually.)

3) Parametric settings: A) Material lost to a cut (the blade 'kerf') B) "Oversize" adjustment -- either an absolute amount, or a percentage, by which pieces are "rough cut" larger than specified, to allow for later finishing to actual specified dimension. C) "Goals" The "percentage waste" points at which the program should output a set of results. A series of increasingly tighter tolerances the program should try to meet -- e.g. 50%, 30%, 20%, 15%, 10%, 7%, 5% D) "Time Limit", the point at which the program 'gives up', and outputs the "best match found so far", *IF* all the goals have -not- been met.

OUTPUTS: 1) List of items from inventory used: W and L of the inventory item W and L of each 'target' piece that comes from this inventory item. H and V 'offset' (from starting corner of inventory piece) for the starting corner of this 'target' piece. The sequence of 'cut' operations required,

CORE LOGIC:

MAIN PROGRAM: 1) read all inputs into internal data structures 2) initialize goal-seeking function set time-limit set current_goal to 1st goal value 3) invoke GOAL-SEEKING function 4) invoke OUTPUT function for saved 'best arrangement' 5) EXIT program

GOAL-SEEKING function: 01) set 'best prior arrangement' to "infinitely bad" 02) WHILE (any goals not met AND time-limit not exceeded) 03) examine next arrangement 04) IF less wasteful than best prior arrangement 05) save percentage waste factor for current ("best") arrangement 06) save current ("best") arrangement 07) IF less wasteful than current goal 08) invoke INTERMEDIATE-OUTPUT function 08) IF current_goal is tightest-tolerance goal 09) EXIT goal-seeking function 10) else 11) set current_goal to next tighter tolerance goal 12) END WHILE 13) EXIT function

INTERMEDIATE_OUTPUT function: 1) open scratch file to write at beginning of file 2) write timestamp to scratch file 3) write 'start of arrangement' header to scratch file 4) write 'percentage waste' value for saved arrangement to scratch file 5) write saved 'best arrangement' to scratch file 6) write 'end of arrangement' footer. to scratch file 7) close scratch file 8) EXIT function

OUTPUT function: 1) write 'start of arrangement' header to primary output 2) write 'percentage waste' value for saved arrangement to primary output 3) write saved 'best arrangement' to primary output 4) write 'end of arrangement' footer. to primary output 5) EXIT function

==========================

COMMENTS: The program obviously 'generalizes' to handle multiple 'kinds' of items, simply by making multiple passes, processing a single kind in each pass.

Trivial input enhancement to allow specifying a 'quantity' of a particular 'target' piece is *deliberately* excluded. whatever 'front-end' generates the list will be responsible for expanding any such "multiples".

*ALL* the 'hard stuff' is the 'goal seeking function'.

First enhancement would be some 'statistics' reporting: total sq. ft. used from 'inventory'. % waste etc.

Obviously, it is 'trivial' to add a 'cost' component to inventory items. and report a total cost at the end. Enhancement includes "cost of pieces", "cost of waste", "cost of stock returned to inventory", and "cost of scrap". "billable cost" would be 'cost of pieces' plus 'cost of scrap'.

A _separate_ program will take a generated cut-list, and do a "pull from inventory" operation, reducing inventory by the 'items used'. and adding any unused off-cuts back into inventory. It'll need saved parameters for minimum 'usable' stock size. anything below those minimums (length, width, and/or 'area') gets put in the 'scrap' list.

Another separate program will do "add to inventory", for items purchased.

*EVENTUALLY* 'inventory' _and_ the 'target' list are probably going to be implemented as "database". That lets people 'transparently' stick whatever other data desired onto the items, _without_ any impact on _this_ program.

WISH-LIST (*WAY* down the road): To be able to include "defects" in the 'inventory item' descriptions, and have the program 'work around' those defects, when doing the layout. this is pretty much irrelevant for sheet stock, but significant for lumber.

It complicates the goal-seeking logic _somewhat_ -- in that it's now not just fitting rectangular pieces into simple rectangular 'container objects'.

Reply to
Robert Bonomi

Hi All, I have been following this thread with a lot of interest as I am involved in the development of a Panel Optimization program PLUS 2D

formatting link
myself.

In addition I have been a long time CAD programmer, in the Unix environment, but have shifted to the Windows env.

I have found that there is a better return on investment on programms written for the windows environment...ie. more people buy your programs... Though my love for Unix has not deminished in the years, and would love to port my application to Unix/Mac/Palm but I reckone windows users are a much bigger market and more likely to pay_for/buy products, and I find it a little difficult to justify the costs involved. just my 2cents worth...

Reply to
Shrikanth S
< snip >

I've written a 2D nesting program that nests non-rectangular shapes in rectangular areas. I can provide some help in this area, if you want. It really is not all that difficult. A defect would simply be considered as an area where something was already nested.

Remove the NOT from my address, if you want to communicate with me.

Reply to
Paul Shirron

No I haven't, and that's always worth a try. However, I've talked to a lot of other developers about porting their stuff to Linux. I usually get the same kind of warm response I used to get at job interviews. Carefully stifled laughter until I'm on the other side of the door, then the sound of the deadbolt slamming home. :)

Reply to
Silvan

EMACS.

:)

Reply to
Walt

Start working in Python with either Tkinter or wxPython GUI frameworks and your problems will be solved. It is _hands down_ the best cross-platform environment I have ever worked in...

Reply to
Tim Daneliuk

I said "development environment" not "operating system."

Reply to
Silvan

Inventory should include Width, Length, Thickness, Species, Type (lumber, plywood, osb, etc), and grain direction and perhaps an indication of quarter, flat or plain sawn.

Target should include Width, Length, Thickness, Species, Type and grain direction.

Iterative algorithm. Aren't there already some better algorithms in the public literature? DAGS pentominos.

How is "less wasteful" quantified?

scott

Reply to
Scott Lurndal

Put your inventory in XML or otherwise use XML for the intermediate format. 90% of your parsing and sorting work is already finished for you then.

Reply to
Bruce Rowen
[SET MOOD = PLAYFUL]

On Thu, 11 Dec 2003 08:27:24 +0000, snipped-for-privacy@host122.r-bonomi.com (Robert Bonomi) brought forth from the murky depths:

Hah, with THIS group? (He make joke, Davey)

This is especially helpful with axe cuts. 5 settings oughta do 'er. Thin kerf, regular kerf, wide kerf, chainsaw kerf, and axe kerf.

Like determining OSB grain direction?

"I'm sorry, but the waste level on this project is 100%. What did you expect when using jum^H^H^Hpineywood?"

-------------------------------------------------------------------- I sent in my $5, so *

formatting link
why haven't I been 'saved'? * Graphic Design - Humorous T-shirts

Reply to
Larry Jaques

Crikey. Looks like a good recipe for a logical, focused beginning, but I can also clearly see that I am *way* out of my league here.

Maybe I would be better equipped to hack on the eventual front-end for this thing.

Run with it, please, by all means, but I don't think I have anything useful to offer at this stage.

Reply to
Silvan

Thickness, species, type, and 'indiction of quarter, flat, or plain sawn' are _irrelevant_ at "Phase I"

READ THE SPECIFICATION -- "it works with a _single_ type of material..."

For reasons identified above, at "phase I", 'thickness, species, and type' are *irrelevant*.

As such they are *deliberately* omitted.

The 2-d packing problem is known to be NP-complete. It is _not_possible_ to write a finite algorithm to come up with the 'best' solution.

You are left with "try it and find out" approaches.

The *ONLY* way to tell which of two (or more) arrangements is better is to _compare_ the candidates.

The postulated 'better algorithm' applies _only_ to the selection of the "next arrangement" to be evaluated

The total surface ares of the stock removed from inventory is broken down into three components: area of desired pieces area of off-cuts big enough to return to inventory area of 'scrap'

The smaller the total area removed from inventory, the the less wasteful the layout.

For "equivalent" demands from inventory, the one with the smaller amount of 'scrap' is preferable.

By design, one makes the 'less wasteful' evaluation a _separate_ function, so that anyone can 'relatively trivially' swap out any provided methodology for one that meets _their_ 'individualized' needs.

For similar reasons the selection of the 'next arrangement' to evaluate is also modularized -- allowing one to insert a 'better' routine, if/when it is developed, and/or *test* different selection algorithms.

Reply to
Robert Bonomi

[SET RESPONSE = "appropriate to questions"]

Nah! Only 5 is woefully inadequate.

Gotta consider the size of the blade for circular saws -- a 48" dia sawmill blade takes a MUCH bigger cut than a 10" WWII thin-kerf.

For chain-saws, it depends on the size (width) of the chain.

As for axes, it is *obvious* that you have to allow for a 'bit' more losses with a double-bitted axe than a single-bitted one. *snicker*

That's _trivial_! "BY DEFINITION", grain runs the 'length' of the stock. If you want it running across the 'short direction', you just define the piece as having a "width" that is greater than the 'length'. "No problemo."

100% waste, or more is _not_ unheard of. If you figure 'waste' as size of off-cuts and scrap vs size of 'needed' pieces.

Trivial example. You need a 2'x2' piece of ply, and all you have is full sheets.

28 sq ft of 'waste', vs 4 sq ft of 'needed'.

"waste level" is SEVEN HUNDRED PERCENT (!!)

Reply to
Robert Bonomi

wow, I'm beginning to think this might even work with a CNC machine. You know that router thingey that slides around and cuts panels, then spits them out as furniture.

Great first Draft, think I'll sit back and watch the progress in amazement. I can do a lot of things but my mind sure don't work like that.

Rich

Reply to
EvoDawg

HomeOwnersHub website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.