Applying triple-block patterns in solving the two-dimensional bin packing problem

Yi-Ping Cui, Yi Yao and Defu Zhang

Journal of the Operational Research Society, 2018, vol. 69, issue 3, 402-415

Abstract: This paper presents a heuristic for the guillotine two-dimensional bin packing problem, where a set of rectangular items are packed using guillotine patterns into bins of the same size, such that the number of bins used is minimized. Both oriented and non-oriented items are considered. The algorithm considers a novel combination of three procedures. The first is a pattern-generation procedure that generates a set of triple-block patterns on each call. The second is a plan-generation procedure that uses some of these patterns to compose the solution. The third is a plan-improvement procedure that solves an integer linear programming model over a given set of patterns generated previously to improve the solution. According to the computational results, the heuristic can obtain very good solution quality. For some classes of instances, the gap to lower bound is reduced by more than 30% compared to algorithms recently published.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1057/s41274-016-0148-5 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:69:y:2018:i:3:p:402-415

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1057/s41274-016-0148-5

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().