نویسنده
Ekici, Ali
تاریخ انتشار
2021-02
محل انتشار
-
Elsevier
موضوع
Bin packing problem with conflicts, Item fragmentation, Heuristic, Lower bound, Oversized items
نوع
دوره ای
زبان
انگلیسی
دیجیتال
بله
نسخه خطی
خیر
کتابخانه
دانشگاه اوزیغین
شناسه دارایی کتابخانه
0305-0548
شماره ثبت
e971c668-9c74-4d52-a310-57d08aaa427e
محل کتابخانه
Industrial Engineering
تاریخ
2021-02
متن نمونه
In this paper, we study the Bin Packing Problem with Conflicts and Item Fragmentation (BPPC-IF) which has applications in the delivery and storage of items that cannot be packed together. Given a set of items each with a certain size, the goal in BPPC-IF is to pack these items into a minimum number of fixed-capacity bins while not packing fragments of conflicting items into the same bin. We assume a size-preserving fragmentation, i.e., the total size of fragments of an item packed into the bins has to be equal to the item's original size. We first prove that BPPC-IF is still NP-hard even though items can be fragmented. Unlike the Bin Packing Problem with Item Fragmentation (BPPIF), we show that BPPC-IF does not necessarily admit optimal solutions with a special structure. Moreover, we show that preprocessing an instance with oversized items (items with size greater than bin capacity) by packing a fragment of such items with size equal to bin capacity to a single bin does not necessarily yield an optimal solution. Using this observation, we develop a lower bounding procedure. Finally, we propose a heuristic algorithm which sequentially packs items into the bins using the observation about the oversized items. Through an extensive computational study, we demonstrate the superior performance of the proposed solution approach over the existing algorithms in the literature.
DOI
10.1016/j.cor.2020.105113
Cilt
126
