Cut List

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

 

Search

 

Search DelphiForFun.org only

Support DFF

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

In Association with Amazon.com

 

Support DFF

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

 

 

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

 

Search DelphiForFun.org only

 

 

 

 

Problem Description

A "Cut List" shows how to cut a given set of parts from a given set of available stock.  This program creates a diagram showing the stock pieces and how the required parts may be cut from them.  

Data may created, deleted, modified and saved to a file for later use. Users can specify the width of material lost during cutting (saw blade kerf width), and the minimum dimension of waste material to report.

Solution searches give priority to crosscuts (vertical on the screen) or rip-cuts (horizontal) first or will try a Combination approach using all possible mixes of both types of cuts.
   

Background & Techniques

This program was originally written 10 years ago, in 1993, to solve a particular woodworking problem.   This year I'm making picture frames for motivational posters for our 7 grandkids and needed to decide whether to buy the backing and Plexiglas pieces precut or cut it myself from 4'X8' sheets.  (Only 6 pieces 22"x28" can be cut from a sheet, so precuts were a better choice.) 

I decided to update and publish the program for others to play with.   I have included several sample files which should make things clear.    A couple of potentially confusing points:

bullet"Width"  of boards is represented vertically on the screen.  "Length" of boards is represented in the horizontal screen direction. 
bulletThere are three options controlling the solution search (Cross cuts first, Rip cuts first, and Combination).   I recommend trying all three and using the one you like best.  The "Combination" option tries all combinations of ripping and cross cutting to find the best solution. 

The  best solution here is defined as the cutting pattern which produces the  leftover  piece with the largest area.

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

Many changes have taken place in the past 10 years - in computer speed more than in Delphi.    The original 1993 program used an OnIdle exit, DoIt, to force processing into the background and had a fairly elaborate record mechanism to save state information between calls.  An OnIdle exit must relinquish control back to the system fairly often in order to avoid impacting other applications and therefore must be able to pick up where it left off at each entry.     All of that code was removed in the current version because computers are 10 times faster today.    Logically, DoIt could now be merged into  the Solve procedure which does the initial search setup.  This has not been done. 

Two classes defined the parts:  TBoard contains dimension information for a board and TBoardList is a TStringList descendant which contains the boards as TBoard Objects attached to each entry.  The Strings associated with each entry contain a string version of the current sort field.   TBoardList objects are used for several purposes, they contain the lists of required parts, the available supply, the leftover pieces after each piece is cut (which are merged back into the supply list for possible use in cutting more pieces), and for working and "best" versions of these lists.

I cleaned up the graphics some and made the drawings respond to resizing.  Most other code is the way it was written 10 years ago.   I'm also sure that any bugs you find are the result of errors made 10 years ago and not during the current revisions.  Surely not!  

Addendum January 15, 2005:   A few needed fixes were posted today to create Version 2.  

bulletThe European comma used for decimal point did not work properly when files were saved and restored.  I think it is working now, but I have a hard time testing it here.     
bulletThe material editing process has been improved, now  pops up a menu to let users modify, insert, delete, rotate, or duplicate parts.
bulletFixed some sort errors to make the solving process work better (i.e. more like I thought it should work). .  

Addendum February 20, 2005:  Version 2.1 posted today includes two nice enhancements suggested by  users:

bulletA "Print" option can now print solutions - the Parts list, the Material list, and the Cutting Diagram.
bulletParts can now be assigned names which will be saved in project files and printed with solutions.   

I also fixed a bug or two in the way that Combination solutions are calculated. 

Addendum March 3: 2005:  An international user pointed out that the Sample projects included in the downloads would not load properly because of the decimal point difference.  The January fix generalized the decimal separator field so that  files created in Europe could be read there.  It never occurred to me that my  samples, which already contain the "proper" decimal point (.), would not read properly in Europe.  Version 2.1.1, posted today, corrects this problem by identifying the decimal separator of the creating system in each project file.   I also corrected a problem which added an extra blank space at the beginning of each part name each time the project was saved.  It is good to have real users!  

Addendum April 14: 2005:  Several users had requested an easier way to enter multiple parts that have the same dimensions.   Today's update solve this by adding a "How many" box for  New,  Insert,  Duplicate requests.  

Addendum January 20, 2006:  Here's  the first update in several months.  No bugs to fix, just added some of enhancements requested by users.  Version 3.1 adds

 Extra supply boards are now  not reported in the output so extra or multiple size choices for available supply may be entered.  
Supply boards used are identified in output displays.
Part dimensions are listed on output display if space permits. 
An "Ignore grain" option will rotate parts by 90 degrees while searching for solutions if "as specified" fit fails.
Last project used is automatically re-opened at startup time if the project file exists.
Solution displays and printouts may be "zoomed" so that board with longest horizontal dimension (length) is enlarged to  full usable width of the screen or page.  This may result in a scrollbar or multiple print pages for solution display.

Let me know when you find bugs or have additional suggestions.  

February 10, 2006:  I found a bug or two (or 10) in the January 20th version so here's Version 3.2.  which fixes at least some of them and also adds two more significant  features:

Supply list items now have a checkbox beside each item which can be used to select or deselect the boards from consideration n the solution.
You can now use fractions rather than decimals to input and display dimensions.

May, 11, 2006:  A couple more minor fixes today (Version 3.2.1);

bullet For large projects, the print out of the cut list diagram could be truncated rather than printing multiple pages. .
bullet If a large project were zoomed online to full width, the display could also be truncated rather than creating a scrollable image.
  When converting decimal dimensions to fractions,  values between 127/128 and 1 caused an "Invalid floating point operation" error. 

May 25, 2006:  One more "fix-up", Version 3.2.2 to correct some printing problems when part names are long (columns overlapped).    I also added an option to allow users to select which lists/diagram to print.  The "scrap" parts list may now also be printed.   It is good to have real users planning real projects to find these things.    

June 1, 2006:  Viewer Ted has been a good beta tester resulting in one more attempt at getting multiple page printing to work.   He designed a  twin and full sized bed frames with lots of parts (176 as I recall) and wanted to print  the solution diagram in landscape mode on legal size paper to maximize the scale.    Version 3.2.3 solves the problem, at least for this case.  The bed frame project is also included so I'll have it for future testing.   Ted has offered the PDF file containing the plans if anyone is interested.    

July 31, 2006:   Version 3.3 posted today  finally implements  a "Human Intelligence" option which allows users to arrange parts on supply pieces as desired.  There are cases where the program generated solution may not be satisfactory for one reason or another.  A new pages allows drag/drop operations to place required part images on available supply board images.  Optionally, parts may be "snapped" into position - automatically moved up and left as far as possible without overlapping parts already in place.  Solutions may be printed and  saved to disk to be restored  later.    When a solution is restored, parts are matched the the currently loaded case.  Be aware that human intelligence solutions are currently "read only".  Changing any part definitions after saving a human intelligence solution will probably invalidate that solution.   If parts have changed in size or identification (e.g. have been renumbered) ,  the re-loader does  not know which parts to place in which locations.

A tip: If you are trying to place pieces that "just fit" on the supply piece, i.e. no tolerance, consider expanding the defined supply piece size by a fraction.  It is difficult to position and drop the piece exactly while manually dragging.  

October 3, 2006:  Viewer Andy  reported a couple of problems with the popup menus are used to modify a case.  Left click opened the menu, but an accidental double click not only opened the menu but deleted the selected entry.  And if the last entry in a list were accidentally deleted, there was no  to undo or add it back.     I haven't implemented the "Undo" yet, but I did make changes so that a left click now only selects the item to be acted on, and  a right click  pops up the change menu.  Also if all items have been deleted, it is now possible to select the list header line and use "Insert After" option to add an entry.  

February 18, 2007:  Another minor fix applied today, Version 3.3.2.   For a case with no solution, if the "Cutwidth" or "Minimum waste size to report" fields were modified, the program repeatedly tried to solve the case.   I never did find the bug, so I went around it.  There is now a separate "Search for solution" button  rather than using the "Search type" radio buttons to trigger the search.

May 28, 2007:  I finally decided to revisit the basic search algorithm and made some significant improvements in the quality of solutions found.  Here is a summary of the changes in Version 3.4:

bulletFrom the user's perspective:
bulletMore and better solutions
bulletThe "Arrange Manually" form now has a "Paste program solution" button which will copy a solution previous found by the program to this form so you can modify it by rearranging parts to suit your needs.
bulletInternally:
bulletThe Crosscut first and Rip first options when solving did not  always work as advertised.  Fixed now.
bulletIn the "combined" search, all combinations of crosscutting and ripping first are tried when trying fit the largest unplaced pieces arranged from largest to smallest into the  in the current of available pieces arranged from smallest to largest.   The lists were not being completely reset between trials.
bulletWhen there are more than 20 pieces, the combinations described above are only applied to the 1st 20 (approximately 1,000,000 combinations).  Previously, all the rest of the pieces were tested as "crosscut first".  Now these pieces are fit using rip or cross cuts based on a random selection.  This seems to work better for the large cases tried so far.

There  were significant changes internally to the program with this update so, as usual,  let me know what I may have broken in the process.  

July 2, 2007:  Fixed a few problems today with the "Paste program solution" option which had trouble displaying, printing, or saving the the results when any pieces had been rotated.  It seems closer to working correctly now.  Thanks to Mike for submitting the case which illustrated the problems. (Mikesdraws.txt defining his kitchen cabinet project is now included.)  New Cutlist version is 3.4.1.

October 5, 2010:  Over 3 years since the last fix .  Version 3.4.2 corrects a problem which can occur if the user tries to load "txtHI", (user manually created solution) without loading the original base case file first.  The situation was not diagnosed and the loading errors got ugly.  I believe it's diagnosed better now, but I haven't done a lot of testing on the fix, so let me know if you find problems (old or new).  

January 14, 2010:  The October release fixed one problem, but introduced another.  Existing "TxtHI" manual solutions could be updated but new ones could not be saved.  Version 3.4.3 released today fixes that problem. 

June 6, 2012: A couple of minor printing fixes corrected today - so minor that I'm not updating the version number. But printed diagrams now have a slightly wider part outlines to improve visibility. And the extra blank page preceding printed diagrams under some conditions has been eliminated.   

Running/Exploring the Program 

bulletDownload  executable
bulletWhere is the source code?

I withdrew the source code a couple of years ago for two reasons:
bullet

1) It is a popular download and complex enough that I was receiving requests for help in understanding or changing it  a few times a year.  Each time it would take me a day to relearn the code myself.  It had grown beyond the "for fun" stage.

bullet

2) It is a very popular download and clearly has commercial possibilities.  I have a dozen or more good enhancement suggestions waiting to  be  implemented and  I may release a "for pay" version one of these days.  The donation model just doesn't work very well as compensation for time spent working on the program.

If you have  enhancement suggestions, I'll be happy to add them to my list.  For commercial use, I can  grant a license for company internal use for $500.  This includes the  program source code.  The license specifically excludes rights to sell or distribute the following outside of your company:   CutList, any modification to CutList, or  programs you develop based on CutList.  If you are interested, provide me with the name and address information for your company and make the $500 donation via the PayPal link on any page of the DFF website.

 

Suggestions for Further Explorations

Done Jan 2005: Add an option to allow pieces to be rotated if doing so would make more efficient use of material.  (An "ignore grain" option.)
Are the lists produced optimum?  Probably not.  Optimum is currently defined as the largest single leftover scrap piece, but other definitions are certainly possible.
"Saw kerf width" and "Smallest reportable scrap" should be saved and reloaded with the project  files.  Currently only the required parts and the available supply pieces are saved.   
Done , Feb 2005 - A Print option for results list and cutting diagram.
The order in which required parts are cut from available stock pieces can affect the results.    The current default is to cut the largest parts first from the smallest  supply pieces.    Perhaps we should trying cutting from all possible arrangements of supply parts.   
Done January  2006: Need to be able to zoom displayed solutions for better readability for large project solution displays.   

 

Original:  October 27, 2003

Modified:  June 05, 2012

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2013, Gary Darby    All rights reserved.