Abstract:We consider the stacking problem where items are temporarily stored in stacks in a stacking area. The stacks are working as Last In First Out (LIFO) data structures. The objective is to avoid {\em shifts} or {\em restows} that occur when an item has to leave the stacking area earlier than an item above it. We present a simple online algorithm for the problem where we pick a stack for an incoming item without any information on future items. We present a sufficient condition for the algorithm to avoid shifts expressed as an inequality involving the dimension of the stacking area, the number of load/unload points and the maximum number of items present at the same time. The condition is relatively tight in the sense that we can find instances requiring shifts for {\em any} algorithm (including offline algorithms) with small modifications of the condition. Our results indicate that our algorithm is useful if the number of load/unload points is relatively small compared to the number of items.
From: Martin Olsen [view email]
[v1]
Fri, 19 Jun 2026 12:28:57 UTC (88 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。