箱子是在线到达的带核元变尺寸装箱问题

本文考虑了一类箱子在线到达的带核元变尺寸装箱问题．假定箱子的尺寸可以是不同的．箱子是在线到达的，仅当箱子到达后其尺寸才知道．给定一个带有核元的物件表，目标是要将表中元素装入到达的箱子中，使得所用的箱子总长最小．我们首先证明了该问题是强NP—Hard，其次分析了经典算法NF(D)和FF(D)的性能界，指出NF(D)和FF(D)算法的性能界可以任意大．最后我们给出了相应的修改算法MNF(D)和MFF(D)，证明了它们的性能界都是3，此界是紧的．     

带参量的非合作装箱博弈

带参量的非合作装箱博弈是指:每个物品的尺寸都介于0和参量x(0相似文献   

物品大小不超过1/2的一维在线装箱模型研究

研究主要针对所有装入物品大小上限为1/2时的一维装箱问题模型展开,根据物品尺寸大小划分的思想,提出一种新的一维在线装箱算法.本模型中,物品在线到来,对即将到来的物品信息及物品数量未知,算法执行过程中,首先根据物品尺寸大小将物品划分成7大类,再根据欲先设定的packing规则,将对应类物品放入对应类型箱子中,任何时刻,算法最多打开7个箱子.算法设计过程中,不再需要额外的空间存储物品,物品一旦装入箱子不允许取出重装,箱子关闭后不允许再打开装其他物品.最后,通过详细的分析计算,验证出本算法能获得1.4236的渐近竞争比.同时通过实例构建得出问题新的下界为1.4231,将上下界之间的缝隙缩小至0.0005.     

超尺寸物品装箱问题

本文给出一类新的装箱问题，超尺寸物品装箱问题。就实际解决该问题所普遍彩的两步法，证明了当采用经典目标函数并且拆分次数不超过2时，第二步采用FFDLR的渐进最坏比为3/2。进而针对超尺寸物品装箱问题的算法提出了一个评价效率更高的目标函数。证明了在此目标函数下，当不限制物品的最大尺寸时，第二步采用最优装法两步法的渐近最坏比为2。最后，给出渐近最坏与拆分次数的关系。     

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

货物尺寸相同的2维装箱问题的等价类

在生产与储运领域,把小长方体货物(盒子)装入大长方体箱子是一项重要的工作.本文涉及的问题是把相同尺寸(a×b×c)的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子(a×b)填装到一个2维箱子X ×Y中.本文讨论当盒子尺寸(a×b包括b×a)给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

关于图的弱核和伪核（英文）

如果图G的每个自同态都是自同构,则称G为一个核.如果图G的每个自同态都是自同构或者自同态的象集是一个核(最大团),则称G为一个弱核(伪核).因为弱核(伪核)的概念最接近于核,判别一个图是否为弱核(伪核)是有意义的问题.我们给出一个图是弱核(伪核)的充要条件和弱核(伪核)的一些例子.     

平面图的Alcuin数

广义渡河问题是一类重要的组合优化问题,它是经典的狼-羊-卷心菜游戏的推广。冲突图是一个图,这个图的任意两个点所代表的物品不相容时(例如,狼和羊代表的物品不相容),则在这两个点之间连结一条边。渡河覆盖问题的目的是确定冲突图全部点所代表的物品从河的一岸安全地摆渡到河的对岸时所需船的最小容量,而冲突图的Alcuin数定义这个最小容量。本文讨论了平面图的Alcuin数, 给出了该类图Alcuin数的完全刻画。     

基于主成分原理的多元质量控制图的构造

控制图是从事统计质量管理经常使用的重要工具,经过多年的发展和实践,一元质量控制图业已得到普遍推广,可是如何开展多元质量控制仍有许多问题值得探讨。在这篇文章中,我们着重讨论了基于主成分分析的多元质量控制图的构造,并结合从企业现场采集到的数据给出了具体的应用说明。     

几类特殊有向循环图的核

有向图D=(V,A)的核K是顶点集V的一个子集,其中K中任意两点在D中均不相邻,并且对V\K中任意一个点v,都存在K中的一个点u,使得(v,u)是D中的一条弧.一般有向图核的存在问题是NP-完全的.Bang-Jensen和Gutin在他们的著作[Digraphs:Theory, Algorithms and Applications, London:Springer-Verlag, 2000]中提出公开问题(Problem 12.3.5):刻画有向循环图核存在性.本文研究了几类特殊有向循环图核的存在问题,并给出了Duchet核猜想(对任意一个不是有向奇圈的无核有向图,都存在一条弧,使得删除这条弧所得到的图仍然是无核的)的一类反例.     

A one-dimensional bin packing problem with shelf divisions

Given bins of size B, non-negative values d and Δ, and a list L of items, each item e∈L with size s_e and class c_e, we define a shelf as a subset of items packed inside a bin with total item sizes at most Δ such that all items in this shelf have the same class. Two subsequent shelves must be separated by a shelf division of size d. The size of a shelf is the total size of its items plus the size of the shelf division. The class constrained shelf bin packing problem (CCSBP) is to pack the items of L into the minimum number of bins, such that the items are divided into shelves and the total size of the shelves in a bin is at most B. We present hybrid algorithms based on the First Fit (Decreasing) and Best Fit (Decreasing) algorithms, and an APTAS for the problem CCSBP when the number of different classes is bounded by a constant C.     

New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems

We consider two types of orthogonal, oriented, rectangular, two-dimensional packing problems. The first is the strip packing problem, for which four new and improved level-packing algorithms are presented. Two of these algorithms guarantee a packing that may be disentangled by guillotine cuts. These are combined with a two-stage heuristic designed to find a solution to the variable-sized bin packing problem, where the aim is to pack all items into bins so as to minimise the packing area. This heuristic packs the levels of a solution to the strip packing problem into large bins and then attempts to repack the items in those bins into smaller bins in order to reduce wasted space. The results of the algorithms are compared to those of seven level-packing heuristics from the literature by means of a large number of strip-packing benchmark instances. It is found that the new algorithms are an improvement over known level-packing heuristics for the strip packing problem. The advancements made by the new and improved algorithms are limited in terms of utilised space when applied to the variable-sized bin packing problem. However, they do provide results faster than many existing algorithms.     

Online variable-sized bin packing with conflicts

We study a new kind of online bin packing with conflicts, motivated by a problem arising when scheduling jobs on the Grid. In this bin packing problem, the set of items is given at the beginning, together with a set of conflicts on pairs of items. A conflict on a pair of items implies that they cannot be assigned to a common bin. The online scenario is realized as follows. Variable-sized bins arrive one by one, and items need to be assigned to each bin before the next bin arrives. We analyze the online problem as well as semi-online versions of it, which are the variant where the sizes of the arriving bins are monotonically non-increasing as well as the variant where they are monotonically non-decreasing.     

Simple but effective heuristics for the 2-constraint bin packing problem

The 2-constraint bin packing problem consists in packing a given number of items, each one characterised by two different but not related dimensions, into the minimum number of bins in such a way to do not exceed the capacity of the bins in either dimension. The development of the heuristics for this problem is challenged by the need of a proper definition of the criterion for evaluating the feasibility of the two capacity constraints on the two different dimensions. In this paper, we propose a computational evaluation of several criteria, and two simple but effective algorithms—a greedy and neighbourhood search algorithms—for solving the 2-constraint bin packing problem. An extensive computational analysis supports our main claim.     

Selfish Square Packing

We consider a game-theoretical bin packing problem. The 1D (one dimensional) case has been treated in the literature as the ʼselfish bin packing problemʼ. We investigate a 2D version, in which the items to be packed are squares and the bins are unit squares. In this game, a set of items is packed into bins. Each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. One at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. At a Nash equilibrium, no player can reduce the cost he is charged by moving his item to a different bin. In the 2D case, to decide whether an item can be placed in another bin with other items is NP-complete, so we consider that players use a packing algorithm to make this decision. We show that this game converges to a Nash equilibrium, independently of the packing algorithm used. We prove that the price of anarchy is at least 2.27. We also prove that, using the NFDH packing algorithm, the asymptotic price of anarchy is at most 2.6875.     

On the sum minimization version of the online bin covering problem

Given a set of m identical bins of size 1, the online input consists of a (potentially infinite) stream of items in (0,1]. Each item is to be assigned to a bin upon arrival. The goal is to cover all bins, that is, to reach a situation where a total size of items of at least 1 is assigned to each bin. The cost of an algorithm is the sum of all used items at the moment when the goal is first fulfilled. We consider three variants of the problem, the online problem, where there is no restriction of the input items, and the two semi-online models, where the items arrive sorted by size, that is, either by non-decreasing size or by non-increasing size. The offline problem is considered as well.     

基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。     

Resource augmented semi-online bounded space bin packing

We study on-line bounded space bin-packing in the resource augmentation model of competitive analysis. In this model, the on-line bounded space packing algorithm has to pack a list L of items with sizes in (0, 1], into a minimum number of bins of size b, b≥1. A bounded space algorithm has the property that it only has a constant number of active bins available to accept items at any point during processing. The performance of the algorithm is measured by comparing the produced packing with an optimal offline packing of the list L into bins of size 1. The competitive ratio then becomes a function of the on-line bin size b. Csirik and Woeginger studied this problem in [J. Csirik, G.J. Woeginger, Resource augmentation for online bounded space bin packing, Journal of Algorithms 44(2) (2002) 308-320] and proved that no on-line bounded space algorithm can perform better than a certain bound ρ(b) in the worst case. We relax the on-line condition by allowing a complete repacking within the active bins, and show that the same lower bound holds for this problem as well, and repacking may only allow one to obtain the exact best possible competitive ratio of ρ(b) having a constant number of active bins, instead of achieving this bound in the limit. We design a polynomial time on-line algorithm that uses three active bins and achieves the exact best possible competitive ratio ρ(b) for the given problem.     

Relations between capacity utilization,minimal bin size and bin number

We consider the two-dimensional bin packing problem given a set of rectangular items, find the minimal number of rectangular bins needed to pack all items. Rotation of the items is not permitted. We show for any integer \({k} \ge 3\) that at most \({k}-1\) bins are needed to pack all items if every item fits into a bin and if the total area of items does not exceed \({k}/4\) -times the bin area. Moreover, this bound is tight. Furthermore, we show that only two bins are necessary to pack all items if the total area of items is not larger than the bin area, and if the height of each item is not larger than a third of the bin height and the width of every item does not exceed half of the bin width.