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
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.
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,
1) read all inputs into internal data structures
2) initialize goal-seeking function
set current_goal to 1st goal value
3) invoke GOAL-SEEKING function
4) invoke OUTPUT function for saved 'best arrangement'
5) EXIT program
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
11) set current_goal to next tighter tolerance goal
12) END WHILE
13) EXIT 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
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
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'.
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
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
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'.