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'.