A comparison of solution methods for the assortment problem

The problem of economically cutting a required bill of material out of standard size stock pieces is shared by the metal, leather, glass, electronic, shipbuilding, and lumber industries. One of the problems in this area is the assortment problem; that is, determining the best combination of stock sizes to keep in inventory to cut a single known (deterministic) bill of material. This problem includes determining the dimensions of the stock pieces as well as the number of unique sizes to stock. In this research a comparison is made between three common heuristic methods for solution of the assortment problem and the introduction of the application of optimization homotopy to the assortment problem, a method developed for the solution of stochastic problems. It is found that while utilizing a specific combination of nesting and sequencing algorithms, the three heuristic methods work very well for simpler problems, and as the complexity of the problem increases optimization homotopy becomes more advantageous.