Two-Dimensional Bin Packing Problem with Guillotine Restrictions

Pietrobuoni, Enrico (2015) Two-Dimensional Bin Packing Problem with Guillotine Restrictions, [Dissertation thesis], Alma Mater Studiorum Università di Bologna. Dottorato di ricerca in Automatica e ricerca operativa, 26 Ciclo. DOI 10.6092/unibo/amsdottorato/6810.
Documenti full-text disponibili:
Documento PDF (English) - Richiede un lettore di PDF come Xpdf o Adobe Acrobat Reader
Download (601kB) | Anteprima


This thesis, after presenting recent advances obtained for the two-dimensional bin packing problem, focuses on the case where guillotine restrictions are imposed. A mathematical characterization of non-guillotine patterns is provided and the relation between the solution value of the two-dimensional problem with guillotine restrictions and the two-dimensional problem unrestricted is being studied from a worst-case perspective. Finally it presents a new heuristic algorithm, for the two-dimensional problem with guillotine restrictions, based on partial enumeration, and computationally evaluates its performance on a large set of instances from the literature. Computational experiments show that the algorithm is able to produce proven optimal solutions for a large number of problems, and gives a tight approximation of the optimum in the remaining cases.

Tipologia del documento
Tesi di dottorato
Pietrobuoni, Enrico
Dottorato di ricerca
Scuola di dottorato
Scienze e ingegneria dell'informazione
Settore disciplinare
Settore concorsuale
Parole chiave
Cutting and Packing, Bin Packing Problem, Guillotine Restrictions, Worst-Case Performance Ratios, Blocked Ring, Heuristic Algorithms
Data di discussione
10 Aprile 2015

Altri metadati

Statistica sui download

Gestione del documento: Visualizza la tesi