An upper bound of Δ(E)<3∕2 for skiving stock instances of the divisible case

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of products with minimum length L that can be constructed by connecting a given supply of m∈N smaller item lengths l1,…,lm with availabilities b1,…,bm. For this NP-hard optimization problem, we investigate the quality of the continuous relaxation by considering the gap, i.e., the difference between the optimal objective values of the continuous relaxation and the skiving stock problem itself. This gap Δ(E) is known to be strictly less than 2 if L∕li∈N is assumed for a given instance E, hereinafter referred to as the divisible case. In this article, we present a heuristic to obtain feasible solutions for the skiving stock problem, and show that this approach provides an alternative (and simpler) constructive proof of the modified integer round-down property (MIRDP) for the divisible case of the skiving stock problem. By means of a more detailed study of this algorithm, we improve the upper bound for the gap of the divisible case to Δ(E)<3∕2.