Exact algorithms for the two-dimensional guillotine knapsack

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.     

Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts

This paper deals with the two-dimensional bin packing problem with conflicts (BPC-2D). Given a finite set of rectangular items, an unlimited number of rectangular bins and a conflict graph, the goal is to find a conflict-free packing of the items minimizing the number of bins used. In this paper, we propose a new framework based on a tree-decomposition for solving this problem. It proceeds by decomposing a BPC-2D instance into subproblems to be solved independently. Applying this decomposition method is not straightforward, since merging partial solutions is hard. Several heuristic strategies are proposed to make an effective use of the decomposition. Computational experiments show the practical effectiveness of our approach.     

A tree search algorithm for the container loading problem

This paper presents a binary tree search algorithm for the three dimensional container loading problem (3D-CLP). The 3D-CLP is about how to load a subset of a given set of rectangular boxes into a rectangular container, such that the packing volume is maximized. In this algorithm, all the boxes are grouped into strips and layers while three constraints, i.e., full support constraint, orientation constraint and guillotine cutting constraint are satisfied. A binary tree is created where each tree node denotes a container loading plan. For a non-root each node, the layer set of its left (or right) child is obtained by inserting a directed layer into its layer set. A directed layer is parallel (or perpendicular) to the left side of the container. Each leaf node denotes a complete container loading plan. The solution is the layer set whose total volume of the boxes is the greatest among all tree nodes. The proposed algorithm achieves good results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff with reasonable computing time.     

单规格一刀切矩形排样问题的启发式搜索算法

针对单规格一刀切二维矩形排样问题,提出了一种启发式搜索算法,称为大小工件分治择优匹配(bigitem smallitem divide-and-conquer best-fit,简称BSDBF)启发式算法.该算法基于组化规则,提出了大小工件分治策略和组块快速举荐算法,是对组化策略的关键补充,这对优解获得至关重要.然后,择优选择适应度高的组块进行递归排样,贪心获得各块板材的排样方案.最后,基于设计的工件拆分方法,对初始解进行后处理小规模重排,进一步提升解的质量.因为没有随机因素,其获得的优解可复现,也是BSDBF算法区别于其他算法的典型特征.大量Benchmark案例的实验结果表明,BSDBF算法求解质量优于其他算法报道结果.     

Two-dimensional on-line bin packing problem with rotatable items

In this paper, we consider a two-dimensional version of the on-line bin packing problem, in which each rectangular item that should be packed into unit square bins is “rotatable” by $\text{90°}$. Two on-line algorithms for solving the problem are proposed. The second algorithm is an extension of the first algorithm, and the worst-case ratio of the second one is at least 2.25 and at most 2.565.     

一种基于二叉树结构表达的矩形物体布局的启发式方法

本文提出了一种利用二叉树结构表达矩形物体布局状态空间的方法．通过将布局空间依次分割，每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块定位于当前布局空间的左上角来完成不同大小矩形物体的布局方案的确定．通过调整调序因子ＫＡ和ＫＢ的值，可得到满足不同要求的优化布局方案．同时，所得布局方案均满足工业上一刀切的要求．实验结果证明了该算法的灵活性和有效性．     

Algorithms for 3D guillotine cutting problems: Unbounded knapsack, cutting stock and strip packing

We present algorithms for the following three-dimensional (3D) guillotine cutting problems: unbounded knapsack, cutting stock and strip packing. We consider the case where the items have fixed orientation and the case where orthogonal rotations around all axes are allowed. For the unbounded 3D knapsack problem, we extend the recurrence formula proposed by [1] for the rectangular knapsack problem and present a dynamic programming algorithm that uses reduced raster points. We also consider a variant of the unbounded knapsack problem in which the cuts must be staged. For the 3D cutting stock problem and its variants in which the bins have different sizes (and the cuts must be staged), we present column generation-based algorithms. Modified versions of the algorithms for the 3D cutting stock problems with stages are then used to build algorithms for the 3D strip packing problem and its variants. The computational tests performed with the algorithms described in this paper indicate that they are useful to solve instances of moderate size.     

Asymptotic fully polynomial approximation schemes for variants of open-end bin packing

We consider three variants of the open-end bin packing problem. Such variants of bin packing allow the total size of items packed into a bin to exceed the capacity of a bin, provided that a removal of the last item assigned to a bin would bring the contents of the bin below the capacity. In the first variant, this last item is the minimum sized item in the bin, that is, each bin must satisfy the property that the removal of any item should bring the total size of items in the bin below 1. The next variant (which is also known as lazy bin covering is similar to the first one, but in addition to the first condition, all bins (expect for possibly one bin) must contain a total size of items of at least 1. We show that these two problems admit asymptotic fully polynomial time approximation schemes (AFPTAS). Moreover, they turn out to be equivalent. We briefly discuss a third variant, where the input items are totally ordered, and the removal of the maximum indexed item should bring the total size of items in the bin below 1, and show that this variant is strongly NP-hard.     

High density packings of equal circles in rectangles with variable aspect ratio

Arranging a fixed number n   of equal non-overlapping circles in a rectangle with variable aspect ratio is a non-standard packing problem. It arises if one has to decide how a certain number of circular items should be packed into a rectangular box when no assumption is made on the shape of the box. How must the box be designed to achieve the maximum packing density? This special problem was investigated by Lubachevsky and Graham in 2003, where they classified record packings for n≤213$n\le 213$. However, their work lacks a precise treatment of the closure of observed vacancies as well as any numerical data of the best arrangements found.     

一种带剪切约束的启发式二维装箱算法

提出一种满足剪切约束的启发式二维装箱算法,通过价值修正策略提高箱的空间 利用率,进而减少箱的使用数量。该启发式算法将较难装箱的物品赋予较高的价值及装箱优先 权;并通过延展或融合剩余零散空间,将未用的空间合并到剩余相邻空间,以改进空间利用率。 基于标杆测试数据集的仿真实验证明了该算法的有效性和相较于其他二维装箱算法的优越性。     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.     

Mechanical Assembly Packing Problem Using Joint Constraints

The three-dimensional packing problem is generally on how to pack a set of models into a given bounding box using the smallest packaging volume. It is known as an NP-hard problem. When discussing the packing problem in mechanical field, the space utilization of a mechanism is low due to the constraint of mechanical joints between different mechanical parts. Although such a situation can be improved by breaking the mechanism into components at every joint, it burdens the user when reassembling the mechanism and may also reduce the service life of mechanical parts. In this paper, we propose a novel mechanism packing algorithm that deliberately considers the DOFs (degrees of freedom) of mechanical joints. With this algorithm, we construct the solution space according to each joint. While building the search tree of the splitting scheme, we do not break the joint, but move the joint. Therefore, the algorithm proposed in this paper just requires the minimal number of splits to meet the goal of space utilization. Numerical examples show that the proposed method is convenient and efficient to pack three-dimensional models into a given bounding box with high space utilization.     

Bin packing problems with rejection penalties and their dual problems

In this paper we consider the following problems: we are given a set of n items {u₁, … , u_n} and a number of unit-capacity bins. Each item u_i has a size w_i ∈ (0, 1] and a penalty p_i ⩾ 0. An item can be either rejected, in which case we pay its penalty, or put into one bin under the constraint that the total size of the items in the bin is no greater than 1. No item can be spread into more than one bin. The objective is to minimize the total number of used bins plus the total penalty paid for the rejected items. We call the problem bin packing with rejection penalties, and denote it as BPR. For the on-line BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio arbitrarily close to 1.75 while the lower bound is 1.540. For the off-line BPR problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 1.5, and an algorithm with an asymptotic worst-case ratio of 1.5. We also study a closely related bin covering version of the problem. In this case p_i means some amount of profit. If an item is rejected, we get its profit, or it can be put into a bin in such a way that the total size of the items in the bin is no smaller than 1. The objective is to maximize the number of covered bins plus the total profit of all rejected items. We call this problem bin covering with rejection (BCR). For the on-line BCR problem, we show that no algorithm can have absolute competitive ratio greater than 0, and present an algorithm with asymptotic competitive ratio 1/2, which is the best possible. For the off-line BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound.     

Iterative approaches for solving a multi-objective 2-dimensional vector packing problem

In this paper, we address a bi-objective 2-dimensional vector packing problem (Mo2-DBPP) that calls for packing a set of items, each having two sizes in two independent dimensions, say, a weight and a height, into the minimum number of bins. The weight corresponds to a “hard” constraint that cannot be violated while the height is a “soft” constraint. The objective is to find a trade-off between the number of bins and the maximum height of a bin. This problem has various real-world applications (computer science, production planning and logistics). Based on the special structure of its Pareto front, we propose two iterative resolution approaches for solving the Mo2-DBPP. In each approach, we use several lower bounds, heuristics and metaheuristics. Computational experiments are performed on benchmarks inspired from the literature to compare the effectiveness of the two approaches.     

Generating pallet loading patterns with considerations of item stacking on end and side surfaces

In late 1979 a two phase heuristic algorithm employing dynamic programming was presented by Steudel for solving the two-dimensional cutting stock problem where all the small rectangles were of the same dimensions, but withour any restrictions that the cutting be performed in a purely “guillotine” fashion. The algorithm was applied to solving the common problem of loading rectangular items of size l by w on a rectangular pallet of size L and W so as to maximize the number of items per layer on the pallet deckboard. In this paper, a new three-phase heuristic is presented which extends the 1979 recursive procedure and evaluates the option of stacking items on their end and/or side surface within the best loading pattern of bottom-stacked items. The resulting pattern is then projected into the third dimension to generate the total “cubic” pallet load. Computation results show that end and/or side stacking (when applicable) can yield average improvements in the range of 5% in items per pallet load.     

Genetic algorithm for robot selection and work station assignment problem

In this paper, we introduce Genetic Algorithm (GA) for optimal Robot Selection and Work station Assignment (RS/WA) problem for a CIM system. In particular, the RS/WA problem can be considered as a generalized two-dimensional multi-type bin packing problem that has been shown to be NP-hard. A multichromosome GA combined with heuristic bin packing algorithm is implemented for solving the problem and the effeciency of proposed method is shown by numerical example. Our approach may be applicable to other this kind of bin packing problems.     

带预选搜索步深的二维一刀切矩形优化排料

排料问题是一种总体资源分配问题，其目标是将定量的资源划分为若干指定的份额。使剩余量极小。本文提出了一种新的二维一刀切矩形优化排料算法。实验结果表明，该算法效率高，灵活性强，可被广泛应用于许多相关排料领域。     

Variable neighbourhood search for the variable sized bin packing problem

The variable sized bin packing problem is a generalisation of the one-dimensional bin packing problem. Given is a set of weighted items, which must be packed into a minimum-cost set of bins of variable sizes and costs. This problem has practical applications, for example, in packing, transportation planning, and cutting. In this work we propose a variable neighbourhood search metaheuristic for tackling the variable sized bin packing problem. The presented algorithm can be seen as a hybrid metaheuristic, because it makes use of lower bounding techniques and dynamic programming in various algorithmic components. An extensive experimentation on a diverse set of problem instances shows that the proposed algorithm is very competitive with current state-of-the-art approaches.     

The load-balanced multi-dimensional bin-packing problem

The bin-packing problem is one of the most investigated and applicable combinatorial optimization problems. In this paper we consider its multi-dimensional version with the practical extension of load balancing, i.e. to find the packing requiring the minimum number of bins while ensuring that the average center of mass of the loaded bins falls as close as possible to an ideal point, for instance, the center of the bin. We formally describe the problem using mixed-integer linear programming models, from the simple case where we want to optimally balance a set of items already assigned to a single bin, to the general balanced bin-packing problem. Given the difficulty for standard solvers to deal even with small size instances, a multi-level local search heuristic is presented. The algorithm takes advantage of the Fekete–Schepers representation of feasible packings in terms of particular classes of interval graphs, and iteratively improves the load balancing of a bin-packing solution using different search levels. The first level explores the space of transitive orientations of the complement graphs associated with the packing, the second modifies the structure itself of the interval graphs, the third exchanges items between bins repacking proper n-tuples of weakly balanced bins. Computational experiments show very promising results on a set of 3D bin-packing instances from the literature.     

New Bounds for Multidimensional Packing

Abstract. New upper and lower bounds are presented for a multidimensional generalization of bin packing called box packing. Several variants of this problem, including bounded space box packing, square packing, variable-sized box packing and resource augmented box packing are also studied. The main results, stated for d=2 , are as follows: a new upper bound of 2.66013 for online box packing, a new 14/9 + ɛ polynomial time offline approximation algorithm for square packing, a new upper bound of 2.43828 for online square packing, a new lower bound of 1.62176 for online square packing, a new lower bound of 2.28229 for bounded space online square packing and a new upper bound of 2.32571 for online two-sized box packing.