期刊
INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS
卷 145, 期 2, 页码 511-530出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ijpe.2013.04.032
关键词
Two-dimensional strip packing problem; Integer programming; Load balancing constraints; Multi-drop requirements; Load bearing constraints
资金
- CNPq
- FAPEG
In the oriented Two-Dimensional Strip Packing Problem (2SP), one has to pack a set of rectangular items into a rectangular strip and minimizes the overall strip height used to pack all items. This paper deals with the 2SP under two practical situations. In the first, feasible packings must respect the load balancing and the multi-drop constraints. That is, the center of gravity of the packing at each moment must lie in a safety region, even after a subset of items is unloaded. In the second situation, the load balancing constraint is combined with the load bearing constraint. In a packing that respect the load bearing constraint, the bearing capacity of each item must be respected. That is, there is a maximum tolerable weight that each item can bear. For both situations, we present approximate 0-1 integer linear programming models and heuristics, based on level-packing algorithms and packing on corner points. The level-packing heuristic has an asymptotic approximation ratio bounded by 1.75, when the number of orders is bounded by a constant. The heuristics have proven to be helpful when combined with the integer models. In addition, many computational experiments validate the integer models and show that they are suitable to deal with problems where the number of possible positions to arrange the items in the bin is small. (C) 2013 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据