The load-balanced multi-dimensional bin-packing problem

Alessio Trivella, David Pisinger

    Research output: Contribution to journalJournal articleResearchpeer-review

    603 Downloads (Pure)

    Abstract

    The bin-packing problem is one of the most investigated and applicable combinatorial optimization problems. In this paper we consider its multi-dimensional version with the practical extension of load balancing, i.e. to find the packing requiring the minimum number of bins while ensuring that the average center of mass of the loaded bins falls as close as possible to an ideal point, for instance, the center of the bin. We formally describe the problem using mixed-integer linear programming models, from the simple case where we want to optimally balance a set of items already assigned to a single bin, to the general balanced bin-packing problem. Given the difficulty for standard solvers to deal even with small size instances, a multi-level local search heuristic is presented. The algorithm takes advantage of the Fekete-Schepers representation of feasible packings in terms of particular classes of interval graphs, and iteratively improves the load balancing of a bin-packing solution using different search levels. The first level explores the space of transitive orientations of the complement graphs associated with the packing, the second modifies the structure itself of the interval graphs, the third exchanges items between bins repacking proper n-tuples of weakly balanced bins. Computational experiments show very promising results on a set of 3D bin-packing instances from the literature.
    Original languageEnglish
    JournalComputers & Operations Research
    Volume74
    Pages (from-to)152-164
    ISSN0305-0548
    DOIs
    Publication statusPublished - 2016

    Keywords

    • Load balancing
    • Local search
    • MILP modeling
    • Multi-dimensional bin-packing

    Fingerprint Dive into the research topics of 'The load-balanced multi-dimensional bin-packing problem'. Together they form a unique fingerprint.

    Cite this