کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7541614 1489051 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Algorithms for the bin packing problem with overlapping items
ترجمه فارسی عنوان
الگوریتم برای مشکل بسته بندی بسته با موارد همپوشانی
کلمات کلیدی
صفحه بندی، بسته بندی بسته بندی مجازی ماشین، برنامه ریزی خطی عدد صحیح، اهریمنی، الگوریتم ژنتیک،
موضوعات مرتبط
مهندسی و علوم پایه سایر رشته های مهندسی مهندسی صنعتی و تولید
چکیده انگلیسی
We study an extension of the bin packing problem, where packing together two or more items may make them occupy less volume than the sum of their individual sizes. To achieve this property, an item is defined as a finite set of symbols from a given alphabet. Unlike the items of Bin Packing, two such sets can share zero, one or more symbols. The problem was first introduced by Sindelar et al. (2011) under the name of VM Packing with the addition of hierarchical sharing constraints making it suitable for virtual machine colocation. Without these constraints, we prefer the more general name of Pagination. After formulating it as an integer linear program, we try to approximate its solutions with several families of algorithms: from straightforward adaptations of classical Bin Packing heuristics, to dedicated algorithms (greedy and non-greedy), to standard and grouping genetic algorithms. All of them are studied first theoretically, then experimentally on an extensive random test set. Based upon these data, we propose a predictive measure of the statistical difficulty of a given instance, and finally recommend which algorithm should be used in which case, depending on either time constraints or quality requirements.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Industrial Engineering - Volume 115, January 2018, Pages 331-341
نویسندگان
, , ,