PCPlus 286: Cutting cloth

Come October 2009, it was time to write about some algorithm I knew nothing about. And so it was that I delved into two-dimensional bin packing; prompted by a reader question about how to cut cloth efficiently and aiming for the smallest waste possible.

It turns out that this is a fascinating area of research that has applications all over the place (a variant is the memory heap problem, or how to allocate memory such that you minimize the amount of wasted memory in between the allocated memory blocks). It turns out that the problem, like other bin-packing conundrums, is NP-complete, that is, there is no optimal solution that runs in polynomial time. So, algorithms to solve the problem tend to be optimization or goal-seeking solutions, where you “fiddle” with a solution to look for a better packing.

To make it easier (!) to analyze the 2D bin-packing problem, we assume that the pieces being cut from the cloth (or packed into the container) are rectangles.

The first algorithm I discuss is Sleator’s algorithm. This is important for (a) appearing in the the first paper that discusses the problem, and (b) being amenable to a bit of mathematical analysis that concludes that Sleator’s packing is within 2.5 times the optimal packing (what you might call God’s algorithm for bin-packing).

The next one is Jacob’s algorithm, which is a fun little algorithm because it works a bit like Tetris, at least a handicapped Tetris where you can’t rotate the pieces. You start at the upper right with a new rectangle, “slide” it down until you can’t go any further, slide it left until you can’t go any further, slide it down, left, etc, until the rectangle cannot be moved any further down or left. This was the first of the “Bottom-left” algorithms and Lui and Teng provided another variant that tried a slightly different strategy: prefer dropping down to moving left.

After those initial solutions, newer algorithms evolved into patented systems.

This article first appeared in issue 286, October 2009.

You can download the PDF here.

(I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so.)

  Loading links to posts on similar topics...