Matheuristics for the irregular bin packing problem with free rotations

A. Martinez-Sykora, R. Alvarez-Valdes, J.A. Bennell, R. Ruiz and J.M. Tamarit

European Journal of Operational Research, 2017, vol. 258, issue 2, 440-455

Abstract: 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.

Keywords: Cutting and packing; Two-dimensional irregular bin packing; Integer Programing (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221716307950
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:258:y:2017:i:2:p:440-455

DOI: 10.1016/j.ejor.2016.09.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().