H3CS Heuristics for the 3D Stock Cutting problem

[JamesBremner]

This divides the items into levels that are the same height and solves each level using a 2D algorithm

The challenge is the 2D algorithm.

In freelance chat I suggesting using DP3UK and confining everything to a single height. The advantage was we already have the code . However, it is a silly idea. DP3UK is unbounded, which means that it is free to duplicate some items and forget about others, which is not what we want here.

The paper references a lot of different possible 2D cutting algorithms, without going into detail for any. So, to keep things moving along I decided to implement an algorithm I am familiar with from my other work in this area. RK2FFG is rectangular knapsack 2D first fit greedy algorithm. https://github.com/JamesBremner/knapsack/blob/master/src/RK2FFG.cpp

I have committed an initial H3CS application using RK2FFG

This issue is intended to discuss how exactly to improve this going forward.

[JamesBremner]

The biggest limitation of RK2FFG is that it does not provide guillotine cuts - cuts that go from one edge of the bin all the way to the other. As I understand it, you are not cutting the timber, but stacking it. So perhaps guillotine cuts are just nice to have rather then necessary? Let me know.

[Cashewfly]

The timber application will require guillotine cuts exclusively.

I must have miscommunicated something earlier. The timber application will be cutting larger timbers into smaller timbers to fill custom timber orders.

[JamesBremner]

Well, I totally got the wrong end of the stick there. It makes a huge difference.

I have done several projects with cutting in 2D, but my 3D work so far has always been bin packing.

[JamesBremner]

Yes, I am planning on implementing a full timber allocation system. Incoming timbers can be up to 100000 integer units (100ft in 100ths of a ft) in length and 3000 integer units in height and depth. Stock will be several hundred timbers, and at any given time there will be several hundred items that will need to be optimally allocated.

"allocated" what doe the word mean to you?

I visualized tracks arriving with bundles of logs and you needing to work out where to place them in the timber yard. But you mean something like orders to be met by cutting large timbers into smaller ordered pieces. A single piece of timber 100 by 30 by 30 ft! Maybe 200 years ago Canada exported timbers like that, but not nowadays.

[Cashewfly]

3d guillotine cutting is why I'm so interested in this paper. As far as I can tell, it's the only place it's addressed.

[Cashewfly]

Oops, I mis-scaled. It would be a maximum of 100x3x3ft. More likely it would be 42x2x2ft.

Allocated means taking an inventory timber (which could be any size because 'waste' is returned to inventory) and cutting out pieces to fill custom orders. The pieces can also be any size. These will be typically be used in churches and residences and often upscale sporting goods stores.

A typical run would be 80 inventory items and 200 order items. Optimizing what is returned to inventory is also a huge factor. Wood is too expensive to let any of it go unused.

[JamesBremner]

Those sizes seem a lot more likely!

[JamesBremner]

Let's talk about guillotine cuts.

Here's a problem from a previous 2D client.

The client accepted this layout, becuase he could set his machine to do two horizontal guillotine cuts ( G-cuts ) and then vertical G-cuts on the smaller bits.

This one was rejected:

[Cashewfly]

I would also accept the first and reject the second.

[JamesBremner]

A typical run would be 80 inventory items and 200 order items.

How would you like to input this data? Do you have a sample dataset?

[JamesBremner]

Extending the idea of G-cuts to 3D: Do you accept the ideas of H3CS? Specifically, dividing up the items to be cut into levels of the same height. Thus the first G-cuts will be horizontal, splitting the levels apart.

If so, then I can use the ideas I developed for doing G-cuts in 2D.

[Cashewfly]

Yes, I think cutting in levels is worth pursuing. It seems likely that in most cases it will give good results.

I'll look into generating an input file of our current inventory and orders tomorrow morning.

Since you already have parsing code for the format from your Pack code I'll generate the data in that format, meaning

The bins should be passed in the following format:

"id:dim_unit:quantity:size1xsize2xsize3:weight"

The items passed like so:

"id:dim_unit:constraints:quantity:size1xsize2xsize3:weight"

[JamesBremner]

I can handle that input.

That format is from my old packing engine and it was inherited from a previous developer, so it is really old fashioned. These days I always have to write frontends for it.

Since we are starting fresh with a new cutting engine, I would prefer to use something more modern, if it is all the same to you Something like this can be simply generated using excel.

i 10000 300 300 5 stock1      // 5 inventory timbers 100ft by 3ft by 3ft  id is stock1  ( bins )

d 600 50 17  20 test        // demand to cut 20 timbers 6ft by 6in by 2in  id is test ( items )

[JamesBremner]

In general: space delimited text file with 6 columns, lines in any order

[Cashewfly]

I've uploaded timber-alloc-data.txt to the data folder

It contains 62 inventory items and 127 order items.

The only change from your suggested format is that the dimensions are scaled by 1000 rather than 100.