On Solving the Oriented Two-Dimensional Bin Packing Problem under Free
  Guillotine Cutting: Exploiting the Power of Probabilistic Solution
  Construction
  Two-dimensional bin packing problems are highly relevant combinatorial
optimization problems. They find a large number of applications, for example,
in the context of transportation or warehousing, and for the cutting of
different materials such as glass, wood or metal. In this work we deal with the
oriented two-dimensional bin packing problem under free guillotine cutting. In
this specific problem a set of oriented rectangular items is given which must
be packed into a minimum number of bins of equal size. The first algorithm
proposed in this work is a randomized multi-start version of a constructive
one-pass heuristic from the literature. Additionally we propose the use of this
randomized one-pass heuristic within an evolutionary algorithm. The results of
the two proposed algorithms are compared to the best approaches from the
literature. In particular the evolutionary algorithm compares very favorably to
current state-of-the-art approaches. The optimal solution for 4 previously
unsolved instances could be found.
