Packing rectangles in a strip

Rectangles with dimensions independently chosen from a uniform distribution on [0,1] are packed on-line into a unit-width strip under a constraint like that of the Tetris game: rectangles arrive from the top and must be moved inside the strip to reach their place; once placed, they cannot be moved again. Cargo loading applications impose similar constraints. This paper assumes that rectangles must be moved without rotation. For n rectangles, the resulting packing height is shown to have an asymptotic expected value of at least (0.31382733 ...)n under any on-line packing algorithm. An on-line algorithm is presented that achieves an asymptotic expected height of (0.36976421 ...)n. This algorithm improves the bound achieved in Next Fit Level (NFL) packing, by compressing the items packed on two successive levels of an NFL packing via on-line movement admissible under the Tetris constraint. Received: 6 February 2001 / 25 June 2002     

Multidimensional Cube Packing

We consider the d-dimensional cube packing problem (d-CPP): given a list L of d-dimensional cubes and (an unlimited quantity of) d-dimensional unit-capacity cubes, called bins, find a packing of L into the minimum number of bins. We present two approximation algorithms for d-CPP, for fixed d. The first algorithm has an asymptotic performance bound that can be made arbitrarily close to 2 – (1/2)^d . The second algorithm is an improvement of the first and has an asymptotic performance bound that can be made arbitrarily close to 2 – (2/3)^d . To our knowledge, these results improve the bounds known so far for d = 2 and d = 3, and are the first results with bounds that are not exponential in the dimension.     

A systolic-based parallel bin packing algorithm

A systolic based parallel approximation algorithm that obtains solutions to the I-D bin packing problem is presented. The algorithm has an asymptotic error bound of 1.5 and time complexity O(n). An experimental study demonstrates that the heuristic offers improved packing and execution performance over parallelizations of two well-known serial algorithms     

求解三维装箱问题的混合模拟退火算法

提出了一个高效求解三维装箱问题(Three Dimensional Container Loading Problem 3D-CLP)的混合模拟退火算法.三维装箱问题要求装载给定箱子集合的一个子集到容器中,使得被装载的箱子总体积最大.文中介绍的混合模拟退火算法基于三个重要算法:(1)复合块生成算法,与传统算法不同的是文中提出的复合块不只包含单一种类的箱子,而是可以在一定的限制条件下包含任意种类的箱子.(2)基础启发式算法,该算法基于块装载,可以按照指定装载序列生成放置方案.(3)模拟退火算法,以复合块生成和基础启发式算法为基础,将装载序列作为可行放置方案的编码,在编码空间中采用模拟退火算法进行搜索以寻找问题的近似最优解.文中采用1500个弱异构和强异构的装箱问题数据对算法进行测试.实验结果表明,混合模拟退火算法的填充率超过了目前已知的优秀算法.     

受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.     

Batched bin packing revisited

We revisit the batched bin packing problem. In this model, items come in K consecutive batches, and the items of the earlier batches must be packed without any knowledge of later batches. We give the first approximation algorithm for the case \(K=2\), with tight asymptotic approximation ratio of 1.5833, while the known lower bound of the model is 1.378. With the application of this result, we are also able to provide an improved algorithm for the recently defined graph-bin packing problem in a special case, where we improve the upper bound from 3 to 2.5833.     

求解online packing problem的F-B绝对近似算法

FF算法由于其在线特性在处理在线装箱问题得到广泛使用,但它无法预测后面达到物品造成装箱率低,提出一种预留一定比例的各类未装满箱体的装箱算法。首先对未装满箱体分类并给出相应的数据结构,接着设计一种绑定配对策略来预留各类未装满箱体数目,并引入间隔函数控制新箱体的启用,最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比。提出了一种预留绑定配对策略为后续输入物品提供预测空间,特别的是F-B算法能得到5/3的绝对近似比。     

有色装箱问题的在线近似算法

有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC－A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC－A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC－A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC－FF表现出相对更好的实验效果。     

A GRASP/Path Relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems

The three-dimensional multiple bin-size bin packing problem, MBSBPP, is the problem of packing a set of boxes into a set of bins when several types of bins of different sizes and costs are available and the objective is to minimize the total cost of bins used for packing the boxes. First we propose a GRASP algorithm, including a constructive procedure, a postprocessing phase and some improvement moves. The best solutions obtained are then combined into a Path Relinking procedure for which we have developed three versions: static, dynamic and evolutionary. An extensive computational study, using two- and three-dimensional instances, shows the relative efficiency of the alternatives considered for each phase of the algorithm and the good performance of our algorithm compared with previously reported results.     

New heuristics for one-dimensional bin-packing

Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.Scope and purposePacking items into boxes or bins is a task that occurs frequently in distribution and production. A large variety of different packing problems can be distinguished, depending on the size and shape of the items, as well as on the form and capacity of the bins (H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin, 1992). Similar problems occur in minimising material wastage while cutting pieces into particular smaller ones and in the scheduling of identical processors in order to minimise total completion time. This work addresses the basic packing problem, known as the one-dimensional bin packing problem, where it is required to pack a number of items into the smallest possible number of bins of pre-specified equal capacity. Even though this problem is simple to state, it is NP hard, i.e., it is unlikely that there exists an algorithm that could solve every instance of it in polynomial time. Solution of more general realistic packing problems is probably contingent upon the availability of effective and computationally efficient solution procedures for the basic problem. In this work we present several heuristics capable of doing that. Extensive computational testing attests to the power of these heuristics, as well as to their computational efficiency.     

Lower bounds for on-line two-dimensional packing algorithms

Summary Many problems, such as cutting stock problems and the scheduling of tasks with a shared resource, can be viewed as two-dimensional bin packing problems. Using the two-dimensional packing model of Baker, Coffman, and Rivest, a finite list L of rectangles is to be packed into a rectangular bin of finite width but infinite height, so as to minimize the total height used. An algorithm which packs the list in the order given without looking ahead or moving pieces already packed is called an on-line algorithm. Since the problem of finding an optimal packing is NP-hard, previous work has been directed at finding approximation algorithms. Most of the approximation algorithms which have been studied are on-line except that they require the list to have been previously sorted by height or width. This paper examines lower bounds for the worst-case performance of on-line algorithms for both non-preordered lists and for lists preordered by increasing or decreasing height or width.This author's work was supported by the Joint Services Electronics Program (U.S. Army, U.S. Navy and U.S. Air Force) under Contract DAAG-29-78-C-0016     

A new heuristic algorithm for cuboids packing with no orientation constraints

The three-dimensional cuboids packing is NP-hard and finds many applications in the transportation industry. The problem is to pack a subset of cuboid boxes into a big cuboid container such that the total volume of the packed boxes is maximized. The boxes have no orientation constraints, i.e. they can be rotated by 90^°${90}^{°}$ in any direction. A new heuristic algorithm is presented that defines a conception of caving degree to judge how close a packing box is to those boxes already packed into the container, and always chooses a packing with the largest caving degree to do. The performance is evaluated on all the 47 related benchmarks from the OR-Library. Experiments on a personal computer show a high average volume utilization of 94.6% with an average computation time of 23 min for the strengthened A1 algorithm, which improves current best records by 3.6%. In addition, the top-10 A2 algorithm achieved an average volume utilization of 91.9% with an average computation time of 55 s, which also got higher utilization than current best records reported in the literature.     

Average-case performance analysis of scheduling random parallel tasks with precedence constraints on mesh connected multicomputer systems

We investigate the problem of scheduling parallel tasks with precedence constraints on mesh connected multicomputer systems. It is still an open problem on whether there exists an approximation algorithm with finite asymptotic worst-case and/or average-case performance bound for this scheduling problem. As an early attempt to solve our problem, we propose and analyze the performance of a level-by-level scheduling algorithm LL. In fact, we solve a special case of the problem when all tasks request for square submeshes and run on a square mesh system whose size is a power of 2. There are three basic techniques in algorithm LL, i.e., the level-by-level scheduling strategy for handling precedence constraints, the largest-task-first algorithm for scheduling tasks in the same level, and the two-dimensional buddy system for system partitioning and processor allocation. Algorithm LL does not have a finite worst-case performance bound; however, it has quite acceptable average-case performance. The main contribution of the paper is to show that under the assumptions that task sizes are independent and identically distributed (i.i.d.) random variables with a common probability distribution, and that task execution times are i.i.d. random variables with finite mean and variance, and that the probability distributions of task sizes and execution times are independent of each other, for wide task graphs and typical task size distributions, algorithm LL has an asymptotic average-case performance bound about two for all probability distributions of task execution times.     

二维不规则零件排样问题的遗传算法求解

提出一种基于遗传算法求解二维不规则零件排样问题的方法，通过提取零件的最小包络矩形，将其转变为矩形件的正交排样问题，应用一种有效的解码算法－“最低水平线法”将编码转变为排样图。实例表明，该算法是有效的。     

On Dynamic Bin Packing: An Improved Lower Bound and Resource Augmentation Analysis

We study the dynamic bin packing problem introduced by Coffman, Garey and Johnson. This problem is a generalization of the bin packing problem in which items may arrive and depart from the packing dynamically. The main result in this paper is a lower bound of 2.5 on the achievable competitive ratio, improving the best known 2.428 lower bound, and revealing that packing items of restricted form like unit fractions (i.e., of size 1/k for some integer k), for which a 2.4985-competitive algorithm is known, is indeed easier. We also investigate the resource augmentation version of the problem where the on-line algorithm can use bins of size b (>1) times that of the optimal off-line algorithm. An interesting result is that we prove b=2 is both necessary and sufficient for the on-line algorithm to match the performance of the optimal off-line algorithm, i.e., achieve 1-competitiveness. Further analysis gives a trade-off between the bin size multiplier 1<b≤2 and the achievable competitive ratio. J.W.-T. Chan’s research is partly supported by Hong Kong RGC Grant HKU5172/03E when the author was with the Department of Computer Science, University of Hong Kong, Hong Kong. P.W.H. Wong’s research is partly supported by Nuffield Foundation Grant NAL/01004/G.     

A simple randomized algorithm for two-dimensional strip packing

Two-dimensional strip packing problem is to pack given rectangular pieces on a strip of stock sheet having fixed width and infinite height. Its aim is to minimize the height of the strip such that non-guillotinable and fix orientation constraints are meet. In this paper, an improved scoring rule is developed and the least waste priority strategy is introduced, and a randomized algorithm is presented for solving this problem. This algorithm is very simple and does not need to set any parameters. Computational results on a wide range of benchmark problem instances show that the proposed algorithm obtains a better or matching performance as compared to the most of the previously published meta-heuristics.     

互联网信息组织和规划中的带拒绝装箱问题

讨论如下定义的带拒绝装箱问题：设有许多等长的一维箱子，给定一个物品集，每个物品有两个参数：长度和罚值．物品可以放入箱子也可被拒绝放入箱子．如果将物品放入箱子，则使该箱剩余长度减少．一旦需将某一物品放入某一箱中，而该箱的剩余长度不够时，则需启用新箱子．如果物品被拒绝放入任何箱中，则产生惩罚．问怎样安排物品使所用箱子数与未装箱的物品总罚值之和最小．该问题是一个新的组合优化问题，来源于内部互联网的信息组织和规划．该文首先给出一个最优解值的下界估计，它可用于分枝定界法求最优解．由于该问题是强NP-难的，该文进一步研究它的离线和在线近似算法的设计与分析．文中给出一个离线算法，其绝对性能比为2；同时给出一个在线算法，其绝对性能比不超过3，渐近性能比为2，还对算法性能比的下界进行了讨论．     

A heuristic block-loading algorithm based on multi-layer search for the container loading problem

This paper presents an efficient heuristic block-loading algorithm based on multi-layer search for the three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing phase, according to a fixed strategy, until no blocks are available. Second, the concept of composite block is introduced, the difference between traditional block and composite block being that composite block can contain multiple types of boxes in one block under some restrictions. Third, based on the depth-first search algorithm, a multi-layer search algorithm is developed for determining the selected block in each packing phase, and making this result closer to the optimal solution. Computational results on a classic data set show that the proposed algorithm outperforms the best known algorithm in almost all the test data.     

An LP-based heuristic algorithm for the node capacitated in-tree packing problem

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.     

Multi-dimensional bin packing problems with guillotine constraints

The problem addressed in this paper is the decision problem of determining if a set of multi-dimensional rectangular boxes can be orthogonally packed into a rectangular bin while satisfying the requirement that the packing should be guillotine cuttable. That is, there should exist a series of face parallel straight cuts that can recursively cut the bin into pieces so that each piece contains a box and no box has been intersected by a cut. The unrestricted problem is known to be NP-hard. In this paper we present a generalization of a constructive algorithm for the multi-dimensional bin packing problem, with and without the guillotine constraint, based on constraint programming.