What is optimising

 

Optimising is the process of creating a set of cutting patterns for a list of part sizes and quantities from one or more different sizes of board, taking into account all the various limitations imposed by the saw, such as trims, minimum size of recuts, maximum stack height and so on.

 

An optimal result is one which minimises the overall cost of the job. In simple terms to minimise material waste and minimise cutting costs by keeping the patterns as simple as possible and by keeping the number of cycles as low as possible. In practice it is very difficult to achieve the actual minimum cost but most results come very close to the best.

 

Optimising is a complex and difficult problem.

 

The cutting optimisation problem is recognised as one of the hardest problems in computer science. There are many problems just like it which are equally hard, for example, scheduling jobs in a factory, loading a fleet of trucks, working out a school timetable. They are called combinatorial optimisation problems.

 

You can begin to see why this problem is more complicated than it looks at first by imagining that you have about 12 different parts sizes to cut (one of each size). You might guess that they all fit into a single board but what is the cutting pattern?

 

One way to work out the cutting pattern is to work carefully through all the possible arrangements of the parts until you find one that fits. But how many possible arrangements have to be tried?

 

In fact for up to 12 pieces there are about 479,000,000 different arrangements and probably only a handful of the arrangements will allow you to cut all the pieces from a single board.

 

It is like looking for a needle in a haystack!

 

It gets much worse as the number of pieces increases. In fact for any reasonable number of pieces the number of combinations is unimaginable and it would take the fastest computers millions of years to generate all the arrangements. For 50 pieces the number of arrangements is about:-

 

300000000000000000000000000000000000000000000000000000000000000000

 

Which is about the same as the number of atoms in the Universe!. Each way of arranging is called a combination hence the term combinatorial optimisation.

 

So for most practical cutting problems it is difficult to find the best (optimal) solution. But of course a solution which is nearly the best is still a very good solution and it is usually one of these near best solutions that an optimiser finds. Given this enormous complexity all optimisers have to compromise and for most problems generate much less than all the possible patterns by using complex mathematical algorithms which try to guide the optimiser towards good sets of patterns. This inevitably means that occasionally the algorithm can overlook a better pattern and you can get less efficient or unexpected results from an optimisation. This usually effects a particular set of sizes or boards or parameter settings and you can often improve the results by changing parameter settings.

 

Unexpected results - As you can see from the above illustration of the enormous complexity that an optimiser faces unexpected results will occur occasionally. These results are usually unexpected because you change a parameter such as the number of head cuts or recuts allowed and do not get the improvement in waste or cutting time that you expect and sometimes the result is worse.

 

These unexpected results are not caused by bugs in the code but are caused by the limitations in the computing power and flexibility that a PC provides. Usually when you change a parameter or increase an allowed value you vastly increase the complexity that the optimiser has to deal with and it has to limit or prune the search as a result and can then overlook a better result and can even not find the previous result.

 

Whilst the algorithms are continually improving to make better use of computing resources (and computer power is always increasing) it may not be possible to fix a particular one-off problem.

 

However, you can help the optimiser in many cases by using your experience when setting the parameters and making sure that it is not spending time looking for results that you cannot use. For example if you usually only deal with 1 head cut in a board then keep the number of head cuts at 1, similarly if you never use multiple recuts keep the recuts set at 1, and so on.

 

Please note that it is important that you report unexpected results to us as they should all be investigated as many can be fixed and the remaining few help us to develop future optimising enhancements.

 

If you get a unexpected result

 

 

An unexpected result does not usually affect any other optimisations with other parts lists - and your optimiser is still working OK - it is just a one-off odd result.

 

Balancing act - Remember too that NO optimiser can produce a result that gives you minimum cutting time, minimum waste, perfect stack height, easy handling and simple patterns. These are often conflicting objectives and the optimiser is attempting to produce a balance (at the lowest possible cost) between all these features.

 

 
See also