Bin Packing Problem with Generalized Precedence Constraints (BPPGP)
Raphael Kramer, Mauro Dell’Amico and Manuel Iori
DISMI, University of Modena and Reggio Emilia,
42100 Reggio Emilia, Italy.
Abstract
The BPP-GP can be formally defined as follows. We are given a set N = {1, 2, ..., n} of items, each having positive weight wj, a set M = {1, 2, ..., m} of identical bins, each having capacity C, and an arc set A used to represent the generalized precedence relationships. With each arc (j, k) ∈ A is associated a non-negative integer value tjk. Let ik be the index of the bin receiving item k and ij the index of the bin containing item j. The precedence constraints impose that ik - ij ≥ tjk, for all (j, k) ∈ A. The aim of the BPP-GP is to pack all items by satisfying capacity and precedence requirements, and minimizing the index of the last bin in which an item is packed.
Key words
Bin Packing Problem, Generalized Precedence Constraints, Iterated Local Search, Batching Moves.
----------
To download the slide presentation click here.
To download the accepted manuscript click here.