Near Optimal Objects Packing through Dimensional Unfolding

All Papers

The efflcieut packiug of regular shaped two dimensional objects is the core problem of several kinds of industry such as steel, thin-film aud paper. This special kind of packing problem consists in cutting small rectangular stripes of different length and width from bigger coiled rectangles of raw material by combining them in such a way that trim loss is as low as possible. Previous attempts to apply "exact " discrete optimization techniques such as Simplex Partial Columns Generation, were not able to produce good cutting plans in large instances. We tackled this Roll Cutting Problem developing a new "dimension decomposition technique" that has been successfully experimented in a big steel industry first and then replicated in other steel and thin-film factories. This "unfolding" technique consists in splitting the overall search for good cutting plans in two seperate graph search algorithms, one for esch physical dimension of the rectangles. Searching inidividually in each dimension improves the overall search strategy allowing the effective pruning of useless combinations. Experimental evidence of how dimensional splitting strengthens the overal search strategy is given.