The Skiving Stock Problem and its Application to Resource Allocation

Abstract

We consider the one-dimensional skiving stock problem (SSP) which is strongly related to the dual bin-packing problem in literature. In the classical formulation, different (small) item lengths $l_1,\ldots,l_m $ and corresponding availabilities $ b_1,\ldots,b_m $ are given. We aim at maximizing the number of objects with a certain minimum length $ L $ that can be constructed by connecting the items on hand. Such computations are of high interest in many real world applications, e.g. in industrial recycling processes, wireless communications and politico-economic challenges. After a short introduction to the SSP, one of these applications, the spectrum allocation in cognitive radio networks, is considered in more detail. As a main contribution, we present three modeling formulations for this problem that can cope with a particular additional constraint arising by hardware limitations, and provide numerical simulations for one of them. In a final step, we discuss possible extensions of the considered optimization problem and show how they can be solved efficiently.

PDF, (Preprint MATH-NM-01-2016, TU Dresden, Juni 2016, 25 p.)

Back