Freecut
From MairasNetWiki
Freecut
Contents |
Introduction
Optimizing board cutting is a very common problem in wood-, metal-, and glassworking and similar crafts. You might want to cut a piece of plywood or sheet metal to get a number of smaller pieces so that the amount of scrap material is minimized. So did I; while planning how to cut an MDF board to small pieces, I began thinking that this is a suitable job for a computer, not for me. Thus, I began investigating the problem.
As it happens, my board cutting problem belongs to a very widely studied area called Cutting and Packing problems. The field concerns problems such as how to place rectangular or irregular items on a larger board or a strip of material, or how to optimally pack a container or a pallet with boxes of pre-defined size. Enough research has been conducted to actually create a typology of the field:
- Gerhard Wäscher, Heike Haußner, and Holger Schumann. An improved typology of cutting and packing problems. European Journal of Operational Research 183:1109–1130, 2007.
However, despite the large amount of research, I was unable to find any open implementation of any C&P algorithm. There are some commercial, albeit inexpensive, Windows programs available, but apparently most implementations are custom manufacturing or logistics applications. So, I decided to implement one algorithm. After some research, I settled to a rectangular guillotine strip packing algorithm. Rectangular stands for to item shape, that is, rectangular items are to be used instead of irregular ones. Guillotine means that the cuts always span the whole board, i.e., you can't have cuts with corners. That is especially suited for cutting material with a circular saw. Strip packing is a problem where you have a strip of material with a pre-defined width but undefined length. You then try to place the items on the strip as to minimize the used length of the material.
While going through the more recent published algorithms in my chosen category, I rather quickly settled for this paper:
- Yaodong Cui, Yuli Yang, Xian Cheng, and Peihua Song. A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem. Computers & Operations Research 35:1281–1291, 2008.
The criteria of selection were the simplicity of algorithm (for ease of implementation), computational efficiency (I was going to implement the algorithm in Python), and the quality of results (no point in implementing a bad algorithm). Unfortunately, during the implementation, it was revealed that the algorithm could have been better, and it took quite some time to actually get it working. However, it works now.
Roadmap
Hopefully, the implementation of the HRBB algorithm is just a tiny first step. It would be nice to make a full-fledged open-source C&P library, spanning many efficient algorithms in different problem domains. While the current implementation is in Python, this library should probably be implemented in C/C++ for efficiency and ease of embedding in different programming languages.
Please contribute!
Examples
This example illustrates a cutting plan for the MDF pieces required by the CNC Router.
Usage
Freecut is currently a command-line application. The dimensions of the items are given in a text file:
301 762 419 539 419 539 650 1502 700 1540
The dimensions are arbitrary. I have used millimeters.
The optimizer is run as follows:
./optimize_cut.py --width 1830 --trim 5 items.txt
where --width is the strip width, in the same units in which the items were defined, and --trim is the amount of trim (extra material between the items consumed as a cutting loss).
The --segments option may be used to make the algorithm prefer vertical segments. This may improve the layout quality in some cases.
Licence
For the time being, Freecut is licenced under GPL version 2. When a proper library is created, I might be willing to change it to LGPL.
Updates
- 2008-04-27
- Added the
--segmentsoption, which may improve the layout in some cases. - 2008-04-26
- Original release
Download
Dependencies
To display the results graphically, Freecut depends on Matplotlib, which is not part of the standard Python distribution. On Ubuntu systems, you can install Matplotlib like this:
sudo apt-get install python-matplotlib