Cut Optimization

This past weekend, I was thinking about cut optimization. This is a method for planning cuts to produce the most pieces of given sizes out of a quantity of material of some length with minimum waste. This was brought about by the planning process involved in building a new garden railway trestle. (I’ll cover the specifics of that in another post – I still have to finish my earlier series on the Curved Trestle with a final part covering stringers and installation.)

As a programmer, of course I always think of writing a program to solve that problem. It turns out, that particular problem is considered NP-Hard, which is a computer scientist way of saying you can’t practically solve that exactly in all cases. With this problem, though, I assumed I could generate a good-enough solution. It turns out, that I could.

First, definitions:

  • The raw material that you have is the “stock.” You have some quantity of stock at given length.
  • The pieces that you need to cut from that are a collection of “pieces,” each with a length and quantity needed.
  • The remaining stock after all the cuts is the “waste.”

Because this is a physical world, and I’m working with wood, I considered the saw blade kerf in the calculation. (The kerf is the width of the cut that the blade produces.)

The first algorithm I tried is the “greedy” method, which finds the longest piece(s) that fit the stock, in turn, until none fit the remaining stock. The last bit after that is “waste”, as there are no pieces that are that size or less.

The second method I tried is what I call “best fit.” This picks the longest piece as the starting point, then finds the one or more pieces that best use up the remaining stock. I used recursion to test all the remaining piece combinations to find the best.

See Cut Optimize for my example program. This uses browser local storage so you can create a project, save it, and refer back to it later. It also uses a table with “editable” content, so there are no input boxes there, just click in the cell and edit the value. Really slick! (I didn’t write the table code.) On first use (or if no jobs are defined) a sample project may be created that has two “jobs”: one for the 90 degree cuts and one for the angled cuts.

What I found was that the greedy algorithm tended to get better results much of the time as a percentage of waste, but most of the waste was in pieces that were too short to have any value for another use (1-2″ long, for instance). The best fit algorithm, though it tends to lose out on a percentage of waste score, does a really good job of using almost all of the stock while there are still short pieces left, and produces more usable waste later in the cut list (3-5″ waste, for instance).

In the examples, both algorithms produced a lot of waste because of the large number of about 9.5″ lengths paired with the 24″ stock length. I’ll likely just get some 20″ or 30″ stock to make most of those pieces, then the waste will be dramatically reduced.

Update: 10/16/2017

I changed a few things:

  • Added a minimum Usable Length setting. Remaining pieces greater than or equal to this value are not considered waste.
  • Expanded the Stock inventory to five lengths and quantities.
  • Changed the buttons to “glyphicons” for a more compact presentation.

Also, fixed a few random bugs in the page.

Total Solar Eclipse 2017

Our eclipse photos were taken with a Pentax K-50 using a 200 mm lens.

Right after start of occlusion.

Totality. If you click on the image, I believe that Mars and Mercury are visible (about 3 o’clock and 8 o’clock, respectively).

“Diamond Ring.”

Near end of eclipse.

Glamping in Madras

We spent the (long) weekend of August 17-22 in Madras, Oregon so we could see the 2017 eclipse. Madras is in the path of totality, but just out of town there was Solar Town, dead center in the path. We got a “Glamping” (Glamorous Camping) package, which got us a very large tent (including set-up and tear-down), two cots, two blankets, a table and two chairs. Also included were showers, which were a luxury to have while camping. We brought everything else needed to survive for a week with minimal services.

We brought the canopy that is in front of our tent, which was really nice to have as the sun was very intense for the weekend. (It was August, after all.)

We arrived early Thursday evening, but got stuck in a two-and-a-half-hour line of cars waiting to get in to Solar Town. It was almost 9:00 P.M. when we finally got into our tent.

With the influx of people continuing Friday, and everyone immediately going to the kybo after the long wait in line, the maintenance crews were unable to empty the shower grey water. The showers were down Saturday and Sunday, which was a bummer. (Kybo is a scouting term for a Porta-Potty or Outhouse.)

Sunday night the Day campers arrive and inundate the kybos (pun intended). They all left Monday after the eclipse, most on the road by noon. The line of cars was very, very long – probably a couple of miles of cars and RVs.

We rode the shuttle into town for a dinner out. We went to Rio Restaurant, which makes Mexican cuisine. We had what were marked specialties on the menu: Puerco Moreliano and Puerco Enmolado. Two big thumbs up! That meal was muy delicioso. See https://www.zomato.com/madras-or/rio-restaurant-madras (The “festival” prices were much higher than normal.)

Sometime after the hordes departed, the crews caught up with emptying kybos and got around to the shower grey water. The showers returned to operation Monday night! We departed Solar Town on Tuesday morning. We encountered just normal traffic and had a pleasant drive home.

One idea we had worked really well: We filled two one-gallon plastic jugs with water and froze them solid in our freezer to use in the ice chest. It was three days later (Sunday) before the ice was mostly gone, as was our perishable food, so we had cold water for drinking!

Garden Railway Construction

I got permission from the boss to build a garden railway in our backyard largely because I am going to put it in the previously uncivilized portion of the yard. So, step one is to civilize the wild parts.

A couple of years ago, I began an ivy eradication project. There must have been 1,000 square feet of ivy, which made that area useless for anything. So, repeated applications of Bayer Advanced Brush Killer has wiped out most of the ivy and some other brush from our yard. (I’m on my 3rd container of Brush Killer.)

Now, I could tackle the wild iris, pyracantha, hawthorn and blackberry canes. Here’s a couple of before photos:

You can see the wild iris on the left, and the massive tangle of brush that I had to contend with. Note also the remnants of (very sickly) ivy. After about a month, here is my progress: 

I still have quite a bit of brush, but it is no longer attached to the ground. And I’ve beaten the iris back to less than half what it was. In a few weeks, the sticks and iris will all be gone.

Note the progress on the wild iris (before and after, above), and the elimination of some holly sticks that were left after the brush killer. As a bonus, friends are taking the dug-up iris away to plant on their property.

Update: Here is the garden area, almost bare ground where there was all that ivy and brush. This represents two to three months of hacking and raking.