Cutlass – Cut Less!

While re-building my house I became obsessed with getting efficiency out of the timber 10materials I was using when planning cutting lists. Most people would want to achieve an efficient cutting plan because of cost-efficiency, effort-reduction or ecological conservation, and of course that was true for me but being a huge nerd I was even more intrigued by the devilishly difficult planning problem itself. Surely an algorithm could be produced to make cutting lists easy to produce, and thereby save enormous amounts of trees?

So what’s the problem?

The Problem

Well I have a) a long list of measured lengths to make tongue and grooved lining boards fit horizontally around our many doors and windows and b) a bunch of raw timber in standard lengths. The challenge is to cut the timber so the waste offcut each time can also be used.

Cutlass Stock Illustration

The Solutions

The woodyard-recommended solution is to order 10% more timber than you need and hope. Then you just throw away the waste. Of course they would recommend you spend 10% more, but I just don’t find this an acceptable attitude.

After trying to figure out a process myself for three complex rooms and 150m of timber I almost had a brain meltdown, I did some research into online tools and then common algorithms. Of course this is a very old problem!

At first I researched the “cutting stock problem” but this is mostly oriented towards reducing waste from cutting 2D sheets of fabric, timber or metal and incorporates complex requirements like reducing knife-changing interruptions.

I found it difficult to find a 1D cutting algorithm, until I came across the “bin packing problem”, which is functionally equivalent to this problem. All you have to do is tilt your head on one side, and view the ‘bins’ as the original stock and the vertical heights of the objects being placed in the bins as the planned lengths required.

Cutlass Stock Illustration (1)

The first-fit algorithm is pretty simple: you find the next longest length in your requirement plan and take that away from the first stock with enough left (i.e. put it in the first bin). Repeat.

It’s not guaranteed to find the overall best usage for all items. In theory, if you tried all possible combinations you could probably get a lot more zero-waste planks, but this sounds like one of those more-atoms-than-the-universe scenarios to me. I might add some level of re-try to it later or do more research into simultaneous equations, which I suspect could offer a solution.

My Implementation

Of course programming this will have a few more practical details like initially sorting the required lengths and handling problems like running out of stock, but that’s the basic algorithm. So I cracked open a new Bootstrap theme and wrote it in Javascript to avoid any unnecessary back-end requirements:

/*
 * Best fit tries to fill the available slots with the minimum remaining.
 * Slots are only brought online when no previous slots can be fitted into.
 * You start with one slot online, and put the first item into it.
 */
bestFitAlgorithm: function(aTimberList, aCuttingList){
  // first we assume there's only one entry in the timber list - phase one!
  var iPlankSize = aTimberList[0][0];
  var iNoPlanks = aTimberList[0][1];
  var aPlanks = [];
  var count, len, min, p, remaining;

  // iterate over the required lengths
  for(var i in aCuttingList){
    len = aCuttingList[i][0];
    count = aCuttingList[i][1];
    while(count--){
      // Check all online planks in order
      min = iPlankSize;
      p = null;
      for(var j in aPlanks){
        remaining = aPlanks[j].remaining - len;
        if(remaining >= 0 && remaining < min){
           min = remaining;
          p = j;
        }
      }
      if(p != null){
        // p is the best fit.
         aPlanks[p].remaining = min;
        aPlanks[p].pieces.push(len);
      }
      else {
        // No fit found, bring another plank online
        aPlanks.push({remaining:iPlankSize-len, pieces:[len]});
      }
    }
  }
  return aPlanks;
}

I surrounded this with some self-unit-testing, a JQuery plugin wrapper and a basic form UI to talk to the humans, and went to work.

The Real World Beta Test – My Lining Boards

The plan that I actually needed was as follows, with length of item in mm (len) and how many (off).

len  off
3100 2
2900 1
360 1
305 16
1300 2
245 13
3740 4
440 8
1070 1
190 7
900 1
4000 2
3820 5
140 9
110 15
1200 2
230 15
120 15
1450 23
500 15
2820 1
120 15
380 15
200 9
1150 3
1150 6
140 9
1270 18

My stock was 5400mm lengths of pre-primed T&G grooved panelling. The algorithm came up with the following cutting list, where the first number is the stock plank index, then the length to cut and finally the waste.

I added a default 3mm kerf (the width of the cut made by the saw) which is easy to forget when planning cuts and soon adds up to a significant amount – especially when you are trying to achieve near zero-wastage with many small pieces (see bottom planks).

0: 4000,1300 waste:100
1: 4000,1300 waste:100
2: 3820,1450,120 waste:10
3: 3820,1450,120 waste:10
4: 3820,1450,120 waste:10
5: 3820,1450,120 waste:10
6: 3820,1450,120 waste:10
7: 3740,1450,200 waste:10
8: 3740,1450,200 waste:10
9: 3740,1450,200 waste:10
10: 3740,1450,200 waste:10
11: 3100,1450,500,305 waste:45
12: 3100,1450,500,305 waste:45
13: 2900,1450,900,140 waste:10
14: 2820,1450,1070 waste:60
15: 1450,1450,1450,500,500 waste:50
16: 1450,1450,1450,500,500 waste:50
17: 1450,1450,1450,500,500 waste:50
18: 1450,1270,1270,1270,140 waste:0
19: 1270,1270,1270,1270,305 waste:15
20: 1270,1270,1270,1270,305 waste:15
21: 1270,1270,1270,1270,305 waste:15
22: 1270,1270,1270,1200,380 waste:10
23: 1200,1150,1150,1150,500,245 waste:5
24: 1150,1150,1150,1150,500,245 waste:55
25: 1150,1150,500,500,500,500,500,440,140 waste:20
26: 440,440,440,440,440,440,440,380,380,380,380,380,380 waste:40
27: 380,380,380,380,380,380,380,380,360,305,305,305,305,305,305,140 waste:30
28: 305,305,305,305,305,245,245,245,245,245,245,245,245,245,245,245,230,230,230,230,230 waste:30
29: 230,230,230,230,230,230,230,230,230,230,200,200,200,200,200,190,190,190,190,190,190,190,140,140,140,140,140 waste:70
30: 140,140,140,140,140,140,140,140,140,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,120,110,110,110,110,110,110,110,110,110,110 waste:40
31: 110,110,110,110,110 waste:4850

Total timber length: 167005
Total waste:5795
Percentace waste:3.47%

So that was pretty impressive 3.5% wastage which is a third of the accepted industry standard.

In theory!

The Messy Real World

When I actually got cutting with my proudly printed-out list, I discovered a few “real world” shortcomings.

  1. Job planning: My initial list was ordered in a real-world sequence from room to room, making it easy to follow while you work from the floor-up (grooves into tongues), and around window features etc. However the algorithm had scattered the pieces all over the stock planks, meaning I had to a) track them down in the list, b) ‘open’ up a stock plank by cutting out that one length, c) keep track of the remaining stock with chalk/tape/pencil which is physically challenging in a small house and 160m of timber!
  2. Mistakes: I had mis-measured a couple of items in my plan! This meant the whole cutting list was wrong and needed updating. So surely a quick re-run through the algorithm? No, because I was now half way through the cutting process and had already cut several planks, so the stock was now of various sizes. Well, I had planned this as a feature for phase-2 but I had taken the kitchen apart and was all covered in sawdust and sweat and wasn’t about to stop and do a couple of hours programming!
  3. Timber quality: no timber stock is perfect (even DAR or this pre-primed luxury). Sometimes it gets knocked, dented or a knot pops. So again we need to be able to discard a piece, and re-run the algorithm as per 2).
  4. Other similar problems: leading to the need for flexibility, better planning and keeping tally on progress and stock/inventory. Often your plan changes while you’re doing carpentry as you work around issues or get into the detail (we have sloping ceilings and other oddities) which just needs a hands-on decision.

Being the Computer

Of course all of these things could be resolved in phase 2, but to finish the project I actually ran the algorithm myself:

  • Select the next longest item in the (current room/job’s) plan
  • Select the shortest stock which this can be cut from
  • Cut it, re-measure and write the measurement on the stock. (This is essentially an index, as you will be reading this measurement many times as you iterate through the stock and it means you can keep the timber stacked which makes it difficult to measure).

This is effectively what experienced carpenters do anyway – I found out later from my father-in-law! But from a craftsman perspective it’s reassuring to know that a rule of thumb is far more practically effective than an algorithm based on advanced mathematical theory and these new-fangled computers.

DIY!

Try out (the alpha version) for yourself here: http://scipilot.org/cutlass

Lessons

While I would like to work on phase 2, I don’t have any major carpentry projects planned at the moment, so I predict lack of necessity will mean this project may sadly stagnate.

However I really think this real-world problem would be a great tutorial or project for a software-engineering course.

  • It encapsulates a very difficult problem with potentially fun mathematical depth,
  • it has no perfect solution which is a reality young programmers have to face,
  • it highlights some real-world complexities requiring good UI/UX to prevent the wonderful maths being totally useless practically
  • and finally it would benefit from expert-interviews (stakeholder input)

i.e. by talk to your father in-law before starting a hair-brained programming project!

This entry was posted in articles, Projects and tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.