Complexity results for storage loading problems with stacking constraints
Complexity results for storage loading problems with stacking constraints
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Florian Bruns;S. Knust;N. V. Shakhlevich
中科院分区：
文献类型：
--
作者：
Florian Bruns;S. Knust;N. V. Shakhlevich
在本文中，我们提出了复杂的结果存储加载问题的存储区域是有组织的固定堆栈有限的共同高度。这样的问题出现在几个实际应用中，例如，在集装箱码头、集装箱船或仓库的情况下。到达存储区域的进入物品必须被分配到堆叠，以便遵守某些约束（例如，不是每个项目都可以堆叠在每个其它项目的顶部）。我们研究的一般模型和特殊情况下，最多两个或三个项目可以存储在每个堆栈的结构特性。除了为其中的一些问题提供多项式时间算法外，我们还建立了NP-困难的边界。
In this paper, we present complexity results for storage loading problems where the storage area is organized in fixed stacks with a limited common height. Such problems appear in several practical applications, e.g., in the context of container terminals, container ships or warehouses. Incoming items arriving at a storage area have to be assigned to stacks so that certain constraints are respected (e.g., not every item may be stacked on top of every other item). We study structural properties of the general model and special cases where at most two or three items can be stored in each stack. Besides providing polynomial time algorithms for some of these problems, we establish the boundary to NP-hardness.