期刊
COMPUTERS & OPERATIONS RESEARCH
卷 39, 期 1, 页码 48-53出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2010.12.018
关键词
Two-dimensional knapsack; Guillotine packing; Exact algorithm
类别
资金
- Ministry of Science, Research and Development of the Islamic Republic of Iran
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据