کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4949584 1440194 2017 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An upper bound of Δ(E)<3∕2 for skiving stock instances of the divisible case
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 229, 1 October 2017, Pages 161-167
نویسندگان
, ,