Hybrid optimisation with ant colony methods for the guillotine bin packing problem

In this paper, we are interested in the guillotine bin packing problem (2BP/O/G). The aim of this problem is to cut a set of rectangular pieces (items) from a set of identical large rectangular pieces (stock sheets). We try to minimize the number of stock sheets used in order to satisfy the demand. This is done applying edge to edge cut, which is called the guillotine constraint. We propose in this paper a resolution approach using Ant Colony Optimization (ACO) and the SHF–FF heuristic of Messaoud et al. in order to solve this NP–hard problem. We improve the best known results.