کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7543423 1489486 2018 26 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The skiving stock problem and its relation to hypergraph matchings
ترجمه فارسی عنوان
مشکل سهام اسکیبینگ و ارتباط آن با پیوند هیپرگراف
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی
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 proper relaxation by considering the proper gap, i.e., the difference between the optimal objective values of the proper relaxation and the skiving stock problem itself. In this regard, we introduce a theory to obtain the proper gap on the basis of hypergraph matchings. As a main contribution, we characterize those hypergraphs that belong to an instance of the skiving stock problem, and consider the special case of 2-uniform hypergraphs in more detail. Moreover, this particular class is shown to correspond one-to-one and onto a certain power set. Based on this result, the number of related non-isomorphic hypergraphs and their possible proper gaps can be calculated explicitly.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 29, August 2018, Pages 77-102
نویسندگان
, ,