TY - JOUR

T1 - An asymptotically optimal algorithm for online stacking

AU - Olsen, Martin

AU - Andersen, Lars Nørvang

AU - Gross, Allan

N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2023/4

Y1 - 2023/4

N2 - Consider a storage area where arriving items are stored temporarily in bounded capacity stacks until their departure. We look into the problem of deciding where to put an arriving item with the objective of minimizing the maximum number of stacks used over time. The decision has to be made as soon as an item arrives, and we assume that we only have information on the departure times for the arriving item and the items currently at the storage area. We are only allowed to put an item on top of another item if the item below departs at a later time. We refer to this problem as online stacking. We assume that the storage time intervals are picked i.i.d. from [0 , 1] × [0 , 1] using an unknown distribution with a bounded probability density function. Under this mild condition, we present a simple polynomial time online algorithm and show that the competitive ratio converges to 1 in probability. The result holds if the stack capacity is o(n), where n is the number of items, including the realistic case where the capacity is a constant. Our experiments show that our results also have practical relevance.

AB - Consider a storage area where arriving items are stored temporarily in bounded capacity stacks until their departure. We look into the problem of deciding where to put an arriving item with the objective of minimizing the maximum number of stacks used over time. The decision has to be made as soon as an item arrives, and we assume that we only have information on the departure times for the arriving item and the items currently at the storage area. We are only allowed to put an item on top of another item if the item below departs at a later time. We refer to this problem as online stacking. We assume that the storage time intervals are picked i.i.d. from [0 , 1] × [0 , 1] using an unknown distribution with a bounded probability density function. Under this mild condition, we present a simple polynomial time online algorithm and show that the competitive ratio converges to 1 in probability. The result holds if the stack capacity is o(n), where n is the number of items, including the realistic case where the capacity is a constant. Our experiments show that our results also have practical relevance.

KW - Asymptotic optimality

KW - Online algorithms

KW - Stacking

KW - Stowage

UR - http://www.scopus.com/inward/record.url?scp=85145690972&partnerID=8YFLogxK

U2 - 10.1007/s00186-022-00808-7

DO - 10.1007/s00186-022-00808-7

M3 - Journal article

AN - SCOPUS:85145690972

SN - 1432-2994

VL - 97

SP - 161

EP - 178

JO - Mathematical Methods of Operations Research

JF - Mathematical Methods of Operations Research

IS - 2

ER -