6533b86ffe1ef96bd12cde2a
RESEARCH PRODUCT
Matheuristics for the irregular bin packing problem with free rotations
José Manuel TamaritAntonio Martinez-sykoraJulia A. BennellRubén RuizRamón Alvarez-valdéssubject
Mathematical optimization021103 operations researchInformation Systems and ManagementGeneral Computer ScienceBin packing problemESTADISTICA E INVESTIGACION OPERATIVA0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchStrip packingTwo-dimensional irregular bin packingConstructiveIndustrial and Manufacturing EngineeringBinCutting and packingSet packingCutting stock problemModeling and Simulation0202 electrical engineering electronic engineering information engineeringInteger Programing020201 artificial intelligence & image processingFree rotationFinite setMathematicsdescription
[EN] We present a number of variants of a constructive algorithm able to solve a wide variety of variants of the Two-Dimensional Irregular Bin Packing Problem (2DIBPP). The aim of the 2DIBPP is to pack a set of irregular pieces, which may have concavities, into stock sheets (bins) with fixed dimensions in such a way that the utilization is maximized. This problem is inspired by a real application from a ceramic company in Spain. In addition, this problem arises in other industries such as the garment industry or ship building. The constructive procedure presented in this paper allows both free orientation for the pieces, as in the case of the ceramic industry, or a finite set of orientations as in the case of the garment industry. We explicitly model the assignment of pieces to bins and compare with the more common strategy of packing bins sequentially. There are very few papers in the literature that address the bin packing problem with irregular pieces and to our knowledge this is the first to additionally consider free rotation of pieces with bin packing. We propose several Integer Programing models to determine the association between pieces and bins and then we use a Mixed Integer Programing model for placing the pieces into the bins. The computational results show that the algorithm obtains high quality results in sets of instances with different properties. We have used both industry data and the available data in the literature of 2D irregular strip packing and bin packing problems. (C) 2016 Elsevier B.V. All rights reserved.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-04-16 |