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

作者：Martinovic J^*; Scheithauer G

来源：Discrete Applied Mathematics, 2017, 229: 161-167.

DOI：10.1016/j.dam.2017.05.015

• Cutting and packing
• Skiving stock problem
• Divisible case
• (Modified) integer round-down property
• Gap

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 is an element of N smaller item lengths l(1),...,l(m) with availabilities b(1),...,b(m). 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 Delta(E) is known to be strictly less than 2 if L/l(i) is an element of 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 A(E) < 3/2.

• 出版日期2017-10-1