Pierre Lemaire

Assistant Professor at Grenoble INP (School of Industrial Engineering); member of the G-SCOP lab

Ph.D. thesis


Packing of Multibin Objects




A multibin object is made of several identical parts; each of them must be packed into a different bin. The height of a bin is the sum of the heights of the objects packed into it. This concept generalizes some well-studied problems of the operations research literature.

A classification of multibin models is provided. Their theoretic bases are studied.

In particular, the complexity for the main object types and objectives is investigated.

A detailed study is carried out when objects are of constant width and the objective is to minimize the height of the highest bin. Lower bounds, fast heuristics with very good performance garantees and a genetic algorithm are proposed to solve this model. The theoretic and experimental behaviors of these algorithms are analyzed.

Key words: bin-packing, scheduling, approximation algorithms, genetic algorithms

The manuscript is available from HAL, as a PS file or as a PDF file (in French). All related software is available from this site.