A tree-search method for solving a cutting stock assignment problem

Many production environments such as carpet or flat glass manufacturing hav e linked operations that perform completely different activities. In this p aper, we consider a two-stage manufacturing process involving a cutting ope ration, followed by an assignment operation. Raw material is cut to meet pr oduct demand with minimum trim loss, and assignments are made to minimize r esource requirements. This cutting stock assignment problem is formulated a s a large-scale, mixed-integer nonlinear programming problem. We propose a solution methodology based on decomposition and tree search heuristic strat egies. We report on extensive computational experiments on a wide range of problems, and apply statistical techniques to determine significant factors . For all small-size problems tested, our method found the exact optimal so lution. For practical-size problems, our method was about two orders of mag nitude faster and produced solutions that were one-third better than tabu s earch.