Friday, May 20, 2011

Part Layout Hand Edit

Also added this video to the candy aisle of the website.

Video description:
It's 550 edits to the part layout for an 8-foot cardboard surfboard core kit.

My bin packing code does an okay job of laying out parts in panels, but it's not as smart as I'd like, yet. So I made this system (that lives in a web browser) to do the final part layout optimization by hand. The game is to reduce the number of panels required as much as possible, and to reduce the distance between where a cut ends on one part and begins on the next.

"Bin packing" is the process of fitting a bunch of things in a container, or a bunch of containers, efficiently. The things might be all different sizes. The containers might even be different sizes - though in my case, I've standardized on roughly 2 foot by 1 foot panels.

The bin packing problem applies to packing lots of surfboards, gear, and people into a limited number of cars and boats, fitting files onto backup CDs, organizing your closet, and, for me, arranging parts efficiently into panels, with a minimum of wasted space, so I can cut down on materials and laser cutting time for core kit production.

You and I are fairly good at bin packing, but it's not simple to translate that skill into a computer program. My system does a decent job of laying out parts for my CNC router. But for the laser-cut core kits, the arrangement needs to be as tight as I can get it. That means editing the part layouts by hand.

The video presents a complete editing session that took me a little more than an hour. Some of my edits are pretty simple things that I'm currently adding to my bin packing program. Other edits are rearrangements that seem simple and obvious to us, but that PhD students struggle to convert into general purpose algorithms.

I haven't yet found any really-free two-dimensional bin packing software. The people who need this kind of thing are usually businesses, so the people who develop good bin packing software have a chance to be rewarded for that effort.

The initial reward though is in developing a good solution. This problem can be an addictive puzzle, and I don't think you can work on it without being caught up in the game. Beyond the merely adequate solution I'm after, my reward will be in cutting these layout review and edit sessions down from an hour plus, to something more like ten minutes.