Efficient algorithms for real-life instances of the variable size bin packing problem

Jørgen Bang-Jensen, Rune Larsen

Research output: Contribution to journalJournal articleResearchpeer-review

992 Downloads (Pure)

Abstract

In this paper we present a local search heuristic for real-life instances of the variable size bin packing problem, and an exact algorithm for small instances. One important issue our heuristic is able to satisfy is that solutions must be delivered within (milli)seconds and that the solution methods should be robust to last minute changes in the data. Furthermore we show that we are able to incorporate the concept of usable leftovers on a single bin, and the implementation of many additional constraints should be supported by the straightforward solution representation. The heuristic is compared to others from the literature, and comes out ahead on a large subset of the instances.
Original languageEnglish
JournalComputers & Operations Research
Volume39
Issue number11
Pages (from-to)2848-2857
ISSN0305-0548
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Variable size bin packing problem
  • Cutting stock
  • Real-life application
  • Heuristics

Fingerprint

Dive into the research topics of 'Efficient algorithms for real-life instances of the variable size bin packing problem'. Together they form a unique fingerprint.

Cite this