Two-dimensional strip packing problem with load balancing, load bearing and multi-drop constraints

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.