Exact algorithms for the two-dimensional guillotine knapsack

作     者：Dolatabadi, Mohammad Lodi, Andrea Monaci, Michele 

作者机构：Univ Bologna DEIS I-40136 Bologna Italy Univ Ferdowsi Fac Math & Stat Mashhad Iran Univ Padua DEI I-35131 Padua Italy 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2012年第39卷第1期

页      面：48-53页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Ministry of Science  Research and Development of the Islamic Republic of Iran 

主　　题：Two-dimensional knapsack Guillotine packing Exact algorithm 

摘      要：The two-dimensional knapsack problem requires to pack a maximum profit subset of small rectangular items into a unique large rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem. In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are computationally evaluated on well-known benchmark instances from the literature. The C++ source code of the recursive procedure is available upon request from the authors. (C) 2011 Elsevier Ltd. All rights reserved.