کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1141404 1489493 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Integer rounding and modified integer rounding for the skiving stock problem
ترجمه فارسی عنوان
گرد کردن عدد صحیح و گرد کردن عدد صحیح اصلاح شده برای مشکل سهام تراش
کلمات کلیدی
برش و بسته بندی. مشکل سهام تراش؛ ویژگی گرد کردن عدد صحیح پایین (اصلاح شده) ؛ شکاف. آرامش مداوم
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی


• For the first time: profound theoretical investigations on the gap of the SSP.
• Generalization of Zak’s theorem to arbitrary values of m.
• Proof of the MIRDP for the divisible case of the SSP.
• Construction of an infinite number of non-equivalent non-IRDP instances.
• We show how a gap arbitrarily close to 22/21 can be obtained.

We consider the one-dimensional skiving stock problem which is strongly related to the dual bin packing problem: find the maximum number of items with minimum length LL that can be constructed by connecting a given supply of m∈Nm∈N smaller item lengths l1,…,lml1,…,lm with availabilities b1,…,bmb1,…,bm. For this 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. In a first step, we derive an upper bound for the gap by generalizing a result of E. J. Zak. As a main contribution, we prove the modified integer round-down property of the divisible case. In this context, we also present a construction principle for non-IRDP instances of the divisible case that leads to gaps arbitrarily close to 22/2122/21.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 21, August 2016, Pages 118–130
نویسندگان
, ,